3341.sagews

Cryptography Goes Pubic

Fall 2011, Willamette University

Mini University

Lets implement RSA like the pros do (well, not exactly, but closer than if we were doing these calculations by hand)

To start with, we need some large primes.  Say something on the order of 100 digits.  Because our need for security is only theoretical, we can be lazy and get our large primes from a website.  Say this one:

http://primes.utm.edu/lists/small/small.html#100

(However, keep in mind that loose primes bust rhymes.  Trying to modify "Loose lips sink ships" to minimal sucess).

# Secret: Known only to Boris
p1=58021664585639791181184025950440248398226136069516938232493687505822471836536824298822733710342250697739996825938232641940670857624514103125986134050997697160127301547995788468137887651823707102007839;

# Secret: Known only to Boris
p2=40992408416096028179761232532587525402909285099086220133403920525409552083528606215439915948260875718893797824735118621138192569490840098061133066650255608065609253901288801302035441884878187944219033;

n=p1*p2;
n

2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593487787304385057027361500093524515166409297413377711924248126458818729472453686878056938782868218587885823670071764562729009142349495541571784324904561621330507874472500533965411133341040440967098999687

Lets get a handle on what is computationally difficult and what is not.  How hard is it to multiply our two large primes?

Not too bad.  How about factoring?

factor(n)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_5.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("ZmFjdG9yKHIp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpxm1fec/___code___.py", line 2, in <module> exec compile(u'factor(r)' + '\n', '', 'single') File "", line 1, in <module> File "/sagenb/sage_install/sage-4.7/local/lib/python2.6/site-packages/sage/rings/arith.py", line 2272, in factor int_ = int_, verbose=verbose) File "integer.pyx", line 3315, in sage.rings.integer.Integer.factor (sage/rings/integer.c:20911) File "integer.pyx", line 3214, in sage.rings.integer.Integer.__factor_using_pari (sage/rings/integer.c:20060) File "gen.pyx", line 8221, in sage.libs.pari.gen.gen.factor (sage/libs/pari/gen.c:37247) KeyboardInterrupt __SAGE__

So factoring bad, multiplying good.... Potential trap-door function:  Product of two large primes.

Let's implement RSA

As Boris, we need to generate and post our public information: $n=p_1*p_2$ and $e$ such that $e$ and $\phi(n))$ are relatively prime

# Public: Boris makes his alphabet encoding scheme, n, and e public
e=8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973;
e

8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973

Our private key is $p_1$, $p_2$ which we can use to find the multiplicative inverse of $e$. 

From our knowledge of $p_1$ and $p_2$ we can calculate the euler phi function $epn=\phi(p_1p_2)=(p_1-1)(p_2-1)$.  Since $(e,\phi(n))=1$, $e$ is a unit modulo $\phi(n)$, and thus there exists an element $d$ such that $de\equiv 1 \pmod{\phi(n)}$, i.e. $q\phi(n)=de-1$, or equivalently $de-q\phi(n)=1$.

Thus, we can use the euclidean algorithm to calculate the inverse $d$ of $e$ given $\phi(n)$.  It's important to verify that an adversary listening in on our conversation with Natasha couldn't do the same thing, i.e. that it is hard to find $\phi(n)$ without knowledge of $p_1$ and $p_2$.

euler_phi(n)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_7.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("ZXVsZXJfcGhpKG4p"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmp4h1Ftg/___code___.py", line 2, in <module> exec compile(u'euler_phi(n)' + '\n', '', 'single') File "", line 1, in <module> File "/sagenb/sage_install/sage-4.7/local/lib/python2.6/site-packages/sage/rings/arith.py", line 2571, in __call__ return ZZ(pari(n).phi()) File "gen.pyx", line 5389, in sage.libs.pari.gen.gen.phi (sage/libs/pari/gen.c:22084) KeyboardInterrupt __SAGE__

Okay, so it's at least hard enough to thwart a busy adversary with a short attention span.  Check.

Now to find the multiplicative inverse $d$ of $e$.

# Secret: Only Boris can calculate this.  Computationally infeasible unless you know p1 and p2
phi_n=(p1-1)*(p2-1);
phi_n

2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593388773231383321208000554835041487392608161992209108765882228850787497448533621447542676133209615461469189875421091211465930278922380187370597205703860368025282137917051249375640960011503739072052772816

# Secret: Known only to Boris
xgcd(e,phi_n)

(1, 639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181, -2346365469262146344438507487725256641650964650078389116886525560719953089366920568236159148831218276394761168875121634886436297934619897154144913269590832162032)

So $d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938 723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328 377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181$

is our multiplicative inverse of $e$ modulo $\phi(n)$.

# Secret: Known only to Boris
d=6395023405083818011739010778975817984078363671235432025179103812839913410169161898632738386389079853716423976302467993626210410703490978863519387232331623032833824903886808275695498029689324061398303399714271614907106493807484716168720509116434273225874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181;
d

639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181

Natasha will now encipher her message and send the ciphertext to us.

How will we decrypt it?

C=2289130750044867831256816339500699294101706592016783081016033620883302687593672434658364872332926153857949038258686073616131248448516777209053325004386660962552740036507233760933959120811325152084195004907441440362163660256083913984643552996832785069005589965647282138318744647078827455680476851665260277359597637244339681537038126724828811008459667247084676950406348805688854822909472743930462630681;
C

2289130750044867831256816339500699294101706592016783081016033620883302687593672434658364872332926153857949038258686073616131248448516777209053325004386660962552740036507233760933959120811325152084195004907441440362163660256083913984643552996832785069005589965647282138318744647078827455680476851665260277359597637244339681537038126724828811008459667247084676950406348805688854822909472743930462630681

T=power_mod(C,d,n);
T

1114102712102928992730211449