Worksheet V RSA Public Key Cryptography

Problem: How to share secret information and not worry about interceptors understanding the message.

Solution: Use a method that is easy to apply, but so difficult to undo that by the time the message is decoded by the eavesdropper, the message is no longer important. RSA is based on the principal that while multiplication is easy, factoring is "hard".

Method:
1. Pick two small prime numbers p and q. Let p= 3 and q= 5.

2. Find the product of p and q and let n= pq. n= 15

3. Find the product of p-1 nad q-1 and let m= (p-1)(q-1). (p-1)(q-1)= 8

4. Find two numbers whose product if 1 modulo m. Label one number s and one number t. s= 3 and t= 3 st= 9 9= 1mod8

5. The receiver of the message makes public n=15 and s=3.

6. To encode the message, take the letter's numerical value, raise it to the exponent s and then reduce it modulo n. C= 2 2^3= 8mod15 Send 8 or I

7. To decode, using the secret key t=3, raise 8 to the t=3 power and reduce modulo n=15, the published base. 8^3=512 512mod15=2mod15 Read 2= C


Try the following:

1. Use the TI-83 program AMODM to reduce 161 modulo 15. xc

2. Using the primes 3 and 7, encode the letter M.

3. Use your own primes to send the message CRYPTO.

4. Given s=7 and n=33, find the value of t needed to decode a message.

5. If numbers are large, it takes computers a very long time to find t. Given n=1643 and s=7, find t.

6. Verify your answer to 5 above using the TI-83 program DIVISORS.

7. Use the TI-83 program RSA to encode SECRETS.