PlaidCTF 2017 - Common (Crypto 600)
''' | |
Common-prime (in group order!) RSA with low private exponent. | |
p = 2ga + 1 | |
q = 2gb + 1 | |
N = p * q | |
phi(N) = 2gab | |
''' | |
from sage.all import * | |
F = PolynomialRing(ZZ, names='x,y') | |
x, y = F.gens() | |
if 0: | |
print "# RSA generated sample - 512 bits" | |
debug = 1 | |
n = 'bits: 511(*8 = 4088):' and 6332209924906212950816505180496214422855463382080555526624065510289860012943655551527746445592934358298843747768711404596123307443271433986242907192036903 | |
lcm = 'bits: 307(*8 = 2456):' and 143204633245102305770892944333114088164113267378582222077214858741657557576780457628982148872 | |
e = 'bits: 306(*8 = 2448):' and 102573151860923483482923635426844028877725507002960664276202012941781377721174662183122336581 | |
d = 'bits: 81(*8 = 648):' and 2297833573541091530506325 | |
p = 'bits: 256(*8 = 2048):' and 96078657335310124036719788604006385717997522720399015824884106923763004145007 | |
q = 'bits: 256(*8 = 2048):' and 65906519725885527799387426619815010642569160879093905257080055731449910333129 | |
k = 'bits: 81(*8 = 648):' and 1645868759613054159239517 | |
g = 'bits: 204(*8 = 1632):' and 22108956188827705981683764894239934965534004098276290804789247 | |
a = 'bits: 51(*8 = 408):' and 2172844717650249 | |
b = 'bits: 51(*8 = 408):' and 1490493697734812 | |
N = n - 1 | |
f = (e*x - 1) * (e*x - 1 + y) | |
solx = d | |
soly = k * (a + b) | |
X = solx + 100 | |
Y = soly + 100 | |
else: | |
print "# Plaid CTF 2017 Quals - Common (Crypto 600) - common prime RSA with small d" | |
debug = 0 | |
TASK_N = n = 58088432169707511884530887899705328460043341752051203523596713643978064163990486003388043207708974302843002172264417411586749486956628013574926573715095249317804208372132481594468281365459316852927039797580064466731086129431102303726096683810636192790138689214881951836298576801818592777778548978736174404573637727968467102304994883348510912250960513170991711142297420921866513951251779528983034404550484931629702384165892697556071097115581299228167852394258387798734409094231193145682416393190929132395057494573898497863918989076392413537702062176268786330410635086565380004463707094857932051066439903977555824218219175469965671350998705376046031482320586719742092257095632485346554447599297796154806971819544073874759609887168714861438380508381072200369356855424637087904990126639040356052220595703217836390163784968964557550834138598331720685971193948909145336792118311346853933919997080542485529346554810899612986872128053464963893904969598870571593590391792680177336466285483108769678524923709955832516312592396932275858180384073997491565078915852990631405792518132787289319255490058314797418779789436482247156880548274241414788581503832731423362447015575598719157544932430682335826661205441977262084135022109705809490179219483 | |
TASK_E = e = 1296863142627338816011174237898978985407338763709131570002553514972553044428195580769854555546152719732990573444787592853632636242677007643888487629752955065888264014132275294946697123213980215879592216819850992977582758776020797257958443371755687921634978634111557036569863976062810460472490135115734285081745257140890782551910267112228842110620084653440977034007333330590567591507504424149155838966172077983891168269103390479149309815192817914537419492632845858394205854892694802909512194639800529863998537677351955149803841057222279150345376221210193853988829004456607875070080035867353641697190133291884195010172677474092272163240020759433657106746641878734177642792083528380007586872967990567342937466301144028345682953828338178443155 | |
TASK_ENC_2 = pow(2, TASK_E, TASK_N) | |
N = n - 1 | |
f = (e*x - 1) * (e*x - 1 + y) | |
# doubled values from another generated sample | |
# [!] the algorithm is quite sensitive to these.. | |
X = 2**657 # d | |
Y = 2**1066 # k (a + b) | |
# X = 2**700 <- does not work... | |
debug = 0 | |
# info | |
bits_XY = RR(log(X*Y, 2)) | |
bits_N = RR(log(N, 2)) | |
print "Ratio:", bits_XY, "/", bits_N, "=", bits_XY / bits_N | |
# polynomial is fine? | |
if debug: | |
assert 0 == f.subs(x=solx, y=soly) % N | |
assert 0 != f.subs(x=solx+1, y=soly) % N | |
assert 0 != f.subs(x=solx, y=soly+1) % N | |
assert 0 != f.subs(x=123, y=31337) | |
# [!] configurable parameters, by hand... | |
m = 3 | |
my = 2 | |
mxy_x = 1 | |
mxy_y = 1 | |
# generate polynomials for lattice | |
polys = [] | |
for k in xrange(m + 1): | |
for i in xrange(m - k +1): | |
p = x**i * f**k * N**(m-k) | |
p = p.subs(x=x*X, y=y*Y) | |
polys.append( p ) | |
for i in xrange(my + 1): | |
p = y**i * f**k * N**(m-k) | |
p = p.subs(x=x*X, y=y*Y) | |
polys.append( p ) | |
for i in xrange(mxy_x + 1): | |
for j in xrange(mxy_y + 1): | |
p = x**i * y**j * f**k * N**(m-k) | |
p = p.subs(x=x*X, y=y*Y) | |
polys.append( p ) | |
polys = sorted(set(polys)) | |
# monomials <-> indices | |
monos = set() | |
for p in polys: | |
for c, mono in p: | |
monos.add(mono) | |
mono_order = sorted(monos) | |
# make matrix with lattice rows | |
m = matrix(ZZ, len(polys), len(mono_order)) | |
for yi, p in enumerate(polys): | |
for c, mono in p: | |
xi = mono_order.index(mono) | |
m[yi,xi] = c | |
print "LLL...", m.nrows(), "x", m.ncols() | |
m = m.LLL() | |
print "Done\n" | |
def topoly(hrow): | |
return sum(c*mono/mono.subs(x=X,y=Y) for c, mono in zip(hrow, mono_order)).change_ring(QQ) | |
# forming polys from coefficients | |
hs = [] | |
for hrow in m: | |
if not hrow: | |
continue | |
h = topoly(hrow) | |
if debug: | |
assert h.subs(x=solx,y=soly) % N == 0 | |
if h.subs(x=solx,y=soly) == 0: | |
hs.append(h) | |
print "Got poly with good root over ZZ. (%d total)" % len(hs) | |
else: | |
hs.append(h) | |
print "Polys", len(hs) | |
# find two algebraically independent polys with target roots | |
def find_roots(hs): | |
roots = set() | |
yy = y.change_ring(QQ) | |
assert str(y) == "y" | |
itr = 0 | |
RQQ = PolynomialRing(QQ, names='x') | |
# TODO: consider smallest h1, h2 first | |
for h1, h2 in Combinations(hs, 2): | |
itr += 1 | |
if itr % 10 == 0: | |
print itr, "/", binomial(len(hs), 2) | |
res = h1.resultant(h2, yy) | |
res = RQQ(res) | |
if not res: | |
continue | |
for r, multiplicity in res.roots(): | |
r = int(r) % N | |
if r and r not in roots: | |
roots.add(r) | |
yield r | |
for r in find_roots(hs): | |
print "Got root!", r | |
if debug: | |
if r == solx: | |
print "Root matches the solution!" | |
elif pow(TASK_ENC_2, r, TASK_N) == 2: | |
print "Solution!" | |
print "d =", r | |
# decrypting flag, basic stuff | |
import sys | |
sys.path += ["/usr/lib/python2.7/dist-packages/"] # for gmpy | |
from rsatool import RSA # https://github.com/ius/rsatool | |
from Crypto.PublicKey import RSA as RSA2 | |
from Crypto.Cipher import PKCS1_OAEP | |
rsa = RSA(n=TASK_N, d=r, e=TASK_E) | |
with open("priv.pem", "w") as fk: | |
fk.write(rsa.to_pem()) | |
print "Key written!" | |
key = RSA2.construct(map(long, (rsa.n, rsa.e, rsa.d, rsa.p, rsa.q))) | |
cipher = PKCS1_OAEP.new(key) | |
print `cipher.decrypt(open("flag.enc").read())` | |
# 'PCTF{Beh0ld_th3_sm1th_of_C0pper_4nd_7he_var1at3_of_Tri}' | |
quit() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment