CoCalc Shared Files5 - Discrete logarithms (prof) / Discrete logarithms (prof).sagews
Author: Gabriel Chênevert
Views : 158

# 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: $\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?
G = 343857231343
X = 146812954167



power_mod(G,x,N) == X

True


x = 218752856473

%time

x = 0 # exponent
L = 1 # left-hand side

found = false

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 $\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

8 * 2^20 / 60 / 60 / 24 / 30.4  # in *months*...

3.19376218323587
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$:
factor(N)

529927 * 1928807
P = 529927
Q = 1928807


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

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$):

%time

x1 = 0
X1 = X % P
L = 1

found = false

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 $\color{blue} Q$:

%time

x2 = 0
X2 = X % Q
L = 1

found = false

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 $\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:

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

1 1

which means that $\color{blue} n_1 \mid P-1$ and $\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 $\color{blue} n_1$ and $\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 $\color{blue} G$ modulo $\color{blue} Q$ is the full $\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 $\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.

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 ($\sim$1024 bits) value of $N$ that you should be able to check is prime:
N = 86844601646560649868094780637332571503839120989191389269065169705359529135507092608792297857681019063810457277558548188728448528090938077246313944755804265972112533180280793723654638832666055107643129445984139660495794107937484688106653612228250521072796597423574141928850698869992171537304337606425013930771

is_prime(N)  # ok

True
and here is the value of $G$ we will use:
G = 72570689021499776134861621598776490116252532465723636429413806901674458103010239446582408282090291258142587383230005189651970621762562107089720846192344104621754639419672599654175023380178236450701973265758429500509929124605111522805167825440782930819573050801690828101812231871160780056476338554123392844516

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

What does this tell us about $N$ ? (or rather, $N-1$)

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

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

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

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

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 $\color{blue} a$ and $\color{blue} B$, can compute her version of the shared secret:

Ka = power_mod(B,a,N)


Bob does the same thing using $\color{blue} b$ and $\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 $\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 $\color{blue} E$ and the base point $\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 $\color{blue} G$ is indeed a point of prime (additive) order $\color{blue} q$ on $\color{blue} E$:

q*G  # point at infinity

(0 : 1 : 0)

Now let's consider the signature as a couple of points on $\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!