Question

(6 points + 4 points) Given p = 71, q = 97, find φ(n). If e = 197, find d. Accordingly, given message m = 8720, find the encrypted message and decrypted message. Show your work. Show how the factorization of n breaks RSA.

Answer 1

Answer:

The value of φ(n) is 6720, while the value of d is 6413 and the Encrypted message is C=3984 while the decrypted one is M=8720.

Step-by-step explanation:

p is given as 71

q is given as 97

so n is

$n=pq=71\times 97=6887$

Now the φ(n) is given as

$\phi(n)=(p-1)(q-1)=(71-1)(97-1)=(70)(96)=6720$

So the value of φ(n) is 6720.

Now

$ed=1 mod \phi(n)$

As e is 197 so

$ed=1 mod \phi(n)\\d=(1 mod 6720)/197\\d=6413$

The value of d is 6413.

m=8720 so the Encryption is given as

$C=m^e mod n\\C=8720^{197} mod 6887\\C=3984$

Now the decryption is

$M=c^d mod\, n\\M=3984^{6413} mod \, 6887\\M=8720$

So the Encrypted message is C=3984 while the decrypted one is M=8720.