## RSA encryption demonstrator

A place where you can post Python-related tutorials you made yourself, or links to tutorials made by others.

### RSA encryption demonstrator

I've written a simple demonstrator program for RSA encryption.

I've implemented the extended GCD algorithm to solve a*x == 1 (mod m). This is used to calculate the decryption exponent after choosing the encryption exponents.

The function is_prp() (is probable prime) is used to test the two prime numbers that make part of the public key. It first tries division by some small numbers and then makes up to 4 calls to strong_psp_test() (strong Fermat pseudoprime test). The is_prp() function is not appropriate for real-world code. A useful improvement would be to repeat strong_psp_test() between 25 and 50 times and use random bases instead of the hardcoded list.

casevh

Code: Select all
`# A collection of number theory functions that are used to create an example# of RSA encryption.# Make this program work with Python 2.7 and later (including Python 3.x).from __future__ import print_functiontry:    input = raw_inputexcept NameError:    passimport randomimport stringimport mathdef gcd(a,b):    """Calculate the Greatest Common Divisor of a and b.    The result will always be >=0.    """    if (a < 0) or (b < 0):        raise ValueError("Both a and b must be non-negative.")    while b:        a, b = b, a % b    return adef gcd_extended(a,b):    """Calculate the Extended GCD of a and b.    Returns (gcd(a,b),x,y) such that ax + by = gcd(a,b).    """    if (a < 0) or (b < 0):        raise ValueError("Both a and b must be non-negative.")    u1, u2, v1, v2 = 1, 0, 0, 1    while b:        q = a // b        u1, u2, a, v1, v2, b = v1, v2, b, u1 - q * v1, u2 - q * v2, a - q * b    return (a, u1, u2)def inverse_mod(a,m):    """Return x such that ax == 1 (mod m).    An ValueError is raised if gcd(a,m) != 1."""    g, x, y = gcd_extended(a,m)    if g != 1:        raise ValueError("Modular inverse requires a,m to be relatively prime.")    # Force the result to be positive.    return x % mdef strong_psp_test(n, base=2):    """Perform the strong Fermat pseudoprime test."""    d, s = n - 1, 0    while not (d % 2):        d, s = d // 2, s + 1    temp = pow(base, d, n)    if temp == 1:        return True    for i in range(s):        if temp == n - 1:            return True        temp = (temp * temp) % n    if temp == n - 1:        return True    else:        return False# Create a set of all prime numbers less than 200.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]# The following test can only **prove** if a number is composite. If the test# returns False, the number is guaranteed to be composite, but if the test# returns True, the number is most likely prime.# A true Miller-Rabin probable prime test will repeat the strong_psp_test()# for a significant number (25 to 50) of random bases. is_prp() is only# testing the bases 2, 3, 5, 7, and 11.def is_prp(n):    """Return True if n is probably prime.    The following tests are performed:      1) Trial factoring up to 199.      2) strong pseudoprime test for base 2, 3, 5, 7, and 11.    """    if (n != abs(int(n))) or (n < 2):        raise ValueError("n must be a positive integer >= 2.")    if n in primes:        return True    for f in primes:        if not (n % f):            return False    if n < 200 * 200:        return True    # The smallest composite that fails the strong pseudoprime test for bases    # 2, 3, 5, 7, and 11 is 2152302898747.    for b in [2, 3, 5, 7, 11]:        if strong_psp_test(n, b):            return True    return Falsedef create_keys(bits):    """Create a public and private key pair for RSA encryption."""    if (bits != abs(int(bits))) or (bits < 32):        raise ValueError("bits me be a positive integer >= 32.")    # There more secure approaches to picking p,q than just selecting two    # random starting positions.    p = random.getrandbits(bits)    if not (p % 2):        p += 1    while not is_prp(p):        p += 2    q = random.getrandbits(bits)    if not (q % 2):        q += 1    while not is_prp(q):        q += 2    n = p * q    h = (p - 1) * (q - 1)    # Select the encryption exponent.    e = random.getrandbits(bits)    while gcd(e,h) != 1:        e = random.getrandbits(bits)    # Calculate the decryption exponent.    d = inverse_mod(e,h)    # Verify that encryption/decryption work.    assert 123456 == pow(pow(123456, e, n), d, n)    return (n,e), (n,d)def string_to_numbers(s,n,restricted=True):    """Convert a string of characters into a list of numbers    Return a list of numbers by taking groups of n characters and converting    them into a number. The maximum numerical value for a group of n characters    is less than 100**n.    If restricted is True, only the 94 visible characters plus space are    allowed. If restricted is False, all whitespace (carriagle return, tab,    etc.) are allowed."""    chars = string.ascii_letters + string.digits + string.punctuation    if restricted:        chars += ' '    else:        chars += string.whitespace    k = len(chars)    # Force the length of s to be a multiple of n.    if len(s) % n:        s += ' ' * (n - (len(s) % n))    result = []    i = 0    group = s[i:n]    while group:        t = 0        for c in reversed(group):            try:                t = t * k + chars.index(c)            except ValueError:                raise ValueError("A non-ascii or illegal character was found.")        result.append(t)        i += n        group = s[i:i+n]    return resultdef numbers_to_string(l,n,restricted=True):    """Convert a list of numbers into a string.    The values for n and restricted must be the same as the values used in    string_to_numbers()."""    chars = string.ascii_letters + string.digits + string.punctuation    if restricted:        chars += ' '    else:        chars += string.whitespace    k = len(chars)    result = []    for group in l:        for _ in range(n):            group, ch = divmod(group, k)            result.append(chars[ch])    return ''.join(result)def rsa(s,k):    """Perform an RSA round on string s using key k."""    # The length of the substrings (n) that are converted to a number must be    # such that 100**n < 2**n.bit_length.    n = int(math.log(2**encrypt_key[0].bit_length(), 100))    return numbers_to_string([pow(i,k[1],k[0]) for i in string_to_numbers(s,n)],n)if __name__ == "__main__":    print("RSA encryption and decryption")    key = 0    while not 32 <= key <= 256:        try:            key = int(input("Please enter the key size in bits, between 32 and 256: "))        except ValueError:            pass    encrypt_key, decrypt_key = create_keys(key)    plain = input("Please enter text to encrypt: ")    print()    print("Encrypting using the key: ", encrypt_key)    print("Encrypted text:")    cipher = rsa(plain, encrypt_key)    print(cipher)    print("Decrypting using the key: ", decrypt_key)    print("Decrypted text:")    plain = rsa(cipher, decrypt_key)    print(plain)`
casevh

Posts: 114
Joined: Sat Feb 09, 2013 7:35 am