网鼎杯20241029青龙组 | Crypto2

undefined2024年11月2日约 1409 字大约 5 分钟

原题

import gmpy2
import random
import binascii
from hashlib import sha256
from sympy import nextprime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from FLAG import flag
#flag = 'wdflag{123}'
 
def victory_encrypt(plaintext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = plaintext.upper()
    ciphertext = ''
 
    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char
 
    return ciphertext
 
victory_key = "WANGDINGCUP"
victory_encrypted_flag = victory_encrypt(flag, victory_key)
 
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
a = 0
b = 7
xG = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
yG = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = (xG, yG)
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
h = 1
zero = (0,0)
 
dA = nextprime(random.randint(0, n))
 
if dA > n:
    print("warning!!")
 
def addition(t1, t2):
    if t1 == zero:
        return t2
    if t2 == zero:
        return t2
    (m1, n1) = t1
    (m2, n2) = t2
    if m1 == m2:
        if n1 == 0 or n1 != n2:
            return zero
        else:
            k = (3 * m1 * m1 + a) % p * gmpy2.invert(2 * n1 , p) % p
    else:
        k = (n2 - n1 + p) % p * gmpy2.invert((m2 - m1 + p) % p, p) % p
    m3 = (k * k % p - m1 - m2 + p * 2) % p
    n3 = (k * (m1 - m3) % p - n1 + p) % p
    return (int(m3),int(n3))
 
def multiplication(x, k):
    ans = zero
    t = 1
    while(t <= k):
        if (k &t )>0:
            ans = addition(ans, x)
        x = addition(x, x)
        t <<= 1
    return ans
 
def getrs(z, k):
    (xp, yp) = P
    r = xp
    s = (z + r * dA % n) % n * gmpy2.invert(k, n) % n
    return r,s
 
z1 = random.randint(0, p)
z2 = random.randint(0, p)
k = random.randint(0, n)
P = multiplication(G, k)
hA = multiplication(G, dA)
r1, s1 = getrs(z1, k)
r2, s2 = getrs(z2, k)
 
print("r1 = {}".format(r1))
print("r2 = {}".format(r2))
print("s1 = {}".format(s1))
print("s2 = {}".format(s2))
print("z1 = {}".format(z1))
print("z2 = {}".format(z2))
 
key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv
encrypted_flag = cipher.encrypt(pad(victory_encrypted_flag.encode(), AES.block_size))
encrypted_flag_hex = binascii.hexlify(iv + encrypted_flag).decode('utf-8')
 
print("Encrypted flag (AES in CBC mode, hex):", encrypted_flag_hex)
 
# output
# r1 = 86806104739558095745988469033305523200538774705708894815836887970976487278764
# r2 = 86806104739558095745988469033305523200538774705708894815836887970976487278764
# s1 = 93400851884262731807098055393482657423555590196362184363643455285862566867372
# s2 = 58741027521216057788923508334695668250013849866589902683641825341545919891746
# z1 = 47591695289461307212638536234394543297527537576682980326526736956079807805586
# z2 = 97911075901954715147720917205165523174582665086645698292621371632896283314804
# ('Encrypted flag (AES in CBC mode, hex):', u'86cd24e2914c0c4d9b87bea34005a98bd8587d14cae71909b917679d3328304e7915e6ba4cad1096faa4a85bc52f8056d3f21ef09516be8a5160f1b338a6b936')

步骤一：安装缺失运行库

# 创建虚拟环境，防止污染本机环境
python3 -m venv venv
source ./venv/bin/activate
# pip安装运行库
pip install gmpy2 sympy pycryptodome

步骤二：分析加密代码实现

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC)
iv = cipher.iv
encrypted_flag = cipher.encrypt(pad(victory_encrypted_flag.encode(), AES.block_size))
encrypted_flag_hex = binascii.hexlify(iv + encrypted_flag).decode('utf-8')

题目提供给我们的是encrypted_flag_hex，我们要获取flag，需要先得到encrypted_flag.

encrypted_flag_hex = u'86cd24e2914c0c4d9b87bea34005a98bd8587d14cae71909b917679d3328304e7915e6ba4cad1096faa4a85bc52f8056d3f21ef09516be8a5160f1b338a6b936'
encrypted_flag_bytes = binascii.unhexlify(encrypted_flag_hex)
iv = encrypted_flag_bytes[:AES.block_size]
encrypted_flag = encrypted_flag_bytes[AES.block_size:]

我们需要获得victory_encrypted_flag的值，也就需要：

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)

victory_encrypted_flag = unpad(cipher.decrypt(encrypted_flag), AES.block_size).decode('utf-8')

这里需要dA的值，而dA在这里定义:

dA = nextprime(random.randint(0, n))

首先生成一个在 0 到 n 之间的随机整数，然后找到大于这个随机整数的下一个质数，并将其赋值给变量dA. 如果要求得dA，就要求得k的值。

步骤三：计算得到`k`值

先看看原函数如何包装k值：

首先，生成范围为(0, n)的随机整数k.

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
k = random.randint(0, n)

然后生成范围为(0, p)的随机整数z1, z2.

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
z1 = random.randint(0, p)
z2 = random.randint(0, p)

z1, z2均已给出输出值。

然后将k, z1, z2分别传入getrs()函数。并输出r1, s1, r2, s2.

r1, s1 = getrs(z1, k)
r2, s2 = getrs(z2, k)

现在已经明白了k是如何被一步步包装成六个变量的，可以根据代码逐步的逆向运算得到k值。

首先，r1, s1, r2, s2指向了一个getrs()函数，我们可以分析一下这个函数。

def getrs(z, k):
    (xp, yp) = P
    r = xp
    s = (z + r * dA % n) % n * gmpy2.invert(k, n) % n
    return r,s

此函数的(xp, yp) = P指向了P = multiplication(G, k).我们可以分析一下multiplication()函数。

def multiplication(x, k):
    ans = zero
    t = 1
    while(t <= k):
        if (k &t )>0:
            ans = addition(ans, x)
        x = addition(x, x)
        t <<= 1
    return ans

这个函数的某些变量指向了addition()函数，我们继续看一下这段函数。

def addition(t1, t2):
    if t1 == zero:
        return t2
    if t2 == zero:
        return t2
    (m1, n1) = t1
    (m2, n2) = t2
    if m1 == m2:
        if n1 == 0 or n1 != n2:
            return zero
        else:
            k = (3 * m1 * m1 + a) % p * gmpy2.invert(2 * n1 , p) % p
    else:
        k = (n2 - n1 + p) % p * gmpy2.invert((m2 - m1 + p) % p, p) % p
    m3 = (k * k % p - m1 - m2 + p * 2) % p
    n3 = (k * (m1 - m3) % p - n1 + p) % p
    return (int(m3),int(n3))

通过这几段有关椭圆函数的运算可以推断出k是使用椭圆曲线数字签名算法（ECDSA）加密的。可参考一文看懂椭圆曲线签名算法 - 知乎进行求解k值。

k = (z1 - z2) * gmpy2.invert(s1 - s2, n) % n

步骤四：计算得到`dA`值

根据之前的分析，可以逆向得到dA.

dA = (s1 * k - z1) * gmpy2.invert(r1, n) % n

步骤五：反推函数得到`victory_encrypted_flag`

阅读“步骤二”可得victory_encrypted_flag的逆向代码。

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)

victory_encrypted_flag = unpad(cipher.decrypt(encrypted_flag), AES.block_size).decode('utf-8')

运行后得到输出值为SDSRDO{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}，这并不是正确flag格式。

步骤六：得到正确`flag`

仔细阅读代码，可以发现victory_encrypted_flag由victory_encrypt()函数得到。

def victory_encrypt(plaintext, key):
    key = key.upper()
    key_length = len(key)
    plaintext = plaintext.upper()
    ciphertext = ''
 
    for i, char in enumerate(plaintext):
        if char.isalpha():
            shift = ord(key[i % key_length]) - ord('A')
            encrypted_char = chr((ord(char) - ord('A') + shift) % 26 + ord('A'))
            ciphertext += encrypted_char
        else:
            ciphertext += char
 
    return ciphertext
 
victory_key = "WANGDINGCUP"
victory_encrypted_flag = victory_encrypt(flag, victory_key)

我们反推victory_encrypt()得到victory_decrypt()

def victory_decrypt(ciphertext, key):
	key = key. upper()
	key_length = len(key)
	ciphertext = ciphertext. upper()
	plaintext = ''
	
	for i, char in enumerate(ciphertext):
		if char.isalpha():
			shift = ord(key[i % key_length]) - ord('A')
			decrypted_char = chr((ord(char) - ord('A') - shift +26)% 26 + ord('A'))
			plaintext += decrypted_char
		else:
			plaintext += char
	
	return plaintext

通过victory_decrypt()可以得到大写的FLAG，将其转换成小写flag即可。

完整实现源码

import binascii
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
import gmpy2

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
r1 = 86806104739558095745988469033305523200538774705708894815836887970976487278764
r2 = 86806104739558095745988469033305523200538774705708894815836887970976487278764
s1 = 93400851884262731807098055393482657423555590196362184363643455285862566867372
s2 = 58741027521216057788923508334695668250013849866589902683641825341545919891746
z1 = 47591695289461307212638536234394543297527537576682980326526736956079807805586
z2 = 97911075901954715147720917205165523174582665086645698292621371632896283314804
k = (z1 - z2) * gmpy2.invert(s1 - s2, n) % n
dA = (s1 * k - z1) * gmpy2.invert(r1, n) % n

encrypted_flag_hex = u'86cd24e2914c0c4d9b87bea34005a98bd8587d14cae71909b917679d3328304e7915e6ba4cad1096faa4a85bc52f8056d3f21ef09516be8a5160f1b338a6b936'
encrypted_flag_bytes = binascii.unhexlify(encrypted_flag_hex)
iv = encrypted_flag_bytes[:AES.block_size]
encrypted_flag = encrypted_flag_bytes[AES.block_size:]

key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)

victory_encrypted_flag = unpad(cipher.decrypt(encrypted_flag), AES.block_size).decode('utf-8')

def victory_decrypt(ciphertext, key):
	key = key. upper()
	key_length = len(key)
	ciphertext = ciphertext. upper()
	plaintext = ''
	
	for i, char in enumerate(ciphertext):
		if char.isalpha():
			shift = ord(key[i % key_length]) - ord('A')
			decrypted_char = chr((ord(char) - ord('A') - shift +26)% 26 + ord('A'))
			plaintext += decrypted_char
		else:
			plaintext += char
	
	return plaintext
 
victory_key = "WANGDINGCUP"
flag = victory_decrypt(victory_encrypted_flag, victory_key)

print(flag)