Атака винера на малую секретную константу(для RSA)

# ПЕРВАЯ ЧАСТЬ, здесь константные значения для всех случаев
p =next_prime(10^10)
q =next_prime(2*p)
n=p*q
print 'p,q,n:',p,q,n
my_phi=(p-1)*(q-1)
h=p/q *1.0
alpha=(h+1)/sqrt(h) *1.0
d_krit=floor(1/sqrt(2*alpha)*n^(0.25))
print 'd_krit:', d_krit
d_border=d_krit^2
print 'd_border',d_border

print '1 случай, когда d1<d_krit и r<1:'

for d in range(d_krit-1,2,-1):
    if GCD(d,my_phi)==1:
        d1=d
        break

print 'd1',d1 , d1<d_krit

r=(d1/d_krit)*1.0
print 'r:', r, r<1

e = 1/d1 % my_phi
k= (e*d1 - 1)/ my_phi

print 'e,k:',e,k

e_n=continued_fraction(e/n)
#print e_n
i=0
while ( e_n.numerator(i) != k ) and (i<len(e_n)):
    i=i+1

print 'i',i
print e_n.numerator(i)/e_n.denominator(i),':',e/n *1.0, e_n.numerator(i)/e_n.denominator(i) *1.0, k/d1 in e_n.convergents()

print '2 случай, когда d2> d_krit и k<k_krit и r>1:'

d2=d_krit+1
while ( GCD(d2,my_phi)!=1 ) and (d2<d_border):
    d2=d2+1

print 'd2:',d2 , d2>d_krit

e = 1/d2 % my_phi
k= (e*d2 - 1)/ my_phi

print 'e,k:',e,k

r=d2/d_krit *1.0
print 'r:',r, r>1

k_krit = d_krit/r *1.0

while (k>= k_krit):
    d2=d2+1
    while ( GCD(d2,my_phi)!=1 ) and (d2<d_border):
        d2=d2+1
    e = 1/d2 % my_phi
    k= (e*d2 - 1)/ my_phi

print 'k_krit:',k_krit, k < k_krit

e_n=continued_fraction(e/n)
#print e_n
i=0
while ( e_n.numerator(i) != k ) and (i<len(e_n)):
    i=i+1

print 'i',i
print e_n.numerator(i)/e_n.denominator(i),':',e/n *1.0, e_n.numerator(i)/e_n.denominator(i) *1.0, k/d2 in e_n.convergents()

print '3 случай, когда d2> d_krit и k_krit<k<2*k_krit и r>1:'

d2=d_krit+1
while ( GCD(d2,my_phi)!=1 ) and (d2<d_border):
    d2=d2+1

e = 1/d2 % my_phi
k= (e*d2 - 1)/ my_phi
if (k_krit<k) and (k<2*k_krit):
    k=k
else:
    while ((k_krit >= k) or (k >= 2*k_krit)) and (d2<d_border):
        #print 'd2:',d2
        d2=d2+1
        while ( GCD(d2,my_phi)!=1 ) and (d2<d_border):
            d2=d2+1
        e = 1/d2 % my_phi
        k= (e*d2 - 1)/ my_phi
if d2==d_border:
    print 'd2!!!'
print 'd2:', d2, d2> d_krit
print 'e,k:',e,k
print 'r:', d2/d_krit *1.0, r>1

e_n=continued_fraction(e/n)
print len(e_n)
#print e_n
i=0
while (e_n.numerator(i) != k ) and (i<len(e_n)):
    i=i+1
if i==len(e_n):
    print('k/d - не является подходящей дробью')
else:
    print 'i',i
    print e_n.numerator(i)/e_n.denominator(i),':',e/n *1.0, e_n.numerator(i)/e_n.denominator(i) *1.0, k/d2 in e_n.convergents()


print '3 случай, когда d2> d_krit и k_krit<k<2*k_krit и r>1, находит случай, когда к/d не является подходящей дробью:'

while i!=len(e_n):
    d2=d2+1
    while ( GCD(d2,my_phi)!=1 ) and (d2<d_border):
        d2=d2+1
    e = 1/d2 % my_phi
    k= (e*d2 - 1)/ my_phi
    if (k_krit<k) and (k<2*k_krit):
        k=k
    else:
        while ((k_krit >= k) or (k >= 2*k_krit)) and (d2<d_border):
            d2=d2+1
            while ( GCD(d2,my_phi)!=1 ) and (d2<d_border):
                d2=d2+1
            e = 1/d2 % my_phi
            k= (e*d2 - 1)/ my_phi
        if d2==d_border:
            print 'd2!!!'
            sys.exit()
        e_n=continued_fraction(e/n)
        i=0
        while (e_n.numerator(i) != k ) and (i<len(e_n)):
            i=i+1
print 'd2:', d2 , d2> d_krit
print 'e,k:',e,k , k_krit<k, k<2*k_krit
print 'r:', d2/d_krit *1.0, r>1

print k/d2 in e_n.convergents()