︠fa8d25c0-dc0b-41f8-b3e8-06465ed1330bi︠
%html
Hellman Pohlig Silver (HPS) Attack Method For Solving DLP
︡541ad392-6d5a-402c-8e6e-763ba99c12f4︡{"done":true,"html":"Hellman Pohlig Silver (HPS) Attack Method For Solving DLP
"}
︠eb4c0a7c-bba1-40d9-9720-547fe60e4616i︠
%md
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=g^x$ mod p (Targed) and the prime P. If successful this attack will return the private key x
︡806b471a-0099-4079-80cb-3b9aac946d01︡{"done":true,"md":"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=g^x$ mod p (Targed) and the prime P. If successful this attack will return the private key x"}
︠0814eeda-deb6-462b-ac0d-c9a45d8b89f2s︠
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 nExample 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.
︡feaac529-6aec-478f-81ce-e4f27a6f889a︡{"html":"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."}︡{"done":true}
︠0a4eaa66-bd98-4cf5-a650-fc4b922d101a︠
q=next_prime(283743928792183019830289149837287463847938240218302198308921094832985743875834);
p=Dirichlet(q);
print("The prime p chosen is:", p)
print("Prime Factorization of (p-1) = ",factor(p-1))
︡7acb10b8-eee1-4c1c-92dc-e7efece39284︡{"stdout":"The prime p chosen is: 42561589318827452974543372475593119577190736032745329746338164224947861581513551\n"}︡{"stdout":"Prime Factorization of (p-1) = 2 * 3 * 5^2 * 283743928792183019830289149837287463847938240218302198308921094832985743876757\n"}︡{"done":true}
︠46e57c33-7354-4fc7-8ef8-f319ccd6fae1i︠
%md
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.
︡275df21f-eda2-43a8-8f54-37bdcc18a8d8︡{"done":true,"md":"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."}
︠ccf8198b-99f3-44df-8a8c-64be15e86c14︠
c1=1
c2=2
c3=3
c4=q-1
︡ba2f8953-d5c6-41dd-8879-bcf3335780bc︡{"done":true}
︠571a9cc4-5aa9-4318-b1e4-9137498f8fb0i︠
%md
Step 2. We use the Chinese Remainder Theorem (CRT) to construct the private key using the numbers in the previous cell
︡108ce3f4-18c6-4a74-9142-4e80d1a8d643︡{"done":true,"md":"Step 2. We use the Chinese Remainder Theorem (CRT) to construct the private key using the numbers in the previous cell"}
︠9ac71e18-1f70-4dc1-953c-a5be0b166f87︠
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
︡1b2d5698-966d-400f-a7a1-b60d38038c19︡{"stdout":"The private key x= 20429562873037177427780818788284697397051553295717758278242318827974973559126503\n"}︡{"stdout":"6\n"}︡{"stdout":"41054398887059433371371700431713125794349681710867297304558452883444515434344919\n"}︡{"done":true}
︠8c8398bd-2d84-46c6-915a-96b6ddc24750i︠
%html
We will show how using the key constructed the attack fails to recover the key.
︡b4fb9ce4-670a-4594-a8f7-59e74e3bb2b5︡{"done":true,"html":"We will show how using the key constructed the attack fails to recover the key."}
︠1ec3c980-b4bd-45af-bca1-0fd93d646d12︠
HPSonP(g,b,p)
︡99f12d70-1592-4e88-8f04-20a231e72cbb︡{"stderr":"Error in lines 1-1\n"}︡{"stderr":"Traceback (most recent call last):\n File \"/cocalc/lib/python3.9/site-packages/smc_sagews/sage_server.py\", line 1230, in execute\n exec(\n File \"\", line 1, in \n File \"\", line 29, in HPSonP\n File \"src/cysignals/signals.pyx\", line 320, in cysignals.signals.python_check_interrupt\nKeyboardInterrupt\n"}︡{"done":true}
︠30db18b2-92b6-416c-b63f-c75c9853c832︠
︡76c33994-c06e-48a1-bf7d-8e9a41afb4e9︡
︠272fa4e5-98c4-44f3-b0e2-e12047b23bbbi︠
%html 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=g^x$ using the HPS attack to find the private key $x$.
︡329c89be-660e-40f7-90ce-9dcff15d6f20︡{"html":"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=g^x$ using the HPS attack to find the private key $x$."}︡{"done":true}
︠cb7d6521-4b15-4bdf-abb9-bb21e6b86e5a︠
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)
︡33d0e19e-97b7-475b-ac86-b34db5b95429︡{"stdout":"106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363\n"}︡{"stdout":"10038748923785\n"}︡{"stdout":"76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656\n"}︡{"stdout":"The HPS attack is successful and the private key x= 1796657865499665589744957847497847499746578947785487659498477484379447758589665971487751806\n"}︡{"done":true}
︠18b7cfd3-b249-4819-9548-d13dc57b62e9︠
factor(p1-1)
︡18b1df33-8670-4aff-855d-841bad84fd12︡{"stdout":"2 * 59 * 898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859\n"}︡{"done":true}
︠4e9ddc5b-b606-4ae8-a8c9-8982f6140d2b︠
x %2; x %59; x %898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859
︡c93ed35d-0e37-496d-99f3-c5c42af1af8a︡{"stdout":"1\n9\n20429562873037177427780818788284697397051553295717758278242318827974973559126503\n"}︡{"done":true}
︠258609d8-674e-4862-aab5-c3d5dd5e0b63i︠
%html
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 $p-1$.
︡920cc641-1b1d-42d9-a96f-222e801f3331︡{"done":true,"html":"Example 3. \nThis 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 $p-1$."}
︠90cb01f2-b35e-4e6b-8037-3e0e68e8289c︠
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
︡41eb992c-0463-4bcb-9553-433fc3e99063︡{"stdout":"(2, 1)\n(113, 1)\n(37493278489327498732487398498393879480898493287489732974921094832985743875881, 1)\n"}︡{"stdout":"The private key x= 8061429807990305502472115551139668027187985041743167486937784600040264790753173\n"}︡{"stdout":"10038748923786\n"}︡{"stdout":"6156089434541705029559508896034912822846473392122022710870417979600647684748946\n"}︡{"done":true}
︠74ba88f9-e862-4388-be35-9f425a42adefi︠
%html
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 $p-1$.
︡dd0b4917-245e-4f4b-b82b-1605d756b25e︡{"done":true,"html":"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 $p-1$."}
︠607c2325-3205-4446-b77a-4552847fffd3s︠
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)
︡481214fc-bc20-467b-9603-683d86a40b46︡{"stdout":"The private key x= 5100445727549814611514952620207778808292978985122645127794514963485975329249\n"}︡{"stdout":"10038748923785\n"}︡{"stdout":"946731983399710512555195230311934479072009381576909000168330179607867912495\n"}︡{"stdout":"We show that this private key is resistant against HPS\n"}︡{"stderr":"Error in lines 14-14\n"}︡{"stderr":"Traceback (most recent call last):\n File \"/cocalc/lib/python3.9/site-packages/smc_sagews/sage_server.py\", line 1230, in execute\n exec(\n File \"\", line 1, in \n File \"\", line 29, in HPSonP\n File \"src/cysignals/signals.pyx\", line 320, in cysignals.signals.python_check_interrupt\nKeyboardInterrupt\n"}︡{"done":true}
︠33450bee-43e0-40f9-a08a-0142d748d897︠