Week 13

Question 1

Describe the three components of a public-key encryption scheme

Answer 1

1. Key generation algorithm: outputs encryption key, decryption key and public params i.e. descriptions of the message space, cipher text space and possible enc/dec key pairs
2. Encryption algorithm: receives encryption key and public params; outputs ciphertext
3. Decryption algorithm: receives decryption key and public params; outputs original message

Question 2

What does the acronym RSA represent?

Answer 2

Rivest, Shamir and Adleman

Question 3

What is a trapdoor one-way function?

Answer 3

Efficient to execute one way, inefficient to execute in the inverse - unless you have the extra information that provides the “trapdoor”, i.e. makes the inverse efficient, too

Question 4

What idea is RSA encryption based on?

Answer 4

The idea that it’s easy to multiply two large primes, but there is currently no known way to efficiently find the prime factors of a number n that is the product of two large primes

Question 5

How are the parameters for the RSA encryption scheme set up?

What is the name of the first parameter?

What is made public and what is kept secret?

What is the minimum size of relevant value(s) needed?

Answer 5

The public param for RSA is an integer 𝒏 (the modulus of the scheme) that is a product of two large primes:

1. Generate two large primes p and q of similar size, but with p ≠ q
2. Calculate 𝒏 = pq

Public: 𝒏

Secret: p and q

Minimum recommended size for 𝒏: 2048 bits long when represented in binary

Question 6

Describe how to generate the keys for the RSA encryption scheme

Answer 6

Compute ɸ(𝒏) = (p - 1)(q - 1)

Encryption key e must be a positive integer coprime to ɸ(𝒏) so that e ∈ Z^*_ɸ(𝒏)

Decryption key d is the multiplicative inverse of e in Z^*_ɸ(𝒏)

Question 7

Describe the RSA encryption and decryption algorithms

(2 steps each)

Answer 7

Assuming our message 𝒎 is represented as an element of ℤ_𝒏.

Encryption:

1. Use the modulus of the scheme, 𝒏, and public encryption key 𝒆 to express E(𝒎, 𝒆) = 𝒎^𝒆 (mod 𝒏)
2. Use techniques like Square & Multiply to calculate the value of this exponential value

Decryption:

1. Use private decryption key 𝒅 and public parameter 𝒏 with ciphertext 𝒄 to express D(𝒄, 𝒅) = 𝒄^𝒅 (mod 𝒏)
2. The fastest way to solve this is to split it into two expressions (since 𝒏 = 𝒑𝒒) in order to use exponent reduction and calculation techniques, ending up with two congruences with 𝒙 to solve using CRT to find 𝒎 (mod 𝒏)

Question 8

Use RSA encryption to encrypt the message 𝒎 = 301.

Then use RSA decryption to decrypt it.

Necessary information:

• The modulus of the scheme and public parameter 𝒏 = 1457
• The modulus was derived from 𝒑 = 31 and 𝒒 = 47
• The public encryption key 𝒆 = 11

The recipient also knows the private decryption key 𝒅 = 251.

Answer 8

Encryption:

1. Ciphertext 𝒄 = E(𝒎, 𝒆) = 301¹¹ (mod 1457)
2. 301¹¹ (mod 1457) ≡ 358 (mod 1457)

Decryption:

1. Message 𝒎 = D(𝒄, 𝒅) = 358²⁵¹ (mod 1457)
2. Knowing 𝒑 = 31 and 𝒒 = 47, we will use CRT to compute 𝒙 ≡ 358²⁵¹ (mod 31) and 𝒙 ≡ 358²⁵¹ (mod 47), which reduce down to 𝒙 ≡ 22²⁵¹ (mod 31) and 𝒙 ≡ 19²⁵¹ (mod 47) respectively - the result is the message, 301

Question 9

Appreciate that an an adversary who can factor an RSA modulus 𝒏 can break RSA

Question 10

Appreciate that it is not known whether breaking RSA is as hard as the problem of factoring the modulus 𝒏

Question 11

Show that the RSA encryption scheme provides correctness for messages 𝒎 that are coprime to 𝒏