Programming Praxis

In 1973, Clifford Cocks invented a method of public-key cryptography in which the recipient of a message holds a private key, known only to himself, and publishes a public key, which may be used by anyone to send him a message that only he will be able to read. Cocks worked for the British security service GCHQ, so he was unable to publish his work. In 1978, three MIT professors, Ronald L. Rivest, Leonard M. Adelman and Adi Shamir invented the same algorithm, independently, which they patented in 1983. The algorithm is now known as RSA, after their initials.

The basic idea of RSA starts with two large prime numbers of equal bit-length, p and q; their product n becomes the modulus of the cryptosystem. The totient of n is computed as φ(pq) = (p−1) × (q−1). Then two keys are chosen, the encryption key e and the decryption key d, such that de ≡ 1 (mod φ(pq)) and gcd(e, φ(pq)) = 1. Then, given a message m, an integer on the range 0 < m <n, the message is encrypted by computing m^e (mod n) and the resulting cipher-text c is decrypted by computing c^d (mod n).

In practice, the keys are generated by selecting a bit-length k and and arbitrary encryption key e. A longer bit-length provides more security than a shorter bit-length; a 768-bit key has recently been factored, albeit with extreme effort (about 2000 PC-years), most commercial users of RSA are probably using 1024- or 2048-bit keys these days, and high-security users (banks, military, government, criminals) are probably using 4096- or 8192-bit keys. E must be odd, is frequently chosen to be prime to force the condition that it is co-prime to the totient, and is generally fairly small; e = 2¹⁶+1 = 65537 is common. Then the key generator chooses p and q at random, computes d as the modular inverse of e, and reports n and d. In that way, nobody, not even the person generating the keys, knows p and q.

Here is a simple example from Wikipedia: Choose p = 61 and q = 53. Then n = p×q = 3233 and the totient φ(pq) = 60×52 = 3120. Choose e=17 which is co-prime to 3120 since 17 is prime and 17∤3120; the corresponding d is the inverse of 17 with respect to the modulus 3120, so d = 2753. Then the message m = 65 is encrypted as c = m^e (mod n) = 65¹⁷ (mod 3233) = 2790, and the cipher-text 2790 is decrypted as m = c^d (mod n) = 2790²⁷⁵³ (mod 3233) = 65.

The standard definition of RSA cryptography is known as PKCS #1. It provides a method for converting a text message to a number m suitable for encryption, and converting it back to the original text message, but we won’t examine that algorithm today. It is also possible to use RSA to provide non-forgeable signatures; the basic idea is that the sender encrypts a message hash with his decryption key, so the receiver can decrypt the message hash with the sender’s public key, which works because only the sender knows his private decryption key.

Your task is to write an RSA key generator and procedures to encrypt and decrypt messages using the RSA algorithm as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2