Created
August 27, 2017 07:42
-
-
Save mananpal1997/73d07cdc91d58b4eb5c818aaab2d38bd to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def rational_to_contfrac(x,y): | |
# Converts a rational x/y fraction into a list of partial quotients [a0, ..., an] | |
a = x // y | |
pquotients = [a] | |
while a * y != x: | |
x, y = y, x - a * y | |
a = x // y | |
pquotients.append(a) | |
return pquotients | |
def convergents_from_contfrac(frac): | |
# computes the list of convergents using the list of partial quotients | |
convs = []; | |
for i in range(len(frac)): convs.append(contfrac_to_rational(frac[0 : i])) | |
return convs | |
def contfrac_to_rational (frac): | |
# Converts a finite continued fraction [a0, ..., an] to an x/y rational. | |
if len(frac) == 0: return (0,1) | |
num = frac[-1] | |
denom = 1 | |
for _ in range(-2, -len(frac) - 1, -1): num, denom = frac[_] * num + denom, num | |
return (num, denom) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from continued_fractions import * | |
n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381 | |
e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205 | |
c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635 | |
def egcd(a, b): | |
if a == 0: return (b, 0, 1) | |
g, x, y = egcd(b % a, a) | |
return (g, y - (b // a) * x, x) | |
def mod_inv(a, m): | |
g, x, _ = egcd(a, m) | |
return (x + m) % m | |
def isqrt(n): | |
x = n | |
y = (x + 1) // 2 | |
while y < x: | |
x = y | |
y = (x + n // x) // 2 | |
return x | |
def crack_rsa(e, n): | |
frac = rational_to_contfrac(e, n) | |
convergents = convergents_from_contfrac(frac) | |
for (k, d) in convergents: | |
if k != 0 and (e * d - 1) % k == 0: | |
phi = (e * d - 1) // k | |
s = n - phi + 1 | |
# check if x*x - s*x + n = 0 has integer roots | |
D = s * s - 4 * n | |
if D >= 0: | |
sq = isqrt(D) | |
if sq * sq == D and (s + sq) % 2 == 0: return d | |
d = crack_rsa(e, n) | |
m = hex(pow(c, d, n)).rstrip("L")[2:] | |
print(m.decode("hex")) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment