## 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−1v < 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.

Pages: 1 2

### 5 Responses to “RSA Cryptography”

```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 . expm
```
2. Eric H said

Racket (with shameless use of libraries):

#! /bin/sh
#| Hey Emacs, this is -*-scheme-*- code!
exec racket -l errortrace –require “\$0″ –main — \${1+”\$@”}
|#

#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)))

3. Graham said

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.

4. Jamie said

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;
}
}

5. Topher Brown said

I solved it in Clojure- my solution is available here: https://github.com/topher200/rsa-cryptography