TMA4155 – exercise 4

• (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\).

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?

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

Exercise 25 on page 108 in T&W.

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

Apply Pollard's \(p-1\) algorithm to factor 253.

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

Exercise 7, page 193 in T&W

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?