hgame部分

babyrsa

题目

from Crypto.Util.number import *
from gmpy2 import *
from random import *
import string
k = randint(30, 40)
str = string.digits + string.ascii_letters + "_@"
flag = b"VIDAR{" + "".join([choice(str) for i in range(k)]).encode() + b"}"
p = getPrime(120)
q = getPrime(120)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f'c = {c}')
print(f'p = {p}')
print(f'q = {q}')

'''
c = 451420045234442273941376910979916645887835448913611695130061067762180161
p = 722243413239346736518453990676052563
q = 777452004761824304315754169245494387
'''

分析

关键:m有强结构

m 不是任意整数。
它满足:

m=bytes_to_long(VIDAR{X} )m = \text{bytes\_to\_long}(\text{VIDAR\{X\} })

m=bytes_to_long⁡(VIDAR{} X )m = \operatorname{bytes\_to\_long}(\texttt{VIDAR\{\} X\ })


转化为数学方程

设:

prefix=bytes_to_long("VIDAR{")prefix = \text{bytes\_to\_long}("VIDAR\{")

suffix=bytes_to_long("}")suffix = \text{bytes\_to\_long}("\}")

将m展开整数形式:

m=P⋅256k+1+X⋅256+Sm=P\cdot 256^{k+1}+X\cdot256+S

我们已知:

m≡m0(modn)m \equiv m_0 \pmod n

代入得:

P⋅256k+1+X⋅256+S≡m0(modn)P \cdot 256^{k+1} + X\cdot256 + S\equiv m_0 \pmod n

将已知量和为止量分开:

X⋅256≡m0−P⋅256k+1−S(modn)X \cdot 256 \equiv m_0 - P\cdot256^{k+1} -S\pmod n

现在问题变成:
求一个长度 k 的整数 X,使得:

  1. X≡Cmod  nX \equiv C \mod n
  2. X 的每个字节来自 64 个合法字符

恢复X

X=∑xi256iX = \sum x_i 256^i

利用xix_i的特点

我们选定一个中心值a

那么所有合法字符的xix_i都离 a不太远,于是:

δi∈[−Δ,Δ]δ_i∈[−Δ,Δ]

是一个很小的整数。

由此:

xi=a+δix_i = a + \delta_i

∑δi256i≡C′(modn)\sum \delta_i 256^i \equiv C' \pmod n

变形:

∑δi256i−C′=tn\sum \delta_i 256^i - C' = t n

可以构造:

L=(100…02560010…02561001…02562⋮⋱⋮000…1256k−1000…0−C′000…0n)L = \begin{pmatrix} 1 & 0 & 0 & … & 0 & 256^0 \\ 0 & 1 & 0 & … & 0 & 256^1 \\ 0 & 0 & 1 & … & 0 & 256^2 \\ \vdots & & & \ddots & & \vdots \\ 0 & 0 & 0 & … & 1 & 256^{k-1} \\ 0 & 0 & 0 & … & 0 & -C' \\ 0 & 0 & 0 & … & 0 & n \end{pmatrix}

(δ0,δ1,…,δk−1,t)L=(δ0,δ1,…,δk−1,1,∑δi256i−C′+tn=0)(\delta_0, \delta_1, …, \delta_{k-1}, t)L = (\delta_0, \delta_1, …, \delta_{k-1}, 1, \sum \delta_i 256^i - C' + t n = 0)

如果这最后两维是 1,0,那我们就得到了合法解

EXP

def solve():

c = 451420045234442273941376910979916645887835448913611695130061067762180161
p = 722243413239346736518453990676052563
q = 777452004761824304315754169245494387
e = 65537

n = p * q
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)
m_trunc = pow(c, d, n)

prefix = b"VIDAR{"
suffix = b"}"
center = 85

# 3. 遍历爆破中间字符的长度
for length in range(30, 41):
print(f"尝试未知长度 k = {length}")

target = m_trunc
# 减去前缀和后缀的权重 (使用 Python 自带的 int.from_bytes)
target -= (256**(len(suffix) + length)) * int.from_bytes(prefix, 'big')
target -= int.from_bytes(suffix, 'big')
# 消除后缀长度的偏移
target = (target * pow(256, -1, n)) % n

# 4. 构建格矩阵
L = Matrix(ZZ, length + 2, length + 2)

for i in range(length):
L[i, i] = 1
L[i, -1] = 256**i
target -= (256**i) * center

L[-2, -2] = 1
L[-2, -1] = -target
L[-1, -1] = n

for i in range(length + 2):
L[i, -1] *= n

res = L.BKZ()

for row in res:
if all(-38 <= x <= 38 for x in row[:-2]):
if row[-2] == 1:
flag_middle = "".join(chr(center + j) for j in row[:-2][::-1])
print(f"\nk = {length}")
print(f"Flag: {prefix.decode()}{flag_middle}{suffix.decode()}\n")
return

elif row[-2] == -1:
flag_middle = "".join(chr(center - j) for j in row[:-2][::-1])
print(f"\nk = {length}")
print(f"Flag: {prefix.decode()}{flag_middle}{suffix.decode()}\n")
return

solve()