<> == Decrypt it (Easy) (Crypto 200pts) == バイナリを読んだ結果，概ね次のような動作をすることがわかった。 {{{#!highlight c srand(time(NULL)); while (!feof(rfp)) { fread(buf, 1, 1, rfp); buf[0] = buf[0] ^ (rand() % 256); fwrite(buf, 1, 1, wfp); } }}} ファイルの最終更新日時を中心に時刻の探索を行った。 {{{#!highlight c #include #include char buf[10]; int main() { FILE *fp = fopen("ecrypt1.bin","r"); fread(buf, 8, 1, fp); int i,j,cnt=0; for(i = 1416606360+100000; i > 1416606360-1000000; i--) { srand(i); char enc[10]; for(j = 0; j < 8; j++) { enc[j] = buf[j] ^ (rand() % 256); } if (enc[0] == (char)0x89 && enc[1] == (char)0x50 && enc[2] == (char)0x4E && enc[3] == (char)0x47 && enc[4] == (char)0x0D && enc[5] == (char)0x0A && enc[6] == (char)0x1A && enc[7] == (char)0x0A) { printf("%d\n", i); } } } }}} 結果，時刻は1416667590であることが判明したので復号を行ったところ次の画像が得られた。 {{attachment:crypt1.png}} これはRabin暗号である。nを素因数分解して秘密鍵を得て復号を行う。 {{{#!highlight ruby require_relative 'math' nn = [0xb8ae199365, 0xb86e78c811, 0x7bd4071e55] bb = [0xffeee, 0xfffee, 0xfefef] cc = [0x8d5051562b, 0x5ffa0ac1a2, 0x6008ddf867] for i in 0..2 n = nn[i] b = bb[i] c = cc[i] p, q= Math::prime_factorization2(n).map{|a|a[0]} puts [p,q].map{|a|a%4} for xx in 1..p if (xx * xx + b * xx - c)% p == 0 p (['!',xx]) x_p = xx end end for xx in 1..p if (xx * xx + b * xx - c)% q == 0 p (['!',xx]) x_q = xx end end puts ['%x' % (Math::chinese_remainder(p, q, x_p, x_q))].pack('H*') puts ['%x' % Math::chinese_remainder(p, q, p - b - x_p, x_q)].pack('H*') puts ['%x' % Math::chinese_remainder(p, q, p - b - x_p, q - b-x_q)].pack('H*') puts ['%x' % Math::chinese_remainder(p, q, x_p, q - b-x_q)].pack('H*') end }}} 暗号文に対して平文は4種類対応するため，その中から意味のあるものを採用する。 こうしてフラグが得られた。 {{{ SECCON{Ra_b1_N} }}} なお，WikipediaのRabin暗号のページに書かれていた式はコンテスト時点では間違っており， 平方根を求めるために\((p+1)/4\)乗すべきところが\((p-1)/2\)乗になっていた。 これでは二乗すると1になってしまう。 これに騙されたチームも多かったのではないだろうか。 === Pari/GP芸Pari/GPによる実装例 === 具体的な数字は最後のブロックだけ {{{ n=531838213717 b=1044463 c=412465625191 p=factor(n)[1,1] q=n/p xp = sqrt(c+Mod(b,p)*b/4)-Mod(b,p)/2 xq = sqrt(c+Mod(b,q)*b/4)-Mod(b,q)/2 x1 = chinese(xp, xq) x2 = chinese(-xp-b, xq) x3 = chinese(xp, -xq-b) x4 = chinese(-xp-b, -xq-b) }}} {{{ ? x1 = chinese(xp, xq) %8 = Mod(421735124605, 531838213717) ? x2 = chinese(-xp-b, xq) %9 = Mod(368810693940, 531838213717) ? x3 = chinese(xp, -xq-b) %10 = Mod(163026475314, 531838213717) ? x4 = chinese(-xp-b, -xq-b) %11 = Mod(110102044649, 531838213717) }}}