RSA Cryptography
November 16, 2010
The key generator takes the number of bits k and the encryption key e and returns the modulus n and the decryption key d. Large primes v are generated as a random integer on the range 2k/2−1 ≤ v < 2k/2; if v is not prime, or not co-prime to e, or not congruent to 3 mod 4 (which avoids some nasty theoretical weaknesses), then it is incremented and the tests are applied again. This process can take a while for large values of k, because the arithmetic on large integers is slow and because it can take hundreds or thousands of trial v before a suitable one is found:
(define (keygen k e)
(define (gen k)
(let loop ((v (randint (expt 2 (- k 1)) (expt 2 k))))
(if (or (< 1 (gcd e (- v 1)))
(not (= (modulo v 4) 3))
(not (prime? v)))
(loop (+ v 1))
v)))
(let* ((k2 (quotient k 2)) (p (gen k2)) (q (gen k2))
(d (inverse e (* (- p 1) (- q 1)))))
(values (* p q) d)))
Encryption and decryption can be done by a single function; as long as you feed it the right key, it will make the right calculation:
(define (crypt text modulus key)
(expm text key modulus))
Here’s a 32-bit example, using the message 42:
> (keygen 32 65537)
1893932189
1461164273
> (crypt 42 1893932189 65537)
1118138102
> (crypt 1118138102 1893932189 1461164273)
42
We don’t know the random numbers p and q used by the key generator, but we can factor n to find them; of course, if n was larger, factoring would be more difficult, which is the basis for the security of the algorithm. We use Fermat’s method to do the factoring, since p and q must be close, so Fermat’s method is better than trial division:
> (factors 1893932189)
(51551 36739)
We steal much code from other sources. Digits, expm, isqrt, and randint come from the Standard Prelude. Euclid, inverse and jacobi come from the exercise on modular arithmetic. Square? comes from the exercise on powering predicates. Prime? is the Baillie-Wagstaff algorithm, and factors is the Fermat method. You can run the program at http://programmingpraxis.codepad.org/rRxeR2C9.
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