Shared5 - Discrete logarithms (prof) / Discrete logarithms (prof).sagewsOpen in CoCalc
Author: Gabriel Chênevert
Views : 98

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.
N = 1022126907089
Suppose we want to solve the following instance of the DLP: find x such that 343857231343x146812954167 mod N. \text{find } x \text{ such that } 343857231343^x \equiv 146812954167 \ \mathrm{mod} \ N. Start doing a brute force search for xx (up to, say, 2202^{20}) to see how fast it goes. How long do you think it would take you to find xx this way?
G = 343857231343 X = 146812954167
power_mod(G,x,N) == X
True
x = 218752856473
%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
logarithm found: False CPU time: 7.81 s, Wall time: 8.03 s

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

8 * 2^20 / 60 / 60 / 24 / 30.4 # in *months*...
3.19376218323587
The situation is actually much better for the attacker (you) since NN was foolishly chosen to be a composite number; Sage has no trouble finding its factors N=PQN = P \cdot Q:
factor(N)
529927 * 1928807
P = 529927 Q = 1928807

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

  • solving the DLP (by brute force if you want) first modulo PP, and QQ;
  • then use the Chinese Remainder Theorem to recover the value of xx modulo the multiplicative order of GG mod NN.

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

%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
logarithm found: True x1 = 463525 CPU time: 3.25 s, Wall time: 3.25 s
power_mod(G,x1,P) == X % P # ok
True

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

%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
logarithm found: True x2 = 1181595 CPU time: 8.20 s, Wall time: 8.28 s
power_mod(G,x2,Q) == X % Q # ok
True

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

power_mod(G,P-1,P) power_mod(G,Q-1,Q)
1 1

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

factor(P-1) factor(Q-1)
2 * 3 * 88321 2 * 11 * 73 * 1201

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

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
529926 98452 489330
n1 = 2*3*88321 # = P-1

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

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
1928806 1389790 842278 1928806
n2 = 2*11*73*1201 # = Q-1

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

gcd(n1,n2)
2

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

new_n2 = n2 // 2 k = (x2 - x1) / n1 % new_n2 x = x1 + k*n1 x
218752856473

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

power_mod(G,x,N) == X % N # ok
True

B) Unsafe parameters, pt. 2

Here is a longer (\sim1024 bits) value of NN that you should be able to check is prime:
N = 86844601646560649868094780637332571503839120989191389269065169705359529135507092608792297857681019063810457277558548188728448528090938077246313944755804265972112533180280793723654638832666055107643129445984139660495794107937484688106653612228250521072796597423574141928850698869992171537304337606425013930771
is_prime(N) # ok
True
and here is the value of GG we will use:
G = 72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516
Despite the appearances, computing discrete logarithms in base GG is trivially easy. Convince yourself of this by looking at the first few powers of GG to see if you spot a pattern.
for i in range(15): print G^i % N
1 72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516 30978188113933032097705976763584690888891625000262698971100774215075871921346747773052637946388591088929353943898139432449661944559882395938514731723800214221965524503085583258007513007168611416996973800804982658883438298257950442973139237729942158763520193358951590970984237665362412128117726948688262309775 24943934366841441793430838795721024377802145130019814054663154529660257665733003659051620501959131153988486191133610934541929483468263682395086207530218551344623202656026041655066343213569626185416024063422106612314543376545676525703533741714636488268627953991537944104596112367953574144362439069155892493721 45196391790847049710191124116582937624731939382376629082952603764308470580924194338897928984924024626560487036855340820813335006391167969069306104065245661755881699781777362880060398064415636162171287761982760549283677416466230884731466419571139464293871996694967920680308815835507576745652170640882480213529 1 72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516 30978188113933032097705976763584690888891625000262698971100774215075871921346747773052637946388591088929353943898139432449661944559882395938514731723800214221965524503085583258007513007168611416996973800804982658883438298257950442973139237729942158763520193358951590970984237665362412128117726948688262309775 24943934366841441793430838795721024377802145130019814054663154529660257665733003659051620501959131153988486191133610934541929483468263682395086207530218551344623202656026041655066343213569626185416024063422106612314543376545676525703533741714636488268627953991537944104596112367953574144362439069155892493721 45196391790847049710191124116582937624731939382376629082952603764308470580924194338897928984924024626560487036855340820813335006391167969069306104065245661755881699781777362880060398064415636162171287761982760549283677416466230884731466419571139464293871996694967920680308815835507576745652170640882480213529 1 72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516 30978188113933032097705976763584690888891625000262698971100774215075871921346747773052637946388591088929353943898139432449661944559882395938514731723800214221965524503085583258007513007168611416996973800804982658883438298257950442973139237729942158763520193358951590970984237665362412128117726948688262309775 24943934366841441793430838795721024377802145130019814054663154529660257665733003659051620501959131153988486191133610934541929483468263682395086207530218551344623202656026041655066343213569626185416024063422106612314543376545676525703533741714636488268627953991537944104596112367953574144362439069155892493721 45196391790847049710191124116582937624731939382376629082952603764308470580924194338897928984924024626560487036855340820813335006391167969069306104065245661755881699781777362880060398064415636162171287761982760549283677416466230884731466419571139464293871996694967920680308815835507576745652170640882480213529

The 1's should jump to the eye! What we observe is that G51modN\color{blue} G^5 \equiv 1 \, \mathrm{mod} \, N: in other words, the multiplicative order of  G\color{blue} G modulo N\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 G\color{blue} G: given X\color{blue} X, just find its position in the 5-element list above (repeated thrice).

What does this tell us about NN ? (or rather, N1N-1)

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

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 QQ until you find one for which N=2Q+1N = 2Q+1 is prime (how long did it take?)
  • Choose a random base GG smaller than NN
and then play out the process of using the Diffie-Hellman key exchange protocol to set up a shared secret between Alice and Bob.

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.

%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
Suitable pair found after 42 trials Sophie Germain prime Q = 32462709730125202688464487430992373352250571328760684568070268760073306708695518389114579622379075864541317340636095998586950984084171601078351476621622682402164732967719344143404046548346726005212251222489619775381609688036104556725018732382034907808179470577291286421127574017531182385098220963467348783159 Safe prime N = 64925419460250405376928974861984746704501142657521369136140537520146613417391036778229159244758151729082634681272191997173901968168343202156702953243245364804329465935438688286808093096693452010424502444979239550763219376072209113450037464764069815616358941154582572842255148035062364770196441926934697566319 CPU time: 203.51 s, Wall time: 204.55 s

The multiplicative group mod \color{N} is a cyclic group of order N1=2Q\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 Q\color{blue} Q. Consequently: almost all (only 2 exceptions!) elements have multiplicative order Q\color{blue} Q or 2Q\color{blue} 2 Q (in the second case, taking the square of the element would be an element of exact order Q\color{blue} Q, if needed).

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
True True

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

a = ZZ.random_element(Q) A = power_mod(G,a,N)

Bob does the same thing on his side:

b = ZZ.random_element(Q) B = power_mod(G,b,N)

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

Ka = power_mod(B,a,N)

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

Kb = power_mod(A,b,N)

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

Ka == Kb
True

D) Elliptic curve cryptography

I just received an ElGamal-encrypted message from Andrew. The ciphertext consists of two points
S = [ 3620473699543156961298497229210520148015536443909434883182, 994581666656960301654202765055841298058574984469318819073 ] C = [ 1521903924796855994281801748988284243893191060475042510545, 4240686587300906118564763592646816031574164277809413619093 ]
that belong to the elliptic curve known as brainpoolP192r1. Decrypt it with my private key
d = 776181986755824308692925852253930933797019417318777412964
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).

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

p = 0xC302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297 A = 0x6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF B = 0x469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9 x = 0xC0A0647EAAB6A48753B033C56CB0F0900A2F5C4853375FD6 y = 0x14B690866ABD5BB88B5F4828C1490002E6773FA2FA299B8F q = 0xC302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1
F = GF(p) E = EllipticCurve(F, [A,B]) G = E([x,y])

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

q*G # point at infinity
(0 : 1 : 0)

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

S = E(S) C = E(C) K = d * S # shared secret M = C - K
import base64 base64.b16decode(hex(ZZ(M[0])).upper())
'Elliptic curves rock!'

Indeed!