Jun-16-2020, 06:10 AM
Hello. I am trying to take the average time for the 1000 signature generation operation. The two keys generated is also taking from the average of 100 random primes.
This coding has run for 7 days but still yet got any result? Can anyone help me have a look at it? Let me know the problem inside? Do the problem is due to the algorithm not efficient enough or anything?
Thank you so much and I do appreciate your help. TQ!
This coding has run for 7 days but still yet got any result? Can anyone help me have a look at it? Let me know the problem inside? Do the problem is due to the algorithm not efficient enough or anything?
Thank you so much and I do appreciate your help. TQ!
from random import randrange, getrandbits
from fractions import Fraction
from random import seed
from random import randint
import hashlib
import timeit
k=1536
N=1000
m=100
def is_prime(n, K=128):
""" Test if a number is prime
Args:
n -- int -- the number to test
k -- int -- the number of tests to do
return True if n is prime
"""
# Test if n is not even.
# But care, 2 is prime !
if n == 2 or n == 3:
return True
if n <= 1 or n % 2 == 0:
return False
# find r and s
s = 0
r = n - 1
while r & 1 == 0:
s += 1
r //= 2
# do k tests
for _ in range(K):
a = randrange(2, n - 1)
x = pow(a, r, n)
if x != 1 and x != n - 1:
j = 1
while j < s and x != n - 1:
x = pow(x, 2, n)
if x == 1:
return False
j += 1
if x != n - 1:
return False
return True
def generate_prime_candidate(length):
""" Generate an odd integer randomly
Args:
length -- int -- the length of the number to generate, in bits
return a integer
"""
# generate random bits
p = getrandbits(length)
# apply a mask to set MSB and LSB to 1
p |= (1 << length - 1) | 1
return p
def generate_prime_number(length):
""" Generate a prime
Args:
length -- int -- length of the prime to generate, in bits
return a prime
"""
p = 4
# keep generating while the primality test fail
while not is_prime(p, 128):
p = generate_prime_candidate(length)
return p
def solve_Dioph(a,b,c):
m1=1
m2=0
n1=0
n2=1
r1=a
r2=b
while r1%r2!=0:
q=r1//r2
aux=r1%r2
r1=r2
r2=aux
aux3=n1-(n2*q)
aux2=m1-(m2*q)
m1=m2
n1=n2
m2=aux2
n2=aux3
return m2*c,n2*c;
def average_prime():
totalp,totalq=0,0
count=0
while(count < m):
count=count+1
p,q=generate_prime_number(k),generate_prime_number(k)
totalp+=p
totalq+=q
print(p,q)
p,q=(int(totalp/m),int(totalq/m))
return p,q;
(p,q)=(average_prime())
def key_generation(p,q):
n=p*q
f=Fraction(p-1,q-1)
s=f.denominator
omega=s*(p-1)+1
seed(1)
for _ in range(1):
u,gamma = randint(1,n),randint(1,n)
(a,b)=solve_Dioph(u, gamma, omega)
(v,Lambda)=(a%n,b%n)
for _ in range(1):
x = randint(1,n)
X1=pow(x,u,n)
X2=pow(x,gamma,n)
#pk=(n,u,gamma,X1,X2)
#sk=(v,Lambda,omega,x)
return n,u,gamma,X1,X2,v,Lambda,omega,x;
def generate_hash2(secret, param_str):
dk = hashlib.sha256()
bsecret = secret.encode('utf-8')
bparam_str = param_str.encode('utf-8')
dk.update(bsecret)
dk.update(bparam_str)
return dk.hexdigest()
def sign_generation(n,u,gamma,X1,X2,v,Lambda,omega,x):
for _ in range(1):
y = randint(1,n)
Y1=pow(y,u,n)
Y2=pow(y,gamma,n)
I=Y1*Y2
M="happy"
c=int(generate_hash2(str(I),M), 16)
z=(pow(x,c,n)*(y%n))%n
return (I,c,z,M);
def sign_verification(n, u, gamma, X1, X2, v, Lambda, omega, x,I,c,z,M):
C=int(generate_hash2(str(I),M), 16)
if pow(z,u+gamma,n)==(pow((X1*X2),C,n)*(I%n))%n:
result='valid'
else:
result='invalid'
return result
def time_sign_generation():
(n,u,gamma,X1,X2,v,Lambda,omega,x)=key_generation(p,q)
start = timeit.default_timer()
(I,c,z,M)=sign_generation(n,u,gamma,X1,X2,v,Lambda,omega,x)
end = timeit.default_timer()
time_SignGen = end - start
return time_SignGen
def average_time_sign_generation():
total=0
for _ in range(N):
time=time_sign_generation()
total += time
average_time_SignGen=total/N
return average_time_SignGen
# def check_signature():
# (n,u,gamma,X1,X2,v,Lambda,omega,x)=key_generation()
# (I,c,z,M)=sign_generation(n,u,gamma,X1,X2,v,Lambda,omega,x)
# check=sign_verification(n, u, gamma, X1, X2, v, Lambda, omega, x, I, c, z, M)
# return check
#print("Signature is",check_signature())
print(N,k,average_time_sign_generation())