[Solved] VE475 Introduction to Cryptography Homework 5

Ex. 1 RSA setup

Most RSA setups require the message m to be coprime to the RSA modulus n. In the exercise we will prove that m can still be decrypted if gcd(m, n) is not 1.

1. Why is it likely for n to be coprime with m ?
2. Let k be a multiple of (n).
3. Show that if gcd(m, n) = 1 , then m^k 1 mod p and mod q.
4. Prove that for any arbitrary m, m^k+1 m mod p and mod q.
5. Let e and d the RSA encryption and decryption exponent, respectively.
6. Show that m^ed m mod n for all m.
7. Conclude on the necessity of having gcd(m, n) = 1.

Ex. 2 RSA decryption

The ciphertext 5859 was obtained using RSA encryption with n = 11413 and e = 7467. Recover the plaintext.

Ex. 3 Breaking RSA

Wieners attack allows to recover the decryption exponent under the condition that it is small enough.

1. Why would one select short encryption or decryption keys?
2. Search and explain how Wieners attack is working.
3. How to ensure not generate a weak decryption key?
4. Given n = 317940011 and e = 77537081, apply Wieners attack in order to factor n. Either provide the source code of your program or clearly detail all the steps.

Ex. 4 Programming

Implement the three functions generate, encrypt and decrypt, which generate the RSA parameters, encrypt, and decrypt, respectively.

The function generate takes as input a security level and generate p and q such that n is long enough to match the required security level. No special requirement is requested on encrypt and decrypt.

Common security levels:

Ex. 5 Simple questions

Let n, e, d, p, q be the usual RSA parameters.

1. A message m is encrypted into the ciphertext c. Explain how to run a CCA attack on texbook RSA.
2. Instead of using a single exponent one wants to encrypt twice using a single n but two different exponents. Is this double encryption adding any security ?Explain your answer.
3. Let n = 642401. Knowing that 516107² 7 mod n and 187722² 4 7 mod n factorize n.
4. Describe how an RSA scheme would work if instead of the two primes p and q, three primes p, q, and r were used. Explain the drawback of such a setup.
5. Determine the smallest generator of U(Z/97Z).
6. Consider the multiplicative group G = U(Z/101Z).
7. Prove that 2 is a generator of G.
8. In G, determine log2 24, knowing that log2 3 = 69.
9. In G, determine log2 24, knowing that log2 5 = 24.
10. Knowing that ³⁶ 44 mod 137, and ³¹⁰ 2 mod 137, find 0 x 135 such that 3X 11 mod 137.
11. Let G = U(Z/11Z)
12. Compute 6⁵ in G.
13. Prove that 2 is a generator of G
14. Let x be such that 2 6 mod 11. Without calculating it, decide whether x is even or odd.

Ex. 6 DLP

In this exercise we want to determine x such that ^3X 2 mod 65537.

1. Prove that 2048 divides x, while 4096 does not.
2. How many possible choices need to be considered for x ?Determine x.
3. Can the Pohlig-Hellman algorithm be applied to this example ? If so show the details.
4. Explain why such primes are not fitting a cryptographic context.

Note: in homework 4 exercise 2 it was proved that 3 is a generator of U(Z/65537Z).