99 Using a spreadsheet such as Excel or a calculator perform

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 encryption, decryption, primality testing, etc.).

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).

Perform the decryption of the obtained ciphertext without using the Chinese Remainder Theorem, and using the Chinese Remainder Theorem.

Solution

Encryption

c = m^e (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 = 2²³ % 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 = c^d mod n

Therefore, m = 21811¹⁹³⁶⁷%56153 = 2 which was our initial message