Naive implementation of the RSA cryptosystem

NaiveRSA.py

import os
import random

class NaiveRSA(object):
    _small_primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
                     101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,
                     181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
                     271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,
                     373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,
                     463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,
                     577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,
                     673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,
                     787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,
                     887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
    _e = 65537

    def _xgcd(self, a, b):
        '''Compute the Bezout multipliers x and y s.t. ax + by = gcd(a,b)'''
        if b == 0:
            return (1, 0)

        q, r = divmod(a, b)
        s, t = self._xgcd(b, r)
        return (t, s-q*t)

    def _miller_rabin(self, n, bases=5):
        '''Perform the Miller-Rabin primailty test with the given number of bases'''
        s, t = n-1, 0
        while s & 1 == 0:
            s >>= 1
            t += 1

        def _is_witness(m):
            '''Determine if m is a witness to the compositeness of n'''
            if pow(m, t, n) == 1:
                return False
            for i in xrange(t):
                if pow(m, (1 << i) * s, n) == n - 1:
                    return False
            return True

        for i in xrange(bases):
            a = random.randrange(2, n)
            if _is_witness(a):
                return False
        
        return True

    def _is_probable_prime(self, n):
        '''Determine if n is probably prime'''
        for i in self._small_primes:
            if n == i:
                return True
            if n % i == 0:
                return False
        return self._miller_rabin(n)

    def _get_probable_prime(self, bits):
        '''Slightly-less-than-naively generate a probably prime number'''
        while True:
            p = int(os.urandom(bits/8).encode('hex'), 16)
            if p & 1 == 0:
                p |= 1
        
            if self._is_probable_prime(p):
                return p

    def generate_keypair(self, bits=128):
        '''Generate an RSA key pair'''
        # Note that we don't ensure p != q and that |p - q| is sufficiently large
        p, q = self._get_probable_prime(bits),  self._get_probable_prime(bits)
        n = p*q
        phi_n = (p-1) * (q-1)
        d = self._xgcd(phi_n, self._e)[1]

        if d < 0:
            d += phi_n

        # yield the (public key, private key)
        return ((n, self._e), (n, d))

    def encrypt(self, key, m):
        '''Encrypt the message m using the provided public key'''
        return pow(m, key[1], key[0])

    def decrypt(self, key, c):
        '''Decrypt the ciphertext c using the provided private key'''
        # Notational, rather than useful
        return self.encrypt(key, c)

if __name__ == '__main__':
    rsa = NaiveRSA()
    public, private = rsa.generate_keypair()
    print 'public key is:', public
    print 'private key is:', private
    c = rsa.encrypt(public, 1357)
    p = rsa.decrypt(private, c)

    print 'Ciphertext is:', c, 'and plaintext is:', p