Last active
July 6, 2016 09:15
-
-
Save sonickun/8bf932d411e1034df5b47df63cf3a706 to your computer and use it in GitHub Desktop.
Sharif University CTF 2016: High-speed RSA Keygen
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
# Sharif University CTF 2016: High-speed RSA Keygen [Part2] | |
def egcd(a, b): | |
if (a == 0): | |
return [b, 0, 1] | |
else: | |
g, y, x = egcd(b % a, a) | |
return [g, x - (b // a) * y, y] | |
def modInv(a, m): | |
g, x, y = egcd(a, m) | |
if (g != 1): | |
raise Exception("[-]No modular multiplicative inverse of %d under modulus %d" % (a, m)) | |
else: | |
return x % m | |
def decrypt(p, q, e, c): | |
n = p * q | |
phi = (p - 1) * (q - 1) | |
d = modInv(e, phi) | |
m = pow(c, d, n) | |
return m | |
n = 0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB | |
e = 65537 | |
c = 0x64A3F710E3CB9B114FD112B45AC4845292D0B1FEE1468147E80FABA3CD56B1206F5C59E5D400A7F20C9BCD5B42C7197A0D07FBBA48BFBDA550C5CAFB562BEC1B1CB301D131E13233F2BD1C80EEB48956FF0BC8DB6AE2CD727FB1DAC62822331B15A6044F825D01D81036DA3CC8A3575165E813051036715CDF5F7865676DC2513AAD08C5113DFFDC4E6B13E6FFCA2FAD1AA6986D3ED9F1896C109F641074DA7DBFE62CCAD3CACE4B80332475FE3C9EC4869FCA31EE2860D45959F8583C2AEC7A00FC2FD63DBF6CBEB1C604D60CF780FE028ED0AD65DC74BC5335F96EE7CEDEA292F76B427E5F402BCC609B39302CD4A51F405C6ACF8B8A7569AAD9A9318F060B | |
p = 144299940222848685214153733110344660304144248927927225494186904499495592842937728938865184611511914233674465357703431948804720019559293726714685845430627084912877192848598444717376108179511822902563959186098293320939635766298482099885173238182915991321932102606591240368970651488289284872552548559190434607447 | |
q = n / p | |
print "p:", p | |
print "q:", q | |
m = decrypt(p, q, e, c) | |
print hex(m)[2:-1].decode("hex") | |
# Result | |
# > python decrypt.py | |
# p: 144299940222848685214153733110344660304144248927927225494186904499495592842937728938865184611511914233674465357703431948804720019559293726714685845430627084912877192848598444717376108179511822902563959186098293320939635766298482099885173238182915991321932102606591240368970651488289284872552548559190434607447 | |
# q: 144245059483864997316184517203073096336312163518349447278779492969760750146161606776371569522895088103056082865212093431805166968588430946389831338526998726900084424430828957236538023320369476765118148928194401317313951462365588911048597017242401293395926609382786042879520305147467629849523719036035657146109 | |
# The flag is ................................................ e7531f1bb9c95c19e823065d3e6a86b6 ......... |
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
# Sharif University CTF 2016: High-speed RSA Keygen [Part1] | |
# Filename: solver.sage | |
from sage.all import * | |
def get_primes(n): | |
numbers = set(range(n, 1, -1)) | |
primes = [] | |
while numbers: | |
p = numbers.pop() | |
primes.append(p) | |
numbers.difference_update(set(range(p*2, n+1, p))) | |
return primes | |
def coppersmith(pbar): | |
global n | |
beta = 0.5 | |
epsilon = beta^2/7 | |
pbits = 1024 | |
kbits = floor(n.nbits()*(beta^2-epsilon)) | |
PR.<x> = PolynomialRing(Zmod(n)) | |
f = x + pbar | |
x0 = f.small_roots(X=2^kbits, beta=beta) # find root < 2^kbits with factor >= n^0.3 | |
if len(x0) > 0: | |
return x0[0] + pbar | |
else: | |
return None | |
####### main ####### | |
n = 0xA4E20DDB854955794E7ABF4AE40051C0FC30488C82AB93B7DD046C1CC094A54334C97E84B523BD3F79331EBEAF5249200D729A483D5B8D944D58DF18D2CA9401B1A1A6CDA8A3AC5C234A501794B76886C426FAC35AD9615ADAB5C94B58C03CCFFA891CE0156CBC14255F019617E40DE9124FBBE70D64CD823DCA870FF76B649320927628250D47DB8DFA9BBCE9964CB3FE3D1B69845BD6FA2E6938DDA1F109E5F4E4170C845B976BBD5121107642FC00606208F9BC83322532739BCFEAF706FB2AF985EBD9769C7FBD50ECBF55566BD44FB241F9FD2DE25069AA8C744F0558514F1E9C8E4297A4D4B25D9F2B7494B466C2E6E2834BA68C5C824215018368B4FB | |
e = 65537 | |
c = 0x64A3F710E3CB9B114FD112B45AC4845292D0B1FEE1468147E80FABA3CD56B1206F5C59E5D400A7F20C9BCD5B42C7197A0D07FBBA48BFBDA550C5CAFB562BEC1B1CB301D131E13233F2BD1C80EEB48956FF0BC8DB6AE2CD727FB1DAC62822331B15A6044F825D01D81036DA3CC8A3575165E813051036715CDF5F7865676DC2513AAD08C5113DFFDC4E6B13E6FFCA2FAD1AA6986D3ED9F1896C109F641074DA7DBFE62CCAD3CACE4B80332475FE3C9EC4869FCA31EE2860D45959F8583C2AEC7A00FC2FD63DBF6CBEB1C604D60CF780FE028ED0AD65DC74BC5335F96EE7CEDEA292F76B427E5F402BCC609B39302CD4A51F405C6ACF8B8A7569AAD9A9318F060B | |
primes = get_primes(443) | |
primes.sort() | |
del primes[0] | |
pi = 1; | |
for x in primes: | |
pi *= x | |
# print "pi=%X" % pi | |
for i in range(1,4096): | |
print i | |
kp = (i + 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19) | |
pbar = kp * pi * (2**400) | |
# High-bit known attack | |
p = coppersmith(pbar) | |
if p != None and n % p == 0: | |
print "Found" | |
print "p", p | |
break | |
# Result | |
# > sage solver.sage | |
# Found | |
# p 144299940222848685214153733110344660304144248927927225494186904499495592842937728938865184611511914233674465357703431948804720019559293726714685845430627084912877192848598444717376108179511822902563959186098293320939635766298482099885173238182915991321932102606591240368970651488289284872552548559190434607447 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
RSAの鍵(素数)生成のコードが渡されるが実装が甘く、1024bit素数の上位約2/3のビットが高々2^12回の試行で総当たりできる。残りのビットが完全にランダムと考えると、Coppersmithの定理を用いてHigh-bit Known Attackが実行でき、素数が求まる。