一、LCG加密原理

qq_pic_merged_1742380840794

解密公式

IMG_20250319_184011

解题记录

NSSCTF

babyLCG

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
from Crypto.Util.number import *
import gmpy2
'''
from secret import flag
m = bytes_to_long(flag)
bit_len = m.bit_length()
a = getPrime(bit_len)
b = getPrime(bit_len)
p = getPrime(bit_len+1)

seed = m
result = []
for i in range(10):
    seed = (a*seed+b)%p
    result.append(seed)
print(result)

'''
result = [699175025435513913222265085178805479192132631113784770123757454808149151697608216361550466652878, 193316257467202036043918706856603526262215679149886976392930192639917920593706895122296071643390, 1624937780477561769577140419364339298985292198464188802403816662221142156714021229977403603922943, 659236391930254891621938248429619132720452597526316230221895367798170380093631947248925278766506, 111407194162820942281872438978366964960570302720229611594374532025973998885554449685055172110829, 1415787594624585063605356859393351333923892058922987749824214311091742328340293435914830175796909, 655057648553921580727111809001898496375489870757705297406250204329094679858718932270475755075698, 1683427135823894785654993254138434580152093609545092045940376086714124324274044014654085676620851, 492953986125248558013838257810313149490245209968714980288031443714890115686764222999717055064509, 70048773361068060773257074705619791938224397526269544533030294499007242937089146507674570192265]


t = []
for i in range(9):
    t.append(result[i+1]-result[i])#计算一阶差分
for i in range(7):
    p = gmpy2.gcd((t[i+1]*t[i-1]-t[i]*t[i]),(t[i+2]*t[i]-t[i+1]*t[i+1]))#计算二阶差分并求取最大公因数p即为模m
    try:
        #建立方程组求取a,b
        a = gmpy2.invert(result[8]-result[7],p)*(result[9]-result[8])%p
        b = (result[9]-result[8]*a)%p
        seed = (result[0]-b)*gmpy2.invert(a,p)%p
        print(long_to_bytes(seed))
    except:
        continue