3246.sagews

Math 356: Number Theory

Fall 2011, Willamette University

Sage Investigation 2: RSA

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).

p1=58021664585639791181184025950440248398226136069516938232493687505822471836536824298822733710342250697739996825938232641940670857624514103125986134050997697160127301547995788468137887651823707102007839;

p2=40992408416096028179761232532587525402909285099086220133403920525409552083528606215439915948260875718893797824735118621138192569490840098061133066650255608065609253901288801302035441884878187944219033;

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

r=p1*p2;
r

2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593487787304385057027361500093524515166409297413377711924248126458818729472453686878056938782868218587885823670071764562729009142349495541571784324904561621330507874472500533965411133341040440967098999687

Not too bad.  How about factoring?

factor(r)

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,\phi(n))\equiv 1\pmod{n}$.

n=p1*p2;
e=8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973;
n,e

(2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593487787304385057027361500093524515166409297413377711924248126458818729472453686878056938782868218587885823670071764562729009142349495541571784324904561621330507874472500533965411133341040440967098999687, 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$.

phi_n=(p1-1)*(p2-1);
phi_n

2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593388773231383321208000554835041487392608161992209108765882228850787497448533621447542676133209615461469189875421091211465930278922380187370597205703860368025282137917051249375640960011503739072052772816

xgcd(e,phi_n)

(1, 639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181, -2346365469262146344438507487725256641650964650078389116886525560719953089366920568236159148831218276394761168875121634886436297934619897154144913269590832162032)

So $d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938 723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328 377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181$

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

d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181;
d

639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181

Natasha has a message $M$ for us.

M=67898674645434323212134567897654678987009887656544324343544657562113436576765454332546768977987655789657654345433245678998987697665454354368511589045427654532455765865442129876087-897665;
M

67898674645434323212134567897654678987009887656544324343544657562113436576765454332546768977987655789657654345433245678998987697665454354368511589045427654532455765865442128978422

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

c=power_mod(M,e,n);
c

2057270156044275297892100308616078668642264072598187671707749435815283413450672920080649675297983188532433202343515703429197601540148226331866229792908344412900414367604981962750806128413478219470250491874564149855485888335157831876353450217766183469992819249026636122415625429689432645013494489849604973974959342304875206755585037827444545793723177511078126986923402783432962353128583703157070491129

How will we decrypt it?

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

67898674645434323212134567897654678987009887656544324343544657562113436576765454332546768977987655789657654345433245678998987697665454354368511589045427654532455765865442128978422

Verifying that we have correctly decrypted the message:

M-T

0

Appendix 1: Some Useful Sage Functions Related to Modular Equivalence, GCD, Primes, and Factorization

# Greatest Common Divisors
gcd(24, 12345)

3

# Extended GCD:  This finds the GCD and the EA linear combination that produces it.
# Example: 2 = (-5)*10 + 1*(52)
xgcd(10, 52)

(2, -5, 1)

# Multiplicative inverses
# To find the inverse of 3 mod 100:
# Note: we know 3 * 33 = 99 = -1 mod 100
#       so 3 *(-33) = -99 = 1 mod 100
inverse_mod(3, 100)

67

# What if we try to find the inverse of 2 modulo 100?
inverse_mod(2, 100)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_8.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("IyBXaGF0IGlmIHdlIHRyeSB0byBmaW5kIHRoZSBpbnZlcnNlIG9mIDIgbW9kdWxvIDEwMD8KaW52ZXJzZV9tb2QoMiwgMTAwKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpbSnUXy/___code___.py", line 3, in <module> exec compile(u'inverse_mod(_sage_const_2 , _sage_const_100 )' + '\n', '', 'single') File "", line 1, in <module> File "/usr/local/sage2/local/lib/python2.6/site-packages/sage/rings/arith.py", line 1740, in inverse_mod return a.inverse_mod(m) File "integer.pyx", line 5155, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:28828) ZeroDivisionError: Inverse does not exist.

# Factoring is useful (and hard!)
factor(1234567)

127 * 9721

# Primality Testing
is_prime(987654321)

False

#Sometimes we want to find a big prime:
next_prime(2^40)

1099511627791

# Or the nth prime
nth_prime(10)

541