椭圆曲线签名算法 | 网鼎杯20241029青龙组 | Crypto2
2024年11月2日约 1417 字大约 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)