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.

About these ads

Pages: 1 2

5 Responses to “RSA Cryptography”

  1. 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 . 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+”$@”}
    |#

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

  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

    I also made a small blog post about it here: http://blog.tophernet.com/2011/04/rsa-cryptography-in-clojure.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 615 other followers

%d bloggers like this: