1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
int __cdecl main(int argc, const char **argv, const char **envp)
{
int v3; // edi
int v4; // eax
int v6; // esi
int v7; // eax
char v9[64]; // [esp+8h] [ebp-40h] BYREF
memset(v9, 0, sizeof(v9));
printf("Input:");
gets(v9);
v3 = -1;
v4 = 0;
if ( !v9[0] )
goto LABEL_20;
do
{
if ( v4 >= 64 )
break;
if ( v9[v4] == '-' )
v3 = v4;
}
while ( v9[++v4] );
if ( v3 > 0
&& (v6 = v4 - v3, v4 - v3 > 0)
&& bn_init_str(&x, v9, v3, a0123456789abcd) > 0
&& bn_init_str(&y, &v9[v3 + 1], v6 - 1, a0123456789abcd) > 0
&& (bn_init_str(&n, aIrtzloz6iub, strlen(aIrtzloz6iub), a0123456789abcd),
bn_set_int(&v1, 0),
bn_set_int(&v2, 0),
bn_cmp(&x, &y) < 0)
&& bn_cmp(&x, &n) < 0
&& bn_cmp(&y, &n) < 0 )
{
v7 = 0;
while ( 1 )
{
loop_conut = v7 + 1;
bn_add(&v1, &v1, &x);
bn_add(&v2, &v2, &y);
bn_mod(&v1, &v1, &n);
bn_mod(&v2, &v2, &n);
bn_set_int(&tmp1, 1);
bn_sub(&tmp1, &v1, &tmp1);
if ( !bn_cmp(&tmp1, &x) )
{
++correctvar;
bn_mul(&tmp1, &tmp1, &x);
}
bn_set_int(&tmp2, 1);
bn_add(&tmp2, &v2, &tmp2);
if ( !bn_cmp(&tmp2, &y) )
{
++correctvar;
bn_div(&tmp2, &n, &y);
}
if ( correctvar == 10 )
break;
v7 = loop_conut;
if ( loop_conut >= 0x200000 )
goto LABEL_20;
}
printf("Success!\n");
return 0;
}
else
{
LABEL_20:
printf("Error.\n");
return 0;
}
}
main函数的明逻辑很简单：给出两个小于n且不相等的整数x和y，统计 (x*loop_count - 1) % n == x 和 (y*loop_count + 1) % n == y 的次数，要求随着loop_count增大至少满足10次。
这两个等式稍微变形即可得到 x*(loop_count-1) = k1 * n + 1 和 y * (loop_count+1) = k1*n - 1，因此 x 和 y 都要与 n 互质
如果想找到两个不同的 loop_count 满足同一个等式，即 x*(loop_count1-1) == 1 (mod n) 且 x*(loop_count2-1) == 1 (mod n)，相减后得到 x * (loop_count2 - loop_count1) == 0 (mod n)，即 n 整除 x * (loop_count2 - loop_count1)。
由于 x 与 n 互质，所以只能是 n 整除 loop_count2 - loop_count1，这意味着在满足一次等式条件后，需要至少再累加 n 次 x 才能再次满足等式，显然超过了限制，因此仅从表面逻辑看，题目似乎是无解的。
其实很多bn_函数内部都有一些奇怪的操作，例如很多无用的对tmp1和tmp2的操作；但是值得注意的是 bn_mul 和 bn_div 中有对 n 的引用，摘抄如下：
这里 n.s[tmp2.s[0]] 访问的是 n.s[32]，即 0x40A9D0+4+32 = 0x40A9F4，是 loop_count 变量；n.s[tmp1.s[0]] 访问的是 n.s[36]，即 0x40A9D0+4+36 = 0x40A9F4，是 correctvar 变量。
所以，如果通过了 main 函数里明逻辑的等式使得 correctvar 加 1 时的 loop_count 等于 32，这部分暗逻辑会把 correctvar 再加上 4，所以才有可能达到明逻辑里 correctvar 等于 10 的最终要求。
如果限定 loop_count == 32，则等式约束变为了 x*(32-1) = k1*n + 1 和 y*(32+1) = k2*n - 1。稍微遍历一下 k1 和 k2 的值使得 31 整除 k1*n + 1 和 33 整除 k2*n - 1，得到 k1 = 12，k2 = 18，从而 x = 3870967741935483871，y = 6129032258064516129，且满足 x < y < n 的约束。
重新编码回去，得到程序正确的输入为 ZSxZerX4xb4-jyvP7x12lI7。
（p.s. 利用越界写隐藏暗逻辑的思路很新颖，而且确实不太容易被发现。这种难度在往年估计都是中后段的题目了，今年竟然才到第二题）
（再p.s. 下一道题，看到出题战队是ArmVMP就很劝退）
如有侵权请联系:admin#unsafe.sh