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).
︡f4e251a1-3bfc-4516-97a3-3b2766131edd︡{"html": "Math 356: Number Theory
\nFall 2011, Willamette University
\nSage Investigation 2: RSA
\nLets implement RSA like the pros do (well, not exactly, but closer than if we were doing these calculations by hand)
\nTo 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:
\nhttp://primes.utm.edu/lists/small/small.html#100\ufeff
\n(However, keep in mind that loose primes bust rhymes. Trying to modify \"Loose lips sink ships\" to minimal sucess).
"}︡ ︠eca33a85-59c9-44f6-9f6e-88157f37c278︠ p1=58021664585639791181184025950440248398226136069516938232493687505822471836536824298822733710342250697739996825938232641940670857624514103125986134050997697160127301547995788468137887651823707102007839; ︡7fc3486b-f896-4281-99b6-480018432133︡︡ ︠b0683756-7c03-461f-968b-2b728e305f62︠ p2=40992408416096028179761232532587525402909285099086220133403920525409552083528606215439915948260875718893797824735118621138192569490840098061133066650255608065609253901288801302035441884878187944219033; ︡33c05594-cfe0-4ad3-a7f4-05ca2b1e82d6︡︡ ︠6bf26774-67dc-4171-a1b8-35c18690d29ai︠ %htmlLets get a handle on what is computationally difficult and what is not. How hard is it to multiply our two large primes?
︡73ad4636-817e-4ec5-878c-08a979f60667︡{"html": "Lets get a handle on what is computationally difficult and what is not. How hard is it to multiply our two large primes?
"}︡ ︠86564b46-932d-4500-8d34-047261aa9dd0︠ r=p1*p2; r ︡8c34d50c-1625-40fc-b7ff-996691224d41︡{"stdout": "2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593487787304385057027361500093524515166409297413377711924248126458818729472453686878056938782868218587885823670071764562729009142349495541571784324904561621330507874472500533965411133341040440967098999687"}︡ ︠602c7841-c42a-49e3-9689-43409ed812a0i︠ %htmlNot too bad. How about factoring?
︡8bff7fa4-194d-4338-b2ee-8f76ebec240d︡{"html": "Not too bad. How about factoring?
"}︡ ︠55defcf1-ca40-412b-a28b-a708054efe0e︠ factor(r) ︡9b798f8d-a152-464c-af6d-a61cde611b92︡{"stderr": "Traceback (most recent call last):\n File \"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}$.
︡0a0beb3a-bb3c-4ad9-896e-79edd33354c0︡{"html": "So factoring bad, multiplying good.... Potential trap-door function: Product of two large primes.
\nLet's implement RSA
\nAs 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}$.
"}︡ ︠2b2f8cb8-ef6c-44ea-be7a-990ffcadd0ab︠ n=p1*p2; e=8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973; n,e ︡7009466f-5d48-4169-8bd8-3955be371d99︡{"stdout": "(2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593487787304385057027361500093524515166409297413377711924248126458818729472453686878056938782868218587885823670071764562729009142349495541571784324904561621330507874472500533965411133341040440967098999687, 8726641590503419650325196619937603416439489172580927797921688450581350540574217626151578525827423033276197489219680752921410238881917731681447358498204217268973)"}︡ ︠829892d7-b528-4803-af68-93b6b69ab146i︠ %htmlOur 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$.
︡92a7ac10-28f7-4881-af42-e6015631a984︡{"html": "Our private key is $p_1$, $p_2$ which we can use to find the multiplicative inverse of $e$.
\nFrom 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$.
\nThus, 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$.
"}︡ ︠81723cc8-b61a-46a2-8ff8-deface9c331b︠ euler_phi(n) ︡fd1ea345-1e08-4261-9c8b-ac207245eba4︡{"stderr": "Traceback (most recent call last):\n File \"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$.
︡8b9bceb3-4dfe-4749-a13b-66b780ee45e6︡{"html": "Okay, so it's at least hard enough to thwart a busy adversary with a short attention span. Check.
\nNow to find the multiplicative inverse $d$ of $e$.
"}︡ ︠32d5e7e4-fcb0-4998-97b6-d348c5300a89︠ phi_n=(p1-1)*(p2-1); phi_n ︡ae598da2-debd-4087-a1af-1dab4ff90349︡{"stdout": "2378447771676281443596926403590129109364434504594246066182003432158462534251841686009044694129678615012579012248227611387806026314165682461696667330145313591052493494416313644526534734479300262581593388773231383321208000554835041487392608161992209108765882228850787497448533621447542676133209615461469189875421091211465930278922380187370597205703860368025282137917051249375640960011503739072052772816"}︡ ︠d97a11e8-61c2-4c56-acb9-249076c7aba6︠ xgcd(e,phi_n) ︡c278ae2a-bf43-493e-ac7f-5bb273cdede3︡{"stdout": "(1, 639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181, -2346365469262146344438507487725256641650964650078389116886525560719953089366920568236159148831218276394761168875121634886436297934619897154144913269590832162032)"}︡ ︠b113d796-1a2e-4f08-b47d-9588f31e17b7i︠ %htmlSo $d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938 723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328 377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181$
is our multiplicative inverse of $e$ modulo $\phi(n)$.
︡53923ef6-46fc-452e-a7d8-a39559024e31︡{"html": "So $d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938 723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328 377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181\ufeff$
\nis our multiplicative inverse of $e$ modulo $\\phi(n)$.
"}︡ ︠f8b784dc-147b-403b-b11c-a922d0aacec6︠ d=639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181; d ︡3ce7bf7f-5c14-4fcf-9ac7-8ad7773f97f6︡{"stdout": "639502340508381801173901077897581798407836367123543202517910381283991341016916189863273838638907985371642397630246799362621041070349097886351938723233162303283382490388680827569549802968932406139830339971427161490710649380748471616872050911643427322573874529550549002203956222154738117328377566176225176611492957102605259323217744555064296434979439530043128312757066741374057433624191205144123806181"}︡ ︠e17a27b2-959e-4b2e-84f6-20286d128ccdi︠ %htmlNatasha has a message $M$ for us.
︡7e29fd5f-7b6a-46f0-8ba9-eed94a58a1b5︡{"html": "Natasha has a message $M$ for us.
"}︡ ︠3c051853-8111-4b67-a5c1-38d44b4fdd3b︠ M=67898674645434323212134567897654678987009887656544324343544657562113436576765454332546768977987655789657654345433245678998987697665454354368511589045427654532455765865442129876087-897665; M ︡99d35404-b378-4850-99e9-6afc9640b21d︡{"stdout": "67898674645434323212134567897654678987009887656544324343544657562113436576765454332546768977987655789657654345433245678998987697665454354368511589045427654532455765865442128978422"}︡ ︠5774ddc8-9de8-4e5e-a0b6-87e8f09c2ed9i︠ %htmlNatasha will now encipher her message and send the ciphertext to us.
︡e2e509bc-4ae2-44de-9e4d-c8becf07ed33︡{"html": "Natasha will now encipher her message and send the ciphertext to us.
"}︡ ︠b41617f5-7d52-4af5-9f95-80c1f28ddaa6︠ c=power_mod(M,e,n); c ︡46d34916-9a92-42a6-bca1-98bb115b5576︡{"stdout": "2057270156044275297892100308616078668642264072598187671707749435815283413450672920080649675297983188532433202343515703429197601540148226331866229792908344412900414367604981962750806128413478219470250491874564149855485888335157831876353450217766183469992819249026636122415625429689432645013494489849604973974959342304875206755585037827444545793723177511078126986923402783432962353128583703157070491129"}︡ ︠131d0baf-9db2-4643-9818-e10a90a4c3bbi︠ %htmlHow will we decrypt it?
︡62f49656-6463-45db-9cd1-56e2cc489a22︡{"html": "How will we decrypt it?
"}︡ ︠754fc37c-a297-4d86-9dec-b5350da294b5︠ T=power_mod(c,d,n); T ︡fe538bde-a0a2-447d-bcb8-e9995648f7a5︡{"stdout": "67898674645434323212134567897654678987009887656544324343544657562113436576765454332546768977987655789657654345433245678998987697665454354368511589045427654532455765865442128978422"}︡ ︠82125d4a-e096-4643-a0e2-e08609c35b79i︠ %htmlVerifying that we have correctly decrypted the message:
︡d08e6c31-97fa-4f12-8f3a-8c92783633a3︡{"html": "Verifying that we have correctly decrypted the message:
"}︡ ︠7b7b30f1-e1cc-4f05-998a-01d0845de3af︠ M-T ︡95c98218-82c6-4313-bc6b-80febce22ed8︡{"stdout": "0"}︡ ︠fabad893-f201-4317-bffd-1610770b5d8di︠ %htmlAppendix 1: Some Useful Sage Functions Related to Modular Equivalence, GCD, Primes, and Factorization
︡e74a8f32-82d1-4077-a097-d9c90be26f96︡{"html": "Appendix 1: Some Useful Sage Functions Related to Modular Equivalence, GCD, Primes, and Factorization
"}︡ ︠dc586da0-e0e9-41d5-a808-e131c9bbd9b2︠ # Greatest Common Divisors gcd(24, 12345) ︡bd877f04-3f69-4473-a1b3-621b8f98055a︡{"stdout": "3"}︡ ︠668cc424-8170-4919-9abb-7f60a1601a9b︠ # Extended GCD: This finds the GCD and the EA linear combination that produces it. # Example: 2 = (-5)*10 + 1*(52) xgcd(10, 52) ︡d03f9bc5-0761-4de0-a26d-00bc90845d84︡{"stdout": "(2, -5, 1)"}︡ ︠79d9aba6-d814-42ac-811b-21ea3adfc048︠ # 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) ︡aa9912b3-9122-4c6d-92cb-a126513571d2︡{"stdout": "67"}︡ ︠291aff41-7fb3-4be0-9958-2f954c6f405d︠ # What if we try to find the inverse of 2 modulo 100? inverse_mod(2, 100) ︡60080941-d5f2-4a90-9c72-41d1848627c7︡{"stderr": "Traceback (most recent call last):\n File \"