# TMA4155 – exercise 4

## 2010-11-01

### 1 – RSA cryptosystem

• (a) Given $p = 31$, $q = 43$ and $e = 11$, complete the key generation (that is, find $n$ and $d$).
• (b) Encrypt $m = 3$.
• (c) Decrypt $c = 2$.

### 2 – Double RSA encryption

Alice and Bob want to improve the security of their RSA system. Instead of using one encryption key they want to use two keys $(n,e_1)$ and $(n,e_2)$ (the same $n$), and to encrypt twice, first using $(n,e_1)$ and then $(n,e_2)$. They think that this is more secure and even believe that it is possible with this method to gain speed by using a much smaller $n$, but keeping the level of security. Are they right?

### 3 – Square roots modulo primes

Find out which of the numbers 2, 5, 18, 21 have square roots modulo 23. Also find the square roots, when possible.

### 4 – Square roots modulo composites

Exercise 25 on page 108 in T&W.

Also, find all solutions to $x^2 \equiv 2 \pmod{33333333333333333333333333333}$

### 5 – Pollard's p−1

Apply Pollard's $p-1$ algorithm to factor 253.

### 7 – Baby step – giant step

Using baby step – giant step, compute the discrete logarithm of 13 to base 5 mod 23.

### 8 – RSA

Exercise 7, page 193 in T&W

### 9 – Shared secret

A secret number in the range 0…100 is shared among a number of participants. To this end, a certain quadratic polynomial $f$ with integer coefficients has been created so that the secret number is $f(0)$. Each participant has been given a pair of numbers $(x,y)$ where $y\equiv f(x)\pmod{101}$. Three of the participants get together and discover that they hold the pairs (1,34), (2,66), and (3,37). What is the secret number?