""" 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)
_______________________________________________ Edu-sig mailing list Edu-sig@python.org https://mail.python.org/mailman/listinfo/edu-sig
