[Python-Dev] [Python-checkins] r87677 - python/branches/py3k/py3rsa.py (original) (raw)

Senthil Kumaran orsenthil at gmail.com
Mon Jan 3 10:57:53 CET 2011

Sorry Folks. I commited to a wrong respository. I was testing it against the latest version py3k and I thought i moved it back to my original respository.

Apologize for the trouble and I shall remove it immediately.

-- Senthil

On Mon, Jan 3, 2011 at 5:47 PM, senthil.kumaran <python-checkins at python.org> wrote:

Author: senthil.kumaran Date: Mon Jan  3 10:47:09 2011 New Revision: 87677

Log: py3k implmentation of RSA algorithm,

Added: python/branches/py3k/py3rsa.py   (contents, props changed) Added: python/branches/py3k/py3rsa.py ============================================================================== --- (empty file) +++ python/branches/py3k/py3rsa.py      Mon Jan  3 10:47:09 2011 @@ -0,0 +1,181 @@ +# Copyright (c) 2010 Russell Dias +# Licensed under the MIT licence. +# http://www.inversezen.com +# +# This is an implementation of the RSA public key +# encryption written in Python by Russell Dias + +author = 'Russell Dias // inversezen.com' +# Py3k port done by Senthil (senthil at uthcode.com) +date = '05/12/2010' +version = '0.0.1' + +import random +from math import log + +def gcd(u, v): +    """ The Greatest Common Divisor, returns +        the largest positive integer that divides +        u with v without a remainder. +    """ +    while v: +        u, v = u, u % v +    return u + +def eec(u, v): +    """ The Extended Eculidean Algorithm +        For u and v this algorithm finds (u1, u2, u3) +        such that uu1 + vu2 = u3 = gcd(u, v) + +        We also use auxiliary vectors (v1, v2, v3) and +        (tmp1, tmp2, tmp3) +    """ +    (u1, u2, u3) = (1, 0, u) +    (v1, v2, v3) = (0, 1, v) +    while (v3 != 0): +        quotient = u3 // v3 +        tmp1 = u1 - quotient * v1 +        tmp2 = u2 - quotient * v2 +        tmp3 = u3 - quotient * v3 +        (u1, u2, u3) = (v1, v2, v3) +        (v1, v2, v3) = (tmp1, tmp2, tmp3) +    return u3, u1, u2 + +def stringEncode(string): +    """ Brandon Sterne's algorithm to convert +        string to long +    """ +    message = 0 +    messageCount = len(string) - 1 + +    for letter in string: +        message += (256**messageCount) * ord(letter) +        messageCount -= 1 +    return message + +def stringDecode(number): +    """ Convert long back to string +    """ + +    letters = [] +    text = '' +    integer = int(log(number, 256)) + +    while(integer >= 0): +        letter = number // (256**integer) +        letters.append(chr(letter)) +        number -= letter * (256**integer) +        integer -= 1 +    for char in letters: +        text += char + +    return text + +def splittoodd(n): +    """ Return values 2 ^ k, such that 2^k*q = n; +        or an odd integer to test for primiality +        Let n be an odd prime. Then n-1 is even, +        where k is a positive integer. +    """ +    k = 0 +    while (n > 0) and (n % 2 == 0): +        k += 1 +        n >>= 1 +    return (k, n) + +def prime(a, q, k, n): +    if pow(a, q, n) == 1: +        return True +    elif (n - 1) in [pow(a, q*(2**j), n) for j in range(k)]: +        return True +    else: +        return False + +def millerrabin(n, trials): +    """ +        There is still a small chance that n will return a +        false positive. To reduce risk, it is recommended to use +        more trials. +    """ +    # 2^k * q = n - 1; q is an odd int +    (k, q) = splittoodd(n - 1) + +    for trial in range(trials): +        a = random.randint(2, n-1) +        if not prime(a, q, k, n): +            return False +    return True + +def getprime(k): +    """ Generate prime of size k bits, with 50 tests +        to ensure accuracy. +    """ +    prime = 0 +    while (prime == 0): +        prime = random.randrange(pow(2,k//2-1) + 1, pow(2, k//2), 2) +        if not millerrabin(prime, 50): +            prime = 0 +    return prime + +def modularinverse(a, m): +    """ To calculate the decryption exponent such that +        (d * e) mod phi(N) = 1 OR g == 1 in our implementation. +        Where m is Phi(n) (PHI = (p-1) * (q-1) ) + +        s % m or d (decryption exponent) is the multiplicative inverse of +        the encryption exponent e. +    """ +    g, s, t = eec(a, m) +    if g == 1: +        return s % m +    else: +        return None + +def keygen(bits): +    """ The public encryption exponent e, +        can be an artibrary prime number. + +        Obviously, the higher the number, +        the more secure the key pairs are. +    """ +    e = 17 +    p = getprime(bits) +    q = getprime(bits) +    d = modularinverse(e, (p-1)*(q-1)) +    return p*q,d,e + +def writetofile(e, d, n): +    """ Write our public and private keys to file +    """ +    public = open("publicKey", "w") +    public.write(str(e)) +    public.write("\n") +    public.write(str(n)) +    public.close() + +    private = open("privateKey", "w") +    private.write(str(d)) +    private.write("\n") +    private.write(str(n)) +    private.close() + + +if name == 'main': +    bits = input("Enter the size of your key pairs, in bits: ") + +    n, d, e = keygen(int(bits)) + +    #Write keys to file +    writetofile(e, d, n) + +    print("Your keys pairs have been saved to file") + +    m = input("Enter the message you would like to encrypt: ") + +    m = stringEncode(m) +    encrypted = pow(m, e, n) + +    print("Your encrypted message is: %s" % encrypted) +    decrypted = pow(encrypted, d, n) +    message = stringDecode(decrypted) +    print("You message decrypted is: %s" % message)

Python-checkins mailing list Python-checkins at python.org http://mail.python.org/mailman/listinfo/python-checkins

-- Senthil

More information about the Python-Dev mailing list