TMA4155 – exercise 4


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?

2010-10-31, Harald Hanche-Olsen