格密码笔记(一)

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 攻破了这个密码体系。