Using the public key in part (4), Alice has encrypted a message (we do not know what was the original message), and sends it to Bob through a public channel. Assume the encrypted message sent by Alice is 16. Eve also has the Bobs public key and receives the encrypted message (sent by Alice). Eve claims that using a simple program (as shown in the following) can find the prime numbers p and q which are used by RSA to calculate N (i.e. N=p.q), thus the original message is 35.

Check the program and verify her claim? (2 marks)

Show your work step-by-step. What is the output of the program? [2 marks]

Explain how she decrypted the message without having Alices private key? [2 marks]

i=2

N=713

while i

if N%i==0:

print("p=",i, "q=", N/i)

break;