> Hi Kirby,
>
> Awesome! You might want to take a look at some similar work; the folks
> who do SICP have as one of their first homework assignments an RSA
> implementation project:
>
> http://mitpress.mit.edu/sicp/psets/ps3/readme.html
>
> I think I have some of this implementation translated into Python on my
> laptop; I'll try hunting for it when I get home.
>
Thanks Danny.
I just eyeballed the code from SICP. I notice the EEA is not explicitly
mentioned, and the code for inverting e mod phi(N) is left to the reader:
;;;(define (solve-ax+by=1 a b)...) you must complete this procedure
;;; Actual RSA encryption and decryption
Also, a simple Fermat filter is used to find primes -- small chance of a
Carmichael squeaking through (Miller-Rabin is stronger). That's OK though
-- at least it's not a black box, as it is with mx.Number.Integer (I'd need
to expound on Miller-Rabin elsewhere [1]).
This is the kind of output I'm displaying. Running the very same demo
encrypts/decrypts the very same message, but with different public keys.
Interim steps give a sense of what's happening -- but of course this'd all
make more sense with accompanying hand-waving with Q&A:
>>> rsa.demo()
hello world --> m=126207244316550804821666916
Two primes:
p=4443976789171856903
q=1026026455556943437
~pow(N,1/3)= 1658224956244
N=4559637753571326430861967232228995611
phi(N)=4559637753571326425391963987500195272
Euler: pow(m, phi(N)+1, N)=
126207244316550804821666916
e=3
phiN mod e = 1
e=3
d=3039758502380884283594642658333463515
d*e mod phiN = 1
c=pow(m,e,N)=441047618940110319203973658343498176
newm=pow(c,d,N)=126207244316550804821666916
126207244316550804821666916 --> plaintext=hello world
>>> rsa.demo()
hello world --> m=126207244316550804821666916
Two primes:
p=3875764993730130869
q=2666745125460919361
~pow(N,1/3)= 2178276378256
N=10335677404461897184814024551585854709
phi(N)=10335677404461897178271514432394804480
Euler: pow(m, phi(N)+1, N)=
126207244316550804821666916
e=3
phiN mod e = 1
d=6890451602974598118847676288263202987
d*e mod phiN = 1
c=pow(m,e,N)=7817547120775391367740832023016453897
newm=pow(c,d,N)=126207244316550804821666916
126207244316550804821666916 --> plaintext=hello world
[1] e.g. see ISBN 0-387-95584-4 pg. 121 (search ISBN in amazon.com).
_______________________________________________
Edu-sig mailing list
[email protected]
http://mail.python.org/mailman/listinfo/edu-sig
