Answer to Question #150193 in Discrete Mathematics for John

Question

Alice decides to set up an RSA public key encryption using the two primes p= 31 and p= 41 and the encryption key e= 11.You must show all calculations, including MOD-calculations using the division algorithm!
Bob decides to send the message M= 30to her using this encryption. What is the code C that he will send her?
What is Alice’s decryption key d?
Alice also receives the message C= 101from Carla. What was her original message M?

Answer 1

$n = p \times q \\ n = 31 \times 41 = 1271 \\ Euler's\; totient\; of \;n \\ ɸ(n) = (p-1)(q-1) \\ = 30 \times 40 = 1200 \\ gcd(ɸ(n),e) = gcd(1200,11) = 1 \\ 1< e<ɸ(n) \\ edmodɸ(n) = 1 \\ = ed \equiv modɸ(n) \\ d = e^{-1}modɸ(n) 11dmod1200 = 1 \\ x mod y \equiv \frac{x}{y} \equiv R \\ \frac{11d}{1200} \\ R = 1 \\ d = 1091$

decryption key d = 1091

Encrypting message M with public key (n,e)

$C = M^emodn \\ = 30^{ʹʹ}mod1200 \\ C = 557$

For C = 101 Decrypting with private key (1271, 1091)

$M = C^dmod n \\ = 101^{1091}mod1271 = 95 \\ d = \frac{1 + iɸ(n)}{e}$

If i = 1

$d= \frac{1 + 1200}{11} = 109.18$

If i = 2

$d= \frac{1 + 2400}{11} = 218.27$

If i = 10

$d= \frac{1 + 12000}{11} = 1091$