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

from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from hashlib import sha512


flag = b'flag{hello_test_flag}'

mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103


def 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)]) & 1
    R_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 = 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 << 1) + temp
    return out

print()
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] = 1
    for i in range(128):
        mat[0, i] = int(mask_bin[i])
    return mat

LFSR1, 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}