0x01 题目

image-20221013180119116

附件📎：LCG-Revenge.zip

0x02 解题

附件中有两个文件：

  • task.py 加密脚本
  • output.txt 输出数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import *
from secret import FLAG
p = getPrime(128)
step = len(FLAG) // 3
xs = [bytes_to_long(FLAG[:step]), bytes_to_long(FLAG[step:2*step]), bytes_to_long(FLAG[2*step:])]
a = getPrime(64)
b = getPrime(64)
c = getPrime(64)
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517

for _ in range(10):
    new_state = (a*xs[0] + b*xs[1] + c*xs[2]) % p 
    xs = xs[1:] + [new_state]
    #print(xs)
print(xs)
print(a, b, c, p)
1
2
[255290883651191064919890629542861653873, 221128501895959214555166046983862519384, 108104020183858879999084358722168548984]
18038175596386287827 15503291946093443851 17270168560153510007 307956849617421078439840909609638388517

0x0201 分析加密脚本

1
2
3
4
5
from Crypto.Util.number import *
from secret import FLAG
p = getPrime(128)
step = len(FLAG) // 3
xs = [bytes_to_long(FLAG[:step]), bytes_to_long(FLAG[step:2*step]), bytes_to_long(FLAG[2*step:])]

这一步将flag分成三等份，由bytes_to_long转换位数字，用于加密计算。

1
2
3
4
5
6
7
a = getPrime(64)
b = getPrime(64)
c = getPrime(64)
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517

给出a、b、c、p的数值

1
2
3
for _ in range(10):
    new_state = (a*xs[0] + b*xs[1] + c*xs[2]) % p 
    xs = xs[1:] + [new_state]

这一步就是简单的LCG加密步骤了，将三等份的flag分步用abc相乘，然后相加取模。

xs = xs[1:] + [new_state]这一步相当于一个队列，将flag的第一部分丢掉，在队尾插入新的new_state。

0x0202 解密脚本

通过分析，可以看出最后输出的xs就是加密完之后的三串数字，只需要一个一个往前推算，就可以算出一开始的xs数组。

设

$n$ = new_state,

$a$ = a,

$b$ = b,

$c$ = c,

$x_1$ = xs[0],

$x_2$ = xs[1],

$x_3$ = xs[2],

$p$ = p

由原式：
$$
n = (a\cdot x_1+b\cdot x_2+c\cdot x_3)mod\space p
$$
可得:
$$
x_1 = (a^{-1}(n-b\cdot x_2-c\cdot x_3))mod\space{p}
$$

注：$a^{-1}$为$a$关于模$p$的模逆元。

以此类推可以推出最初开始运算的三等份flag。

最终脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
xs=[
    # 211953980103675814981551589541062177303,
    255290883651191064919890629542861653873,
    221128501895959214555166046983862519384,
    108104020183858879999084358722168548984,
    ]
#new_state = (a*xs[0] + b*xs[1] + c*xs[2]) % p
# xs1 = 255290883651191064919890629542861653873
# xs2 = 221128501895959214555166046983862519384
# new_state = 108104020183858879999084358722168548984
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517
MMI = lambda A, n,s=1,t=0,N=0: (n < 2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n),-1)[n<1]#模逆运算
a_1 = MMI(a,p) #a相对于模数p的逆元
for _ in range(10):
    xs0 = (a_1*(xs[2]-b*xs[0]-c*xs[1])) % p
    xs = [xs0] + xs[:2]
print(xs)
print((a*xs[0] + b*xs[1] + c*xs[2]) % p)
print(long_to_bytes(xs[0])+long_to_bytes(xs[1])+long_to_bytes(xs[2]))

image-20221013182348378