第四届“网鼎杯”网络安全大赛青龙组 Crypto WriteUp

CRYPTO01

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
n = p * q
d = getPrime(299)
e = inverse(d,(p-1)*(q-1))
m = bytes_to_long(flag)
c = pow(m,e,n)
hint1 = p >> (512-70)
hint2 = q >> (512-70)

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"hint1 = {hint1}")
print(f"hint2 = {hint2}")

n = 102986063343828181691017061322961752231482650979117614592328540336319559999419987417702811972323418742113520151888629472567603955481992514927285801019993715247868027388036294100323295206260750653997980051233409135844852567338000284382992259587294344858347675971990058869658603742150067210112531948312675289517
e = 94332227188033251470419190704216678578924281824166571884737945076375866824249376355159909654478713223003101525619990336866998705667204377661713202948952171655143192075943578946573888576484746209261469970149381872389631389369537155026693263975338398261567274837717090694055171425503933824240291370948820767571
c = 84437879482958388121051989985943610317985560730924629180079819055930253313815835352959163593476985818700482462237552702247843204909498317690512763185777267125647066466604295815291929505489611365030554559376546705541333232100362213541469056985011640358767366350305910694542127597286950765375388740496062563517
hint1 = 737132842226563731129
hint2 = 1083219649182192077965

和上个月打的SCTF中Signin那题一样的思路 SCTF 2024 Crypto WriteUp

\begin{array} ed = 1 mod(p-1)(q-1) \\ ed = 1+k(p-1)(q-1) \\ 其中 p = p_{high} + p_{low} \\ q = q_{high} + q_{low} \\ 所以 e*d = 1+k*(n-(p_{high}+q_{high})-(p_{low}+q_{low})+1)\\ 因为e很大，d.bit=299，n.bit=e.bit，所以k.bit = 299 \\ 令s = (p_{low}+q_{low})，s.bit=512-70=443 \\ 上二元copper \end{array}

import itertools
from sage.all import *

n = 102986063343828181691017061322961752231482650979117614592328540336319559999419987417702811972323418742113520151888629472567603955481992514927285801019993715247868027388036294100323295206260750653997980051233409135844852567338000284382992259587294344858347675971990058869658603742150067210112531948312675289517
e = 94332227188033251470419190704216678578924281824166571884737945076375866824249376355159909654478713223003101525619990336866998705667204377661713202948952171655143192075943578946573888576484746209261469970149381872389631389369537155026693263975338398261567274837717090694055171425503933824240291370948820767571
c = 84437879482958388121051989985943610317985560730924629180079819055930253313815835352959163593476985818700482462237552702247843204909498317690512763185777267125647066466604295815291929505489611365030554559376546705541333232100362213541469056985011640358767366350305910694542127597286950765375388740496062563517
hint1 = 737132842226563731129
hint2 = 1083219649182192077965


def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	if isinstance(f, Polynomial):
		x, = polygens(f.base_ring(), f.variable_name(), 1)
		f = f(x)

	R = f.base_ring()
	N = R.cardinality()
	
	f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficient_matrix()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []



p_h = hint1 << (512-70)
q_h = hint2 << (512-70)
R.<k,s> = PolynomialRing(Zmod(e))
f = 1+k*(n-(p_h+q_h)-s+1)
bounds=(2^299,2^442)
print(small_roots(f , bounds , m=3 , d=4))

得到 $s=(p_{low}+q_{low})=$9550178615344700914680629079025067847696951426770132671301164698245456687003654693629604604208743524263711750791129602421650031009422

列方程组求 $p$ 和 $q$

# 导入必要的库
from sage.all import *

# 已知的数值
n = 102986063343828181691017061322961752231482650979117614592328540336319559999419987417702811972323418742113520151888629472567603955481992514927285801019993715247868027388036294100323295206260750653997980051233409135844852567338000284382992259587294344858347675971990058869658603742150067210112531948312675289517
hint1 = 737132842226563731129
hint2 = 1083219649182192077965
sum_of_low_bits = 9550178615344700914680629079025067847696951426770132671301164698245456687003654693629604604208743524263711750791129602421650031009422

# 将 hint 扩展到 512 位
p_high = hint1 << (512 - 70)
q_high = hint2 << (512 - 70)

# 定义低位变量
p_low_bits = var('p_low_bits')
q_low_bits = var('q_low_bits')

# 构造 p 和 q 的完整表示
p = p_high + p_low_bits
q = q_high + q_low_bits

# 构造方程组
eq1 = p * q == n
eq2 = p_low_bits + q_low_bits == sum_of_low_bits

# 使用 SageMath 的求解器来求解方程组
solution = solve([eq1, eq2], p_low_bits, q_low_bits)

# 输出结果
if len(solution) > 0:
    p_low_solution = solution[0][0].rhs()
    q_low_solution = solution[0][1].rhs()
    p_value = p_high + p_low_solution
    q_value = q_high + q_low_solution
    print(f"Found p: {p_value}")
    print(f"Found q: {q_value}")
else:
    print("No solution found.")

解RSA

from Crypto.Util.number import *

p = 12301968561617489464815050947766830293114620865458225788140524305916037841132536540947500706435198484135356575495711684836395758643449054231737718416631877
q = 8371510854380475760171492071954527819328254117130991402450088629039514773535702565532229588993733813828621162046243254767866899527502246818456584983541321
n = 102986063343828181691017061322961752231482650979117614592328540336319559999419987417702811972323418742113520151888629472567603955481992514927285801019993715247868027388036294100323295206260750653997980051233409135844852567338000284382992259587294344858347675971990058869658603742150067210112531948312675289517
e = 94332227188033251470419190704216678578924281824166571884737945076375866824249376355159909654478713223003101525619990336866998705667204377661713202948952171655143192075943578946573888576484746209261469970149381872389631389369537155026693263975338398261567274837717090694055171425503933824240291370948820767571
c = 84437879482958388121051989985943610317985560730924629180079819055930253313815835352959163593476985818700482462237552702247843204909498317690512763185777267125647066466604295815291929505489611365030554559376546705541333232100362213541469056985011640358767366350305910694542127597286950765375388740496062563517

phi = (p-1)*(q-1)
assert GCD(e,phi)==1
d = inverse(e,phi)
m = pow(c, d, n)  
print(long_to_bytes(int(m)))

CRYPTO02

# coding: utf-8
#!/usr/bin/env python2

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 = 79874160726532694994695169930412771917232180361879898603881940022649943683773
# r2 = 79874160726532694994695169930412771917232180361879898603881940022649943683773
# s1 = 29358608937016239753744265269188516080175172712689524937715100977220465955435
# s2 = 67554961634695394998835343503747996265453236901689755090159384880221643931064
# z1 = 111511522136129031618364434769531873844221489323948711851532783654702149742966
# z2 = 47212724661755436010060930908038151157054551065082199607150851950104041315615
# ('Encrypted flag (AES in CBC mode, hex):', u'103fb6abfe2757b21f6f9ce6901af904cee9f46ce8adb7d42d0c52e968c6bb5ba0bd2b526db879c5e1fd2f452a2bb67eba3f45fac530f43d878408a763e900eb')

根据已知的 $r1, r2, s1, s2, z1, z2$ ，我们可以推导出 $k$ 的值。根据 ECDSA 的签名生成过程，我们有以下关系：

$r=(k⋅G)_x\mod n$

$s=(z+r⋅dA)⋅k^{-1}\mod n$

因此，我们可以写出：

$s1=(z1+r1⋅dA)⋅k^{-1}\mod n$

$s2=(z2+r2⋅dA)⋅k^{-1}\mod n$

从上面的两个方程中，我们可以解出 $k$ 的值。

首先，我们可以通过以下方程消去 $dA$ ：

$s_1⋅k\equiv z_1+r_1⋅dA\mod n$

$s_2⋅k\equiv z_2+r_2⋅dA\mod n$

两式相减得：

$s_1⋅k-s_2⋅k\equiv z_1+r_1⋅dA-(z_2+r_2⋅dA)\mod n$

$(s_1-s_2)⋅k\equiv(z_1-z_2)+(r_1-r_2)⋅dA\mod n$

因为 $r_1$ 和 $r_2$ 相同，所以上式简化为：

$(s_1-s_2)⋅k\equiv(z_1-z_2)\mod n$

$k\equiv(z_1-z_2)⋅(s_1-s_2)-1\mod n$

from sympy import mod_inverse
# 已知值
r1 = 79874160726532694994695169930412771917232180361879898603881940022649943683773
r2 = 79874160726532694994695169930412771917232180361879898603881940022649943683773
s1 = 29358608937016239753744265269188516080175172712689524937715100977220465955435
s2 = 67554961634695394998835343503747996265453236901689755090159384880221643931064
z1 = 111511522136129031618364434769531873844221489323948711851532783654702149742966
z2 = 47212724661755436010060930908038151157054551065082199607150851950104041315615
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

# 计算 k
delta_z = (z1 - z2) % n
delta_s = (s1 - s2) % n

# 计算 delta_s 的模逆元
inverse_delta_s = mod_inverse(delta_s, n)

# 计算 k
k = (delta_z * inverse_delta_s) % n
print("k =", k)

得到了k，现在我们可以利用已知的 $r_1$ ， $s_1$ ， $z_1$ ，和 $k$ 来计算私钥 $dA$

$s_1=(z_1+r_1·dA)·k^{-1}\mod n$

$s_1·k\equiv z_1+r_1·dA\mod n$

$dA\equiv (s_1·k-z_1)·r_1^{-1}$

temp = (s1 * k - z1) % n
inverse_r1 = mod_inverse(r1, n)
dA = (temp * inverse_r1) % n
print("dA =", dA)

解AES

victory_encrypted_flag = "103fb6abfe2757b21f6f9ce6901af904cee9f46ce8adb7d42d0c52e968c6bb5ba0bd2b526db879c5e1fd2f452a2bb67eba3f45fac530f43d878408a763e900eb"
encrypted_flag = binascii.unhexlify(victory_encrypted_flag)
iv = encrypted_flag[:16]
ciphertext = encrypted_flag[16:]
key = sha256(long_to_bytes(dA)).digest()
cipher = AES.new(key, AES.MODE_CBC,iv=iv)
decrypted_flag = unpad(cipher.decrypt(ciphertext), AES.block_size)
print(decrypted_flag)

解位移密码

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 + ord('A'))
            plaintext += decrypted_char
        else:
            plaintext += char
    return plaintext

victory_key = "WANGDINGCUP"
flag = victory_decrypt(decrypted_flag.decode(), victory_key)
print(flag.lower())