CoCalc Shared FilesHPSonP.sagews
Author: Liljana Babinkostova
Views : 194
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 xrange(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

#Constructing El Gamal key resistant against Hellman Pohlig Silver attack
#Choose a large prime number q
q=next_prime(283743928792183019830289149837287463847938240218302198308921094832985743875834);
#Use the Dirichlet procedure to find a prime number p such that (p-1) has q as one of its prime factors
p=Dirichlet(q);
p
factor(p-1);
#Choose random numbers c_i<q_i where g_i are the prime factors of (p-1). Note that all c_i can be small except one which is (q-1).
c1=1
c2=2
c3=3
c4=q-1
#Use the Chinese Remainder Theorem to generate the private key.
x=crt([c1,c2,c3,c4],[2,3,25,q])
x
#Choose primitive root modulu p
g=primitive_root(p);
g
#Compute g^x mod p.
b=power_mod(g,x,p)
b


42561589318827452974543372475593119577190736032745329746338164224947861581513551 2 * 3 * 5^2 * 283743928792183019830289149837287463847938240218302198308921094832985743876757 20429562873037177427780818788284697397051553295717758278242318827974973559126503 6 41054398887059433371371700431713125794349681710867297304558452883444515434344919
# Weak Key
p1=106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363
p1
g1=10038748923785
g1
b1=76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656
b1
z=HPSonP(g1,b1,p1)
z

106002814064480269794952513002373002485048157919343771910410171578387417756790292317777351363 10038748923785 76871742130979314778314404545706060673310122744275546975332059870805519009266628675037686656 1796657865499665589744957847497847499746578947785487659498477484379447758589665971487751807
factor(p1-1)

2 * 59 * 898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859
z %2; z %59; z %898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859

1 51 89

#Constructing a signature key that is resistant to the HPSonP attacks

q1 = next_prime(37493278489327498732487398498393879480898493287489732974921094832985743875834)
p1 = Dirichlet(q1)
fL1=list(factor(p1-1))
for test in fL1:
print test
c11 = 1
c21 = 100
c31 = 374932784893274987324873984983938794808984932874897329749210948329857438758
x1 = crt([c11,c21,c31],[fL1[0][0],fL1[1][0],fL1[2][0]])
x1
g1=findLargePrimitiveRoot(10038748923784,p1)
g1
b1 = power_mod(g1,x1,p1)
b1

(2, 1) (113, 1) (37493278489327498732487398498393879480898493287489732974921094832985743875881, 1) 8061429807990305502472115551139668027187985041743167486937784600040264790753173 10038748923786 6156089434541705029559508896034912822846473392122022710870417979600647684748946
q2 = next_prime(89324793827492374982748732402938332894798230912830912921094832985743875834)
p2 = Dirichlet(q2)
fL2=list(factor(p2-1))
c12 = 1
c22 = 30
c32 = 8932479382749237498274873240293833289479823091283091292109483298574387616
x2 = crt([c12,c22,c32],[fL2[0][0],fL2[1][0],fL2[2][0]])
x2
g2=findLargePrimitiveRoot(10038748923784,p2)
g2
b2 = power_mod(g2,x2,p2)
b2

5100445727549814611514952620207778808292978985122645127794514963485975329249 10038748923785 946731983399710512555195230311934479072009381576909000168330179607867912495

q3 = next_prime(898328932749832794872478923748923749873289473892743829749238742189723879294832985743875834)
p3 = Dirichlet(q3)
fL3=list(factor(p3-1))
c13 = 1
c23 = 50
c33 = 898328932749832794872478923748923749873289473892743829749238742189723879294832985743875859
x3 = crt([c13,c23,c33],[fL3[0][0],fL3[1][0],fL3[2][0]])
x3

67374669956237459615435919281169281240496710541955787231192905664229290947112473930790689425

B=11739085287969531650666764880307069646178466406133747
G=122
P=4559251933765135908042850372269050947311088678478407
P
G
B

4559251933765135908042850372269050947311088678478407 122 11739085287969531650666764880307069646178466406133747
#HPSonP(B,G,P)
factor(P-1)


2 * 3^3 * 3559 * 23723122047210181324565006672021119890684486271