# discrete_log_rho OverflowError: Python int too large to convert to C long

When I run this code below, I get OverflowError, How can I fix this? keep this big prime

import random
import time
@interact
def _(a1=0,a2=0,a3=0,a4=0,a5=7,p1=('p',input_box(default=1461501637330902918203684832716283019655932584637)),auto_update=False):
p=p1
if (is_prime(p)==True):
print 'Elliptic Curve yang digunakan y^2 + a1*xy + a3*y = x^3 + a2*x^2 + a4*x + a5'
F = GF(p)
E = EllipticCurve(F,[a1,a2,a3,a4,a5])
G = E.gen(0)
random = randint(0,p)
P = random*G
if (is_prime(P.order())==True):
random1 = randint(0,p)
Q = random1*P
print 'P = ',P
print 'Q = ',Q
print 's = ', random1
print '#Break ECC dengan Algoritma Pollard Rho (Q = k*P), k=?'
#Now we need to find the private key: q1 = G*privateKey so we do this:
print 'Start searching.......'
start = time.time()
k = discrete_log_rho(Q, P, ord = P.order(), operation='+')
print 'Key ditemukan!!!'
print 'Key = s = ',k
end = time.time()
print 'Computation time = ',end-start,'detik'
else:
print 'Failed. Orde P is not prime!!'
else:
print 'p must be prime!'

edit retag close merge delete

I think it means that the Pollard Rho implementation you are relying on is written to use C 64-bit integers, and therefore cannot accept input that doesn't fit in 64 bits. One solution would be to write an implementation that does accept larger integers (it's not that hard to write). Beware, though: cryptosystems in current use are designed to not be easily broken, and people are aware of Pollard Rho. I would expect that your chance for success within the lifetime of the sun is vanishing small if this curve is industrial-strength.

( 2018-12-23 21:20:12 +0200 )edit