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 mod p (Targed) and the prime P. If successful this attack will return the private key x
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.
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.
Step 2. We use the Chinese Remainder Theorem (CRT) to construct the private key using the numbers in the previous cell
The private key x= 20429562873037177427780818788284697397051553295717758278242318827974973559126503
6
41054398887059433371371700431713125794349681710867297304558452883444515434344919
We will show how using the key constructed the attack fails to recover the key.
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 using the HPS attack to find the private key .
106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363
10038748923785
76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656
The HPS attack is successful and the private key x= 1796657865499665589744957847497847499746578947785487659498477484379447758589665971487751806
2 * 59 * 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 .
(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 .
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