June 28, 2024
#math #crypto

2024.6.28 某(农信?)行业赛 Crypto 与 Misc

目录

Crypto

easyLCG

题目代码

 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

from Crypto.Util.number import *
from random import randint

FLAG = ?
ROUND = randint(200, 300)

class LCG:
    lcg_a = getPrime(498)
    lcg_b = getPrime(498)
    lcg_n = getPrime(512)

    def __init__(self, lcg_seed):
        self.state = lcg_seed

    def next(self):
        self.state = (self.state * self.lcg_a + self.lcg_b) % self.lcg_n
        return self.state

seed = bytes_to_long(FLAG)
print(seed.bit_length())
lcg = LCG(seed)
for _ in range(ROUND-6):
    lcg.next()
print([lcg.next() for _ in range(6)])

# 351
# [2485483242304449696161151168576736302336140244327446722677621064961717587947642623655706309294371876714311165214262071924932913930440142186509325733360885, 6174672247406972581092780254648964828729162316422924118545162215261641830776919624579500836375440017861960302702691972683448546062254126073514097080361044, 4584872703321313263026316988830140564935997972340636369234263637913498924218112980629201945528119162637762726584003527994733552009906632734086040880127542, 4829175497283310360340169484343201154685159906303099960915060755507745973302279262836696523131741537828200567942990339422885197644614494869008027862313162, 6669041483112643196441450289748743294802963984583343809912658359929976814854869038886397237458253328867571805574485994275429182399171275201561798677581761, 2732859498560958306654933055106793656103744294844703560692860713169132266734427400301681246251133210447387861776419850678194913478737337289544516324708390]

思路

比较基础的参数恢复后逆推 seed

flag 是初始 seed 的 bytes 形式, 且 seed 的 bit 长度为 $351$

同时分析代码中 class LCG 的 next() 有

1

self.state = (self.state * self.lcg_a + self.lcg_b) % self.lcg_n

且 $lcg_a, lcg_b, lcg_n$ 都是 prime 式子写的简单点

$$\text{state}_{i+1} = \text{state}_i * a + b \pmod n$$

逆向时

$$\text{state}_i * a = \text{state}_{i+1} - b \pmod n$$

$$\text{state}_i = (\text{state}_{i+1} - b) * a^{-1} \pmod n$$

或者

$$\text{state}_{i-1} = (\text{state}_i - b) * a^{-1} \pmod n$$

做了 $\text{ROUND}-6$ 次 next() 操作, 且最后 6 次的结果为 lcg_next_6 而 $\text{ROUND}$ 是在 $200-300$ 之间随机选取的, 恢复完参数后轻度暴力即可

Exploit

 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

from Crypto.Util.number import long_to_bytes, inverse, GCD, isPrime

seed_bit_length = 351
lcg_next_6 = [2485483242304449696161151168576736302336140244327446722677621064961717587947642623655706309294371876714311165214262071924932913930440142186509325733360885, 6174672247406972581092780254648964828729162316422924118545162215261641830776919624579500836375440017861960302702691972683448546062254126073514097080361044, 4584872703321313263026316988830140564935997972340636369234263637913498924218112980629201945528119162637762726584003527994733552009906632734086040880127542,
              4829175497283310360340169484343201154685159906303099960915060755507745973302279262836696523131741537828200567942990339422885197644614494869008027862313162, 6669041483112643196441450289748743294802963984583343809912658359929976814854869038886397237458253328867571805574485994275429182399171275201561798677581761, 2732859498560958306654933055106793656103744294844703560692860713169132266734427400301681246251133210447387861776419850678194913478737337289544516324708390]

x = lcg_next_6
t = []

for i in range(1, len(x)):
    t.append(x[i] - x[i-1])

n = 0
for i in range(1, len(t)-1):
    n = GCD(t[i+1]*t[i-1] - t[i]*t[i], n)

# GCD 次数不足(n 不为素数)时可以手动寻找因子
# n //= 2
print(f'n = {n}')
assert isPrime(n), 'n is not prime'
a = (x[3] - x[2]) * inverse(x[2] - x[1], n)
b = (x[2] - a * x[1]) % n

inva = inverse(a, n)
x1 = x[0]
for i in range(300):
    x1 = (x1 - b) * inva % n
    try:
        flag = long_to_bytes(x1)
        if b'DASCTF' in flag:
            print(flag)
    except Exception as err:
        print(err)
        continue

Output

1
2
3
4

"""
n = 7642858529392485624403081338250108535640074968325145472090548671095864994667289189097604333801954294420317959057026316661377130940078429076765670598241807
b'DASCTF{342232bd-3f4e-4a79-b38b-565e3242ef16}'
"""

ez_dp

题目代码

 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

from gmpy2 import *
from Crypto.Util.number import *
from secret import flag

m = bytes_to_long(flag)

def get_key():
    p = getPrime(1400)
    f = getRandomNBitInteger(1024)
    while True:
        q = getPrime(512)
        if gcd(f, q) != 1:
            continue
        else:
            break
    h = (invert(f, p) * q) % p
    return p, h

def encrypt1(m):
    p1 = getPrime(512)
    q = getPrime(512)
    e = 65537
    n = p1 * q
    d = invert(e, ((p1 - 1) * (q - 1)))
    dp = d % (p1 - 1)
    c1 = pow(m, e, n)
    s1 = dp
    print("n=", n)
    print("e=", e)
    print("c1=", c1)
    return s1

def encrypt2(msg, p, h):
    s = getRandomNBitInteger(512)
    c = (s * h + msg) % p
    return c

s = encrypt1(m)

p, h = get_key()
c = encrypt2(s, p, h)
print("p =", p)
print("h =", h)
print("c =", c)

'''
n= 110260074814257848908838625078501714960458516741889369726732143430937734210697873759425002497330033320466835750445829174684997535308856662838681041846947794426431497972796103034618905050690681625345580286974329394317326231752377513909290333601657981626779958969848432585669863801355518000831123865599294226787
c1= 87410783012997497089334969426735453553497110834602573140546865362447022991078781629894253455830313940054370072857581848649396014751510236334195667629699713694613970526418637921762179732923254584016634361975803026314654688055431785462894448431844588694708213156437494671986610728148872504904151549242154736587
p = 21012869988761718338002056668434640022381086646751731449032721137037733345551758802860184993656068733215079498246765657259553828250758201376752862965670037141641108407264413512347418547149638244577961647868099781047690086047340253092665472213200209122580168177065790399345363610449214898111612290510197602660551433726293151325348011730919876875489664094858613139260007122677438946422077569668626396394096578756269392219213
h = 6770491790682953636942614852064358677927258711756829789136991143125359571318236604881493887413710952826577625598345974890598833192705608538873219275181448971593360238243436263218203203262930354812832507464385245721509296553554707977362798787013782539283042526261689534233491245951252995706501115900819405349059258311900443901042496821340275234460907395830177886146041399137964230712722194756085629793582418840916735512277
c = 6132552687547528285732276436929419970961603850889618566398215255235030332018277282050536908271855446943919146591207662267815289943461335956844983042713305437715890977506659305069814807759223451215542538520079466091582962427203571721480729032807618768679976218582641269768441380693229147722826754954050492620043730436678935654351184167023259917544557009809604068417077921029798974332993383467713648518164609614847827656355
'''

思路

Exploit

正在烹饪ing

p-1高位攻击

题目质量还不错，考构造与对 Coppersmith 参数的理解

题目代码

SageMath’s Code

 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

import uuid
from Crypto.Util.number import *
from sage.all import *

flag = ("DASCTF{" + str(uuid.uuid4()) + "}").encode()
m = bytes_to_long(flag)
p,q = getPrime(256),getPrime(256)
phi = (q-1)*(p-1)
e = getPrime(256)
while True:
    e = next_prime(e)
    d = inverse_mod(e,phi)
    print(int((e*d-1)//phi).bit_length())
    if (e*d-1)//phi.bit_length() >= 120:
        ed1 = e*d - 1
        phi = (p-1)*(q-1)
        break
q_high = q >> 120 << 120
print(f'{p = }')
print(f"{q_high = }")
print(f'{e = }')
print(f'{d = }')
c = pow(m,d,p*q)
print(f"{c = }")
"""
p = 104972055463933479200574678219895894194023752029484798658224692242190851628301
q_high = 72503520013659319553438202098095419026840442742112803280959116977958759170048
e = 76798736050861087860251573138624328801131026809587391139129370361257176660643
d = 4516628399629928927666639239260422748934760909253970963332110111403362750325520573822831057720436368752480789235094323353455057451415359187266585002061707
c = 6270136250823720520545290554363376477855894636577767047522294947358559798810833186509641487748745519863674705966550753544189154739420020332172828310262938
"""

分析

一个小 bug

1

if (e*d-1)//phi.bit_length() >= 120:

这段代码似乎是想告诉玩家 $k$ 大于 $120$ bit，堵上爆破 $k$ 这条路，但出题人似乎搞错了符号优先级。实测这段代码含义是用 $k*\varphi$ 整除 $\varphi$ 的 bit 长。

做题思路：看到高位泄露很自然想到 Coppersmith，但这里 $e$ 又很大，且 $n$ 未知。同时 flag bit 长度大于 $p$ 的比特长，无法部分因子直接解密。利用给出的 $e,d$ 尝试与 $\varphi$ 建立联系，根据 RSA 的基本流程，我们有：

$$ e * d \equiv 1 \pmod {\varphi{(n)}} $$

转为等式：

$$ e * d - 1 = k * {\varphi{(n)}} $$

由于欧拉函数是积性函数，我们又有 $\varphi{(n)} = \varphi{(p)} * \varphi{(q)}$，而 $p$ 我们已知，且其为素数，则可以计算 $\varphi{(p)}$，即为 $p-1$。接着我们可以计算出 $k * \varphi{(q)}$，利用 Coppersmith 的强大能力，算法可以自己寻找真实的模，这时我们已经构造好了无幂运算的模下多项式，非常适合 Coppersmith 来求解。

参数选择

$\beta$ 参数在预估真实的模在 $k * \varphi{(q)}$ 中所占的比例后（$k$ 大于 $120$bit，后面实测大约 $255$ bit），辅以直觉设为 $0.49$ $X$ 参数为解的上限，很轻松的选为未知 bit 长度 $\epsilon$ 参数在其余参数设置正确且确认 Coppersmith 在本题数据有效时不断缩小即可

密码学是这样的，玩家只需要设定好参数就好了，而 Coppersmith 要考虑的事情就很多了~

咕咕咕，一定看 ch19

Exploit

SageMath’s Code

 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

from sage.all import *
from Crypto.Util.number import long_to_bytes

p = 104972055463933479200574678219895894194023752029484798658224692242190851628301
q_high = 72503520013659319553438202098095419026840442742112803280959116977958759170048
e = 76798736050861087860251573138624328801131026809587391139129370361257176660643
d = 4516628399629928927666639239260422748934760909253970963332110111403362750325520573822831057720436368752480789235094323353455057451415359187266585002061707
c = 6270136250823720520545290554363376477855894636577767047522294947358559798810833186509641487748745519863674705966550753544189154739420020332172828310262938

# 推导与构造
#         k*phi(p*q) | phi(p)
#         k*phi(p)*phi(q) | phi(p)
#         k * phi(q)
# 不懂为什么看到的 WP 要加这一步求 GCD, 他们的最大公约数就是 p - 1
# temp = GCD(e * d - 1, p - 1)
k_phi_q = (e * d - 1) // (p - 1)

PR = PolynomialRing(Zmod(k_phi_q), 'low_q')
low_q = PR.gen()
f = q_high + low_q - 1
fm = f.monic()
res = fm.small_roots(X=2^120, beta=0.49, epsilon=0.03)
for i in res:
    # print(k_phi_q % ZZ(f(i)))  # 0 则为 k 倍
    q = ZZ(f(i)) + 1
    n = p * q 

    # check k
    phi = (p - 1) * (q - 1)
    right_k = (e * d - 1) / phi
    print(f'check k: {right_k == k_phi_q // ZZ(f(i))}')
    
    m = power_mod(c, e, n)
    try:
        print(long_to_bytes(m))
    except Exception as error:
        print(error)

Output

1
2
3
4

"""
check k: True
b'DASCTF{81e5cb8c-d836-4372-b2aa-133f67a44e25}'
"""

Misc

XQR

看到群里在讨论此题，找 1cePeak 要了附件

有点猜…

放进 010 Editor 打开题目给的 PNG, 没发现什么有效信息 ExifTool 查看, 也没发现什么有效信息

开始大叫()

尝试 Stegsolve 打开, 查看 RGB 通道的 MSB, 发现 MSB 藏有数据(LSB 也有), Preview 时会有个很典的 PK 文件头, 命名 .zip 打开 可以解压得到 flag 文件, 但本身没什么有效信息 注意到压缩包有 60kb 左右, 而解压出的 flag 文件只有约 15kb 打开压缩包发现压缩包结束标志位后还有数据, 以及一个非常明显的 0x64 再往后还有一些数据, 不懂了, 卡了很久

开始大叫()

群里看到有人说是 XOR, 且只有一个字节的 key, 那就逐位 XOR 试试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def xor(data, key):
    return bytes([b ^ key for b in data])

data = open('flag', 'rb').read()
key = 0x64
ans = xor(data, key)

open('flag_xor', 'wb').write(ans)
# 开头为 IHDR, 分析大概是 PNG 文件
# https://www.freebuf.com/articles/others-articles/265879.html
# 与常规 PNG 文件比对后发现开头缺少 0x89 0x50 0x4E 0x47 0x0D
# 写入
open('flag_xor_add.png', 'wb').write(b'\x89PNG\x0D\x0A' + ans)

010 Editor 再次打开, 发现

1
2
3

"""
*ERROR: CRC Mismatch @ chunk[0]; in data: 3ee0fbfd; expected: 284e83cb
"""

使用 Deformed-Image-Restorer 修复 CRC 后, 得到可打开的半边图片, 看起来是个 QR Code, 结合群里看到的信息 这里笔者先生成了一个空的二维码将其拼接, 后面发现不如直接拼接刚开始的图片 将题目压缩包的二维码与刚刚得到的少半边图片拼接 尝试使用 QRazyBox 打开图片 右上角 Tools -> Extract QR Infomation, 得到

Output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

"""
QR version : 3 (29x29)
Error correction level : H
Mask pattern : 0
Number of missing bytes (erasures) : 0 bytes (0.00%)
Data blocks :
["00100000","10001100","00110010","01011011","01010011","10011001","10011111","00010111","00010100","11011011","10100001","01011001","00000100","01001000","00011110","01001000","11010110","01001000","01001100","01011111","00011101","01000000","01010111","11101100","11010001","00010001","11111011","10100001","00000000","01001011","10101100","01011111","11110101","11100111","11110110","11100011","11011110","00011010","00110010","00010101","11011100","00111111","00010101","01001011","01001010","00000010","00101110","11011001","10101101","01001001","11110001","00001010","10001101","01000111","01100001","11101110","00101001","01101011","01000000","00111001","01101011","11000111","01110110","11110010","10100110","01100100","11000010","11010011","11001110","10001011"]
Final data bits :
0010000000110010010100111001111100010100101000010000010000011110110101100100110000011101010101111101000110001100010110111001100100010111110110110101100101001000010010000100100001011111010000001110110000010001
[0010] [000000110] [010010100111001111100010100101000]
Mode Indicator : Alphanumeric Mode (0010)
Character Count Indicator : 6
Decoded data : DASCTF
[0100] [00010000] [01111011010010110010010011000001101110101010010111110100100011000100110001011011011100110110010001001011111011011011010110110010100100100001001001000010010010000101101111101000]
Mode Indicator : 8-bit Mode (0100)
Character Count Indicator : 16
Decoded data : {Y0u_F1nd_me!!!}
Final Decoded string : DASCTF{Y0u_F1nd_me!!!}
"""

约一年前看过 QR Code 的原理，忘了…

#math #crypto

Similar articles: