# [Python-Dev] [Python-checkins] r87677 - python/branches/py3k/py3rsa.py

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,
>
>
>
>   python/branches/py3k/py3rsa.py   (contents, props changed)
>
> ==============================================================================
> --- (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 split_to_odd(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 miller_rabin(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) = split_to_odd(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 get_prime(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 miller_rabin(prime, 50):
> +            prime = 0
> +    return prime
> +
> +def modular_inverse(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 key_gen(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 = get_prime(bits)
> +    q = get_prime(bits)
> +    d = modular_inverse(e, (p-1)*(q-1))
> +    return p*q,d,e
> +
> +def write_to_file(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 = key_gen(int(bits))
> +
> +    #Write keys to file
> +    write_to_file(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
```