RSA Encryption

Encryption has been used to exchange information between two parties and keep that information from a third party. The problem with classical symmetric encryption is that the key used to encrypt the information must be distributed to the people who are supposed to be able to read the message before they can decrypt it. When a lot of messages are to be exchanged, lots of keys must be distributed which can be a logistical problem. Computers can efficiently encrypt and decrypt messages with symmetric ciphers.

In 1976, Whitfield Diffie along with Martin Hellman discovered public key cryptography and purposed the Diffie-Hellman key exchange which is still a commonly used key exchange.

In 1977, Ron Rivest, Adi Shamir, and Leonard Aldeman at MIT publicized the algorithm named from the initials of the three inventors. The algorithm is based on the fact that it is easy to multiply two large prime numbers together to get a product but it is very difficult to reverse the process. Given the product, it is difficult to calculate what two prime numbers were multiplied together initially.

In 1991, Senate Bill 266 was introduced by the US government. This anti-crime bill had a measure in it requiring all encryption software must have a back door in it to allow the government to obtain the plaintext of voice, data and other communications when authorized by law. This bill prompted Phil Zimmerman to develop Pretty Good Privacy (PGP). In the pgpguide.1st in PGP 1.0 was the following:

The 17 Apr 1991 New York Times reports on an unsettling US Senate proposal that is part of a counterterrorism bill. If this nonbinding resolution became real law, it would force manufacturers of secure communications equipment to insert special "trap doors" in their products, so that the Government can read anyone's encrypted messages. It reads: "It is the sense of Congress that providers of electronic communications services and manufacturers of electronic communications service equipment shall insure that communications systems permit the Government to obtain the plain text contents of voice, data, and other communications when appropriately authorized by law."

The problem with public key encryption systems with includes RSA is that they are computationally intense and run slowly as compared to symmetric key ciphers when dealing with large pieces of data. PGP utilized the RSA public key/private key system to exchange the symmetric key securely. The gist of a public key/private key system is that the key you want to exchange is encrypted with the recipient’s public key and the only way to decrypt the key is to have the corresponding private key. Knowing the public key does not help someone in trying to decrypt the message. PGP uses the RSA public key system to encrypt the session key that the rest of the message is encrypted in. RSA can run fairly quickly with the small amount of data that makes up the session key. So the message is encrypted with the IDEA cipher using a randomly generated key. The key is encrypted with the public key of the recipient using RSA. The recipient receives the message and uses his private RSA key to decrypt what the IDEA key was and that is used to decrypt the message itself.

I was involved in the porting of PGP to A/UX (Apple’s Unix) and so I thought a puzzle based on a simplified RSA would be interesting for my contribution to the TOM Creative Group puzzle.

The RSA algorithm in detail

RSA involves a public key and a private key. The public key can be known by everyone and be used to encrypt messages being sent to the recipient who uses the private key to decrypt the message. The keys for the RSA algorithm are generated the following way:

1. Choose two large prime numbers p and q
2. Compute n=pq
3. Compute the totient φ(n) = (p-1)(q-1)
4. Choose an integer e such that 1 < e < φ(n)  and e and phi(n) are coprime (share no common factors other than 1) and frequently is chosen as 3 or 17 or 65537.
5. Compute d such that 1 < d <φ(n)  and ed ≡ 1 mod φ(n)  (To compute the value for d, use the Extended Euclidean Algorithm this is known as modular inversion.)
6. The public key is (n,e) and the private key is (n,d). The values of p,q, and φ(n)  should be kept secret.

∙ n is known as the modulus
∙ e is known as the public exponent or encryption exponent
∙ d is known as the private exponent or decryption exponent

A very simple example of RSA encryption

This example can be done using a calculator or by hand.

1. Choose p=3 and q=11
2. n=pq =3*11=33  and φ(n) = (p-1)(q-1)=(2)(10)=20
3. choose e=3 which is >1 and coprime to φ(n)=20 ie they have no common factors
4. compute d such that ed ≡ 1 mod(φ(n)) 
   or d = e ^-1mod φ(n)
   or find d such that φ(n) divides (ed – 1) 
   or find d such that 20 divides 3d – 1                                                   
5. by brute force d=7 or (3*7-1)/20 = (21-1)/20 = 20/20=1
   the public key is (33,3) and the private key is (33,7)

If we want to encrypt the message m = 7
c = m^e mod n = 7³ mod 33 = 343 mod 33 = 13

If we want to decrypt the ciphertext c = 13
m = c^d mod n = 13⁷ mod 33 = 7 which is the original message text.

Now if you decide you want to try for this cache, you will need to follow the following link. This will take you to a web site where you will fill out a very short form with your geocaching login name and email address. I will need to do a bit of behind the scenes bit fiddling to get things set up and then you will be sent instructions and another link to go to that after you put in your geocaching login name you will be taken to a page with a couple of things on it and a place to put your answer. The page will present you with n (the product of two primes) and one of the encryption keys. Your job will be to factor the number n into the two primes used to generate it and then calculate the other (decryption) key. If you put in the correct decryption key, you will be rewarded with a success screen with the coordinates of this cache. If anyone logs the cache without first calculating the correct decryption key (and everyone will have theor own unique number n and encryption key), your log will be erased.