Commits

Anonymous committed 14c6c00

Added RSA encryption algorithm.

Comments (0)

Files changed (2)

source/security/rsa.py

+#! /usr/bin/python
+#-*- coding: utf-8 -*-
+
+import sys
+import math
+import zlib
+import random
+import base64
+import hashlib
+
+from cPickle import dumps, loads
+
+import utils
+
+
+class RSA(object):
+    """
+    RSA public-key encryption.
+    """
+    def __init__(self, p = None, q = None, b = None, nb_bits = 256):
+        """Initialization of keys.
+
+        Generates 'p' and 'q' prime numbers randomly.
+        Computes a, b and n thanks to phi.
+        """
+        if p == None and q == None:
+            p = random.getrandbits(nb_bits)
+            q = random.getrandbits(nb_bits)
+            while not utils.miller_rabin(p):
+                p = random.getrandbits(nb_bits)
+            while not utils.miller_rabin(q):
+                q = random.getrandbits(nb_bits)
+        n   = p * q
+        phi = (p - 1) * (q - 1)
+        if b == None:
+            while True:
+                b = random.randint(2, phi - 1)
+                if utils.premier(b, phi):
+                    break
+        a  = utils.inv_modulo(b, phi)
+        self.a = a
+        self.b = b
+        self.n = n
+
+    def encrypt_int(self, x):
+        """Encrypts the message."""
+        return utils.expo_modulaire_rapide(x, self.b, self.n)
+
+    def decrypt_int(self, y):
+        """Decrypts the message."""
+        return utils.expo_modulaire_rapide(y, self.a, self.n)
+
+    def encrypt_text(self, message):
+        """Encrypts a string 'message' with the public key"""
+        return self.chopstring(message, self.encrypt_int)
+
+    def decrypt_text(self, cypher):
+        """Decrypts a cypher with the private key"""
+        return self.gluechops(cypher, self.decrypt_int)
+
+    def chopstring(self, message, funcref):
+        """Cut 'message' in blocs.
+
+        Used by encrypt_text.
+        """
+        msglen = len(message)
+        mbits = msglen * 8
+        nbits = int(math.floor(utils.log(self.n, 2)))
+        nbytes = nbits / 8
+        blocks = msglen / nbytes
+
+        if msglen % nbytes > 0:
+            blocks += 1
+
+        cypher = []
+
+        for bindex in range(blocks):
+            offset = bindex * nbytes
+            block = message[offset:offset+nbytes]
+            value = utils.bytes2int(block)
+            cypher.append(funcref(value))
+
+        return self.picklechops(cypher)
+
+    def gluechops(self, chops, funcref):
+        """Reconstructs blocs into string.
+
+        Used by decryt_text.
+        """
+        message = ""
+
+        chops = self.unpicklechops(chops)
+
+        for cpart in chops:
+            mpart = funcref(cpart)
+            message += utils.int2bytes(mpart)
+
+        return message
+
+    def picklechops(self, chops):
+        """Serializes and transforms 'chops' in base 64."""
+        value = zlib.compress(dumps(chops))
+        encoded = base64.encodestring(value)
+        return encoded.strip()
+
+    def unpicklechops(self, string):
+        """Deserializes 'string'."""
+        return loads(zlib.decompress(base64.decodestring(string)))
+
+    def __str__(self):
+        """Pretty print of keys."""
+        return """\
+            Private key : %s
+            Public key : %s
+            Modulo: %s""" % (self.a, self.b, self.n)
+
+
+if __name__ == '__main__':
+    # Point of entry in execution mode
+    rsa = RSA(nb_bits = 128)
+    print rsa
+    cr = rsa.encrypt_text("Bonjour, comment allez-vous ?\nJe vais très bien, merci.")
+    dcr = rsa.decrypt_text(cr)
+    print
+    print "Cipher text :"
+    print cr
+    print
+    print "Plain text :"
+    print dcr

source/security/utils.py

+#! /usr/local/bin/python
+#-*- coding: utf-8 -*-
+
+"""Some usefull functions.
+"""
+
+import math
+import types
+import random
+import operator
+
+def gcd_bezout(x, y):  # a > b > 0
+    """ Extended great common divisor, returns x , y
+        and gcd(a,b) so ax + by = gcd(a,b)       """
+    if x % y == 0:
+        return (0, 1, y)
+    q = []
+    while x % y != 0:
+        q.append(-1*(x//y))
+        (x, y)=(y, x%y)
+    (x, y, gcd) = (1, q.pop(), y)
+    while q:
+        (x,y) = (y, y*q.pop()+x)
+    return (gcd, x, y)
+
+def gcd(x,y):
+    """Return GCD of x and y."""
+    while y:
+        (x, y) = (y, x%y)
+    return abs(x)
+
+def premier(a, b):
+    """Return True if a and b are coprime.
+    """
+    return gcd(a, b) == 1
+
+def log(x, base = 10):
+    """Return neperian logarithm of 'x'."""
+    return math.log(x) / math.log(base)
+
+def miller_rabin_pass(a, n):
+    d = n - 1
+    s = 0
+    while d & 1:
+        d = d >> 1
+        s = s + 1
+
+    a_to_power = expo_modulaire_rapide(a, d, n)
+    if a_to_power == 1:
+        return True
+    for i in xrange(s-1):
+        if a_to_power == n - 1:
+            return True
+        a_to_power = (a_to_power * a_to_power) % n
+    return a_to_power == n - 1
+
+def miller_rabin(n):
+    for repeat in xrange(20):
+        a = 0
+        while a == 0:
+            a = random.randrange(n)
+        if not miller_rabin_pass(a, n):
+            return False
+    return True
+
+def expo_modulaire_rapide(a, p ,n):
+    """Calcul l'exposant modulaire (pow()).
+
+    Selon Wikipédia (http://fr.wikipedia.org/wiki/Exponentiation_modulaire)
+    """
+    result = a % n
+    remainders = []
+    while p != 1:
+        remainders.append(p & 1)
+        p = p >> 1
+    while remainders:
+        rem = remainders.pop()
+        result = ((a ** rem) * result ** 2) % n
+    return result
+
+def inv_modulo(a,m):
+    """Retourne l'inverse modulaire de a modulo m.
+    """
+    (d, x, _) = gcd_bezout(a, m)
+    if d == 1:
+        return x % m
+    return None
+
+def bytes2int(bytes):
+    """
+    >>> (128*256 + 64)*256 + + 15
+    8405007
+    >>> l = [128, 64, 15]
+    >>> bytes2int(l)
+    8405007
+    """
+    if not (type(bytes) is types.ListType or type(bytes) is types.StringType):
+        raise TypeError("Liste ou String.")
+
+    # Convert byte stream to integer
+    integer = 0
+    for byte in bytes:
+        integer <<= 8 #integer *= 256
+        if type(byte) is types.StringType:
+            byte = ord(byte)
+        integer += byte
+
+    return integer
+
+def int2bytes(number):
+    """
+    >>> bytes2int(int2bytes(123456789))
+    123456789
+    """
+    if not (type(number) is types.LongType or type(number) is types.IntType):
+        raise TypeError("Long ou String.")
+
+    string = ""
+
+    while number > 0:
+        string = "%s%s" % (chr(number & 0xFF), string)
+        number >>= 8 #integer /= 256
+
+    return string
+
+if __name__ == '__main__':
+    # Point of entry in execution mode.
+    pass