RSA Cryptography
November 16, 2010
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 me (mod n) and the resulting cipher-text c is decrypted by computing cd (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 = 216+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 = me (mod n) = 6517 (mod 3233) = 2790, and the cipher-text 2790 is decrypted as m = cd (mod n) = 27902753 (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.
Programming Praxis 
My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/16/programming-praxis-rsa-cryptography/ for a version with comments):
keygen :: Integer -> Integer -> IO (Integer, Integer) keygen bits key = do p <- gen (div bits 2) q <- gen (div bits 2) let d = inv key ((p - 1) * (q - 1)) return (p * q, d) where gen k = fmap (until valid succ) $ randomRIO (2 ^ (k - 1), 2 ^ k) valid v = gcd key (v - 1) == 1 && mod v 4 == 3 && isPrime v crypt :: Integer -> Integer -> Integer -> Integer crypt = flip . expmRacket (with shameless use of libraries):
#! /bin/sh
#| Hey Emacs, this is -*-scheme-*- code!
exec racket -l errortrace –require “$0″ –main — ${1+”$@”}
|#
;; https://programmingpraxis.com/2010/11/16/rsa-cryptography/ but of
;; course also http://en.wikipedia.org/wiki/Rsa
#lang racket
(require rackunit rackunit/text-ui
(planet soegaard/math/math)
srfi/27)
(define *bit-length* (make-parameter 10))
(define (random-prime)
(let* ([min (expt 2 (sub1 (*bit-length*)))]
[r (+ min (big-random min))])
(next-prime r)))
(provide make-keys)
(define (make-keys [defaults? #f])
(let* (
[p (if defaults? 61 (random-prime))]
[q (if defaults? 53 (random-prime))]
[n (* p q)]
[φ (* (sub1 p) (sub1 q))]
[e (if defaults? 17 65537)]
[d (inverse e φ)]
)
(values (cons n e) ;public
(cons d (cons n e)) ;private
)))
(provide encrypt-integer)
(define (encrypt-integer m pubkey)
(match-define (cons n e) pubkey)
(with-modulus n (^ m e)))
(provide decrypt-integer)
(define (decrypt-integer c privkey)
(match-define (cons d (cons n e)) privkey)
(with-modulus n (^ c d)))
(define-test-suite praxis-tests
(let ()
;; example from Programming Praxis
(define-values (pub priv) (make-keys #t))
(check-equal? (encrypt-integer 65 pub) 2790)))
(define-test-suite random-tests
(for ([_ (in-range 5)])
(define-values (pub priv) (make-keys))
(define plaintext (big-random (car pub)))
(check-equal? (decrypt-integer (encrypt-integer plaintext pub) priv) plaintext)
(printf “W00t~%”)))
(define-test-suite all-tests
random-tests
praxis-tests)
(provide main)
(define (main . args)
;; This indirectly affects big-random. Feh.
(random-source-randomize! default-random-source)
(exit (run-tests all-tests ‘verbose)))
Once again, my submission is entirely too large to fit here nicely.
The problem: I needed to either import some number-theoretic functions (Extended Euclidean Algorithm, primality
test), or define them myself if the incredible gmpy library is unavailable for the Python installation being used.
Though I’m certainly biased, I’m a huge fan of the mathematical exercises here! Sorry it took so long for me to get to
this.
Works for any N = 18, the integers get too big.
import java.math.BigInteger;
import java.security.SecureRandom;
/**
* Cryptography.
*
* Generates public and private keys used in encryption and
* decryption
*
* Author: Jamie
* Version: Dec 27, 2011
*/
public class RSA
{
private final static BigInteger one = new BigInteger(“1”);
private final static SecureRandom random = new SecureRandom();
// prime numbers
private BigInteger p;
private BigInteger q;
// modulus
private BigInteger n;
// totient
private BigInteger t;
// public key
private BigInteger e;
// private key
private BigInteger d;
private String cipherText;
/**
* Constructor for objects of class RSA
*/
public RSA(int N)
{
p = BigInteger.probablePrime(N/2, random);
q = BigInteger.probablePrime(N/2, random);
// initialising modulus
n = p.multiply(q);
// initialising t by euler’s totient function (p-1)(q-1)
t = (p.subtract(one)).multiply(q.subtract(one));
// initialising public key ~ 65537 is common public key
e = new BigInteger(“65537”);
}
public int generatePrivateKey()
{
d = e.modInverse(t);
return d.intValue();
}
public String encrypt(String plainText)
{
String encrypted = “”;
for(int i = 0; i < plainText.length(); i++){
char m = plainText.charAt(i);
BigInteger bi1 = BigInteger.valueOf(m);
BigInteger bi2 = bi1.modPow(e, n);
m = (char) bi2.intValue();
encrypted += m;
}
cipherText = encrypted;
return encrypted;
}
public String decrypt()
{
String decrypted = "";
for(int i = 0; i < cipherText.length(); i++){
char c = cipherText.charAt(i);
BigInteger bi1 = BigInteger.valueOf(c);
BigInteger bi2 = bi1.modPow(d, n);
c = (char) bi2.intValue();
decrypted += c;
}
return decrypted;
}
}
I solved it in Clojure- my solution is available here: https://github.com/topher200/rsa-cryptography
I also made a small blog post about it here: http://blog.tophernet.com/2011/04/rsa-cryptography-in-clojure.html