H&NCTF2025 Crypto

Crypto

lcgp

常规的LCG问题，

观察函数generate

1
2
3
def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m  # %代表取余运算
        return self.seed

输入seed，获得一个新的seed \[ seed = a\cdot seed + b \pmod{m} \] 接着循环了5次，产生了5次种子

换而言之，我们需要利用这5个种子，求出一开始的种子

不妨设，一开始的seed为x1，然后我们写成数列的形式 \[ 已知x_2,x_3,...x_{5},x_{n+1}=ax_n+b\mod m,求x_1 \] 接着来看算法的关键

\[ x_{n+1}=ax_n + b \mod m \]

这里面a，b，m都是未知的，b好处理，因为在常数的位置，两个式子相减就能消掉

考虑

\[ x_{n+2}-x_{n+1}=a(x_{n+1}-x_{n}) \mod m \]

这时候，我们以\(x_{n+1}-x_{n}\)作为一个新数列，那么这时候只剩下两个未知数了

设\(y_n =x_{n+1}-x_n\)

那么\(y_{n+1}=ay_n \mod m\)

于是构造了一个等比数列

$$ \[\begin{align} y_{n+1}=ay_n \mod m\ y_{n+2}=ay_{n+1} \mod m \end{align}\] $$

说到等比数列，等比中项就是一个有趣的性质，那么，对于这个同余的等比数列，是否有着等比中项呢，可以一试

\[ y_{n+2}y_n \equiv ay_ny_{n+1} \equiv y_{n+1}^2 \mod m \]

a消失了，那么此时，只剩下m这一个未知数

把同余式写成等式

\[ y_{n+1}^2 = y_ny_{n+2} + km \]

可以求出k1m,k2m,等等

如果两个k没有公因数的话，那么m就是它们的最大公因数

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *
y = []
km = []
possiblem = []
for i in range(4):
    y.append(x[i+1]-x[i])
for j in range(2):
    km.append(y[j+1]*y[j+1]-y[j]*y[j+2])
    if j >= 1:
        if isPrime(GCD(km[j],km[j-1])): 
            possiblem.append(GCD(km[j],km[j-1]))

这样我们就得到了可能为m的possiblem

1
17685238729089629081000199791073775580173848219782600577303616658328942786376878589055722139055973814631247947507009292556525580971952751595622172013382374577299734041726162411213993858497140178230251563824957482883763872967881950049985507310408962206729214890421322185752340466578359217999838551622613116097987673746844913920603425686103175874552686869764028906518131374266999714020645422015426801070343771422250037085635856203202935123956520415086942807824199018302630540169113637093488756273183240186533936637562954227188102214396705205042491881526862572569275650908415160529650027016717502470758797514488134766043

只有一个，这非常好，既然m求出来了，那么就可以求a了

\[ a \equiv y_{n+1}y_{n}^{-1} \mod m \]

1
a = y[1]*inverse(y[0],m) % m

我们先考虑求出a之后如何解决

$$ \[\begin{align} x_2 - x_3 \equiv a(x_1 - x_2) \pmod m \ x_1 \equiv a^{-1}(x_2-x_3) + x_2 \pmod m \end{align}\] $$

1
2
x_1 = (x[0] + inverse(a,m)*(x[0]-x[1])) % m 
print(long_to_bytes(x_1))

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
y = []
km = []
possiblem = []
for i in range(4):
    y.append(x[i+1]-x[i])
for j in range(2):
    km.append(y[j+1]*y[j+1]-y[j]*y[j+2])
    if j >= 1:
        if isPrime(GCD(km[j],km[j-1])): 
            possiblem.append(GCD(km[j],km[j-1]))
m = 17685238729089629081000199791073775580173848219782600577303616658328942786376878589055722139055973814631247947507009292556525580971952751595622172013382374577299734041726162411213993858497140178230251563824957482883763872967881950049985507310408962206729214890421322185752340466578359217999838551622613116097987673746844913920603425686103175874552686869764028906518131374266999714020645422015426801070343771422250037085635856203202935123956520415086942807824199018302630540169113637093488756273183240186533936637562954227188102214396705205042491881526862572569275650908415160529650027016717502470758797514488134766043
a = y[1]*inverse(y[0],m) % m
print(a)
x_1 = (x[0] + inverse(a,m)*(x[0]-x[1])) % m 
print(long_to_bytes(x_1))

哈基coke

逆向Arnold即可

exp:

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
import numpy as np
import cv2

def arnold_decode(encoded_image, shuffle_times, a, b):
    """
    Arnold逆变换解密图像
    
    参数:
        encoded_image: 加密后的图像
        shuffle_times: 加密时使用的迭代次数
        a, b: 加密时使用的参数
        
    返回:
        解密后的图像
    """
    decoded_image = np.zeros(shape=encoded_image.shape)
    h, w = encoded_image.shape[0], encoded_image.shape[1]
    N = h  # 假设图像是正方形
    
    # 计算逆变换的参数
    det = (1 * (a*b + 1) - b * a)  # 行列式值
    inv_det = pow(det, -1, N)  # 模逆元
    
    # 逆变换矩阵
    inv_a = (a*b + 1) * inv_det % N
    inv_b = (-b) * inv_det % N
    inv_c = (-a) * inv_det % N
    inv_d = 1 * inv_det % N
    
    for time in range(shuffle_times):
        for new_x in range(h):
            for new_y in range(w):
                # 计算原始位置
                ori_x = (inv_a * new_x + inv_b * new_y) % N
                ori_y = (inv_c * new_x + inv_d * new_y) % N
                
                decoded_image[ori_x, ori_y, :] = encoded_image[new_x, new_y, :]
        
        encoded_image = np.copy(decoded_image)
    
    return decoded_image

# 使用示例
if __name__ == "__main__":
    # 读取加密后的图像
    encrypted_img = cv2.imread(r"C:\Users\infinite\Desktop\python\hnctf\en_flag.png")
    
    # 解密参数必须与加密时一致
    a = 9
    b = 1
    shuffle_times = 6  # 加密时使用的迭代次数
    
    # 解密图像
    decrypted_img = arnold_decode(encrypted_img, shuffle_times, a, b)
    
    # 保存解密后的图像
    cv2.imwrite('decrypted_flag.png', decrypted_img, [int(cv2.IMWRITE_PNG_COMPRESSION), 0])
    
    print("图像解密完成，已保存为 decrypted_flag.png")
img

为什么出题人的rsa总是ez

分为两个挑战

part1涉及到common prime的生成

$$ h_1 = p+bq

h_2 = ap+q $$

注意到

\[ h_1h_2=ap^2+pq+abpq+bq^2 \equiv ap^2+bq^2 \mod n \]

注意到

\[ ap = h_2 -q \ bq =h_1-p \]

那么

\[ h_1h_2 \equiv h_2p-pq+h_1q-pq \equiv h_2p+h_1q \mod n \]

注意到p,q相对于n来说都是小根,可以考虑作为短向量

构造

\[ L = \begin{pmatrix} n & 0 & 0 & 0 \ h_1h_2 & 1 & 0 & 0 \ -h_2 & 0 & 1 & 0 \ -h_1& 0 & 0 &1\end{pmatrix} \]

那么

\[ (k,1,p,q)L = (0,1,p,q) \]

就得到了一个短向量

使用LLLcvp

1
2
3
4
5
6
7
8
9
10
11
12
13
from sage.all import *
from Crypto.Util.number import long_to_bytes
from lll_cvp import solve_inequality
L = matrix([[n, 0, 0, 0], [h1 * h2, 1, 0, 0], [-h2, 0, 1, 0], [-h1, 0, 0, 1]])
lb = [0, 1, 0, 0]
ub = [0, 1, 2**1024, 2**1024]
sol = solve_inequality(L, lb, ub)
_, _, p, q = map(int, sol)
assert p * q == n
phi = (p - 1) * (q - 1)
d = pow(0x10001, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

得到flag{e_is_xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix,bubbleBabble}

提示了bubbleBabble加密

用网站解码得到

e = 81733668723981020451323

part2 特殊素数生成

common prime已知g

强网杯的题，稍微修改一下

第八届强网杯-wp_第八届强网杯wp-CSDN博客

里ezrsa的脚本

exp:

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
h = (N - 1) // g

u = h // g

v = h % g
def Solve_c():
    sqrt_N = int(sqrt(N))
    C = sqrt_N//g^2
    a = 2
    b = pow(a,g,N)

    for i in range(2,C):
        D = (int(sqrt(C)) + 1) * i
        final = pow(int(b),int(u),int(N))
        tmp = 1
        gs = pow(int(b), int(D), N)
        for r in tqdm(range(D)):
            for s in range(D):
                #if powmod(int(b),int(r*D+s),N) == final:
                if tmp == final:
                    print("r =",r,"s =",s,"i =",i)
                    return r * D + s
                tmp = (tmp * int(b)) % N
c = Solve_c()
A = u - c  # x * y = u - c

B = v + c * g  # x + y = v + c * g

delta = iroot((B * B - 4 * A), 2)[0]

x = (B + delta) // 2

y = (B - delta) // 2

a = x // 2

b = y // 2

p = 2 * g * a + 1

q = 2 * g * b + 1

d = invert(e, (p - 1) * (q - 1))

m = powmod(C, d, N)

print(long_to_bytes(m))

数据处理

简单的求个离散对数

然后这里数字被替换了

直接遍历一遍所有组合，爆破就行了

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from tqdm import *
Z = Zmod(2^512)
m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399
new_flag=str(discrete_log(Z(c), Z(m)))
lowercase = '0123456789' 
uppercase = '7***4****5' 
from itertools import permutations
for i in tqdm(permutations("0123689")):
    up = f"7{''.join(i[:3])}4{''.join(i[3:])}5"
    table = ''.maketrans(up, lowercase) 
    flag = new_flag.translate(table)
    try:
        res = (long_to_bytes(int(flag)).decode())
        if res.startswith("H&NCTF"):
            print(res)
    except:
        pass

ezfactor

注意到 \[ hint = kp+r \] 其中k是512位，r是248位，r远远小于hint

那么我们有 \[ hint - r \equiv 0\mod p \] r是一个小根，使用CopperSmith慢慢调参数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
R = 2^248  # r 的上界
e=0x10001
P.<x> = PolynomialRing(Zmod(N))
f = hint -x
f = f.monic()
# r = f.small_roots(X=R, beta=0.495, epsilon=0.015)[0] 
# print("Found r =", r)
r = 310384729555967603261671853388867753979360895944109353196595111340924855459
p = gcd(hint - r, N)
q = N // p
assert p * q == N
print("Found p =", p)
print("Found q =", q)
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,N)
print(long_to_bytes(m))

ez-factor-pro

后面只是障眼法，关键还是求r

这里r变成了252位，怎么调参发现都不太行

所以考虑爆破几位r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
R = 2^252  # r 的上界
e=0x10001
P.<x> = PolynomialRing(Zmod(N))
high_bits = 12 #爆破高位
X = 2^(rbits - high_bits) - 1  

for high in trange(2^high_bits,-1,-1):
    r_high = high << (rbits - high_bits)
    
    # 多项式：hint - (r_high + x) ≡ 0 mod p
    P.<x> = PolynomialRing(Zmod(N))
    f = hint - (r_high + x)
    f = f.monic()
    roots = f.small_roots(X, beta=0.495, epsilon=0.03)
    
    if roots:
        r_low = roots[0]
        r = r_high + r_low
        print(f"Found r = {r}")
        break

得到r，后面就没什么了

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
r = 7166351305785506670352015492214713707534657162937963088592442157834795391917
c = "476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37"
c = bytes.fromhex(c)
leak=N*r
p = gcd(hint - r, N)
q = N // p
r_bytes = long_to_bytes(leak)
iv = r_bytes[:16] if len(r_bytes) >= 16 else r_bytes + b'\0'*(16-len(r_bytes))
key = sha256(str(p + q + r).encode()).digest()[:16] 
crypt_sm4 = CryptSM4()
crypt_sm4.set_key(key, SM4_DECRYPT) 
decrypted = crypt_sm4.crypt_cbc(iv, c)  
flag = unpad(decrypted, 16)
print("Flag:", flag.decode())

Three vertical lines

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *
from secret import flag
from rsa.prime import getprime
while(1):
    p=getprime(256)
    q=getprime(256)
    if isPrime(3*p**5+4*q**5):
        print(3*p**5+4*q**5)
        break

e = 65537
print(pow(bytes_to_long(flag), e, p * q))
#72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
#2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223

给了一个 \[ 3p^5+4q^5=h \] 对于这种齐次式子，常见的做法就是消元 \[ p = aq \mod h \] 那么就有 \[ 3a^5+4 \equiv 0\mod h \] 我们求出这个a之后，就可以造格子了因为 \[ \begin{pmatrix} p & a \\ 0 & 1 \end{pmatrix}\begin{pmatrix}k\\q\end{pmatrix}=\begin{pmatrix}p\\q\end{pmatrix} \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
h=72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
P.<x> = PolynomialRing(Zmod(h))
f = 3*x^5+4
a = f.roots()[0][0]
# print((Integer(iroot(h,5)[0])).nbits())
L = matrix(ZZ,[[h,0],[a,1]])
res=L.LLL()[0]
p,q = res
p,q = abs(p),abs(q)
n = p*q
c=2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223
e = 65537
phi = (p-1)*(q-1)
d= inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))