Decrypt it (Easy) (Crypto 200pts)
バイナリを読んだ結果,概ね次のような動作をすることがわかった。
ファイルの最終更新日時を中心に時刻の探索を行った。
1 #include <stdlib.h>
2 #include <stdio.h>
3 char buf[10];
4 int main() {
5 FILE *fp = fopen("ecrypt1.bin","r");
6 fread(buf, 8, 1, fp);
7 int i,j,cnt=0;
8 for(i = 1416606360+100000; i > 1416606360-1000000; i--) {
9 srand(i);
10 char enc[10];
11 for(j = 0; j < 8; j++) {
12 enc[j] = buf[j] ^ (rand() % 256);
13 }
14 if (enc[0] == (char)0x89 &&
15 enc[1] == (char)0x50 &&
16 enc[2] == (char)0x4E &&
17 enc[3] == (char)0x47 &&
18 enc[4] == (char)0x0D &&
19 enc[5] == (char)0x0A &&
20 enc[6] == (char)0x1A &&
21 enc[7] == (char)0x0A) {
22 printf("%d\n", i);
23 }
24 }
25 }
結果,時刻は1416667590であることが判明したので復号を行ったところ次の画像が得られた。
これはRabin暗号である。nを素因数分解して秘密鍵を得て復号を行う。
1 require_relative 'math'
2 nn = [0xb8ae199365, 0xb86e78c811, 0x7bd4071e55]
3 bb = [0xffeee, 0xfffee, 0xfefef]
4 cc = [0x8d5051562b, 0x5ffa0ac1a2, 0x6008ddf867]
5 for i in 0..2
6 n = nn[i]
7 b = bb[i]
8 c = cc[i]
9
10 p, q= Math::prime_factorization2(n).map{|a|a[0]}
11 puts [p,q].map{|a|a%4}
12
13 for xx in 1..p
14 if (xx * xx + b * xx - c)% p == 0
15 p (['!',xx])
16 x_p = xx
17 end
18 end
19 for xx in 1..p
20 if (xx * xx + b * xx - c)% q == 0
21 p (['!',xx])
22 x_q = xx
23 end
24 end
25
26 puts ['%x' % (Math::chinese_remainder(p, q, x_p, x_q))].pack('H*')
27 puts ['%x' % Math::chinese_remainder(p, q, p - b - x_p, x_q)].pack('H*')
28 puts ['%x' % Math::chinese_remainder(p, q, p - b - x_p, q - b-x_q)].pack('H*')
29 puts ['%x' % Math::chinese_remainder(p, q, x_p, q - b-x_q)].pack('H*')
30 end
暗号文に対して平文は4種類対応するため,その中から意味のあるものを採用する。
こうしてフラグが得られた。
SECCON{Ra_b1_N}
なお,WikipediaのRabin暗号のページに書かれていた式はコンテスト時点では間違っており, 平方根を求めるために\((p+1)/4\)乗すべきところが\((p-1)/2\)乗になっていた。 これでは二乗すると1になってしまう。 これに騙されたチームも多かったのではないだろうか。
<del>Pari/GP芸</del>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)