# Weiner's Little D Attack

Aug 14th, 2018
1,616
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #!/usr/bin/env python
2.
3.
4. def rational_to_contfrac(x,y):
5.     # Converts a rational x/y fraction into a list of partial quotients [a0, ..., an]
6.     a = x // y
7.     pquotients = [a]
8.     while a * y != x:
9.         x, y = y, x - a * y
10.         a = x // y
11.         pquotients.append(a)
12.     return pquotients
13.
14. def convergents_from_contfrac(frac):
15.     # computes the list of convergents using the list of partial quotients
16.     convs = [];
17.     for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i]))
18.     return convs
19.
20. def contfrac_to_rational (frac):
21.     # Converts a finite continued fraction [a0, ..., an] to an x/y rational.
22.     if len(frac) == 0: return (0,1)
23.     num = frac[-1]
24.     denom = 1
25.     for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num
26.     return (num, denom)
27.
28. n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381
29.
30. e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205
31.
32. c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635
33.
34. def egcd(a, b):
35.     if a == 0: return (b, 0, 1)
36.     g, x, y = egcd(b % a, a)
37.     return (g, y - (b // a) * x, x)
38.
39. def mod_inv(a, m):
40.     g, x, _ = egcd(a, m)
41.     return (x + m) % m
42.
43. def isqrt(n):
44.     x = n
45.     y = (x + 1) // 2
46.     while y < x:
47.         x = y
48.         y = (x + n // x) // 2
49.     return x
50.
51. def crack_rsa(e, n):
52.     frac = rational_to_contfrac(e, n)
53.     convergents = convergents_from_contfrac(frac)
54.
55.     for (k, d) in convergents:
56.         if k != 0 and (e * d - 1) % k == 0:
57.             phi = (e * d - 1) // k
58.             s = n - phi + 1
59.             # check if x*x - s*x + n = 0 has integer roots
60.             D = s * s - 4 * n
61.             if D >= 0:
62.                 sq = isqrt(D)
63.                 if sq * sq == D and (s + sq) % 2 == 0: return d
64.
65. d = crack_rsa(e, n)
66. m = hex(pow(c, d, n)).rstrip("L")[2:]
67. print(m.decode("hex"))
RAW Paste Data