︠e7995e9b-0b68-47d5-b7e3-72d55326b9d0i︠ %html

# Lab 5 – Discrete logarithms (prof version)

Names of the collaborators:

## A) Unsafe parameters, pt. 1

Here is a small (40 bits) modulus that we will use for demonstration purposes. ︡6d2cf457-d2b2-4c36-abb0-326992c4b71d︡{"html":"\n

# Lab 5 – Discrete logarithms (prof version)

\n\nNames of the collaborators:\n

\n\n

## A) Unsafe parameters, pt. 1

\nHere is a small (40 bits) modulus that we will use for demonstration purposes.\n"}︡ ︠1e9ad225-7cba-43ea-aa1b-e7a34ba647afs︠ N = 1022126907089 ︡35f9e036-3382-44b8-b353-35e7fea9e4e4︡{"done":true} ︠41803a98-4778-4cba-bbb7-cf2fdc0c955ai︠ %html Suppose we want to solve the following instance of the DLP: $$\text{find } x \text{ such that } 343857231343^x \equiv 146812954167 \ \mathrm{mod} \ N.$$ Start doing a brute force search for $x$ (up to, say, $2^{20}$) to see how fast it goes. How long do you think it would take you to find $x$ this way? ︡7db21e70-d980-49d0-8aba-406a82fce020︡{"html":"Suppose we want to solve the following instance of the DLP:\n$$\\text{find } x \\text{ such that } 343857231343^x \\equiv 146812954167 \\ \\mathrm{mod} \\ N.$$\nStart doing a brute force search for $x$ (up to, say, $2^{20}$) to see how fast it goes. How long do you think it would take you to find $x$ this way?\n"}︡ ︠2070e199-3f19-45d4-a88f-29ff51f84b36︠ G = 343857231343 X = 146812954167 ︡abf83f60-52ed-4c1b-a82e-617fff41447b︡ ︠026f739e-e39c-422f-9c38-08c6eee478aas︠ ︡300c853a-5610-41f0-b4f7-9d85ce3a2aef︡ ︠9e8e8cc0-9bae-4997-91f7-2099a2bcf9e9s︠ power_mod(G,x,N) == X ︡f2de3dd2-ee2b-40b9-a0e5-76e0722f925a︡{"stdout":"True\n"}︡{"done":true} ︠2a33625e-4b2b-44ad-b4ad-1220630b632f︠ ︡6cdacb10-37bf-4317-9b42-0b9627d103b3︡ ︠7d4d80d2-eba8-47d0-ac51-eadc95fbe598s︠ x = 218752856473 ︡46955ace-0e9b-4ff8-9f8f-78cb2b8a24e9︡{"done":true} ︠331932f8-0553-41f0-8410-c6708b031f65︠ %time x = 0 # exponent L = 1 # left-hand side found = false while x < 2^20 and not found: L = L * G % N x += 1 found = (L == X) print "logarithm found: %s" % found ︡3ae06b1b-8de7-4d5a-a32b-7f2764b1c141︡{"stdout":"logarithm found: False\n"}︡{"stdout":"CPU time: 7.81 s, Wall time: 8.03 s\n"}︡ ︠be977590-0118-423a-9674-1fc44ac2b572i︠ %html

It took roughly $\color{blue} 8$ seconds to test $\color{blue} 2^{20}$ values... Since the sought-after exponent (if it exists) is no bigger than $\color{blue} \varphi(N) \leq N-1$, a full brute-force search would "only" take roughly

︡0e52fd3e-5c80-4ea9-b793-86c1101327ed︡{"html":"

It took roughly $\\color{blue} 8$ seconds to test $\\color{blue} 2^{20}$ values... Since the sought-after exponent (if it exists) is no bigger than $\\color{blue} \\varphi(N) \\leq N-1$, a full brute-force search would \"only\" take roughly

\n \n"}︡ ︠05b96df3-5aac-4357-83f6-bdfeb3b6125b︠ 8 * 2^20 / 60 / 60 / 24 / 30.4 # in *months*... ︡e67d6674-e34c-4c88-9b89-9e079ab34952︡{"stdout":"3.19376218323587\n"}︡ ︠aaabfae4-6deb-489a-8cdb-8feeddce258ei︠ %html The situation is actually much better for the attacker (you) since $N$ was foolishly chosen to be a composite number; Sage has no trouble finding its factors $N = P \cdot Q$: ︡f297671a-4ba8-40a9-94f2-2b04c8e74b7f︡{"html":"The situation is actually much better for the attacker (you) since $N$ was foolishly chosen to be a composite number; Sage has no trouble finding its factors $N = P \\cdot Q$:\n"}︡ ︠c1f4cf8e-1af2-44bf-bd3c-d5d0ec5c44d0︠ factor(N) ︡3a01aaa9-cb74-428b-86fd-b65e07a16f8d︡{"stdout":"529927 * 1928807\n"}︡ ︠f8ac2b3e-983d-4a04-be15-7bfa56028283︠ P = 529927 Q = 1928807 ︡5e401705-359b-4a48-91cd-446dca583672︡ ︠bf2ea4c9-ae74-43ec-9439-373af5f8fd95i︠ %html

Using this knowledge, you should be able to quite easily find the value of $x$ by:

• solving the DLP (by brute force if you want) first modulo $P$, and $Q$;
• then use the Chinese Remainder Theorem to recover the value of $x$ modulo the multiplicative order of $G$ mod $N$.
︡21d90075-f597-4c47-82d2-d374319b702f︡{"html":"

Using this knowledge, you should be able to quite easily find the value of $x$ by:

\n
\n
• solving the DLP (by brute force if you want) first modulo $P$, and $Q$;
• \n
• then use the Chinese Remainder Theorem to recover the value of $x$ modulo the multiplicative order of $G$ mod $N$.
• \n
\n"}︡ ︠e32db82d-e017-4832-9d8a-787bc5db9c48i︠ %html

Let's first find an $\color{blue} x_1$ such that $\color{blue} G^{x_1} \equiv X \, \mathrm{mod} \, P$ (a reasonable thing to brute-force, since $\color{blue} P$ is only roughly half as long as $\color{blue} N$):

︡6b576fcc-60fe-46a0-b30d-138b32a180ee︡{"html":"

\n Let's first find an $\\color{blue} x_1$ such that $\\color{blue} G^{x_1} \\equiv X \\, \\mathrm{mod} \\, P$ (a reasonable thing to brute-force, since $\\color{blue} P$ is only roughly half as long as $\\color{blue} N$):\n

\n"}︡ ︠e0e7ccf4-28fe-4584-8fc0-476956319c02︠ %time x1 = 0 X1 = X % P L = 1 found = false while x1 < P-1 and not found: L = L * G % P x1 += 1 found = (L == X1) print "logarithm found: %s" % found print "x1 = %s" % x1 ︡bf358112-f90c-4801-be38-9a57f0eb0955︡{"stdout":"logarithm found: True\n"}︡{"stdout":"x1 = 463525\n"}︡{"stdout":"CPU time: 3.25 s, Wall time: 3.25 s\n"}︡ ︠4183fc40-3885-4d12-a4fc-b401a47e7021︠ power_mod(G,x1,P) == X % P # ok ︡04da4f5f-3428-4d75-ad29-9d7254d783e5︡{"stdout":"True\n"}︡ ︠0ad27fd5-1c87-4e09-92ae-336854feca11i︠ %html

and the same thing mod $\color{blue} Q$:

︡8368e947-a040-40f2-8e9e-04419ef40106︡{"html":"

\n and the same thing mod $\\color{blue} Q$:\n

\n"}︡ ︠4ee77532-6235-4506-bed1-4649583e7182︠ %time x2 = 0 X2 = X % Q L = 1 found = false while x2 < Q-1 and not found: L = L * G % Q x2 += 1 found = (L == X2) print "logarithm found: %s" % found print "x2 = %s" % x2 ︡16c45024-4aba-4b9e-b761-fa3f6a57238f︡{"stdout":"logarithm found: True\n"}︡{"stdout":"x2 = 1181595\n"}︡{"stdout":"CPU time: 8.20 s, Wall time: 8.28 s\n"}︡ ︠5e0618bf-205e-45c9-a842-d587ec46f405︠ power_mod(G,x2,Q) == X % Q # ok ︡807f0853-dbc3-4e25-b2be-f679ad153d65︡{"stdout":"True\n"}︡ ︠aad601c8-9ce3-4f29-a0bb-51a9f45dd8fci︠ %html

Now we only need to recover $\color{blue} x$, knowing that it satisfies the system of congruences: $$\color{blue} \begin{cases} x \equiv x_1 \, \mathrm{mod} \, n_1 \\ x \equiv x_2 \, \mathrm{mod} \, n_2 \end{cases}$$ where $\color{blue} n_1$ and $\color{blue} n_2$ are the multiplicative orders of $\color{blue} G$ modulo $\color{blue} P$ and $\color{blue} Q$, respectively. To find these partial moduli, we can use the fact that:

︡1a8562b9-eaa7-41bd-ae03-fc9de9a5d716︡{"html":"

\n Now we only need to recover $\\color{blue} x$, knowing that it satisfies the system of congruences: $$\\color{blue} \\begin{cases} x \\equiv x_1 \\, \\mathrm{mod} \\, n_1 \\\\ x \\equiv x_2 \\, \\mathrm{mod} \\, n_2 \\end{cases}$$\n where $\\color{blue} n_1$ and $\\color{blue} n_2$ are the multiplicative orders of $\\color{blue} G$ modulo $\\color{blue} P$ and $\\color{blue} Q$, respectively. To find these partial moduli, we can use the fact that:\n \n

\n"}︡ ︠b6203ee7-f0c3-4fba-ab1e-17f76b34db8c︠ power_mod(G,P-1,P) power_mod(G,Q-1,Q) ︡965df3c1-c00d-4a69-a534-ab9fd3fa636a︡{"stdout":"1\n"}︡{"stdout":"1\n"}︡ ︠76decf19-b15c-4e42-b694-e97663a8de24i︠ %html

which means that $\color{blue} n_1 \mid P-1$ and $\color{blue} n_2 \mid Q-1$ (a quite general fact, actually).

\n which means that $\\color{blue} n_1 \\mid P-1$ and $\\color{blue} n_2 \\mid Q-1$ (a quite general fact, actually).\n

\n"}︡ ︠08914836-4e78-4ad2-8bd2-0d0c23c05364︠ factor(P-1) factor(Q-1) ︡e50f0e8a-60ad-4a4b-a6ed-6abf8921e9ce︡{"stdout":"2 * 3 * 88321\n"}︡{"stdout":"2 * 11 * 73 * 1201\n"}︡ ︠2b6b4454-a658-4629-9803-fd13e07ee2d4i︠ %html

This does not leave a lot of possibilities for $\color{blue} n_1$ and $\color{blue} n_2$ ...

︡573887f8-9f8c-467d-be5f-1a863b62fe7a︡{"html":"

\n This does not leave a lot of possibilities for $\\color{blue} n_1$ and $\\color{blue} n_2$ ...\n

\n"}︡ ︠0c5f72f5-047e-4e0c-9234-e3a485f9d50d︠ power_mod(G, 3*88321, P) # not 1, thus n1 must contain 2 as a factor power_mod(G, 2*88321, P) # not 1, thus n1 must contain 3 as a factor power_mod(G, 2*3, P) # not 1, thus n1 must contain 88321 as a factor ︡cf316ec1-d998-446f-82b8-9db4d0a2caf3︡{"stdout":"529926\n"}︡{"stdout":"98452\n"}︡{"stdout":"489330\n"}︡ ︠e24d5511-317c-4326-aca7-be2faa3b1a20︠ n1 = 2*3*88321 # = P-1 ︡e50ff133-1acb-4d1a-90ff-0600749c320a︡ ︠30df4211-624a-44fa-95f9-f28860b2578di︠ %html

Likewise, we find that the multiplicative order of $\color{blue} G$ modulo $\color{blue} Q$ is the full $\color{blue} Q-1$:

︡d1cb52db-e7fa-46fc-81f8-2bcb6de5e1e2︡{"html":"

\n Likewise, we find that the multiplicative order of $\\color{blue} G$ modulo $\\color{blue} Q$ is the full $\\color{blue} Q-1$:\n

\n"}︡ ︠cb0bcc2d-85fd-4fc5-9dfb-fffd385ea372︠ power_mod(G, 11*73*1201, Q) # not 1 power_mod(G, 2*73*1201, Q) # not 1 power_mod(G, 2*11*1201, Q) # not 1 power_mod(G, 11*73*1201, Q) # not 1 ︡bcc6f680-b7bf-4fe6-9a45-a31771d734ad︡{"stdout":"1928806\n"}︡{"stdout":"1389790\n"}︡{"stdout":"842278\n"}︡{"stdout":"1928806\n"}︡ ︠8c02e279-5bbc-40dd-bdde-ee8a04b40cc7︠ n2 = 2*11*73*1201 # = Q-1 ︡d1905f6b-235e-42f0-a3b6-80a09ce0cf9c︡ ︠df0934dd-1a9e-4950-a034-d3da71a23ea2i︠ %html

Now we know that $\color{blue} x \equiv x_1 \, \mathrm{mod} \, n_1$, so that we can write $$\color{blue} x = x_1 + k n_1$$ for some integer $\color{blue} k$. If we look at this modulo $\color{blue} n_2$, we get $$\color{blue} x_2 \equiv x_1 + k n_1 \, \mathrm{mod} \, n_2$$ that we can now solve for $\color{blue} k$: $$\color{blue} k n_1 \equiv x_2 - x_1 \, \mathrm{mod} \, n_2.$$ In this equation, we can divide both sides by $\color{blue} n_1$ (i.e. multiply by its modular inverse) – provided $\color{blue} n_1$ and $\color{blue} n_2$ share no common factor.

︡5d4e3fba-ffea-4cbc-b231-c3b37d7733e8︡{"html":"

\n Now we know that $\\color{blue} x \\equiv x_1 \\, \\mathrm{mod} \\, n_1$, so that we can write\n $$\\color{blue} x = x_1 + k n_1$$\n for some integer $\\color{blue} k$. If we look at this modulo $\\color{blue} n_2$, we get\n $$\\color{blue} x_2 \\equiv x_1 + k n_1 \\, \\mathrm{mod} \\, n_2$$\n that we can now solve for $\\color{blue} k$:\n $$\\color{blue} k n_1 \\equiv x_2 - x_1 \\, \\mathrm{mod} \\, n_2.$$\n In this equation, we can divide both sides by $\\color{blue} n_1$ (i.e. multiply by its modular inverse) – provided $\\color{blue} n_1$ and $\\color{blue} n_2$ share no common factor.\n

\n"}︡ ︠f70db168-ec31-4ba4-bfeb-75792bbfefaa︠ gcd(n1,n2) ︡c7033286-4af8-406d-abc9-560d924a49c6︡{"stdout":"2\n"}︡ ︠f3c35bc5-95da-498f-90f9-9f1c703717c9i︠ %html

But that's not so bad, we can just divide everything by this common factor:

︡e3ae37b3-4917-4402-94a4-acf857b494c3︡{"html":"

\n But that's not so bad, we can just divide everything by this common factor:\n

\n"}︡ ︠d0aeef6b-39ae-4e9e-8724-71085cc9b77b︠ new_n2 = n2 // 2 k = (x2 - x1) / n1 % new_n2 x = x1 + k*n1 x ︡6b4c3b09-a051-46ba-8e04-694af502552f︡{"stdout":"218752856473\n"}︡ ︠0f4cfd0e-11e6-41a2-a88e-3397edf2c63ci︠ %html

It's always good practice to check the result of such an involved computation...

︡09560cfa-298e-4845-aea8-f6607d5f71f8︡{"html":"

\n It's always good practice to check the result of such an involved computation...\n

\n"}︡ ︠413d83c0-50bd-485c-a0da-e441539471f2︠ power_mod(G,x,N) == X % N # ok ︡1353761a-aba4-431d-b2de-81dfced755f2︡{"stdout":"True\n"}︡ ︠328c77f7-9b92-44ec-b47e-971c6501836ai︠ %html

## B) Unsafe parameters, pt. 2

Here is a longer ($\sim$1024 bits) value of $N$ that you should be able to check is prime: ︡cc49bd24-08fd-4b65-83a7-7dc1de20d514︡{"html":"

## B) Unsafe parameters, pt. 2

\nHere is a longer ($\\sim$1024 bits) value of $N$ that you should be able to check is prime:\n"}︡ ︠7e26e830-cddd-4d65-8334-d3761c610dab︠ N = 86844601646560649868094780637332571503839120989191389269065169705359529135507092608792297857681019063810457277558548188728448528090938077246313944755804265972112533180280793723654638832666055107643129445984139660495794107937484688106653612228250521072796597423574141928850698869992171537304337606425013930771 ︡a04da054-c7cb-4174-9baa-b2420fdbf61e︡ ︠116268fb-56ca-4d5c-8ab1-a075fffcc197︠ is_prime(N) # ok ︡f4b31e78-a3cc-42f8-8f92-7b936fde0667︡{"stdout":"True"}︡{"stdout":"\n"}︡ ︠6ab4ed72-9890-4fdf-8c1b-18fc57812320i︠ %html and here is the value of $G$ we will use: ︡3cb73a43-80b1-4b64-9737-1897a6ee2a05︡{"html":"and here is the value of $G$ we will use:\n"}︡ ︠53ba398f-833d-4bd8-9182-da868b8a4649︠ G = 72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516 ︡8d3e25c7-7136-431c-a53c-d7329dd19356︡ ︠68ef36c9-7e81-45af-bf8c-1f2715e79eadi︠ %html Despite the appearances, computing discrete logarithms in base $G$ is trivially easy. Convince yourself of this by looking at the first few powers of $G$ to see if you spot a pattern. ︡50000566-26d2-45b9-ad1d-b2aaf5dcb493︡{"html":"Despite the appearances, computing discrete logarithms in base $G$ is trivially easy. Convince yourself of this by looking at the first few powers of $G$ to see if you spot a pattern.\n"}︡ ︠23908ab1-bc4b-4ddb-9718-58a88486fc46︠ for i in range(15): print G^i % N ︡a2950910-87cd-4727-8c14-24742fa84a0f︡{"stdout":"1\n72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516\n30978188113933032097705976763584690888891625000262698971100774215075871921346747773052637946388591088929353943898139432449661944559882395938514731723800214221965524503085583258007513007168611416996973800804982658883438298257950442973139237729942158763520193358951590970984237665362412128117726948688262309775\n24943934366841441793430838795721024377802145130019814054663154529660257665733003659051620501959131153988486191133610934541929483468263682395086207530218551344623202656026041655066343213569626185416024063422106612314543376545676525703533741714636488268627953991537944104596112367953574144362439069155892493721\n45196391790847049710191124116582937624731939382376629082952603764308470580924194338897928984924024626560487036855340820813335006391167969069306104065245661755881699781777362880060398064415636162171287761982760549283677416466230884731466419571139464293871996694967920680308815835507576745652170640882480213529\n1\n72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516\n30978188113933032097705976763584690888891625000262698971100774215075871921346747773052637946388591088929353943898139432449661944559882395938514731723800214221965524503085583258007513007168611416996973800804982658883438298257950442973139237729942158763520193358951590970984237665362412128117726948688262309775\n24943934366841441793430838795721024377802145130019814054663154529660257665733003659051620501959131153988486191133610934541929483468263682395086207530218551344623202656026041655066343213569626185416024063422106612314543376545676525703533741714636488268627953991537944104596112367953574144362439069155892493721\n45196391790847049710191124116582937624731939382376629082952603764308470580924194338897928984924024626560487036855340820813335006391167969069306104065245661755881699781777362880060398064415636162171287761982760549283677416466230884731466419571139464293871996694967920680308815835507576745652170640882480213529\n1\n72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516\n30978188113933032097705976763584690888891625000262698971100774215075871921346747773052637946388591088929353943898139432449661944559882395938514731723800214221965524503085583258007513007168611416996973800804982658883438298257950442973139237729942158763520193358951590970984237665362412128117726948688262309775\n24943934366841441793430838795721024377802145130019814054663154529660257665733003659051620501959131153988486191133610934541929483468263682395086207530218551344623202656026041655066343213569626185416024063422106612314543376545676525703533741714636488268627953991537944104596112367953574144362439069155892493721\n45196391790847049710191124116582937624731939382376629082952603764308470580924194338897928984924024626560487036855340820813335006391167969069306104065245661755881699781777362880060398064415636162171287761982760549283677416466230884731466419571139464293871996694967920680308815835507576745652170640882480213529\n"}︡ ︠55294f4c-4f57-43c6-bb2f-1e478c0cd95fi︠ %html

The 1's should jump to the eye! What we observe is that $\color{blue} G^5 \equiv 1 \, \mathrm{mod} \, N$: in other words, the multiplicative order of $\color{blue} G$ modulo $\color{blue} N$ is 5. The space of exponents cannot possibly offer much more than 2 bits of security! Said differently: it is very easy to compute discrete logarithms with this $\color{blue} G$: given $\color{blue} X$, just find its position in the 5-element list above (repeated thrice).

︡4d662cb2-97a2-4ba4-b2d5-a7c5490f515e︡{"html":"

\n The 1's should jump to the eye! What we observe is that $\\color{blue} G^5 \\equiv 1 \\, \\mathrm{mod} \\, N$: in other words, the multiplicative order of $\\color{blue} G$ modulo $\\color{blue} N$ is 5. The space of exponents cannot possibly offer much more than 2 bits of security! Said differently: it is very easy to compute discrete logarithms with this $\\color{blue} G$: given $\\color{blue} X$, just find its position in the 5-element list above (repeated thrice).\n

\n"}︡ ︠aed3a238-3eee-4e4b-b278-bc2567b27eafi︠ %html What does this tell us about $N$ ? (or rather, $N-1$) ︡88dc051f-2fca-4246-925c-d47e8f6d8c0d︡{"html":"What does this tell us about $N$ ? (or rather, $N-1$)\n"}︡ ︠f59f63fb-0062-411f-a8fb-4c94102a7ab4i︠ %html

Well, since $\color{blue} G$ is of multiplicative order $\color{blue} 5$ and we know that this multiplicative order must divide $\color{blue} \varphi(N) = N-1$ (because $\color{blue} N$ is prime), we can say for sure that $\color{blue} 5 \mid N-1$, i.e. $\color{blue} N$ is of the form $\color{blue} 5 k + 1$. We really cannot say much more than that without further information. In particular, the fact that one base mod $\color{blue}N$ is unsuitable for cryptography does not mean that it is the case for all bases mod $\color{blue} N$.

︡1becf180-5d8d-4be6-ab4f-7d120c21870f︡{"html":"

\n Well, since $\\color{blue} G$ is of multiplicative order $\\color{blue} 5$ and we know that this multiplicative order must divide $\\color{blue} \\varphi(N) = N-1$ (because $\\color{blue} N$ is prime), we can say for sure that $\\color{blue} 5 \\mid N-1$, i.e. $\\color{blue} N$ is of the form $\\color{blue} 5 k + 1$. We really cannot say much more than that without further information. In particular, the fact that one base mod $\\color{blue}N$ is unsuitable for cryptography does not mean that it is the case for all bases mod $\\color{blue} N$.\n

\n"}︡ ︠4fcd77d5-91a2-4ea3-8996-289fc5a917c9i︠ %html

## C) Diffie-Hellman

Let's now start doing things properly and help Alice and Bob set up a secure shared secret. First:

• Generate 1024-bit primes $Q$ until you find one for which $N = 2Q+1$ is prime (how long did it take?)
• Choose a random base $G$ smaller than $N$
and then play out the process of using the Diffie-Hellman key exchange protocol to set up a shared secret between Alice and Bob. ︡66b6728b-a7e5-4124-8d7d-249b8e56b14e︡{"html":"

## C) Diffie-Hellman

\n

Let's now start doing things properly and help Alice and Bob set up a secure shared secret. First:

\n
\n
• Generate 1024-bit primes $Q$ until you find one for which $N = 2Q+1$ is prime (how long did it take?)
• \n
• Choose a random base $G$ smaller than $N$
• \n
\nand then play out the process of using the Diffie-Hellman key exchange protocol to set up a shared secret between Alice and Bob.\n"}︡ ︠367fb1bd-ffbc-4b7c-8f1e-8a184434b831i︠ %html

Generating parameters can take a while (depending on your luck)... the good news is that we can safely reuse them so this is not the kind of operation that need to be performed very often in practice.

︡4f75313e-3d9f-4942-bcb2-eb0603fe9363︡{"html":"

\n Generating parameters can take a while (depending on your luck)... the good news is that we can safely reuse them so this is not the kind of operation that need to be performed very often in practice.\n

\n"}︡ ︠9e29d305-787f-4256-af04-a956ad9e7197︠ %time l = 1024 found = false ctr = 0 while not found: Q = random_prime(2^l) ctr += 1 found = is_prime(2*Q + 1) N = 2*Q + 1 print "Suitable pair found after %s trials" % ctr print "Sophie Germain prime Q = %s" % Q print "Safe prime N = %s" % N ︡bd764436-ad7f-4dcd-972c-80eb81511fb2︡{"stdout":"Suitable pair found after 42 trials\n"}︡{"stdout":"Sophie Germain prime Q = 32462709730125202688464487430992373352250571328760684568070268760073306708695518389114579622379075864541317340636095998586950984084171601078351476621622682402164732967719344143404046548346726005212251222489619775381609688036104556725018732382034907808179470577291286421127574017531182385098220963467348783159\n"}︡{"stdout":"Safe prime N = 64925419460250405376928974861984746704501142657521369136140537520146613417391036778229159244758151729082634681272191997173901968168343202156702953243245364804329465935438688286808093096693452010424502444979239550763219376072209113450037464764069815616358941154582572842255148035062364770196441926934697566319\n"}︡{"stdout":"CPU time: 203.51 s, Wall time: 204.55 s\n"}︡ ︠1fd01019-1377-43d0-ad99-fee446600175i︠ %html

The multiplicative group mod $\color{N}$ is a cyclic group of order $\color{blue} N - 1 = 2 Q$, which can be seen as a direct product of a cyclic group of order 2 and a cyclic group of prime order $\color{blue} Q$. Consequently: almost all (only 2 exceptions!) elements have multiplicative order $\color{blue} Q$ or $\color{blue} 2 Q$ (in the second case, taking the square of the element would be an element of exact order $\color{blue} Q$, if needed).

︡402c80ef-b515-40de-b67d-99ef524d6487︡{"html":"

\n The multiplicative group mod $\\color{N}$ is a cyclic group of order $\\color{blue} N - 1 = 2 Q$, which can be seen as a direct product of a cyclic group of order 2 and a cyclic group of prime order $\\color{blue} Q$. Consequently: almost all (only 2 exceptions!) elements have multiplicative order $\\color{blue} Q$ or $\\color{blue} 2 Q$ (in the second case, taking the square of the element would be an element of exact order $\\color{blue} Q$, if needed).\n

\n"}︡ ︠95d51b33-d905-4974-9970-ef8dc7a34ea2︠ G = ZZ.random_element(N) power_mod(G,Q,N) == 1 # (slightly less than) 50% of the time power_mod(G^2,Q,N) == 1 # (slightly less than) 100% of the time ︡53822eaf-957b-4351-b9f0-9ccc35175a67︡{"stdout":"True\n"}︡{"stdout":"True\n"}︡ ︠8f1b396c-278e-41d2-8e39-b95f501be595i︠ %html

Now for the Diffie-Hellman key agreement protocol: first Alice chooses a random exponent and computes the corresponding power, to be sent to Bob.

︡cca5f743-3dab-4e85-a1b6-632eb875f925︡{"html":"

\n Now for the Diffie-Hellman key agreement protocol: first Alice chooses a random exponent and computes the corresponding power, to be sent to Bob.\n

\n"}︡ ︠28735ad3-c6b6-47f3-b7d6-6b4392a2b67e︠ a = ZZ.random_element(Q) A = power_mod(G,a,N) ︡ced78bd3-bf6e-4ef2-aa2f-164d7f957a5f︡ ︠45254a8b-9ec1-45a1-9a80-a6da8947403ei︠ %html

Bob does the same thing on his side:

︡86baf600-57f5-42ab-9416-17ea92f43e2c︡{"html":"

Bob does the same thing on his side:

\n"}︡ ︠0ff27938-7f58-4d69-8153-b937554796e1︠ b = ZZ.random_element(Q) B = power_mod(G,b,N) ︡ff6c2b96-ee04-4131-9780-f656fb559423︡ ︠b9edbdf1-5cd5-412b-bdbe-b35009c27b1di︠ %html

Now Alice, knowing $\color{blue} a$ and $\color{blue} B$, can compute her version of the shared secret:

︡df91b873-7d96-4129-b09b-61baee57c1fb︡{"html":"

\n Now Alice, knowing $\\color{blue} a$ and $\\color{blue} B$, can compute her version of the shared secret:\n

\n"}︡ ︠1dc6fcaa-2b51-4686-be73-6d5deb8282f6︠ Ka = power_mod(B,a,N) ︡568e1267-9bcf-455a-bdf2-ab80d2eb8125︡ ︠2d1d84c0-654a-4106-a06f-4428c40a539ci︠ %html

Bob does the same thing using $\color{blue} b$ and $\color{blue} A$:

\n Bob does the same thing using $\\color{blue} b$ and $\\color{blue} A$:\n

\n"}︡ ︠ec3d0ee8-2b5f-447d-907a-1de8dec87b02︠ Kb = power_mod(A,b,N) ︡987cfbbf-4e58-43e3-9bb6-c7b591e3d2f7︡ ︠31cebe49-0a3e-4408-8f54-0bed23cadf8ci︠ %html

We can check that Alice and Bob do indeed share a common secret (protected by the hardness of the base $\color{blue} G$ DLP):

\n We can check that Alice and Bob do indeed share a common secret (protected by the hardness of the base $\\color{blue} G$ DLP):\n

\n"}︡ ︠14ac9c4f-7911-4cc0-b501-df08072ae309︠ Ka == Kb ︡93292e1b-d776-4aaa-b43c-6864908e773c︡{"stdout":"True\n"}︡ ︠e8689217-c50e-4e05-8d9c-4ce939ba8815i︠ %html

## D) Elliptic curve cryptography

I just received an ElGamal-encrypted message from Andrew. The ciphertext consists of two points ︡8c015293-89e1-4fb8-bbfb-694acc56cbe4︡{"html":"

## D) Elliptic curve cryptography

\nI just received an ElGamal-encrypted message from Andrew. The ciphertext consists of two points\n"}︡ ︠8ef0c907-522c-4a2c-b8fe-c871af5e7b74︠ S = [ 3620473699543156961298497229210520148015536443909434883182, 994581666656960301654202765055841298058574984469318819073 ] C = [ 1521903924796855994281801748988284243893191060475042510545, 4240686587300906118564763592646816031574164277809413619093 ] ︡a960e27b-3f7f-4631-85c9-fc9bdc5c3429︡ ︠ad112701-d19e-40f9-a3ed-eaca1dee6b3bi︠ %html that belong to the elliptic curve known as brainpoolP192r1. Decrypt it with my private key ︡0f132cef-adf6-4cb0-af6d-6afe860d8a72︡{"html":"that belong to the elliptic curve known as brainpoolP192r1. Decrypt it with my private key\n"}︡ ︠aa428f6c-bec1-41c5-9c14-45eeb04ec4ab︠ d = 776181986755824308692925852253930933797019417318777412964 ︡be58ead7-7765-48f1-96f0-048bfbab32b0︡ ︠db56eaab-8c8e-4446-9f8a-7c4d09384eabi︠ %html to see what he has to say about all this (the original message is the x-coordinate of the resulting point, interpreted as a base-256 string). ︡2ef9cc5e-f0b4-4056-8e7f-7d266533840f︡{"html":"to see what he has to say about all this (the original message is the x-coordinate of the resulting point, interpreted as a base-256 string).\n"}︡ ︠7274c2d6-01bd-4674-83c1-06ef4319eac4i︠ %html

We first import from the document the parameters that define the elliptic curve $\color{blue} E$ and the base point $\color{blue} G$:

︡bf4d7480-5a4e-48a3-a3e7-7b2675451d48︡{"html":"

\n We first import from the document the parameters that define the elliptic curve $\\color{blue} E$ and the base point $\\color{blue} G$:\n

\n"}︡ ︠dd09b5bd-879b-4e0a-b8e3-531bd13145ee︠ p = 0xC302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297 A = 0x6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF B = 0x469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9 x = 0xC0A0647EAAB6A48753B033C56CB0F0900A2F5C4853375FD6 y = 0x14B690866ABD5BB88B5F4828C1490002E6773FA2FA299B8F q = 0xC302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1 ︡97dfef69-413b-4e8c-8843-852e8487fde9︡ ︠b2030a3a-f391-43c0-9f7a-10d39048020e︠ F = GF(p) E = EllipticCurve(F, [A,B]) G = E([x,y]) ︡1b7a1f5b-5ba3-4a5c-9748-46d073331407︡ ︠5c9e5c69-1686-4cf0-a19e-b4885d646e7ei︠ %html

We may check that $\color{blue} G$ is indeed a point of prime (additive) order $\color{blue} q$ on $\color{blue} E$:

︡2daac8bf-0980-48d0-9133-4b0daf8235c2︡{"html":"

\n We may check that $\\color{blue} G$ is indeed a point of prime (additive) order $\\color{blue} q$ on $\\color{blue} E$:\n

\n"}︡ ︠095f8ab3-768c-4a14-9524-6e7d4d795370︠ q*G # point at infinity ︡d68932fe-2c5c-4a72-a813-60aead320454︡{"stdout":"(0 : 1 : 0)\n"}︡ ︠e95a9182-62ff-4332-812e-6ca07eafab18i︠ %html

Now let's consider the signature as a couple of points on $\color{blue} E$ and proceed to the actual decryption:

︡31e7cb85-f011-4e38-80b6-1af655234aae︡{"html":"

\n Now let's consider the signature as a couple of points on $\\color{blue} E$ and proceed to the actual decryption:\n

\n"}︡ ︠c966d1fc-26be-4c29-a905-5b16abf3d6aa︠ S = E(S) C = E(C) K = d * S # shared secret M = C - K ︡9877e371-0488-4032-9c7a-92974e879e21︡ ︠309253bd-0f37-41b8-ae78-c66b47087233︠ import base64 base64.b16decode(hex(ZZ(M)).upper()) ︡eaf1c5b5-0ba7-420c-9700-659dd39d46d8︡{"stdout":"'Elliptic curves rock!'\n"}︡ ︠164d8402-c480-4189-8d73-996c9df83875i︠ %html

Indeed!

︡eba852c7-dfb6-46dc-b2ee-744a8ce71925︡{"html":"

\n Indeed!\n

\n"}︡ ︠e9dce584-6dea-4b1a-8a5c-aedc806b8c20︠