青龙
crypto001
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}")
已知 p,q 高位的bd_attack，纯原题了，详解可以参考 2023 CryptoCTF-Insights 一题
CryptoCTF -Insights
Van1sh，公众号：Van1sh2023 CryptoCTF（二）
crypto002
# 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)
题目是一个很明显的套娃题，先用维吉尼亚密码把 flag 加密（密钥已知），然后又用 ECDSA 对两条消息做了一个签名，其中临时密钥重用，并且签名私钥的哈希又用作了 AES 的加密密钥，加密了 前面的 flag 密文。
所以解题步骤也是显而易见。先是临时密钥重用攻击获取 ECDSA 签名私钥，然后对密文 AES解密，维吉尼亚解密，就可以了。
临时密钥重用攻击
s = (z + r * dA % n) % n * gmpy2.invert(k, n) % n
签名公式
其中 已知， 不变
所以
# sagemath
r1 =
r2 =
s1 =
s2 =
z1 =
z2 =
k = (z1-z2)/(s1-s2) % n
d = (s1*int(k)-z1) / int(r1) % n
AES 解密
c = ''
c = bytes.fromhex(c)
iv = c[:16]
c = c[16:]
key = sha256(long_to_bytes(d)).digest()
cipher = AES.new(iv= iv, key=key, mode = AES.MODE_CBC)
victory_encrypted_flag = cipher.decrypt(c)
维吉尼亚解密，+ shift 改成 – shift 就好了。
def victory_decrypt(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"
key_length=len(victory_key)
victory_encrypted_flag = ''
flag = victory_decrypt(victory_encrypted_flag, victory_key)
print(flag.lower())
白虎
crypto01
from sage.all import *
from Crypto.Util.number import *
block_size = 64
rounds = 14
P_permutation = Permutations(list(range(block_size))).random_element()
inverse_P_permutation = [P_permutation.index(i) for i in range(block_size)]
MASK = 0b1110001001111001000110010000100010101111101100101110100001001001
IV = 7
b2i = lambda x: Integer(sum([x[i] * 2**i for i in range(len(x))]))
def pad(x):
padlen = block_size - len(x) % block_size
return x + bytes([padlen] * padlen)
def P(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = [bit_x[P_permutation[i]] for i in range(block_size)]
return b2i(bit_x)
def P_inv(x):
bit_x = x.bits()
if len(bit_x) < block_size:
bit_x.extend([0] * (block_size - len(bit_x)))
bit_x = [bit_x[inverse_P_permutation[i]] for i in range(block_size)]
return b2i(bit_x)
def S(x):
x1 = x
x2 = x << IV & MASK
x3 = x << IV & ((1 << block_size) - 1) | MASK
return x1 ^ x2 ^ x3
def encrypt(message_block, key):
ret = message_block
for i in range(rounds):
ret = P_inv(S(P(ret)) ^ key)
return ret
from secret import flag
from hashlib import md5
message = pad(flag)
message = [Integer(bytes_to_long(message[i:i+8])) for i in range(0, len(message), 8)]
key = int(md5(flag).hexdigest(), 16) & ((1 << block_size) - 1)
ciphertext = [encrypt(m, key) for m in message]
print(ciphertext)
print(P_permutation)
注意到 encrypt 函数里除了 P 和 P_inv 是非线性置换，剩下的 S 和 密钥异或都是线性操作。然后每一轮的 P 和 P_inv 又都相互抵消，只留一个最开始的 P 和最后的 P_inv。
这里又知道一组明文（flag的格式，外加爆破一个字节）和密文，那我们就先对明文 P 一个，再对密文 P 一个，然后添加约束条件， ，就齐活了。
from z3 import *
def encryptwhithoutP(message_block, key):
ret = message_block
for i in range(rounds):
ret = (S(ret) ^ key)
return ret
m=
c=
key = BitVec("key",64)
s = Solver()
s.add(encryptwhithoutP(P(m),key) == P(c))
if s.check() == sat:
m = s.model()
print(m)
有了一个密钥，再用同样的方法把明文约束出来就行了。
crypto02
from Crypto.Util.number import getPrime, isPrime, GCD, inverse
nbits = 2048
gbits = 1000
g = getPrime(int(gbits))
while True:
a = getPrime(int(nbits*0.5)-gbits)
p = 2*g*a + 1
if isPrime(p):
break
while True:
b = getPrime(int(nbits*0.5)-gbits)
q = 2*g*b + 1
if p!=q and isPrime(q):
break
N = p*q
e = 65537
def str2int(s):
return int(s.encode('latin-1').hex(),16)
def int2str(i):
tmp=hex(i)[2:]
if len(tmp)%2==1:
tmp='0'+tmp
return bytes.fromhex(tmp).decode('latin-1')
with open('pubkey.txt','w') as f:
f.write(str(e)+'n')
f.write(str(N)+'n')
with open('flag.txt') as f:
plain = str2int(f.read())
c = pow(plain,e,N)
with open('cipher.txt','wb') as f:
f.write(int2str(c).encode('latin-1'))
19 年的原题，夸张了说实话。[密码学学习笔记 之 浅析Pollard’s rho algorithm及其应用 | Van1sh的小屋]
Btw，这里的map是 ，后面有一篇新的论文指出，的 map 要更好些。参考 Common Prime RSA 笔记 | 独奏の小屋：[hasegawaazusa.github.io/common-prime-rsa.html]
原文始发于微信公众号（Van1sh）：2024 网鼎杯 青龙&白虎
