RSA implementation in python

rsa.py

# !usr/bin/python
# coding: utf-8
# author: mdubourg001 : https://github.com/mdubourg001

import random
import base64
import struct
import sys
from random import randrange


def is_prime(n, k=30):
    if n <= 3:
        return n == 2 or n == 3
    neg_one = n - 1
    s, d = 0, neg_one
    while not d & 1:
        s, d = s+1, d>>1
    assert 2 ** s * d == neg_one and d & 1

    for i in range(k):
        a = randrange(2, neg_one)
        x = pow(a, d, n)
        if x in (1, neg_one):
            continue
        for r in range(1, s):
            x = x ** 2 % n
            if x == 1:
                return False
            if x == neg_one:
                break
        else:
            return False
    return True

def randprime(N=10**8):
    p = 1
    while not is_prime(p):
        p = randrange(N)
    return p

def pgcd(a,b) :
   while a%b != 0 :
      a, b = b, a%b
   return b

def rand_e():
    e = 3
    while True:
        e += 1
        if ((random.randint(1, 1000) % 42) == 0) and pgcd(e, fn) == 1:
            return e
    return e

def multinv(modulus, value):
    x, lastx = 0, 1
    a, b = modulus, value
    while b:
        a, q, b = b, a // b, a % b
        x, lastx = lastx - q * x, x
    result = (1 - lastx * modulus) // value
    if result < 0:
        result += modulus
    assert 0 <= result < modulus and value * result % modulus == 1
    return result

def print_encoded(ascii_arr):
    toprint = ""
    for nb in ascii_arr:
        toprint += str(nb)
    print ("Your encoded message is: " + toprint)


def encode(message):
    # return a list containing (ascii_value_of_char**e % n)
    to_return = []
    for c in message:
        # fast exponentiation using pow
        to_return.append(pow(ord(c), e, n))
    return to_return

def decode(ascci_msg):
    result = ""
    for nb in ascci_msg:
        result += chr(pow(nb, d, n))
    return result


p = randprime(2**512)
q = randprime(2**512)
n = p * q
fn = (p-1) * (q-1)
e = rand_e()
d = multinv(fn, e)

if len(sys.argv) > 1:
    m = sys.argv[1]
else:
    m = "bonjour je suis le message a chiffrer puis a dechiffrer"

# public key is the couple (e, n) but conventionnaly b64 encoded
print ("Your b64 encoded public key is: \n\n %s, %s \n\n\n" % (base64.b64encode(str(e)), base64.b64encode(str(n))))
# private key is the couple (d, n) but n is known in public key
print ("Your b64 encoded private key is \n\n%s  \n\n\n" % (base64.b64encode(str(d))))

crypt = encode(m)
#print_encoded(crypt)
print ("Your decoded message is " + decode(crypt))