点击此处获得更好的阅读体验
WriteUp来源
题目考点
解题思路
libdivination.so里其实就做了循环左移/右移和异或的操作,算法还原如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14k = 1
for(i=3;i<129;i+=2){
for(j=3;j<12;j+=2){
if(!(i%j)) {
continue;
}
}
if(k) {
result ^=RotateLeft(input, i);
} else {
result ^=RotateRight(input, i);
}
k = !k;
}
无法通过简单逆推求flag,这里涉及有限域的知识。对256bit的数做循环移位和异或分别等价于在有限域GF(2^256)上做乘法和加法的操作,因此我们可以将对该数所做的操作抽象成有限域中的一个元素,对这个元素在有限域上取逆即为相应的逆操作,对结果做逆操作即为原始数值。
求解脚本如下:
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
typedef boost::multiprecision::uint256_t uint256;
// flag{YoU\C4n/s01Ve%f1Nite_F1e1d}
//unsigned char key[32] = {0x5a,0x4e,0xd7,0x16,0xd8,0x3d,0x04,0x7a,0x30,0xcf,0x0f,0xc6,0x56,0x5a,0x64,0x88,0x19,0x1b,0x70,0xbf,0x7d,0xd4,0x48,0x25,0xde,0xd0,0xac,0xf1,0x26,0x45,0x76,0xe7};
unsigned char key[32] = {0x34,0x39,0xa7,0x64,0xbd,0x4d,0x7d,0x12,0x5e,0xb8,0x7f,0xb4,0x33,0x2a,0x1d,0xe0,0x77,0x6c,0x00,0xcd,0x18,0xa4,0x31,0x4d,0xb0,0xa7,0xdc,0x83,0x43,0x35,0x0f,0x8f};
unsigned char arr[] = {254,253,252,248,247,245,244,243,241,239,238,237,232,231,230,229,228,227,226,223,220,219,218,217,215,214,213,209,208,207,205,199,197,194,193,190,188,187,186,182,180,176,171,169,163,162,161,160,158,156,155,154,153,146,144,141,139,137,135,131,130,129,127,125,122,120,117,114,111,107,103,102,101,100,99,98,97,94,93,92,89,88,87,86,85,78,73,72,71,69,66,62,61,59,58,57,54,52,51,50,49,48,47,46,44,41,39,36,35,34,32,31,30,29,28,24,23,22,17,15,14,13,12,9,6,2,0};
uint256 lrol(uint256 c,unsigned int b)
{
uint256 left=c<<b;
uint256 right=c>>(256-b);
uint256 temp=left|right;
return temp;
}
int main()
{
int i;
uint64_t *p, x=0x687970657270776e;
char *c;
p = (uint64_t *)key;
for(i=0;i<4;i++){
p[i]^=x;
}
uint256 n=-1;
memset(&n,0,32);
memcpy(&n, key, 32);
uint256 m=0;
for(i=0;i<sizeof(arr);i++){
m ^= lrol(n, arr[i]);
}
c = (char*)&m;
puts(c);
for(i=0;i<32;i++){
putchar(c[31-i]+4);
}
putchar('\n');
return 0;
}
其中,arr数组为逆操作,推导的脚本如下:
1
2
3
4
5
6#!/usr/bin/env python
# coding=utf-8
from pyfinite import ffield
F = ffield.FField(256, gen=2**256+1, useLUT=0)
x = 1 + 2**13 + 2**(256-17) + 2**19 + 2**(256-23) + 2**29 + 2**(256-31) + 2**37 + 2**(256-41) + 2**43 + 2**(256-47) + 2**53 + 2**(256-59) + 2**61 + 2**(256-67) + 2**71 + 2**(256-73) + 2**79 + 2**(256-83) + 2**89 + 2**(256-97) + 2**101 + 2**(256-103) + 2**107 + 2**(256-109) + 2**113 + 2**(256-127)
print(F.ShowPolynomial(F.Inverse(x)))
Flag
1
flag{YoU\C4n/s01Ve%f1Nite_F1e1d}