9.9 Using a spreadsheet (such as Excel) or a calculator, perform the operations

Question

9.9 Using a spreadsheet (such as Excel) or a calculator, perform the operations described below. Document results of all intermediate modular multiplications. Determine a number of modular multiplications per each major transformation (such as encryp- tion, decryption, primality testing, etc.).

Test all odd numbers in the range from 233 to 241 for primality using the Miller- Rabin test with base 2.

Encrypt the message block M = 2 using RSA with the following parameters: e = 23 and n = 233 * 241.

Compute a private key (d, p, q) corresponding to the given above public key (e, n).

d. Perform the decryption of the obtained ciphertext

1. without using the Chinese Remainder Theorem, and 2. using the Chinese Remainder Theorem.

Explanation / Answer

To encrypt message M=2 using RSA with parameters e=23 and n=233*241.

Here, p=233, q=241.

Encryption

c = me (mod n)

Here, n = p*q = 233*241

Both 233 and 241 are prime since they are not divisible by any number greater than 1 and less than sqrt(233) and sqrt(241) respectively.

Also e (23) is less than (p-1)(q-1) and e and n are coprime. Hence, e can be taken as 23.

therefore c = 223 % 233*241

c = 21811

phi(n) = (p-1)*(q-1) = 232*240 = 55680

Now we need to choose d such as (d*e)%phi(n) = 1. So, we can take d = 19367.

Decryption

m = cd mod n

Therefore, m = 2181119367%56153 = 2 which was our initial message.

Related Questions

Navigate

• Browse (All)
• Browse 9
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.