Sunday, May 21, 2006

RSA using Pythonic Notation

Euler's Theorem:
if gcd(b, N) == 1: assert pow(b, totient(N), N) == 1
Also, if public key N = p*q with p,q being big probable primes per Miller-Rabin, then the totient(N) is simply (p-1) * (q-1).

Using the Extended Euclidean Algorithm (EEA), we compute: d = inverse(e, totient(N)) such that (e*d) % totient(N) == 1.

So now d is the secret complement of public key N, presumably not derivable minus knowledge of factors p and q, and presumably N can't be factored in any reasonable amount of time (win big bucks if you're able to crack these large Ns).

Then RSA works essentially as follows:
ciphertext = pow( plaintext, e, N)
plaintext = pow( ciphertext, d, N)
I've got more discussion of all this at the Math Forum under the heading of Gnu Math.