RSA.py

#!/usr/bin/python3.3
# -*- coding: utf-8 -*-

import fractions, random

class RSA:
    def __init__(self, p, q, b):
        self.p = p
        self.q = q
        self.n = p*q
        self.phi = (p-1)*(q-1)
        assert b < self.phi, 'b must be lesser than phi(n)'
        assert fractions.gcd(b, self.phi), 'gcd(n, phi(n)) must be equal to 1'
        self.b = b
        self.a = self.euclide(b, self.phi)

    def encrypt(self, message):
        """Encrypt the message using given parameters"""
        clear = [ord(i)-65 for i in message.upper()]
        cipher = [self.exponentiate(i, self.b, self.n) for i in clear]
        return cipher

    def decrypt(self, cipher):
        """Decrypt the message using given parameters"""
        decrypted = [self.exponentiate(i, self.a, self.n) for i in cipher]
        clear = ''.join(chr(i+65) for i in decrypted)
        return clear

    @staticmethod
    def euclide(b, n):
        """Returns the inverse of b mod n"""
        n_0, b_0, t_0, t = n, b, 0, 1
        q = n_0//b_0
        r = n_0 - q*b_0
        while r > 0:
            temp = t_0 - q*t
            if temp >= 0:
                temp = temp%n
            else:
                temp = n - -temp%n
            t_0, t, n_0, b_0 = t, temp, b_0, r
            q = n_0//b_0
            r = n_0 - q*b_0
        if b_0 != 1:
            raise ArithmeticError('{0} has no inverse mod {1}'.format(b, n))
        else:
            return t

    @staticmethod
    def exponentiate(x, c, n):
        """Fastly exponentiates x^c mod n"""
        gen_c = (int(i) for i in list(bin(c))[2:])
        z = 1
        l = len(bin(c))-2
        for i, c_i in zip(range(l-1, -1, -1), gen_c):
            z = (z**2)%n
            if c_i == 1:
                z = (z*x)%n
        return z

    @staticmethod
    def generate(n, odd=True):
        """Fastly generates a random number <= 2^n - 1 and >= 2^(n-1)"""
        nb = 1
        for i in (random.randint(0, 1) for i in range(n-1)):
            nb = (nb<<1)+i
        return (nb<<1)+odd

    @classmethod
    def is_residue(c, x, p):
        """Checks wether x is a quadratic residue mod p or not"""
        n = c.exponentiate(x, int((p-1)/2), p)
        if n != 1:
            return False
        else:
            return True

    @classmethod
    def legendre(c, a, p):
        """Calculates the Legendre symbol (a/p)"""
        if a%p == 0:
            return 0
        elif c.is_residue(a, p):
            return 1
        else:
            return -1

    @staticmethod
    def fac2(n):
        """Factorizes a number x by powers of two, returns (i, n) where x = 2^i * n"""
        r_bin_n = [int(i) for i in list(bin(n))[2:]]
        i = 0
        while r_bin_n[-1] == 0:
            i += 1
            r_bin_n.pop()
        reduced = int(''.join(str(j) for j in r_bin_n), 2)
        return (i, reduced)