Recitation 7 2 Let' s try it out! You'll probably need extra paper. Check your work carefully As a team, go through the beforehand steps Choose primes p and q to be relatively small, say in the range 10-20. In practice, p and q might contain several hundred digits, but small numbers are easier to handle with pencil and paper ry e=3.5 T until you find something that works. Use Euclid's algorithm to compute the gcd Find d using the Pulverizer When you're done, put your public key on the board. This lets another team send you a message Now send an encrypted message to another team using their public key. Select your message m from the codebook below: 2= Greetings and salutations! 3=Yo, wassup 4= You guys suck 5=All your base are belong to 6= Someone on our team thinks someone on your team is kinda cute 7= You are the weakest link. Goodbye Decrypt the message sent to you and verify that you received what the other team sent Explain how you could read messages encrypted with RSa if you could quickly factor large numbers Solution. Suppose you see a public key(e, n). If you can factor n to obtain p and then you can compute d using the Pulverizer. This gives you the secret key(d, n) and so you can decode messages as well as the inteded recipientRecitation 7 2 2 Let’s try it out! You’ll probably need extra paper. Check your work carefully! • As a team, go through the beforehand steps. – Choose primes p and q to be relatively small, say in the range 10­20. In practice, p and q might contain several hundred digits, but small numbers are easier to handle with pencil and paper. – Try e = 3, 5, 7, . . . until you find something that works. Use Euclid’s algorithm to compute the gcd. – Find d using the Pulverizer. When you’re done, put your public key on the board. This lets another team send you a message. • Now send an encrypted message to another team using their public key. Select your message m from the codebook below: 2 = Greetings and salutations! 3 = Yo, wassup? 4 = You guys suck! 5 = All your base are belong to us. 6 = Someone on our team thinks someone on your team is kinda cute. 7 = You are the weakest link. Goodbye. • Decrypt the message sent to you and verify that you received what the other team sent! • Explain how you could read messages encrypted with RSA if you could quickly factor large numbers. Solution. Suppose you see a public key (e, n). If you can factor n to obtain p and q, then you can compute d using the Pulverizer. This gives you the secret key (d, n), and so you can decode messages as well as the inteded recipient