Aperi’CTF 2019 - Not Funny
Challenge details
| Event | Challenge | Category | Points | Solves |
|---|---|---|---|---|
| Aperi’CTF 2019 | Not Funny | Cryptography | 175 | 2 |
Votre voisin est un fan de cryptographie à tendance sadique. Il ne prend pas vos compétences en cryptanalyse au sérieux et a une dent contre vous depuis que vous avez été embauché dans l’entreprise où il avait postulé et pas lui.
Il vous a volé un document crucial pour votre avenir professionnel et vous a laissé une lettre de moqueries.
Fichiers : letter - md5sum: 2a00764510e267d601331dad192b45d4
TL;DR
This is a relaxed model of RSA that was broken by Coppersmith and Howgrave-Graham.
Methodology
Based on the information in the description of the challenge, the MSB of p are known.
This is a relaxed model of RSA that was broken by Coppersmith and Howgrave-Graham.
There is a github page that provides a sage implementation of this attack.
Full script available here
#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# This file was *autogenerated* from the file rsaQuarterRecovery.sage
from sage.all_cmdline import * # import sage library
_sage_const_3 = Integer(3); _sage_const_2 = Integer(2); _sage_const_1 = Integer(1); _sage_const_0 = Integer(0); _sage_const_7 = Integer(7); _sage_const_4 = Integer(4); _sage_const_1024 = Integer(1024); _sage_const_200 = Integer(200); _sage_const_0p5 = RealNumber('0.5')
import time, sys
debug = False
def ntos(x):
n = hex(x)[2:].rstrip("L")
if len(n)%2 != 0:
n = "0"+n
return n.decode("hex")
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[_sage_const_0 ]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[_sage_const_1 ]):
a += '0' if BB[ii,jj] == _sage_const_0 else 'X'
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print a
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|modulus, b >= modulus^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt
#
# checks
#
if not _sage_const_0 < beta <= _sage_const_1 :
raise ValueError("beta should belongs in (0, 1]")
if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")
#
# calculate bounds and display them
#
"""
* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
* we know LLL will give us a short vector v such that:
||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
* we will use that vector as a coefficient vector for our g(x)
* so we want to satisfy:
2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
(it's important to use N because we might not know b)
"""
if debug:
# t optimized?
print "\n# Optimized t?\n"
print "we want X^(n-1) < N^(beta*m) so that each vector is helpful"
cond1 = RR(XX**(nn-_sage_const_1 ))
print "* X^(n-1) = ", cond1
cond2 = pow(modulus, beta*mm)
print "* N^(beta*m) = ", cond2
print "* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD"
# bound for X
print "\n# X bound respected?\n"
print "we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M"
print "* X =", XX
cond2 = RR(modulus**(((_sage_const_2 *beta*mm)/(nn-_sage_const_1 )) - ((dd*mm*(mm+_sage_const_1 ))/(nn*(nn-_sage_const_1 )))) / _sage_const_2 )
print "* M =", cond2
print "* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD"
# solution possible?
print "\n# Solutions possible?\n"
detL = RR(modulus**(dd * mm * (mm + _sage_const_1 ) / _sage_const_2 ) * XX**(nn * (nn - _sage_const_1 ) / _sage_const_2 ))
print "we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)"
cond1 = RR(_sage_const_2 **((nn - _sage_const_1 )/_sage_const_4 ) * detL**(_sage_const_1 /nn))
print "* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1
cond2 = RR(modulus**(beta*mm) / sqrt(nn))
print "* N^(beta*m) / sqrt(n) = ", cond2
print "* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)"
# warning about X
print "\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n"
#
# Coppersmith revisited algo for univariate
#
# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()
# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)
# construct lattice B
BB = Matrix(ZZ, nn)
for ii in range(nn):
for jj in range(ii+_sage_const_1 ):
BB[ii, jj] = gg[ii][jj]
# display basis matrix
if debug:
matrix_overview(BB, modulus**mm)
# LLL
BB = BB.LLL()
# transform shortest vector in polynomial
new_pol = _sage_const_0
for ii in range(nn):
new_pol += x**ii * BB[_sage_const_0 , ii] / XX**ii
# factor polynomial
potential_roots = new_pol.roots()
# print "potential roots:", potential_roots
# test roots
roots = []
for root in potential_roots:
if root[_sage_const_0 ].is_integer():
result = polZ(ZZ(root[_sage_const_0 ]))
if gcd(modulus, result) >= modulus**beta:
roots.append(ZZ(root[_sage_const_0 ]))
#
return roots
if __name__ == "__main__":
# when partially know p or q
N = Integer(21475596280939174139431514855487916848280293757877221629494000423065740039343165568040911365501931709899474457901218636286613252968091838444984682784515413643636881148238753087604560665820935690301341977536386047275665017274334379698691769474381442859960487730730928509631882014534379721535881772034345790413578890481396738792233363159809423111473169292217241145616333232083518177326358298078048628120127179798565879267980968193362945481320953732076711233595860392612661434058587237963218791159823174473621469045407472255263769629994834663464420068453008215132214063751047917187048914808372378795396554061907744836817)
e = 65537
c = 20754532737949147742223373902498179634482610091973401913965157562215452429498008912598985786021744450617885408505714822236352995311810091314580467491358612250746471365079581324215426926430950841351364153354904788124987738423489564283310714390723281967378568516974010529197725382065316878282378564285294967866976464084855095285979327325380990150508854537668589744102474681630473341864971730762504436287798866508217036746708084200623440756971882983470032827345378642632637403720063632023394983904708937936062655036947907107788458010769639935212088808550212043364417102917046970788178629455261301698308788491373995670906
qbar = Integer(136032115030209730841795989556533149289798564864039724005919755642131398781579565419215111294655920896216631707218214703673379732583990633646915047476669276370539105011413159892850208470199569891528387660241874080000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
length_N = len(N.digits(2))
F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',)); (x,) = F._first_ngens(1);
pol = x + qbar
dd = pol.degree()
# PLAY WITH THOSE:
beta = RealNumber('0.4') # we should have q >= N^beta
epsilon = beta / _sage_const_7 # <= beta/7
mm = ceil(beta**_sage_const_2 / (dd * epsilon)) # optimized
tt = floor(dd * mm * ((_sage_const_1 /beta) - _sage_const_1 )) # optimized
XX = ceil(N**((beta**_sage_const_2 /dd) - epsilon)) # we should have |diff| < X
# Coppersmith
start_time = time.time()
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
# output
if len(roots) >= 1:
r = roots[0]
q = qbar + int(r)
p = N/q
o = (p-1)*(q-1)
d = inverse_mod(e,o)
print ntos(int(pow(c,d,N)))
Flag
APRK{c0pP3rSm1th_H0wgr4v3_b1g_fl4G_suCh_sk1lls_mucH_R3w4rd1ng}
ENOENT