格密码笔记（一）

Lattice based crypto 我从 2020 年春季就立志要学，一直摸了一年。
现在决定加急学习，不能再摸了，一定要出重拳！
2021.01.14

关于格密码

　　众所周知，公钥密码学的安全性，往往建立在数学问题的困难性上。如 RSA 基于大数分解的困难性，DH 和 Elgamal 以及 ECC，是基于有限域上求离散对数的困难性。我们接下来要考虑一类新的难题，它们支撑了格（lattice）密码学。

　　对比起之前的公钥密码学体系，格密码提供了许多优势：首先，加密、解密速度可以更快（RSA 慢得难以忍受）；可以抵抗量子攻击。目前来看，暂且没有量子算法可以高效解决 lattice 难题。

　　lattice 除了可以开创新的公钥密码体系之外，还提供了一整套新的数学方法，可以用来解决许多传统密码学的问题。攻击 RSA 时经常采用的 Coppersmith 方法，就是基于 lattice 的。

　　所谓“格”，是一种与向量空间类似的数学空间。实数空间 $\mathbb{R}$ 上的向量空间 $V$，是一些向量的集合；其中两个向量可以相加、向量可以和一个实数相乘，运算保持封闭。也就是说，向量空间支持向量加法和标量乘法。而 lattice 与向量空间的区别，就是将标量乘法中的乘数，从实数改为整数。

　　格可以视为向量的集合，也可以视为点的集合。直观地看，lattice 上的点排列非常整齐，与栅栏、铁丝网、化学中的晶格类似。

　　由于 lattice 的理论本身比较晦涩，我们先看一个具体的例子。这个例子并不关 lattice 什么事，但是其隐含了 lattice 的一些理论。

一个公钥密码学方案

　　现在来看这一个密码学方案。它是一个 toy model，并不安全。它是 lattice 可用于传统公钥密码分析的例证，另外也是 NTRU 公钥密码体系的一个低端版本。

　　首先，Alice 选择一个大整数 $q$ 作为公共参数。然后选择两个比较小的整数 $f,g$ 满足 $$f < \sqrt{q/2}, \qquad \sqrt{q/4} < g < \sqrt{q/2}, \qquad \gcd(f, qg) = 1$$亦即 $f$ 的长度大约小于 $q/2$ 的一半；$g$ 的长度大约在 $q/4$ 的一半到 $q/2$ 的一半之间。从而 $f, g$ 远远小于 $q$，为 $\mathcal{O}(\sqrt q)$. 另外要求 $f$ 与 $q, g$ 都互质。接下来，Alice 计算 $$h \equiv f ^ {-1} g \pmod q$$注意到尽管 $f$ 很小，其逆元仍然会很大，于是 $h$ 是 $\mathcal{O}(q)$ 的级别。Alice 的公钥是 $h$，私钥是 $\langle f, g\rangle$.

　　现在来考虑 Bob 如何给 Alice 发送消息。首先，Bob 有一个小于 $\sqrt{q/4}$ 的明文 $m$，然后他随机选择整数 $r < \sqrt{q/2}$. 计算 $$e \equiv rh + m \pmod q$$将 $e$ 作为密文发送给 Alice. 接下来 Alice 如此解密：先计算 $$a\equiv fe\pmod q$$然后计算 $$b\equiv f ^ {-1} a \pmod {{\color{blue} g}}$$其中 $f$ 的逆元也是在模 $g$ 群中的。我们断言这里求出来的 $b$，就等于 $m$.

　　首先，有 $a$ 满足 $$a\equiv fe \equiv rg + fm \pmod q$$我们注意到 $rg+fm < \sqrt{\frac q2}\sqrt{\frac q2} + \sqrt{\frac q2}\sqrt{\frac q4} < q$，从而知道 $a$ 就是 $rg+fm$ 的真实值，即$$a = rg + fm$$

　　接下来的步骤就顺理成章了。将 $a$ 模掉 $g$，分离出 $fm \pmod g$；然后乘以 $f$ 的逆元得到 $m \pmod g$. 而 $m$ 是小于 $g$ 的，从而这个 $m$ 是真实值。

　　纵观整个加密体系，最大的跨越在于 “得到 $rg+fm$ 的真实值”。正因为有了 $rg+fm$ 的确切值，才可以模掉 $g$，从而解开 $rg$ 的混合，得到 $fm$.

import random
from numpy import sqrt, gcd
from gmpy2 import invert

class SimpleScheme():
    
    def __init__(self):
        while True:
            self.q = random.randint(1<<128, (1<<129) - 1)
            self.f = random.randint(1, sqrt(self.q / 2))
            self.g = random.randint(sqrt(self.q / 4), sqrt(self.q / 2))

            if gcd(self.f, self.q * self.g) == 1:
                break
        
        self.h = invert(self.f, self.q) * self.g % self.q
        
        print(f'pk = (q, h) = ({self.q}, {self.h})')
        print(f'sk = (f, g) = ({self.f}, {self.g})')
    
    def enc(self, m):
        assert m < sqrt(self.q/4)
        
        r = random.randint(1, sqrt(self.q / 2))
        e = (r * self.h + m) % self.q
        
        print(f'rg+mf = {r*self.g + m*self.f}')
        
        print(f'e = {r * self.h % self.q} + {m} = {e}')
        
        return int(e)

    def dec(self, e):
        a = self.f * e % self.q
        
        print(f'a = {a}')
        
        b = invert(self.f, self.g) * a % self.g
        
        print(f'b = {b}')

worker = SimpleScheme()
c = worker.enc(114514)
worker.dec(c)

# pk = (q, h) = (514230918051282920692602780404498492433, 115647624614577988455515336107635422730)
# sk = (f, g) = (2405709868378346209, 15028670797073718546)
# rg+mf = 13054637933699032665165943687110631912
# e = 259719708311083043320270690207664511027 + 114514 = 259719708311083043320270690207664625541
# a = 13054637933699032665165943687110631912
# b = 114514

　　现在，我们来考虑敌手 Eve 如何攻击这个密码体系。仅仅已知公钥 $(q, h)$，她并不能找到真正的 $(f, g)$；但她可以找到一组 $(F,G)$，如果 $(F,G)$ 在解密时表现与 $(f,g)$ 相同，那么 Eve 就可以完成解密工作。具体而言，她需要找到 $F,G$ 满足 $$Fh\equiv G \pmod q,\qquad F=\mathcal{O}(\sqrt q),\qquad G=\mathcal{O}(\sqrt q)$$显然真正的 $(f,g)$ 是合法的 $(F,G)$. 现在的问题是为什么这样的 $(F,G)$ 可以用于解密。我们有$$Fe \equiv F \cdot (r h+ m) \equiv rG + Fm \pmod q$$注意到这求出了 $rG+Fm$ 的真实值。继续按照原先的解密算法来操作，模掉 $G$ 获得 $Fm \pmod G$，乘以 $F$ 的逆元，即可恢复出 $m$.

　　也就是说，Eve 只需要找到合法的 $(F,G)$，就可以攻破这个密码体系。将 $Fh\equiv G \pmod R$ 改写为等价形式 $Fh = G + qR$，那么 Eve 的任务就是找到足够小的 $F,G$ 使得 $$F(1,h) - R(0, q) = (F,G)$$

　　这个式子等价于 $(1,h), (0,q)$ 这两个向量以 $F, R$ 为系数进行线性组合。如果我们能找到合适的 $F,R$，使得线性组合出来的向量足够短，那么我们就找到了合法的 $(F,G)$ 来攻击密码体系。

　　上面的问题可以概括为：有两个已知的向量，需要找出一套线性组合系数（必须是整数），来生成一个足够短的向量。Eve 的任务是：已知 $\newcommand\bv{{\boldsymbol{v}}} \bv_1 = (1,h)$ 和 $\bv_2 = (0,q)$，长度均为 $\newcommand\mo{{\mathcal{O}}} \mo(q)$，要寻找它们的线性组合 $\boldsymbol{w} = a_1 \bv_1 + a_2 \bv_2$，长度为 $\mo(\sqrt q)$. 要求系数 $a_1, a_2$ 均为整数。

　　从 lattice 的角度看，Eve 是在一个 lattice $L$ 中寻找一个很短的向量：$$L = \{a_1\bv_1 + a_2\bv_2 : a_1, a_2 \in \mathbb{Z} \}$$

　　在二维的 lattice 里面找最短向量，是有高效算法的（Gauss 的工作）。于是 Eve 攻破了这个密码体系。