Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 999
Image: ubuntu2004

Hellman Pohlig Silver (HPS) Attack Method For Solving DLP

Description. This attack takes advantage of the factorization of (P-1) when (P-1) is smooth (contains only small prime factors). The SAGE function for this attack 'HPSonP' takes three inputs: primitive root g (Generator), the publuc value b=gxb=g^x mod p (Targed) and the prime P. If successful this attack will return the private key x

import itertools def HPSonP (Generator, Target, P): Unknown = 0 N = P - 1 K = factor(N) K = list(K) #print K for pk in K: #print pk primes =pk[0] #Maple code to convert #primes = op(1, op(1, op(i, K))) #if len(K[i]) == 1: #if len(op(i, K)) == 1: # powers = 1 #else: # powers = op(2, op(i, K)) powers = pk[1] Z = N / primes chi = power_mod(int(Generator), int(Z),int(P)) n = 0 t = [0]*powers a = [0]*powers d = [0]*powers for j in range(0, powers): #print j if j == 0: a[j - 1] = Target else: Z2 = (d[j - 1 - 1] * power_mod(int(primes),int(j - 1),int(N))) % N Pt = power_mod(int(Generator), int(Z2),int(P))# % P a[j-1] = (a[j - 1 - 1] / Pt) % P y = Z / primes ** j t[j-1] = power_mod(int(a[j - 1]),int(y),int(P))# % P s = 1 for k in itertools.count(): #print "k",k if t[j - 1] == s: d[j - 1] = k break s = (s * chi) % P n = (n + d[j - 1] * primes ** j) % N NN = N / primes ** powers X = (1 / NN) % primes ** powers Unknown = (Unknown + NN * n * X) % N #unassign(t) return(Unknown) def Dirichlet (q): j=0 #for j in numpy.arange(0.10e1, infinity + 0.10e1, 0.10e1): while True: j+=1 p = 2 * j * q + 1 if is_prime(p) == True: return(p) def findLargePrimitiveRoot(n,p): n=n+1 eulerp = euler_phi(p) Q = list(factor(eulerp)) while n<p: found = True for Q2 in Q: q=Q2[0] totest = power_mod(ZZ(n),ZZ(eulerp/q),ZZ(p)) # print(totest) if totest==1: found = False if found: return n n+=1

Example 1. We show a construction of a key resistant to the HPS attack. We construct the prime p using the 'Dirichlet' procedure so that (P-1) has at least one large prime factor. We then construct our private key x using the Chinese Remainder Theorem (CRT) so that x modulo the large prime factor is large.

q=next_prime(283743928792183019830289149837287463847938240218302198308921094832985743875834); p=Dirichlet(q); print("The prime p chosen is:", p) print("Prime Factorization of (p-1) = ",factor(p-1))
The prime p chosen is: 42561589318827452974543372475593119577190736032745329746338164224947861581513551 Prime Factorization of (p-1) = 2 * 3 * 5^2 * 283743928792183019830289149837287463847938240218302198308921094832985743876757

Step 1. We construct 4 random numbers for the residues of the factors of (P-1). For c4 we make sure that the random number coresponding to the large prime factor q of (p-1) to be large.

c1=1 c2=2 c3=3 c4=q-1

Step 2. We use the Chinese Remainder Theorem (CRT) to construct the private key using the numbers in the previous cell

x=crt([c1,c2,c3,c4],[2,3,25,q]) print("The private key x=",x) g=primitive_root(p); g b=power_mod(g,x,p) b
The private key x= 20429562873037177427780818788284697397051553295717758278242318827974973559126503 6 41054398887059433371371700431713125794349681710867297304558452883444515434344919

We will show how using the key constructed the attack fails to recover the key.

HPSonP(g,b,p)
Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python3.9/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> File "", line 29, in HPSonP File "src/cysignals/signals.pyx", line 320, in cysignals.signals.python_check_interrupt KeyboardInterrupt

Example 2. This example indicates a choice of weak keys against the HPS attack. Let p=106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363, g=10038748923785, b=76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656. We need to solve the DLP b=gxb=g^x using the HPS attack to find the private key xx.

p1=106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363 p1 g1=10038748923785 g1 b1=76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656 b1 x1=HPSonP(g1,b1,p1) print("The HPS attack is successful and the private key x="",x1)
106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363 10038748923785 76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656 The HPS attack is successful and the private key x= 1796657865499665589744957847497847499746578947785487659498477484379447758589665971487751806
factor(p1-1)
2 * 59 * 898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859
x %2; x %59; x %898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859
1 9 20429562873037177427780818788284697397051553295717758278242318827974973559126503

Example 3. This is another example for generating a key resitant to HPS attack. In this example we use the command list(factor()) to find the factors of p1p-1.

q1 = next_prime(37493278489327498732487398498393879480898493287489732974921094832985743875834) p1 = Dirichlet(q1) fL1=list(factor(p1-1)) for test in fL1: print (test) c11 = 1 c21 = 100 c31 = 374932784893274987324873984983938794808984932874897329749210948329857438758 x2 = crt([c11,c21,c31],[fL1[0][0],fL1[1][0],fL1[2][0]]) print("The private key x=",x2) g1=findLargePrimitiveRoot(10038748923784,p1) g1 b1 = power_mod(g1,x1,p1) b1
(2, 1) (113, 1) (37493278489327498732487398498393879480898493287489732974921094832985743875881, 1) The private key x= 8061429807990305502472115551139668027187985041743167486937784600040264790753173 10038748923786 6156089434541705029559508896034912822846473392122022710870417979600647684748946

Example 4. This is another example for generating a key resitant to HPS attack. In this example we use the procedure findLargePrimitiveRoot() to find the large primitive root of p1p-1.

q2 = next_prime(89324793827492374982748732402938332894798230912830912921094832985743875834) p2 = Dirichlet(q2) fL2=list(factor(p2-1)) c12 = 1 c22 = 30 c32 = 8932479382749237498274873240293833289479823091283091292109483298574387616 x3 = crt([c12,c22,c32],[fL2[0][0],fL2[1][0],fL2[2][0]]) print("The private key x=",x3) g2=findLargePrimitiveRoot(10038748923784,p2) g2 b2 = power_mod(g2,x3,p2) b2 print("We show that this private key is resistant against HPS") HPSonP(g2,b2,p2)
The private key x= 5100445727549814611514952620207778808292978985122645127794514963485975329249 10038748923785 946731983399710512555195230311934479072009381576909000168330179607867912495 We show that this private key is resistant against HPS
Error in lines 14-14 Traceback (most recent call last): File "/cocalc/lib/python3.9/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> File "", line 29, in HPSonP File "src/cysignals/signals.pyx", line 320, in cysignals.signals.python_check_interrupt KeyboardInterrupt