#diceCTF_2021 #good_challenges_2021
Two agents, Blex and Kane, have simultaneously known very secret message and transmitted it to Center. You know following: 1) They used RSA with this public key 2) They sent exactly the same messages except the signatures (name appended, eg. "[message]Blex") 3) They did encryption this way: m = int(message.encode("hex"), 16) c = pow(m, e, N) 4) And here are cryptograms you have intercepted: N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529 e = 1048577 ciphertext_Blex = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178 ciphertext_Kane = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472 Now tell me that secret message! (The answer for this task starts from 'dice{')
どうみても Franklin-Reiter Related Message Attackなのでそれをやればいいんだけど、が大きいという問題がある。一変数多項式のgcd の方法では ちょっと遅すぎる
N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529 e = 1048577 ciphertext_Blex = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178 ciphertext_Kane = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472 mb = b"Blex" mk = b"Kane" mb = int(mb.hex(), 16) mk = int(mk.hex(), 16) P.<x> = PolynomialRing(Zmod(N)) # x = m1 -> ([message]Blex) g1 = x^e - ciphertext_Blex g2 = (x - mb + mk)^e - ciphertext_Kane gcd(g1, g2) # gcd(g1, g2) -> (x - m1) # tooo slow
そこで half-GCDを使う。これまでのGCDがていどの計算量だったのに対してこちらはと非常に高速
非常に高速とはいえがでかいので解くのには5000秒以上かかった。おいおい
def pdivmod(u, v): """ polynomial version of divmod """ q = u // v r = u - q*v return (q, r) def hgcd(u, v, min_degree=10): """ Calculate Half-GCD of (u, v) f and g are univariate polynomial http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf """ x = u.parent().gen() if u.degree() < v.degree(): u, v = v, u if 2*v.degree() < u.degree() or u.degree() < min_degree: q = u // v return matrix([[1, -q], [0, 1]]) m = u.degree() // 2 b0, c0 = pdivmod(u, x^m) b1, c1 = pdivmod(v, x^m) R = hgcd(b0, b1) DE = R * matrix([[u], [v]]) d, e = DE[0,0], DE[1,0] q, f = pdivmod(d, e) g0 = e // x^(m//2) g1 = f // x^(m//2) S = hgcd(g0, g1) return S * matrix([[0, 1], [1, -q]]) * R def pgcd(u, v): """ fast implementation of polynomial GCD using hgcd """ if u.degree() < v.degree(): u, v = v, u if v == 0: return u if u % v == 0: return v if u.degree() < 10: while v != 0: u, v = v, u % v return u R = hgcd(u, v) B = R * matrix([[u], [v]]) b0, b1 = B[0,0], B[1,0] r = b0 % b1 if r == 0: return b1 return pgcd(b1, r) import time N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529 e = 1048577 ciphertext_Blex = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178 ciphertext_Kane = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472 mb = b"Blex" mk = b"Kane" mb = int(mb.hex(), 16) mk = int(mk.hex(), 16) P.<x> = PolynomialRing(Zmod(N)) # x = m1 -> ([message]Blex) g1 = x^e - ciphertext_Blex g2 = (x - mb + mk)^e - ciphertext_Kane t1 = time.time() r = pgcd(g1, g2) t2 = time.time() print(t2-t1) print(r) print(r, g1 % r, g2 % r) print(bytes.fromhex(hex(inverse_mod(int(-r[1]), N) * r[0] % N)[2:])) # gcd(g1, g2) -> (x - m1)