NTRU 公钥密码的量子算法攻击研究*

董 经, 蔡彬彬, 吴宇森, 高 飞, 秦素娟, 温巧燕

1. 北京邮电大学网络与交换技术国家重点实验室, 北京 100876

2. 密码科学技术国家重点实验室, 北京 100878

1 引言

上述对NTRU 公钥密码的量子算法分析都是依托于量子搜索算法, 即Grover 算法. 那么是否仍存在其他量子算法可以实现对NTRU 的攻击？本文发现, Claw-Finding 量子算法[20]对NTRU 密码的分析具有同样的攻击效果. 但是, 原始Claw-Finding 算法针对的函数输出值为单比特, 而分析NTRU 中所构造的函数输出为比特串. 因此, 本文对原Claw-Finding 算法做了适当修改, 并应用修改的Claw-Finding量子算法实现对NTRU 密码的攻击. 在攻击复杂度与文献[19] 相等的情况下, 本文给出的量子攻击避免了应用Grover 算法时强量子Oracle 的前提假设, 且不需要文献[19] 在每次Oracle 叠加查询时维护指数大列表O(f3).

2 预备知识

2.1 NTRU 公钥密码基础

在介绍NTRU 公钥密码之前, 首先介绍算法中涉及的数学知识.

定义1 (模) 给定正整数m, 整数a,b, 若满足m|(a-b), 则称a,b模m同余, 记为a ≡b(modm).

定义1 中式子a ≡b(modm) 称为模m的同余式,m称为同余式的模. 在NTRU 密码算法中涉及到的多项式的模, 与上述定义中的整数模含义一致. 在数学上, 对于模运算有以下性质:

定理1 给定整数A,B以及模数k, 若有A ≡B(modk), 那么对于任意整数C, 都有(A+C)≡(B+C) (modk) 成立.

定义2 (环) 若包含两种代数运算的代数系统(A,+,*) 满足以下条件:

(1) (A,+) 构成交换群;

(2) (A,*) 构成半群;

(3)* 运算关于+ 运算满足左、右分配律;则称(A,+,*) 是一个环. 这里+ 和* 是二元运算. 通常情况下, + 运算为环中的加法,* 运算为环中的乘法. 在NTRU 密码算法中二元运算是加法和乘法.

定义3 (截尾多项式环, truncated polynomial ring)R= Z[x]/(xN-1) 表示N-1 次整数多项式的集合. 用N维向量[a0,a1,··· ,aN-1] 表示(N-1) 次整数多项式a=a0+a1x+···+aN-1xN-1,R上的加法运算+ 和乘法运算* 如下:

(1) [a0,a1,··· ,aN-1]+[b0,b1,··· ,bN-1]=[a0+b0,a1+b1,··· ,aN-1+bN-1];

(2) [a0,a1,··· ,aN-1]*[b0,b1,··· ,bN-1] = [c0,c1,··· ,cN-1], 其中k阶系数ck为:ck=a0bk+a1bk-1+···+akb0+ak+1bN-1+ak+2bN-2+···+aN-1bk+1=∑i+j≡k(modN)aibj.

则(R,+,*) 构成的代数系统称为截尾多项式环, 也称为卷积多项式环, 用R= Z[x]/(xN-1) 表示, 其中Z 表示整数.

特别地, NTRU 公钥密码中所用到的多项式环的系数均为整数. 本文介绍的多项式环R中元素的多项式表示和向量表示将不再区分. 假设多项式a是R中的截尾多项式环, 若关于模整数q有a*A= 1(modq), 则称多项式A为截尾多项式环a的逆元.

NTRU 公钥密码系统中主要用到了三个截尾多项式环, 形式如下:

多项式环Rp和Rq分别由多项式环R的系数模上p和q所得. 下面给出在NTRU 密码中用到的三值多项式的定义.

定义4 (三值多项式) 设d1和d2是正整数, 定义

T(d1,d2) 中的多项式称为三值多项式.

NTRU 密码算法主要由三个整数参数(N,p,q)和四个度最多为N-1 的三值多项式集合Lf,Lg,Lr,Lm共同决定. 正整数N决定了在NTRU 中所有多项式的度最多为N- 1. 正整数p,q为NTRU密码算法中模运算的模数, 满足gcd (p,q) = 1, 且一般情况下q远大于p. 本文中用* 表示截尾多项式环上的卷积运算. 例如多项式A(x) = 1 + 2x+ 3x2和B(x) = 1 +x, 此时N= 3. 卷积运算C(x)=A*B=1+3x+5x2+3x3=1+3x+5x2+3=4+3x+5x2. 这个运算包括了环上的加法和乘法, 并且运算结果的多项式的度最多仍为N-1. 三个三值多项式集合Lf,Lg,Lr的选取参照定义4, 而明文多项式Lm由通信过程中的发送方选取. 在本文中我们讨论的参数集中均有正整数p=3. NTRU 密码算法可分为三部分: 密钥生成算法、加密算法、解密算法. 由于本文只关心在获取公钥信息后如何得到私钥的信息, 所以只讨论密钥生成算法, 而并不具体推导加密和解密算法的过程. 对于NTRU 密码系统工作的具体流程, 在文献[1] 均有详细讨论. 为描述方便, 我们将通信双方用Alice 和Bob 表示, 其中Alice表示发送方, Bob 为接收方.

2.2 NTRU 公钥密码密钥生成算法

首先, Bob 选择多项式f(x)∈Lf(df+1,df),g(x)∈Lg(dg,dg), 其中参数(df,dg) 由NTRU 相应的参数集给定, 多项式f(x) 称为私钥多项式,g(x) 为生成多项式. 随后Bob 计算私钥多项式f(x) 的模逆fp(x),fq(x), 其中fp(x)∈Rp,fq(x)∈Rq, 且满足

若私钥多项式f(x) 的模逆fp(x) 或fq(x) 有一个不存在, Bob 需要重新选择f(x). 最后Bob 通过式子h(x) =pfq(x)*g(x) (modq) 得到公钥多项式h(x), 符号* 为前面提到的卷积运算. 计算完成后, Bob将公钥h发送给Alice. 这里f(x),fp(x),fq(x) 和g为Bob 私有, Alice 并不知道.

考虑到NTRU 密码中用到的是卷积运算, 如果私钥足够稀疏(即多项式系数非零项越少), 卷积计算速度越快, 密码算法的效率越高. 基于此, 研究学者们提出NTRU 密码算法参数集的另一种工作模式——乘积多项式模式[1,19,21](对应的上述方式称为直接选择模式). 顾名思义, 在乘积多项式模式下Bob 选择私钥多项式f(x) 时不直接选择私钥, 而是选择三个小系数多项式f1(x),f2(x),f3(x) 共同组成私钥多项式, 即f(x) =f1(x)f2(x)+f3(x), 这里fi(x)∈Lfi(dfi,dfi),i= 1,2,3. 由于f1(x),f2(x),f3(x)中的非零项远小于零项, 形成的向量比直接选择的私钥多项式向量更稀疏. 计算公钥时, Bob 仍旧按照h(x)=pfq(x)*g(x) (modq) 得到公钥h(x), 然后在通信过程中将公钥h(x) 发送给Alice. Alice 用接收到的公钥h(x) 对消息进行加密并发送给Bob, 最后Bob 通过f(x),fp(x) 进行解密得到Alice 发送的消息. NTRU 加解密的具体计算过程参考文献[1,22–24]. 为分析方便, 本文中省略多项式表示中的自变量,如将f(x) 记为f.

3 NTRU 公钥密码的量子搜索算法攻击

2015 年Fluhrer 基于Grover 搜索算法提出对NTRU 密码的量子攻击[19], 包括两种密钥恢复攻击和两种明文恢复攻击. 这里我们仅介绍文献[19] 给出的第一种密钥恢复攻击. 值得注意的是, NTRU 密码算法中每一个参数集都会给定安全参数k, 这一参数表明攻击者对参数集执行任何攻击复杂度都不低于2k.

由密钥生成算法的公钥生成等式h=pfq*g(modq) 可得, 卷积运算经过简单的数学转换易表示为向量的乘积形式:

其中H表示公钥h的循环转移矩阵. 若公钥h的向量形式为h=h0,h1,··· ,hN-1, 那么相应的H可表示为

观察等式(4)可以发现, 除了p是一个固定常数, 其他参数都是向量或者矩阵. 因此, 如果在等式两边同时模p可得

在乘积多项式模式下, 式(6)可表示为

根据定理1 有

文献[19] 的攻击思想是根据小系数多项式f3的系数多样性, 存储所有可能的(f3,(-f3H(modq))(modp))的值,如存在某个列表L中. 随后,在f1f2上应用Grover 算法搜索f1f2满足(f1f2H(modq))(modp) 的值在列表L中, 即搜索满足(-f3H(modq)) (modp) = (f1f2H(modq)) (modp). 因此,Grover 算法的搜索空间为|f1f2|. 为进一步降低搜索复杂度, 文献[19] 引用了以下引理:

引理1 给定两个多项式A,B ∈F[x]/(xN-1),AB表示两个多项式的乘积. 若有A′=xmA, 则有(xmA)B=xm(AB) 成立, 即A′B=xm(AB).

引理2 给定两个多项式A,B ∈F[x]/(xN- 1),AB表示两个多项式的乘积. 若有A′=xmA,B′=x-mB, 则有(xmA)(x-mB)=AB成立, 即A′B′=AB.

引理1 中若m是正整数, 则xm表示多项式向右移动了m位. 若m是负整数, 则xm表示多项式向左移动了m位. 引理1 表明, 多项式A′B和AB的系数是相等的, 唯一不同的是系数的位置移动了m位. 根据引理1, 式子fH=pg(modq) 有xmfH=pxmg(modq). 若用多项式xmf对密文(通常用e(x) 表示) 进行解密操作, 可以得到明文(通常用m(x) 表示) 的循环移位多项式xmm(x), 攻击者仅通过计算xmm(x) 的循环转移即可获得明文消息m(x). 因此, 若多项式对(f′(x),g′(x)) 满足fH=pg(modq), 则多项式f′(x) 便可以作为NTRU 密码的私钥多项式对密文进行解密. 同样地, 在等式(8)中,目标(f1f2,f3) 也有((xmf1f2)H(modq)) (modp) = (-xmf3H(modq)) (modp) 成立, 即满足等式(8)的多项式对((f1f2)′,f′3) 组成的多项式f′就很有可能可以作为NTRU 的私钥多项式. 在NTRU 的密码分析中, 通常认为攻击者得到私钥(明文) 多项式的任意循环转移多项式, 都可攻破NTRU 公钥密码.应用引理1 和2 后可得, 等式(8)中f1f2的搜索空间由|f1f2| 降为|f1f2|/N,f3的搜索空间由|f3| 降为|f3|/N. 该攻击在具体参数集上的分析见表1. 其中k表示安全参数, 指列表维护大小指每次Oracle 查询需要查询列表(f3,(-f3H(modq)) (modp)) 的大小.

表1 文献[19] 在具体参数集上的分析Table 1 Analysis of quantum attack of Ref. [19] on parameter sets

4 NTRU 密码的量子算法攻击分析及改进

通过上述分析可以发现, 若预先将(f3,(-f3H(modq)) (modp)) 的值存在列表L中, Grover 搜索的量子Oracle 为以下形式:

这里有匹配的意思是指满足等式(-f3H(modq)) (modp) = (f1f2H(modq)) (modp). 如在参数集EES593EP1 中,f1f2的搜索空间为2271.165, 提前存储下来的(f3,(-f3H(modq)) (modp)) 的列表L的大小为O(2107.285). 在文献[19] 中, 该攻击是基于上述量子OracleOc(x)能以常数复杂度(即O(1))实现判断某个f1f2对应的(f1f2H(modq)) (modp) 的值是否存在于列表L中. 而实际上, 这一操作的复杂度不能以常数时间实现. 换句话说, 该量子Oracle 的假设增大了该量子攻击算法的实现难度, 无法达到文献[19] 声明的攻击效果.

因此,为了避免上述攻击的强量子Oracle 假设和维护指数大的列表L所带来的消耗,本文基于Claw-Finding 量子算法[20]设计了新的攻击. 该攻击将类似中间相遇攻击(MITM) 的两部分看成两个函数, 函数的自变量分别为f1f2和f3,因变量为对应的(f1f2H(modq)) (modp)和(-f3H(modq)) (modp).利用Claw-Finding 算法求解出满足两个函数相等关系的(f1f2,f3), 即可通过推导得到私钥多项式f.

4.1 Claw-Finding 量子算法

问题1 (Claw-Finding) 给定两个函数f:x ∈X →Z和g:y ∈Y →Z,X,Y和Z表示一个有限集合. 找到一对Claw (x,y), 其中x ∈X,y ∈Y, 使得f(x)=g(y).

2009 年, Tani[20]基于Szedegy 量子漫步算法[25]提出了解决Claw-Finding 问题的确定性算法.该算法基于Johnson 图实现, 利用二分查找(binary search) 和四分查找(4-ary search) 解决搜索问题.Johnson 图是一类特殊的图, 用J(n,k) 来表示. 它是一个有(nk)个顶点的连通正则图, 图上的每一个顶点都是[n] 的大小为k的子集(这里[n] = 1,2,··· ,n). 当且仅当两个子集中仅有一个元素不同时, 这两个子集在图上的两个点之间有边, 在数学上常称之为集合之间的对称差为2. 待检测点集合(a,b,c,d,e,f)六个点组成的Johnson 图J(6,3) 如图1 所示.

图1 顶点数为()=20 的Johnson 图J(6,3) [26]Figure 1 Johnson graph J(6,3) with number of vertices()=20 [26]

当且仅当顶点集合的对称差为2 时, 顶点之间才有边. 若点a为目标点, 则在Johnson 图中顶点abc,abd,abe,abf,acd,ace,acf,ade,adf,aef均为标记点. 容易发现, 目标点a在集合(a,b,c,d,e,f) 中的概率为, 而在Johnson 图中由目标点a组成的标记点的概率为这使得找到目标点的概率变大[27].

在Claw-Finding 算法中, 首先定义两个Johnson 图Jf(|X|,l),Jg(|Y|,m), 图中的X和Y分别对应函数f和g的自变量,l和m则对应两个自变量的子集. 根据这两个图, 定义图类积G=Jf×Jg, 若Jf(|X|,l) 上的点表示为F,Jg(|Y|,m) 上的点为G, 那么图类积上的点为(F,G). 当且仅当Jf(|X|,l) 上的两个点F,F′之间有边且Jg(|Y|,m) 上的两个点G,G′之间有边时, 图类积G=Jf×Jg的点(F,G),(F′,G′) 之间才有边. 若顶点(F,G) 中存在一对(x,y)∈F×G, 使得f(x)=g(y) 成立, 那么顶点(F,G)即为目标点. 另外, 我们用LF,G来表示每一个顶点(F,G) 对应的具体函数值. 为方便分析, 令|X|=K,|Y|=M. 通常情况下,K ≤M.

容易看出上述定义的Johnson 图是一个无向图, 文献[25] 通过引入自循环将原始图变为部分有向图,即目标点仅会漫步到下一个目标点, 而不会漫步到其他非目标点. 这种漫步依然是通过转移概率矩阵实现,算法中漫步算子定义为W=RBRA. 散射算子RB,RA的定义与文献[25]相同,只是将x,y变为(F,G)和(F′,G′). 具体如下:

这里|cF,G〉和|rF′,G′〉中的系数表示图类积中某个点的转移概率. 如图2 所示, 左图是原始图, 其中标号5是目标点, 右图则是引入自循环后的修改的图[28]. 原始图中的量子漫步的转移概率是均匀的, 但在修改的图中并不是均匀的. 修改图中的漫步算子W=RBRA与文献[25] 中的量子漫步算法相同, 将根据修改图的转移概率矩阵来定义. 以RA为例, 当|F,G〉为目标点时,|F,G〉|F′,G′〉将标记为-|F,G〉|F′,G′〉,且不再散射到其他点. 否则|F,G〉|F′,G′〉将依据定义的RA进行散射.

并且, 为了在量子算法中读取函数值, 文献[20] 定义了量子OracleOf,g:|i,h,z〉 →|i,h,z ⊕Hi(h)(mod|Z|)〉,i ∈{0,1}, 这里H0(h):=f(h),H1(h):=g(h). 通过量子OracleOf,g将函数值读出, 并存为LF,G.

图2 (a) 原始图, (b) 修改图Figure 2 (a) is original graph, (b) is modified graph

下面给出该算法的具体步骤:

步骤1: 定义初态为图上点的均匀叠加态

步骤2: 查询量子OracleOf,g, 此时系统状态为

算法可以分为两部分, 检测算法(Claw-Detect algorithm) 和搜索算法(Claw-Search algorithm). 其中, 检测算法作为搜索算法的子程序, 辅助得到最终的Claw(x,y). 所以下面我们给出检测算法的具体算法步骤(见算法1), 而搜索算法仅给出算法思想.

?

下面介绍搜索算法的思想.

图3 Claw-Search 算法思想Figure 3 Idea of Claw-Search algorithm

如图所示, 图3 中X和Y分别表示函数f(x) 和g(y) 的自变量空间. 若X={x1,x2,··· ,xn},Y={y1,y2,··· ,yn}, 则X1={x1,x2,··· ,xn/2},X2={xn/2+1,··· ,xn},Y1={y1,y2,··· ,yn/2},Y2={yn/2+1,··· ,yn}. Claw-Finding 问题中通常|X|≤|Y|, 因此算法优先判断搜索空间Y的大小. 如果Y=cX(其中c表示某个常数), 直接将X和Y以4-ary 搜索执行Detect 算法. 若存在Claw 于集合(X1,Y1) 中, 则将(X1,Y1) 作为新的搜索空间(X,Y). 重复执行直至搜索空间X和Y足够小. 如果|Y|≥|X|2, 则将Y以2-ary 搜索执行Detect 算法, 直至Y=cX, 然后重复执行上述4-ary 搜索判断Claw. 最后, 当搜索空间X和Y降为O(1) 时, 通过经典查询即可获得目标Claw.

4.2 应用Claw-Finding 量子算法分析NTRU 密码

现在, 我们根据Claw-Finding 算法给出对NTRU 密码的量子攻击. 首先, 构造函数f:X →Z和g:Y →Z, 其中f(x)=(-xH(modq)) (modp),g(y)=(yH(modq)) (modp), 即x对应f3,y对应(f1f2),z ∈Z={0,1,··· ,p-1}. 应用Claw-Finding 算法找到一对(x,y), 使得f(x)=g(y). 即找到了对应的(f3,f1f2), 计算f=f1f2+f3可得NTRU 的私钥多项式. 当|X|=K,|Y|=M, Claw-Finding算法找到一对Claw(x,y) 的复杂度为

然而, 在原Claw-Finding 算法中两个函数的输出均为单比特. 而在NTRU 密码中, 函数的输出为比特串, 因为不论是(f1f2H(modq)) (modp) 还是(-f3H(modq)) (modp), 计算所得的结果都是一个向量. 因此, 这里我们需要通过修改Claw-Finding 算法以达到攻击NTRU 的目的. 具体地, 在得到量子态|(f1f2H(modq)) (modp)〉(用|φa〉表示) 和|(-f3H(modq)) (modp)〉(表示为|φb〉) 后, 计算两个量子态的重叠程度(Overlap) 表示为z(φa,φb) =|〈φa|φb〉|2. 在量子环境下若两个比特串完全相等, 则两个比特串的内积(即〈φa|φb〉) 为1; 否则为0. 因此我们可以用z(φa,φb) 来判断两个比特串(即两个向量) 是否相等. Overlap 的计算参考文献[29], 具体由定理2 给出.

定理2 给定两个量子态Ua|0〉=|φa〉,Ub|0〉=|φb〉, 定义量子态

下面, 我们通过修改的Claw-Finding 算法给出对NTRU 公钥密码的攻击. 首先, 通过访问量子Oracle 得到初态(15), 观察发现公式(15)可重写为

(1) 制备量子态

这里

|0〉1表示单比特|0〉态;

(2) 对|0〉1|ψ12〉和|0〉1|ψ22〉做量子交换测试(quantum swap test) 操作可得

(3) 应用定理2 于|ψ2〉可得

(4) 对|0〉1|ψ12〉和|0〉1|ψ22〉做逆量子交换测试操作可得

至此,|ψ4〉中已得到每一组的|F,G〉和|F′,G′〉对应(x,y) 的函数值(f(x),g(y)) 的内积. 若对应的(x,y) 为Claw, 则(f(x),g(y)) 的内积为1; 否则(f(x),g(y)) 的内积为0.|LF〉和|LG〉(|LF′〉和|LG′〉)对应的每一个函数值均可通过上述操作, 得到对应值的内积, 我们用|TF,G〉(|TF′,G′〉) 表示. 算法的检测部分为检测F,G(F′,G′) 对应的函数值|LF〉和|LG〉(|LF′〉和|LG′〉) 是否相等: 若|TF,G〉|TF′,G′〉为|00〉, 则F,G和F′,G′中均不存在Claw; 否则认为F,G或F′,G′中存在Claw. 具体地, 检测|F,G〉和|F′,G′〉中是否存在Claw, 也即检测对应的量子态|F,G〉和|F′,G′〉是否为目标点, 通过使用酉操作2|00〉〈00|-I作用到|TF,G〉|TF′,G′〉上即可实现目标量子位翻转.

综上所述, 在考虑引理1 和2 的情况下应用修改的 Claw-Finding 量子算法可以在复杂度为O((|f1f2|/N)1/2) 下得到对应的Claw(f3,f1f2). 表2 中给出文献[19] 与本文所提攻击的比较.

表2 文献[19] 与本文所提攻击与之间的比较Table 2 Comparison of quantum attack between Ref. [19] and proposed attack

虽然本文提出的量子攻击复杂度与文献[19] 相同, 但所提攻击避免了应用Grover 算法时强量子Oracle 的前提假设, 并且文献[19] 需要在每次Oracle 迭代中都需要调用指数大的列表, 而本文所提攻击不需要这些额外的消耗.

5 总结

本文分析了Fluhrer 提出基于Grover 搜索算法对NTRU 公钥密码的攻击. 该攻击存在一个强量子Oracle 的前提假设, 所需的量子Oracle 实现难度较大, 且需要维护O(|f3|/N) 的指数大列表. 针对这些缺陷, 本文基于修改的Claw-Finding 算法给出对NTRU 的新的量子攻击. 其中, 修改的Claw-Finding量子算法中定义的函数输出为多比特串. 通过引入量子幅度放大和相位估计计算两个函数输出比特串的内积, 算法能有效识别目标量子态. 在与文献[19] 所提量子攻击具有相同攻击复杂度的情况下, 本文提出的攻击有效地避免了强量子Oracle 的假设, 并且不需要维护指数大列表, 减少了资源消耗.