第四届网鼎杯 青龙组 Crypto02 WriteUP
Last updated
Was this helpful?
Last updated
Was this helpful?
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')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) % nvictory_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)Note Contributors： and me