daily pastebin goal
29%
SHARE
TWEET

Weiner's Little D Attack

RootOfTheNull Aug 14th, 2018 190 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top