︠0c689cbc-ebe7-49fa-97a3-8a4ff9bfdd9fi︠
%html
<p style="text-align: center;"><span style="font-size: xx-large;">Cryptography Goes Pubic<br /></span></p>
<p style="text-align: center;"><span style="font-size: large;">Fall 2011, Willamette University</span></p>
<p style="text-align: center;"><span style="font-size: x-large; font-family: comic sans ms,sans-serif;">Mini University<br /></span></p>
<p>Lets implement RSA like the pros do (well, not exactly, but closer than if we were doing these calculations by hand)</p>
<p>To start with, we need some large primes.&nbsp; Say something on the order of 100 digits.&nbsp; Because our need for security is only theoretical, we can be lazy and get our large primes from a website.&nbsp; Say this one:</p>
<p style="text-align: center;"><a href="http://primes.utm.edu/lists/small/small.html#100">http://primes.utm.edu/lists/small/small.html#100</a></p>
<p>(However, keep in mind that loose primes bust rhymes.&nbsp; Trying to modify "Loose lips sink ships" to minimal sucess).</p>

︡5329cd68-e788-44a4-94c5-2cae4dabf9a0︡{"html": "<p style=\"text-align: center;\"><span style=\"font-size: xx-large;\">Cryptography Goes Pubic<br /></span></p>\n<p style=\"text-align: center;\"><span style=\"font-size: large;\">Fall 2011, Willamette University</span></p>\n<p style=\"text-align: center;\"><span style=\"font-size: x-large; font-family: comic sans ms,sans-serif;\">Mini University<br /></span></p>\n<p>Lets implement RSA like the pros do (well, not exactly, but closer than if we were doing these calculations by hand)</p>\n<p>To start with, we need some large primes.&nbsp; Say something on the order of 100 digits.&nbsp; Because our need for security is only theoretical, we can be lazy and get our large primes from a website.&nbsp; Say this one:</p>\n<p style=\"text-align: center;\"><a href=\"http://primes.utm.edu/lists/small/small.html#100\">http://primes.utm.edu/lists/small/small.html#100\ufeff</a></p>\n<p>(However, keep in mind that loose primes bust rhymes.&nbsp; Trying to modify \"Loose lips sink ships\" to minimal sucess).</p>"}︡
︠34ccb689-b520-41b3-bf0b-acb9556f7aad︠
# Secret: Known only to Boris
p1=58021664585639791181184025950440248398226136069516938232493687505822471836536824298822733710342250697739996825938232641940670857624514103125986134050997697160127301547995788468137887651823707102007839;
︡29ac4079-d8c1-4c3c-abe5-dd0ebf7286df︡︡
︠3e73a40e-d2e1-4e38-9836-ac7470c964da︠
# Secret: Known only to Boris
p2=40992408416096028179761232532587525402909285099086220133403920525409552083528606215439915948260875718893797824735118621138192569490840098061133066650255608065609253901288801302035441884878187944219033;
︡48347f6e-a03e-4bc8-917b-2be5f2e9b121︡︡
︠518d106c-b0bb-4f5d-9781-a4eeed9499ee︠
n=p1*p2;
n
︡30670c0b-bf98-4ff1-ba2a-792fc4beff4f︡{"stdout": "2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593487787304385057027361500093524515166409297413377711924248126458818729472453686878056938782868218587885823670071764562729009142349495541571784324904561621330507874472500533965411133341040440967098999687"}︡
︠89282d1e-8d6d-4955-a071-40276eda801di︠
%html
<p>Lets get a handle on what is computationally difficult and what is not.&nbsp; How hard is it to multiply our two large primes?</p>

<p>Not too bad.&nbsp; How about factoring?</p>

︡69423979-3046-4708-a977-27d4c1d9c677︡{"html": "<p>Lets get a handle on what is computationally difficult and what is not.&nbsp; How hard is it to multiply our two large primes?</p>\n\n<p>Not too bad.&nbsp; How about factoring?</p>"}︡
︠95ecdc0e-f402-409a-8eb0-457cfed3131f︠
factor(n)
︡5b4fa0b0-3154-4bd8-afd0-b608fe5d28a3︡{"stderr": "Traceback (most recent call last):\n  File \"<stdin>\", line 1, in <module>\n  File \"_sage_input_5.py\", line 10, in <module>\n    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')\n  File \"\", line 1, in <module>\n    \n  File \"/tmp/tmpxm1fec/___code___.py\", line 2, in <module>\n    exec compile(u'factor(r)' + '\\n', '', 'single')\n  File \"\", line 1, in <module>\n    \n  File \"/sagenb/sage_install/sage-4.7/local/lib/python2.6/site-packages/sage/rings/arith.py\", line 2272, in factor\n    int_ = int_, verbose=verbose)\n  File \"integer.pyx\", line 3315, in sage.rings.integer.Integer.factor (sage/rings/integer.c:20911)\n  File \"integer.pyx\", line 3214, in sage.rings.integer.Integer.__factor_using_pari (sage/rings/integer.c:20060)\n  File \"gen.pyx\", line 8221, in sage.libs.pari.gen.gen.factor (sage/libs/pari/gen.c:37247)\nKeyboardInterrupt\n__SAGE__"}︡
︠2980aad0-8e2f-4be9-a4fc-9d6eda4f2725i︠
%html
<p>So factoring bad, multiplying good.... Potential trap-door function:&nbsp; Product of two large primes.</p>
<p>Let's implement RSA</p>
<p>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</p>

︡597bfcb9-0353-4e28-9e62-84fd0dd8f51a︡{"html": "<p>So factoring bad, multiplying good.... Potential trap-door function:&nbsp; Product of two large primes.</p>\n<p>Let's implement RSA</p>\n<p>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</p>"}︡
︠0b7e82ab-e6c2-4490-b9f4-a80a5be0f553︠
# Public: Boris makes his alphabet encoding scheme, n, and e public
e=8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973;
e
︡75c70235-05b0-4a47-a8eb-ec1f303d4161︡{"stdout": "8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973"}︡
︠f211302b-b8d0-4332-91ff-aceb2ea503fci︠
%html
<p>Our private key is $p_1$, $p_2$ which we can use to find the multiplicative inverse of $e$.&nbsp;</p>
<p>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)$.&nbsp; 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$.</p>
<p>Thus, we can use the euclidean algorithm to calculate the inverse $d$ of $e$ given $\phi(n)$.&nbsp; 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$.</p>

︡ef459fe0-6ef6-44bb-81d1-69f84ad60b82︡{"html": "<p>Our private key is $p_1$, $p_2$ which we can use to find the multiplicative inverse of $e$.&nbsp;</p>\n<p>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)$.&nbsp; 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$.</p>\n<p>Thus, we can use the euclidean algorithm to calculate the inverse $d$ of $e$ given $\\phi(n)$.&nbsp; 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$.</p>"}︡
︠628aee23-53fa-4df9-94c2-8a1a90863ed3︠
euler_phi(n)
︡75f65216-7477-4735-ad68-8915771a8382︡{"stderr": "Traceback (most recent call last):\n  File \"<stdin>\", line 1, in <module>\n  File \"_sage_input_7.py\", line 10, in <module>\n    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')\n  File \"\", line 1, in <module>\n    \n  File \"/tmp/tmp4h1Ftg/___code___.py\", line 2, in <module>\n    exec compile(u'euler_phi(n)' + '\\n', '', 'single')\n  File \"\", line 1, in <module>\n    \n  File \"/sagenb/sage_install/sage-4.7/local/lib/python2.6/site-packages/sage/rings/arith.py\", line 2571, in __call__\n    return ZZ(pari(n).phi())\n  File \"gen.pyx\", line 5389, in sage.libs.pari.gen.gen.phi (sage/libs/pari/gen.c:22084)\nKeyboardInterrupt\n__SAGE__"}︡
︠948fa2fe-2516-4ba9-b2b9-b22ed9f48ad6i︠
%html
<p>Okay, so it's at least hard enough to thwart a busy adversary with a short attention span.&nbsp; Check.</p>
<p>Now to find the multiplicative inverse $d$ of $e$.</p>

︡3f94e43e-53d0-40a0-b1bd-e38f3792b3ad︡{"html": "<p>Okay, so it's at least hard enough to thwart a busy adversary with a short attention span.&nbsp; Check.</p>\n<p>Now to find the multiplicative inverse $d$ of $e$.</p>"}︡
︠6f786c42-edeb-4320-875d-558835fb9208︠
# Secret: Only Boris can calculate this.  Computationally infeasible unless you know p1 and p2
phi_n=(p1-1)*(p2-1);
phi_n
︡acdbdba8-f1fe-431e-9419-37d40eb82a69︡{"stdout": "2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593388773231383321208000554835041487392608161992209108765882228850787497448533621447542676133209615461469189875421091211465930278922380187370597205703860368025282137917051249375640960011503739072052772816"}︡
︠5c593569-8673-4c5a-858a-32adc7516b57︠
# Secret: Known only to Boris
xgcd(e,phi_n)
︡2403e193-55cc-43d1-9527-ff5b0f81385d︡{"stdout": "(1, 639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181, -2346365469262146344438507487725256641650964650078389116886525560719953089366920568236159148831218276394761168875121634886436297934619897154144913269590832162032)"}︡
︠a9cdab82-bf52-4c72-a8c0-f6edbd074be0i︠
%html
<p>So $d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938 723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328 377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181$</p>
<p>is our multiplicative inverse of $e$ modulo $\phi(n)$.</p>

︡bc26b40e-f985-4f6a-b5ab-e23687f872b3︡{"html": "<p>So $d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938 723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328 377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181\ufeff$</p>\n<p>is our multiplicative inverse of $e$ modulo $\\phi(n)$.</p>"}︡
︠7ca880bb-b5d7-4441-87d2-14931ed5b17f︠
# Secret: Known only to Boris
d=6395023405083818011739010778975817984078363671235432025179103812839913410169161898632738386389079853716423976302467993626210410703490978863519387232331623032833824903886808275695498029689324061398303399714271614907106493807484716168720509116434273225874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181;
d
︡86197827-73ea-4cf0-8f8a-5f68f0894eed︡{"stdout": "639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181"}︡
︠502dee85-cbc1-44f5-b3ad-ff22ab712f76i︠
%html
<p>Natasha will now encipher her message and send the ciphertext to us.</p>

<p>How will we decrypt it?</p>

︡64f483d6-948c-40ec-bb31-659fa2ece483︡{"html": "<p>Natasha will now encipher her message and send the ciphertext to us.</p>\n\n<p>How will we decrypt it?</p>"}︡
︠ea3e20db-0a58-4247-9944-f365e552a188︠
C=2289130750044867831256816339500699294101706592016783081016033620883302687593672434658364872332926153857949038258686073616131248448516777209053325004386660962552740036507233760933959120811325152084195004907441440362163660256083913984643552996832785069005589965647282138318744647078827455680476851665260277359597637244339681537038126724828811008459667247084676950406348805688854822909472743930462630681;
C
︡b29f71c7-67ee-4b71-a0d4-93183336f803︡{"stdout": "2289130750044867831256816339500699294101706592016783081016033620883302687593672434658364872332926153857949038258686073616131248448516777209053325004386660962552740036507233760933959120811325152084195004907441440362163660256083913984643552996832785069005589965647282138318744647078827455680476851665260277359597637244339681537038126724828811008459667247084676950406348805688854822909472743930462630681"}︡
︠c921b86d-6769-4c01-afff-b6bcf08efc5c︠
T=power_mod(C,d,n);
T
︡564a4964-d6b2-47b9-abf3-d50fb30ff26c︡{"stdout": "1114102712102928992730211449"}︡