How does a chosen ciphertext attack work on textbook RSA?

Question

I am very new to cryptography and I am confused with something. Here is the homework question I am having trouble with:

Write a program to attack the Textbook RSA Encryption Scheme, in order to decrypt the encrypted file key_enc.txt which contains the 128 bits AES secret key together with the initialisation vector (IV) for Question 2.

You must explain and show how the attack is done.

The RSA parameters are as follows:

N: 92001629535369949668182190680140710002429961412439471184834723194899969898404162 82428855806975402440064473888135838545187330646754494062187654035542047167435016 34608863342073173012508616123265965429721791336874605919036975439595316606713189 21259313523852555003517715050369476348174980850810194157624985747443

e: 65537

My questions are:

• is it possible to use the formula in the link to find the answer with such a big value?
• inside the link, the plaintext value is given but the homework didn't provide a plaintext. Do I need to guess it?

Answer 1

Since you have your n and e, you should get d and your totient. which is ϕ(n).

Here is the example:

Using: e(d) mod ϕ(n) ≡ 1, you can use an Euclidean algorithm to solve this equation to get d.

How to get the n? Usually you take your two large prime numbers. e.g (p = 7 and q = 11) Your n in this case will be p*q-(7*11 = 77).

How to get ϕ(n)-totient? Usually you take (p-1)*(q-1) = ϕ(n). That is (7-1)*(11-1) = 60, so your totient is 60: ϕ(n) = 60.

Your e must be < n and must not share common factors with ϕ(n), then e = 17

Then, e(d) mod ϕ(n) ≡ 1-----------> e=17, d=? , ϕ(n) = 60

substitute 17(d) mod 60 ≡ 1 <---- in this case you are looking for d which is 53, because 17*53 mod 60 will give you remainder 1 which satisfies this equation---> e(d) mod ϕ(n) ≡ 1

To decrypt your cipher text use this:
m=c^e mod n
where:
m = plain text
c = cipher text
e = encryption key
n = product of two large prime numbers.

Answer 2

• n is the product of two large primes, so by definition n is always a large number.
• The question wants you to write a program that decrypts the cipehertext, which by definition means that the program must return the plaintext.

Answer 3

I would try a meet-in-the-middle attack.

Given a public key (N,e) and the ciphertext c and knowing it's textbook RSA on a 128-bit key, you can recover the original message (the secret key) a good fraction of the time in time O(2⁶⁸).

Basically, you assume the plaintext message is factorable into two values that are less than 2⁶⁸ -- that is (m = a*b), where a < b < 2⁶⁸. Note we know that since m < 2¹²⁸ if it's factorable the smaller factor is less than 2⁶⁴.

Note c = m^e (mod N) or c = a^e b^e (mod N) or c / a^e = b^e (mod N) for the correct values of a and b.

Build two tables -- the first consisting of c/a^e mod N for all possible values of a (from 1 to 2⁶⁴), the second consisting of all b^e mod N for all possible values of b (from 1 to 2⁶⁸).

Now sort your two lists and see if there are any pair a,b such that a^e = C/b^e mod N. If there is a match, you've then take the corresponding values of a and b and the original message (the encrypted 128-bit AES key) will be their product m = a*b.