当前位置：首页 > news >正文

CCF IVC 2025“汽车安全攻防赛” -- Crypto -- WriteUp

news 2025/8/3 14:33:40

CCF IVC 2025“汽车安全攻防赛” – Crypto – WriteUp

Curve

task

import random
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Curve import curveFLAG = b"flag{????????????????????????????}"def Add(P, Q):x3 = (P[0] * Q[0] + D * P[1] * Q[1]) % py3 = (P[0] * Q[1] + P[1] * Q[0]) % preturn (x3, y3)def C_multiplication(P, n):Q = (1, 0)while n > 0:if n % 2 == 1:Q = Add(Q, P)P = Add(P, P)n = n // 2return Qdef get_key():private_key = random.randint(1, p - 1)public_key = C_multiplication(G, private_key)return (public_key, private_key)def get_shared_secret(P, n_k):return C_multiplication(P, n_k)[0]curve_info = curve()
p = curve_info["p"]
D = curve_info["D"]
G = (curve_info["G.x"], curve_info["G.y"])
A, n_a = get_key()
B, n_b = get_key()print("D =", D)
print("G =", G)
print("A =", A)
print("B =", B)
shared_secret = get_shared_secret(A, n_b)key = sha256(long_to_bytes(shared_secret)).digest()
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(FLAG, 16))
print("C =", ciphertext.hex())# D = 841
# G = (1100598635269059922265259097431205826869659019985617812588900225256796699368319232, 269583433230904539404618502954816143916504972586573484672290485092817854594102981)
# A = (522493413431164541763578890114416187756743905387601370337657937604705331138537817, 1508871699477090073528276437418263853138631109882880455850153282479682759269308568)
# B = (775700026584506740810283787673112405277484661261929762130750879159326080315752049, 164554371563691962332379023518848094645187895772638009983860665200242350372953279)
# C = 7727ceae1edbfa37f913e09b44c10e6fa846891f4b520c87d829fc55299b1f02621af77a1f1f1107d1159c4088250834

analysis

过程分析：
$设定曲线x^2-841y^2=1mod\ p;选取随机数n\_a,n\_b,计算A=P * n\_a,B = P * n\_b\\ output = G,A,B;key = (A * n\_b).x$
根据其曲线加法函数ADD的特殊性，我们可以推断出曲线的完整方程，相较于以往的曲线题目，这里覆盖了模数p。在求解下述内容之前，寻找到正确的模数p就是我们工作的重中之重。
我们可以根据曲线方程转化之后的结果使p的倍数进行分析，经过结果取最大公因数之后，我们可以再进行分解，求解得到大于这三个结果的素数作为p即可。此处可以通过检验p - 1光滑为下述高效求解提供证明。
注意此处的D = 841 = 29 ** 2,这就为我们进行离散对数求解所需值n_b进行了提示和很高的可行性，针对于求解n_b之后，我们就可以进行key的计算以及flag的求解了。

exp

from hashlib import sha256
from Crypto.Util.number import long_to_bytes
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpadD = 841
G = (1100598635269059922265259097431205826869659019985617812588900225256796699368319232, 269583433230904539404618502954816143916504972586573484672290485092817854594102981)
A = (522493413431164541763578890114416187756743905387601370337657937604705331138537817, 1508871699477090073528276437418263853138631109882880455850153282479682759269308568)
B = (775700026584506740810283787673112405277484661261929762130750879159326080315752049, 164554371563691962332379023518848094645187895772638009983860665200242350372953279)
C = "7727ceae1edbfa37f913e09b44c10e6fa846891f4b520c87d829fc55299b1f02621af77a1f1f1107d1159c4088250834"def compute_p():"""由曲线方程可知N1, N2, N3均为p的倍数"""N1 = G[0] ** 2 - D * G[1] ** 2 - 1N2 = A[0] ** 2 - D * A[1] ** 2 - 1N3 = B[0] ** 2 - D * B[1] ** 2 - 1g = gcd(N1, N2)g = gcd(g, N3)factors = factor(g)p_candidates = [f for f, _ in factors if f > max(G[0], G[1], A[0], A[1], B[0], B[1])]return max(p_candidates)p = compute_p()
print(f"Computed prime p = {p}")
print(f"Is prime? {is_prime(p)}")Fp = GF(p)
g_val = Fp(G[0] + 29 * G[1])
b_val = Fp(B[0] + 29 * B[1])
a_val = Fp(A[0] + 29 * A[1])# 检验p - 1是否光滑
factors = factor(p - 1)
print("\nFactorization of p-1:")
print(factors)# 离散对数求解
n_b = discrete_log(b_val, g_val, operation='*')
print(f"\nSolved n_b = {n_b}")assert g_val**n_b == b_val, "Discrete log solution is incorrect"z = a_val ** n_b
z_inv = z ** -1
shared_secret_x = (z + z_inv) / Fp(2)key = sha256(long_to_bytes(int(shared_secret_x))).digest()
key = key.hex()
print(f"The key is: {key}")key = bytes.fromhex(key)
ciphertext = bytes.fromhex(C)cipher = AES.new(key, AES.MODE_ECB)
decrypted_padded = cipher.decrypt(ciphertext)flag = unpad(decrypted_padded, 16)print(flag)
# flag{c728026f-8c2d-4687-8f1e-db3229caf517}

nfsr

task

from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from hashlib import sha512flag = b'flag{hello_test_flag}'mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103def lfsr(R, mask):R_bin = [int(b) for b in bin(R)[2:].zfill(128)]mask_bin = [int(b) for b in bin(mask)[2:].zfill(128)]s = sum([R_bin[i] * mask_bin[i] for i in range(128)]) & 1R_bin = [s] + R_bin[:-1]return (int("".join(map(str, R_bin)), 2), s)def ff(x0, x1, x2, x3):return (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)def round(R, R1_mask, R2_mask, R3_mask, R4_mask):out = 0R1_NEW, _ = lfsr(R, R1_mask)R2_NEW, _ = lfsr(R, R2_mask)R3_NEW, _ = lfsr(R, R3_mask)R4_NEW, _ = lfsr(R, R4_mask)for _ in range(256):R1_NEW, x1 = lfsr(R1_NEW, R1_mask)R2_NEW, x2 = lfsr(R2_NEW, R2_mask)R3_NEW, x3 = lfsr(R3_NEW, R3_mask)R4_NEW, x4 = lfsr(R4_NEW, R4_mask)temp = ff(x1, x2, x3, x4)print(temp, end = "\t")if _ % 10 == 0 and _ != 0:print()out = (out << 1) + tempreturn outprint()
key = getRandomNBitInteger(128)
out = round(key, mask1, mask2, mask3, mask4)
cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
print(out)
print(cipher.encrypt(pad(flag, 16)))
# 68014145798558789680147296296059748493170180017159509061459191404846898978879
# b'\x9c\xaf\x89\x98\x90<\xdf\xe8\xef\xd7\x06\x9c\xf1\xb0\x1c3\xcc\x12\xab\xdc\x0e\xfa/\x1b\x95\xe8\xd6\xa9a\xe6\x86"\x18\x86q|\xfa\xa6\xf9\xed\xe7\x80G\x16a\x18\x04\xcb'

analysis

nfsr问题，但是根据题目提示以及task代码部分，先后对于单个的lfsr，单个的lfsr流密码生成的过程变得简单了些，但是约束条件进行了混淆。ff函数的相应功能与正常的lfsr类似。
针对于此，我们先进行了测试，打出一部分真值表进行比对。此后转化该函数为bool函数，这个时候为了获取得到关键数据key进行解密，task转化为获得其相应的二进制位。思路如下：
找到一个由式子x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4得到的bool函数，使其乘积为0的时候得到相应的约束条件。如果out中某一位为1的时候，搜集这些等式的解。
由于相应的key的数据与循环次数并不相等的缘故，如果循环次数改为300次，则可以稳定预测该nfsr，针对于这道题，我们需要kernel爆破部分内容。

exp

from Crypto.Util.number import *
from hashlib import sha512
from Crypto.Cipher import AES
from sage.all import *mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103
out = 68014145798558789680147296296059748493170180017159509061459191404846898978879
c = b'\x9c\xaf\x89\x98\x90<\xdf\xe8\xef\xd7\x06\x9c\xf1\xb0\x1c3\xcc\x12\xab\xdc\x0e\xfa/\x1b\x95\xe8\xd6\xa9a\xe6\x86"\x18\x86q|\xfa\xa6\xf9\xed\xe7\x80G\x16a\x18\x04\xcb'def trans(mask):mask_bin = bin(mask)[2:].zfill(128)mat = Matrix(Zmod(2), 128, 128)for i in range(127):mat[i + 1, i] = 1for i in range(128):mat[0, i] = int(mask_bin[i])return matLFSR1, LFSR2, LFSR3, LFSR4 = trans(mask1), trans(mask2), trans(mask3), trans(mask4)
out = bin(out)[2:].zfill(256)L = []
for i in range(len(out)):if(out[i] == "1"):L.append((LFSR1 ** (i + 2) + LFSR2 ** (i + 2) + LFSR4 ** (i + 2))[0])
L = Matrix(Zmod(2), L)
M = L.solve_right(vector(Zmod(2), [1 for i in range(out.count("1"))]))
sol = list(L.right_kernel().basis())for i in range(len(sol)):k = M + L.right_kernel().basis()[i]k = int("".join(map(str,k)), 2)cipher = AES.new(long_to_bytes(k), mode = AES.MODE_ECB)print(cipher.decrypt(c))
# flag{41fe9100-0ac8-4869-9193-69a5a047c060}