[Edu-sig] RSA in Brief

[kirby urner]

"""
RSA in brief (in Python 3)
See:
http://www.4dsolutions.net/ocn/crypto3.html
http://mathforum.org/kb/thread.jspa?threadID=2663184
http://mathforum.org/kb/thread.jspa?forumID=206&threadID=2653047
(c) MIT License, 4D Solutions
"""

import random

# download a chunk of numbers from:
https://primes.utm.edu/lists/small/millions/
cut_and_paste = """ \
 961807463 961807471 961807499 961807501 961807529 961807549 961807573
961807597
 961807621 961807661 961807663 961807669 961807673 961807733 961807739
961807747
 961807753 961807757 961807783 961807843 961807871 961807909 961807921
961807937
 961807967 961807993 961807999 961808009 961808017 961808033 961808039
961808041
 961808051 961808083 961808087 961808093 961808123 961808161 961808179
961808189
 961808231 961808293 961808297 961808311 961808339 961808347 961808357
961808401
 961808413 961808429 961808431 961808459 961808513 961808521 961808567
961808597
 961808629 961808689 961808699 961808713 961808723 961808773 961808807
961808831
""".split()
some_primes = [int(x) for x in cut_and_paste] # turn strings to ints

# pick any two primes
p = random.choice(some_primes)
q = random.choice(some_primes)


def bingcd(a,b):
    """Extended version of Euclid's Algorithm (binary GCD)
    Returns (m,n,gcd) such that  m*a + n*b = gcd(a,b)"""
    g,u,v = [b,a], [1,0], [0,1]
    while g[1] != 0:
        y = g[0] // g[1]
        g[0], g[1] = g[1], g[0] % g[1]
        u[0], u[1] = u[1], u[0] - y*u[1]
        v[0], v[1] = v[1], v[0] - y*v[1]
    m = v[0] % b
    gcd = (m * a) % b
    n = (gcd - m * a) // b
    return (m, n, gcd)

def inverse(a,b):
    """If gcd(a,b)=1, then inverse(a,b)*a mod b = 1,
    otherwise, if gcd(a,b)!=1, return 0

    Useful in RSA encryption, for finding d such that
    e*d mod totient(n) = 1"""
    inva, n, gcd = bingcd(a,b)
    return (gcd==1) * inva

# Alice
N = p * q
e = 13
phi_N = (p-1)*(q-1)    # totient of N
d = inverse(e, phi_N)  # Euler's Extended GCD
# if d == 0 then degenerate case of e dividing phi_N

print("Public N =", N)
print("Secret d =", d)
print("Check: (e*d) % phi_N =", e*d % phi_N)  # should be 1

# Bob
plaintext = 555777888
print("plaintext =", plaintext)
cyphertext = pow(plaintext, e, N) # power e mod N
print("cyphertext = ", cyphertext)

# Alice
decoded = pow(cyphertext, d, N)
print("decoded =", decoded)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/edu-sig/attachments/20141205/6b5b9a4b/attachment.html>