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

肿圬后 · 2025-8-2 22:16:57

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 curve
FLAG = b"flag{????????????????????????????}"
def Add(P, Q):
x3 = (P[0] * Q[0] + D * P[1] * Q[1]) % p
y3 = (P[0] * Q[1] + P[1] * Q[0]) % p
return (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 // 2
return Q
def 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 unpad
D = 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 - 1
N2 = A[0] ** 2 - D * A[1] ** 2 - 1
N3 = B[0] ** 2 - D * B[1] ** 2 - 1
g = 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
[code]from Crypto.Cipher import AESfrom Crypto.Util.number import *from Crypto.Util.Padding import padfrom hashlib import sha512flag = b'flag{hello_test_flag}'mask1 = 211151158277430590850506190902325379931mask2 = 314024231732616562506949148198103849397mask3 = 175840838278158851471916948124781906887mask4 = 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 * mask_bin for i in range(128)]) & 1 R_bin = + 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 = 0 R1_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

账号		自动登录	找回密码
密码			立即注册

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

浏览过的版块

签约作者