tkbctf4 Write-up rcrypto (cryptography200)

　tkbctfにチームm1z0r3として参加しました．結果は600点で71チーム中15位．自分が解いたのはrcryptoの1問だけでした．（つらい）
　javascriptの2問が解けそうで解けなかったのが悔しかったです．引き続き解いてみてWrite-upを書こうと思います．

rcrypto (cryptography200)

　encrypto.pyとresul.txtの2つのファイルが渡されます．

encrypto.py

import struct

N = 0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

def encrypt(M, B):
    return M * (M + B) % N

if __name__ == '__main__':
    s = open('flag', 'r').read()
    tkbctf = struct.unpack('<2I', 'tkbctf4\0')
    flag = int(s.encode('hex'), 16)
    print "1: %d" % encrypt(flag, tkbctf[0])
    print "2: %d" % encrypt(flag, tkbctf[1])

result.txt

1: 2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
2: 869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714

　encrypt.pyで暗号化された結果がresulet.txtに出力されています．暗号化前の平文がフラグになっているようです．
　暗号アルゴリズムは，平文(フラグ)をM，鍵をB,N，暗号文をRとすると

R = M * (M + B) (mod N)

　となっています．暗号化というよりハッシュっぽいですね．
　この式から単純にMを導くことは不可能ですが，今回はこの暗号化が以下のように2パターンあります．青字が既知の値で，赤字が未知の値です．

R1 = M * (M + B1) (mod N)　・・・①
R2 = M * (M + B2) (mod N)　・・・②

　この2式から未知の値Mを推定します．
　R1>R2かつB1>B2のとき，①式から②式を減算すると

R1 - R2 = M( B1 - B2 ) (mod N)

　が成り立ちます．（証明は省略）
　つまり

M( B1 - B2 ) - ( R1 - R2 ) = kN　　　　(kは自然数)
⇒ M = {kN + ( R1 - R2)} / (B1-B2)

　となりM=の式が出来ます．この式において，Mが整数になるようにkをブルートフォースします．
　作成したスクリプトがこちら．

import struct

tkbctf = struct.unpack('<2I', 'tkbctf4\0')
t=tkbctf[0]-tkbctf[1]

R1=2302864379938375384787522457289953058762346515694717964988017701221632252068998721016780659512789645178039929483162432085291148128875938650563974652974607897108753247761759018159346471819526717450317624121005691577913298753406802656066710989103644069541226797561238591832001786871030959032526532824897381416113004865029523158041337929652792421367459253385313006702525506606665513325657107841851439410104118856833250549528309345600994438901026890993789031255524302387252820866177521016309668779564405438776186649089481716393902512049059686799788362854701624870108840227739233423565617147635810535089953364777452765391
R2=869821841437664579273841208702057334636310328092375384661895122870843280009327763942775667106913326453781559554453279690395959752854296081023254897131426262762124201024166059200347755016000992120349762030587256929453375758557293418778029046615012379759165445526510048231152939113590563355048407714266168812177988203610092674509339069396233061882191910214456155546393848777696938097852335164090584476493820466258280954729469300306911409684786367255431603152145902151223834708442564731418184393252984714050882676106734102146980036229108895568198263271905480015122766218776429803994468521463000793677542363327966917714
x=R1-R2

N=0xcd892c64f1803742a89e68567aea60283066b368d2c2454ad55f740fb0ff8e98e03f70cd9a2c9168294eee89a9f995d2596f2c0be881bfbfa72cccbb18a77287134e2ffc89e7bce766cca9136074a19f6807c3ff51e5cf53ec79838067cbefac809fccbbe2c1c4d170f3be58b34b9c3dfaeb2914341697d6503a826716073f9808b91c747030e2cdeaf20620b269c701d5ce96623c95c983678fd1175243b9eda7f6a310b4ccfd6c69fa836adb82271c56aa7ca267c1d47e64e69a0c3541f63432b4d75b881c1694a07b546eaee036521213967201cd91ff6a4e1e7c89027eb57096f2e3e5cd274d5cd272be44435b21648538f31760b4f8b50cbcd42f0873d5

k=1
while(1):
	if (k*N+x)%t==0:
		print (k*N+x)/t
		break
	else:
		k+=1
	print k

Result

k=569111799
M=8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519

　計算に1時間以上かかりました．（途中何度諦めかけたことか・・・）
　きっともっと効率のいい解法があると思います．

　あとは得られたMをASCII文字に変換するだけ．

$ python
>>>a=8874284088105576854948238238614457044505028639011349374021861498995036023097152049555857239549350287166006347100199983957544356840501980854784901113821946197380611177705292212987004478484951309819182405098846767765333862409425926812573611864910204824928321142829182839508679805462040296761411851272619037561124670207800113160725445151643233355853069817035845548582628939322952705418085312089629008831113802005771457751200233715401850140367028206001736592528758851066145310031045563613680644635600425736132514865977264503188118025685603053077990165729300195014737832785024786331903041102248425142311946913492026078519
>>> s = hex(a)[2:]
>>> z=''
>>> for i in range(0, len(s), 2):
...   z += chr(int( (s[i]+s[i+1]), 16))
...
>>> z
'FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y573m 15 v3ry 1n73r3571ng!!!}FLAG{R4b1n cryp705y57'