## 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 2^{k/2−1} ≤ *v* < 2^{k/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.

Pages: 1 2

My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/16/programming-praxis-rsa-cryptography/ for a version with comments):

Racket (with shameless use of libraries):

#! /bin/sh

#| Hey Emacs, this is -*-scheme-*- code!

exec racket -l errortrace –require “$0″ –main — ${1+”$@”}

|#

;; http://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