Inequality_Solving_with_CVP

给了一个Padding Oracle，每次将接收到的c先解密，然后告诉你对应的明文有没有经过padding。即要满足：

$c^d \approx K (mod\; n)$

也就是：

$L\le m\equiv c^d (mod\; n)\le R$

考虑到可以找到一系列$a_i$​使得:

$L\le a_im (mod\; n)\le R$

就可以这样构造Lattice：

$L= \left( \begin{matrix} 1 & a_1 & a_2 & \cdots & a_n\\ & n & & & \\ & & n & & \\ & & & \ddots & \\ & & & & n \end{matrix} \right)$

这个格子里包含了某个向量$v$，其上下界分别为$(0,L,L,\cdots)$和$(B,R,R,\cdots)$，$B$为$m$的上界。然后再套用CVP解不等式即可。

这里再介绍一下Inequality_Solving_with_CVP的思想。

首先记 $lb$ 为下界向量，$ub$ 为上界向量，算法的大致思路就是利用Babai求关于 $(lb+ub)//2$ 的CVP问题。算法的精髓在于将 $lb-ub$ 进行归一化，使得 $lb[i]-ub[i]$ 都相等，做法就是给 $lb[i]$ 和 $ub[i]$ 以及$L$ 的第 $i$ 列同时乘以一个权重 $ineq\_weight$

for i in range(num_ineq):
		ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
		applied_weights.append(ineq_weight)
		for j in range(num_var):
			mat[j, i] *= ineq_weight
		lb[i] *= ineq_weight
		ub[i] *= ineq_weight

最后放一下原题：

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

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p * q
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)

print(f"n = {n}")
print(f"e = {e}")
print(f"flag_length = {flag.bit_length()}")

# Oops! encrypt without padding!
c = pow(flag, e, n)
print(f"c = {c}")

# padding format: 0b0011111111........
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)

    return (m >> (padding_pos - 8)) == 0xFF


while True:
    c = int(input("c = "))
    print(check_padding(c))

本地测试的exp:

from Crypto.Util.number import *
from random import *
p = getPrime(256)
q = getPrime(256)
n = p * q
e = 65537
d = inverse_mod(e, (p - 1) * (q - 1))
flag = 923527005889600515717927945977637659146494233475843599679540322066522531810019204383510355169667412726034587411782045475101164773757
flag_length = flag.nbits()
c = pow(flag, e, n)
def check_padding(c):
    padding_pos = n.bit_length() - 2
    m = pow(c, d, n)
    return (m >> (padding_pos - 8)) == 0xFF

k = n.bit_length() - 2 - 8
L = 0xFF << k
R = L + (1 << k) - 1
B = 1 << flag_length
good = []
while len(good) < flag_length // 10 + 10:
    a = randrange(1, n)
    cc = pow(a, e, n) * c % n
    res = check_padding(cc)
    if res:
        good.append(a)
print(len(good))

M = matrix(good).stack(matrix.identity(len(good)) * n)
M = matrix([1] + len(good) * [0]).T.augment(M)

load("./Inequality_Solving_with_CVP/solver.sage")
_, _, fin = solve(M, [0] + [L] * len(good), [B] + [R] * len(good))
print(long_to_bytes(ZZ(fin[0])))