GSDP
Catégorie: hard
Points: 164
Résolutions: 24
Énoncé
A very modern cryptography! Break it harder!
from Crypto.Util.number import *
from flag import flag
def hash_base(m):
m = M(m)
_M = M(zero_matrix(d))
for i in range(d):
for j in range(d):
_M[i, j] = pow(2, m[i, j], n)
return M(_M)
def rand_poly(deg):
P = PolynomialRing(Zn, 'x')
x = P.gen()
f = 0
for _ in range(deg):
f += randint(0, deg**2)*x**(_)
return f
def matrox(a, b):
a, b = M(a), M(b)
R = zero_matrix(d)
for i in range(d):
for j in range(d):
R[i, j] = int(a[i, j]) ^^ int(b[i, j])
return M(R)
flag = flag.lstrip('CCTF{').rstrip('}')
assert len(flag) == 25
msg = [[ord(flag[j]) for j in range(5*i, 5*i + 5)] for i in range(5)]
nbit = 72
p, q = [getPrime(nbit) for _ in '01']
n = p * q
d, Zn = 5, Zmod(n)
M = MatrixSpace(Zn, d, d)
m = hash_base(msg)
u, v = [randint(2, 14) for _ in '01']
P = PolynomialRing(Zn, 'x')
x = P.gen()
f, h = rand_poly(d), x**d + x + 1
r, s = [random_matrix(Zn, d) for _ in '01']
y = f(r) ** u * s * f(r) ** v
c_1 = h(r) ** u * s * h(r) ** v
c_2 = matrox(hash_base(h(r) ** u * y * h(r) ** v), m)
print(f'n = {n}')
print(f'r = {r}')
print(f's = {s}')
print(f'y = {y}')
print(f'c_1 = {c_1}')
print(f'c_2 = {c_2}')
Description mathématique
On se donne un entier n (composé).
On doit retrouver une matrice secrète M[i,j] = pow(2, flag[5*i+j], n) étant donnés:
Des matrices r, s choisies au hasard.
Un polynôme secret f
Un polynôme connu h = X^d + X + 1
Des entiers inconnus u, v entre 2 et 13.
La valeur de 3 matrices:
y = f(r)^u × s × f(r)^v
c1 = h(r)^u × s × h(r)^v
c2[i,j] = pow(2, HY[i,j], n) XOR M[i,j]
où HY = h(r)^u × y × h(r)^v
On voit qu’il suffit de calculer HY pour en déduire M:
HY = h(r)^u × f(r)^u × s × f(r)^v × h(r)^v
= f(r)^u × h(r)^u × s × h(r)^v × f(r)^v
= f(r)^u × c1 × f(r)^v
(on utilise ici la commutativité du produit entre polynômes d’une même matrice)
On peut obtenir u et v par recherche exhaustive en essayant de calculer c1 à partir des données connues (h, r, s).
Solution
Zn = Zmod(n)
P = Zn['x']
x = P.gen()
h = x**5 + x + 1
# Brute force u and v
u, v = next((_u, _v) for _u in range(2, 14) for _v in range(2, 14)
if h(R)**_u * S * h(R)**_v == C1)
print(f"Found u, v = {u}, {v}")
# Found u, v = 11, 12
pows = [pow(2, i, n) for i in range(256)]
Z = h(R) ** u * Y * h(R) ** v
msg = []
for i in range(5):
for j in range(5):
val = pow(2, int(Z[i,j]), n) ^ int(C2[i,j])
msg.append(pows.index(val))
print(bytes(msg))
# b'PKCS_N0n_cOmMu74T!v3_rIn9'
Données fournies
n = 20474248118672564431085568112167867588651829
r = [ 2168977325369444782802512809005167009163457 9637731563002649997560875900298785659999735 11402741982195550777990817093767890991834736 6248261665690503242396669505673833765541530 18383713927317640760514600671318653784954042]
[16744026390724915738262959513570982580233867 10819123318870588054961801715028528659245735 5382293825969147064471127752184942873958882 2344559383975384575566938072263260707083674 6107831242377773278696901510341268870768483]
[13913478639322625565461944432421523802028490 1657756157808133991943366467693421012417454 20077078978711296540965234618986335826824167 15787724170325517021960596569296223410283963 11311327970428371404045885802092772454814312]
[ 6961572103900078883590821780051797472394845 9455345930492634517894541442153982197931104 7188007809979291502164073459871201264229019 5450777010613496799286069470550372888274079 19294083677962489844799387987438241606854764]
[ 2085952337131731679161648956407072286901978 6312527395255217479599228946227018949620025 3768572167307432043022080651953496439648407 12149358492352082063390352013944276402659624 1238053480843820309901822772557963596458725]
s = [14359986778171934757328112351570087412922923 11851267097835964101770194163721259897123880 12595767519284390452196370829927812771980581 206471849033914539608937494910010443534631 16748276256578102130941428769109053956841543]
[17260552917456245674154511124533873366489719 6705751087806309384311406617121931614484164 17060390771834209118913353599009244296476485 14200001344699610276445944574627003822066232 11014902955514050741738009264685742116160993]
[ 6574547665819712697427953197398960761636762 12380657135986764418898027400335749204149860 20268210493845979828493975027685347139394991 18542561637456865344299035395313783209218383 7517573123535289654812496192079398350464721]
[11797258068553520501845550128339899816126913 18396577268206658268808323909560870783161039 5490905135614309369346662799065239256309022 14271245849005639472351475697722779937695903 4543895191969014210971676462965142633095929]
[ 8211670484406041965410550067328494865731128 9385233048164928123059801337014436991987865 2095213218314387589455876832673480152942740 13404162072797239424739266925419641170015472 6893572325245832032339890201821364839102869]
y = [ 9455266042843307825749316910810796871873373 15333106063741475447799261101208428669252581 17507977101165165875868259123812011424101505 18840713703683969794184618879025658583771001 8194677825423260832777930195809869229371863]
[12501728660245911874452737460699597975974127 19510243647017562462989706821025083261970404 16201393977361396153964696776216973010001356 9663056411865435751212414658633217623172749 3239680106699734686590526219042751814995824]
[ 3712586611180063604215543952289707697324027 14733212399197986119485181728946640781107458 2840139099323763287710523315368925837277792 13720228569300291500610175158110171144774084 6108815350519225911945135207538331156078296]
[ 7943973119701029382921917301472306070824581 2869347305630973901685036806460889911095637 10842022254827356928486285947954965977783240 20363982398752260203093070660357855892929807 3232527006736169029584220678644241677651188]
[18741615057330867264302735709730246936126331 7207581826003452274777064725926668618294351 12235279908760679864964056098862023499484670 11395481161377031878998588680860748310228740 14691306415490831547905993706341909177907668]
c_1 = [14520715136678131886650886394655992310739740 5133803346119603685589690243318329447613811 8631069083165564771821540186676532972101042 11371460936058753234877719062830204068473293 4675643908977844081807119750891783452511801]
[10758446634943798177756512241470807154028028 230322671654482905785761279475308992164431 19859272618066856343509476253828743509021381 10790059806866303289733349155468067057434048 7937553273189724162746367232714449171157875]
[12713707768421115203045631708468778038780988 6562443329388128558909111073920129986165358 8629397281530840800788762372728359271085200 3497280351202001940823865223283895540070188 16324531747558707671873605114378727152000738]
[17664302494165645750553234381674396726461155 11329821313213471881023356172069963076578223 17420708004114170496283987639981918922808988 4025301508682028642713745479550070150287792 13516995862604528976910352157951268294502659]
[13197381126644223748863331681581035046689048 18134793368131211547774737770284104243998582 3304296884612368960093061281547555357926671 17654343876553302292700074689920978613390384 19965538184282119398237005639724114717256368]
c_2 = [ 7467508370111086497875591641000575993385737 436730215933598480688770862716304678927061 16388674389038775692052384536812272916184391 1544929917235051621830007372321346311674993 20266847919326089072814025756784393554435095]
[ 8525400103718228392870804572553779730855209 6910832586632574200490719455813022347001485 17879158289938108082881632425571195671456277 10773037736439027909506921110474733019517450 6673285991052846421739430171898388311111793]
[ 9870026505859633975247413380429542368374340 3599087047295232637660012477486366289652163 9771908525081529326761727267151928531319243 19335625816265272435673905591707160166566864 15219307175745538685718076680399058971932192]
[ 7121095235650179073589022177762837236165521 10051305836914620675997951100253778882475518 14120877609199150307731361282669945615365363 3064435253345055470095756982744706296418025 126078528977194834765813221549264972548412]
[18926039657432874696099563502261812215936524 14159758827498805644159739654028640645658626 4643672049840979864316682883185591331924981 20293416534996028081504808704845564317319704 5806383537343185356941724671128323142478351]