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

Postby casevh » Sun Mar 17, 2013 5:48 am

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

Some comments...

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_function
try:
    input = raw_input
except NameError:
    pass

import random
import string
import math

def 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 a

def 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 % m

def 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 False

def 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 result

def 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: 56
Joined: Sat Feb 09, 2013 7:35 am

Return to Tutorials

Who is online

Users browsing this forum: No registered users and 2 guests