格密码笔记五

一、SVP & CVP

最短向量问题（The Shortest Vector Problem, SVP）
在 lattice L 中找到一个最短非零向量。亦即，找到一个非零向量 v∈L 使得 ‖v‖ 最小。

最近向量问题（The Closest Vector Problem, CVP）
给定一个不在 L 中的向量 $w∈R^m$，找到向量 v∈L，最小化 ‖w−v‖.

SVP、CVP 问题可能有多解
SVP 和 CVP 都是很困难的问题，当 lattice 的纬度增加，它们的复杂度也快速增加。（但求其近似解比直接求 SVP, CVP 要低一些）
CVP 是 NP-hard 的问题¹。SVP 在有极大可能性在多项式时间内停机并输出正确结果的概率多项式时间（PPT）算法²，也属于多项式时间算法”的语境下也是 NP-hard 的。

¹:(1条消息) NP-Hard问题浅谈_bitcarmanlee的博客-CSDN博客
²:provable security - uniform vs. non-uniform PPT - Cryptography Stack Exchange　　

计算上，一般认为 CVP 比 SVP 稍微难一点点。SVP 可以归约到 CVP。

在攻击 Merkle-Hellman 的时候，子集和问题是一个典型的 CVP，而我们通过一点点技巧，从 n 维升到 n+1 维，于是利用 SVP 解决了问题。

尽管在一般情况下， SVP 和 CVP 都是极度困难的问题，但现实使用中，未必能达到这个困难程度。基于 NP-hard/NP-complete 问题的密码体系，往往是依赖该问题的某个特殊情境（目的是产生陷门，或者使得诚实方可以高效计算），但这也可能会为攻击者大开方便之门。例如，我们知道子集和问题是困难的，但基于“混淆过的超级递增序列”的子集和问题，则可以被攻击者比较快速地解决。³

³:格密码基础 9 (Lecture5, CVP 和 SVP) - 知乎 (zhihu.com)

二、SVP & CVP 变形　　

（一）最短基问题（Shortest Basis Problem, SBP）

找到最短的基向量 v1,…,vn，使得它们（在指定的长度定义下）最短。

（二）近似最短向量问题（apprSVP）

设$ψ(n)$ 是 n 的函数。对于维度为 n 的 lattice L，找到一个非零向量，其长度不能超过 ψ(n) 倍的（真正的）最短非零向量。

也就是说，若我们记 L 的最短非零向量为$ v{shortest}$，则要寻找向量 v∈L 满足$‖v‖≤ψ(n)‖v{shortest}‖$

不同的 ψ(n) 给出不同的 apprSVP
- 例如，可能会要求$‖v‖≤3\sqrt{n}‖v_{shortest}‖$
- 显然，不同版本的 apprSVP 的难度差异可能很大
- 例如，解决 $ψ(n)=3\sqrt{n}$ 的 apprSVP 远比解决 $ψ(n)=2^{n/2}$ 的 apprSVP 简单。如果维度不太大，甚至后者都可能是有实际用处的。

三、Hermite 定理 & Minkowski 定理

一个 lattice 的最短非零向量到底有多长？

这和 L 的维度以及协体积有关。

（一）Hermite 定理

每一个 n 维的 lattice L，都包含一个非零向量 v∈L 满足$‖v‖≤\sqrt{n}det(L)^{1/n}$

定义 Hermite 常数 $γ_n$，来研究 n 维 lattice L 的最短向量长度上界。L 必定包含一个非零向量 v 满足：$‖v‖^2≤γ_ndet(L)^{2/n}$

Hermite 定理说明了性质 $γ_n≤n$⁴。而至于 γn 的确切值，我们只知道 1≤n≤8 以及 n=24 的情形，但是这显然不够我们用，因为密码学用途中，n 往往很大。我们有一个更紧的界：$\frac{n}{2πe}≤γ_n≤\frac{n}{πe}$

⁴:格密码学研究—王小云 - 豆丁网 (docin.com)　　

我们上面的讨论都是针对一个最短向量的。

对于一组基（多个向量），也有定理：$‖v_1‖‖v_2‖⋯‖v_n‖≤n^{n/2}(detL)$

这构成了基向量长度之积的上界。

Hadamard 不等式⁵给出了其下界：$‖v_1‖‖v_2‖⋯‖v_n‖≥detL$

定义一组基$ B={v_1,…,v_n} $的 Hadamard ratio：$H(B)=(\frac{detL}{‖v_1‖‖v_2‖⋯‖v_n‖})^{1/n}$，显然有 0≤H(B)≤1，而且这个 Hadamard ratio 越接近 1，这组基向量越像正交。

（二）Minkowski 定理

1、预备知识：

闭球（closed ball） 对于任意 a∈Rn 以及任意 R>0，我们称半径为 R、球心为 a 的“闭球”为$B_R(a)={x∈R^n:‖x−a‖≤R}$

设 S 是 $R^n$ 的子集，那么：

称 S 是有界（bounded）的，当且仅当 S 内向量的长度是有界的。
等价描述：S 是有界的，当且仅当 S 包含在 $B_R(0)$ 中。
称 S 是对称（symmetric）的，当且仅当对于 S 中的每一个点 a，其相反向量 −a 也在 S 中。
称 S 是凸（convex）的，当且仅当对于 S 中的任意两个点 a,b，连接它们的线段完全在 S 内。
称 S 是闭（closed）的，当且仅当如下性质成立：若 $a∈R^n$ 是一个点使得任意球 $B_R(a)$ 都包含 S 中的点，则 a 在 S 中。
即：边界上的点也在 S 中。

2、Minkowski’s Theorem

设 $L⊂R^n$ 是一个 n 维 lattice，$S⊂R^n$ 是一个有界的、对称的、凸的点集，且满足$Vol(S)>2^ndetL$，则 S 包含一个非零 lattice 向量。
如果 S 还是闭的，则条件松弛到 $Vol(S)≥2^ndetL$。

四、CTF中的应用

（一）预备知识

Hidden number problem（HNP） ⁶

⁶:The Hidden Number Problem – kel.bz

（二）BCTF 2018 - guess_number

题目提供了服务器端的代码：

import random, sys
from flag import FLAG
import gmpy2

def msb(k, x, p):
    delta = p >> (k + 1)
    ui = random.randint(x - delta, x + delta)
    return ui

def main():
    p = gmpy2.next_prime(2**160)
    for _ in range(5):
        alpha = random.randint(1, p - 1)
        # print(alpha)
        t = []
        u = []
        k = 10
        for i in range(22):
            t.append(random.randint(1, p - 1))
            u.append(msb(k, alpha * t[i] % p, p))
        print(str(t))
        print(str(u))
        guess = raw_input('Input your guess number: ')
        guess = int(guess)
        if guess != alpha:
            exit(0)

if __name__ == "__main__":
    main()
    print(FLAG)

可以看到，程序一共执行 5 轮。在每一轮，程序会生成一个随机的α和 22 个随机的$ti$。对于每一个$t_i$，程序会取$u_i=MSB{10,p}(α⋅t_i\ mod\ p)$，随后发送给客户端。

我们需要根据提供的$t_i$和$u_i$计算出对应的α。可以看到，该问题是一个典型的 Hidden number problem，于是可以使用上述算法解决：

import socket
import ast
import telnetlib

#HOST, PORT = 'localhost', 9999
HOST, PORT = '60.205.223.220', 9999

s = socket.socket()
s.connect((HOST, PORT))
f = s.makefile('rw', 0)

def recv_until(f, delim='\n'):
    buf = ''
    while not buf.endswith(delim):
        buf += f.read(1)
    return buf

p = 1461501637330902918203684832716283019655932542983
k = 10

def solve_hnp(t, u):
    # http://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf
    M = Matrix(RationalField(), 23, 23)
    for i in xrange(22):
        M[i, i] = p
        M[22, i] = t[i]

    M[22, 22] = 1 / (2 ** (k + 1))

    def babai(A, w):
        A = A.LLL(delta=0.75)
        G = A.gram_schmidt()[0]
        t = w
        for i in reversed(range(A.nrows())):
            c = ((t * G[i]) / (G[i] * G[i])).round()
            t -= A[i] * c
        return w - t

    closest = babai(M, vector(u + [0]))
    return (closest[-1] * (2 ** (k + 1))) % p

for i in xrange(5):
    t = ast.literal_eval(f.readline().strip())
    u = ast.literal_eval(f.readline().strip())
    alpha = solve_hnp(t, u)
    recv_until(f, 'number: ')
    s.send(str(alpha) + '\n')

t = telnetlib.Telnet()
t.sock = s
t.interact()