The Golden Gate (Programming 400pts)
ユニバーサル基板上にゲートICを10個と,スイッチとLEDを8個ずつ配置して実際に製作されたエンコーダーの写真が与えられた。
ゲートICは調べてみるとNANDゲートが4つ入っていることがわかる。 裏表の写真を行き来しながら接続を確認して回路図に落とした。 スイッチは押すと0になるものと1になる物両方存在している。
この回路図を元にプログラムを作成して動作をシミュレーションした。 結論から言えば,依存関係順に並べれば一度に計算を終わらせることも可能であったが, フリップフロップが含まれていて順序回路になっている可能性もあったため結果が安定するまで繰り返し計算するように実装した。 どちらが上位ビットなのかわからなかったため,切り替えられるようにしてある。 また,与えられたのはエンコーダであるから,結果を逆引きして平文を求めている。
1 #include <stdio.h>
2
3 #define UPPER 0
4
5 int nand(int x, int y) {
6 return !(x && y);
7 }
8
9 int gate[10][5];
10 unsigned char f(unsigned char x) {
11 int i;
12 int plus = 1;
13 #if UPPER
14 int sw1 = !(x & 0x80);
15 int sw2 = !(x & 0x40);
16 int sw3 = !!(x & 0x20);
17 int sw4 = !!(x & 0x10);
18 int sw5 = !(x & 0x08);
19 int sw6 = !!(x & 0x04);
20 int sw7 = !(x & 0x02);
21 int sw8 = !!(x & 0x01);
22 #else
23 int sw1 = !(x & 0x01);
24 int sw2 = !(x & 0x02);
25 int sw3 = !!(x & 0x04);
26 int sw4 = !!(x & 0x08);
27 int sw5 = !(x & 0x10);
28 int sw6 = !!(x & 0x20);
29 int sw7 = !(x & 0x40);
30 int sw8 = !!(x & 0x80);
31 #endif
32 for (i = 0; i < 100; i++) {
33 gate[1][1] = nand(sw1, gate[8][2]);
34 gate[1][2] = nand(gate[1][1], gate[8][2]);
35 gate[1][3] = nand(gate[1][1], sw1);
36 gate[1][4] = nand(gate[1][2], gate[1][3]);
37 gate[2][1] = nand(plus, gate[3][1]);
38 gate[2][2] = nand(gate[2][1], gate[3][2]);
39 gate[2][3] = nand(gate[2][2], gate[3][3]);
40 gate[2][4] = nand(gate[2][3], gate[3][4]);
41 gate[3][1] = nand(plus, sw3);
42 gate[3][2] = nand(sw3, gate[3][1]);
43 gate[3][3] = nand(gate[2][2], gate[6][2]);
44 gate[3][4] = nand(gate[3][3], gate[6][2]);
45 gate[4][1] = nand(sw2, gate[5][1]);
46 gate[4][2] = nand(gate[4][1], gate[5][2]);
47 gate[4][3] = nand(gate[8][2], gate[5][3]);
48 gate[4][4] = nand(gate[4][3], gate[5][4]);
49 gate[5][1] = nand(sw2, sw4);
50 gate[5][2] = nand(gate[5][1], sw4);
51 gate[5][3] = nand(gate[8][2], gate[6][2]);
52 gate[5][4] = nand(gate[5][3], gate[6][2]);
53 gate[6][1] = nand(sw2, gate[7][1]);
54 gate[6][2] = nand(gate[6][1], gate[7][2]);
55 gate[6][3] = nand(gate[4][2], gate[7][3]);
56 gate[6][4] = nand(gate[6][3], gate[7][4]);
57 gate[7][1] = nand(sw2, sw3);
58 gate[7][2] = nand(gate[7][1], sw3);
59 gate[7][3] = nand(sw6, gate[4][2]);
60 gate[7][4] = nand(gate[7][3], sw6);
61 gate[8][1] = nand(sw6, gate[9][1]);
62 gate[8][2] = nand(gate[8][1], gate[9][2]);
63 gate[8][3] = nand(gate[6][2], gate[9][3]);
64 gate[8][4] = nand(gate[8][3], gate[9][4]);
65 gate[9][1] = nand(sw6, sw8);
66 gate[9][2] = nand(gate[9][1], sw8);
67 gate[9][3] = nand(gate[6][2], sw5);
68 gate[9][4] = nand(gate[9][3], sw5);
69 gate[0][1] = nand(sw7, sw2);
70 gate[0][2] = nand(gate[0][1], sw2);
71 gate[0][3] = nand(sw7, gate[0][1]);
72 gate[0][4] = nand(gate[0][2], gate[0][3]);
73 }
74 int out1 = gate[1][4];
75 int out2 = gate[2][4];
76 int out3 = gate[2][2];
77 int out4 = gate[4][4];
78 int out5 = gate[0][4];
79 int out6 = gate[6][4];
80 int out7 = gate[4][2];
81 int out8 = gate[8][4];
82 x = 0;
83 #if UPPER
84 x |= out1 << 7;
85 x |= out2 << 6;
86 x |= out3 << 5;
87 x |= out4 << 4;
88 x |= out5 << 3;
89 x |= out6 << 2;
90 x |= out7 << 1;
91 x |= out8 << 0;
92 #else
93 x |= out1 << 0;
94 x |= out2 << 1;
95 x |= out3 << 2;
96 x |= out4 << 3;
97 x |= out5 << 4;
98 x |= out6 << 5;
99 x |= out7 << 6;
100 x |= out8 << 7;
101 #endif
102 x ^= 0xff;
103 return x;
104 }
105
106
107 unsigned char table[256];
108 void maketable() {
109 int c;
110 for (c = 0; c < 256; c++) {
111 int c2 = f(c);
112 table[c2] = c;
113 }
114 /*
115 for (c = 0; c < 256; c++) {
116 fprintf(stderr, "%02x ", table[c]);
117 if (c % 16 == 15)
118 fprintf(stderr, "\n");
119 }
120 fprintf(stderr, "\n");
121 //*/
122 }
123
124 int main(int argc, char **argv) {
125 int i, j;
126 for (i = 0; i < 10; i++) {
127 for (j = 0; j < 5; j++) {
128 gate[i][j] = 0;
129 }
130 }
131 maketable();
132 while (1) {
133 int c = getchar();
134 if (c == -1) break;
135 if (*argv[1] == 'd')
136 putchar(table[c]);
137 else
138 putchar(f(c));
139 }
140 }
これによりgzip圧縮されたフラグが得られた。
% make solve && ./solve d < ct | file - cc solve.c -o solve /dev/stdin: gzip compressed data, from Unix, last modified: Tue Nov 25 00:13:06 2014 % ./solve d < ct > result.gz % gzip -dc result.gz The flag is SECCON{Hlvd0toiXgloBhTM}
LEDが点灯するのは回路の出力が0になった時であることになかなか気づけなかった。