Sharif University CTF 2016: High-speed RSA Keygen

decrypt.py

# 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 .........

solver.py

# 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

The Flag is "e7531f1bb9c95c19e823065d3e6a86b6" :)

RSAの鍵(素数)生成のコードが渡されるが実装が甘く、1024bit素数の上位約2/3のビットが高々2^12回の試行で総当たりできる。残りのビットが完全にランダムと考えると、Coppersmithの定理を用いてHigh-bit Known Attackが実行でき、素数が求まる。