计  算  机  学  报      2019 年  masked  state,  which  can  effectively  guarantee  the  security  of  data.  The  masking  technology  contains  Boolean  Masking  and Arithmetic  Masking.  As  an  important  property  of  public  key  cryptosystem,  homomorphic  computation  algorithm  can  operate ciphertext,  and  can  achieve  Arithmetic  Masking  between  ciphertext.  In  order  to  solve  the  problems  of  side  channel  attack  in  the implementation process of NTRU, a novel Fully Homomorphic Masking (FHM) defense scheme is proposed and its circuit design model is given. Our scheme can effectively implement the mask for all the polynomial coefficients and resist the Power Attack. In this scheme, the key generation uses Gaussian abstraction algorithm, and the decryption part applies the homomorphic encryption to realize  fully  homomorphic  calculation  between  ciphertexts.  In  the  circuit  model  of  fully  homomorphic  masking  scheme  we constructed, data sampling area, storage area, and operation area are divided according to the algorithm function. By analysis, it is obvious that lattice attack can be avoided as if the key of NTRU is generated by Gaussian abstraction, and that all the coefficients of polynomials can be masked by the homomorphic calculation between the ciphertext. Because of double mask, it can effectively resist the Zero Value Attack. With the analysis of the algorithm homomorphism, the correctness of our scheme has been verified; it shows that  Chosen  Ciphertext  Attack,  Differential  Power  Attack,  Zero  Value  Attack  and  Correlation  Power  Attack  all  can  be  resisted effectively in the implementation process of this scheme.  Key word：Number Theory Research Unit,   Power Attack,   Chosen Ciphertext Attack,   Masking,   Homomorphic encryption  1  引言 后量子密码体系主要包括四个分支：基于格理论的后量子密码、基于 Hash 的后量子密码、基于多变量的后量子密码以及基于编码理论的后量子密码，其中基于格理论的后量子密码体制由于其良好的数学性质而受到广泛的研究。然而，即使算法本身的设计是安全的，在其实现过程中也难免会遭受各种各样的攻击，其中，侧信道攻击对后量子密码体制带来了越来越大的安全威胁。 1998 年，美国布朗大学的 Jeffrey Hoffstein、Jill Pipher 和 Joseph  H.  Silverman 三位数学教授发明的一种公钥密码体制 NTRU（Number Theory Research Unit）[1]，相比较于基于椭圆曲线上的离散对数问题[2]和基于大数分解问题[3]的公钥密码体制而言，NTRU 的安全性依赖于格上的最短向量问题[4]，具备抗量子计算机攻击的能力。NTRU 自从被提出以来就备受关注，目前已正式成为 IEEEP1363 标准及美国金融服务行业标准[5]。 由 Kochor 提出的侧信道攻击[6-7]，主要是根据密码算法在执行过程中的消耗信息进行破译。此后，侧信道攻击与防御技术的研究成为密码学的一个重要分支，受到了广泛关注。能量攻击是最重要、最有效的侧信道攻击形式之一，尤其对智能卡等设备的实际安全性造成严重的威胁。而 NTRU 算法特别适合用于智能卡、无线保密网及认证系统等业务[8]，也就是说 NTRU 的算法面临着侧信道攻击的风险。 能量攻击通过利用密码设备的能量消耗特征来获取秘密信息，是一种非接触式的攻击方法。差分能量攻击通过分析芯片运行过程中的能量消耗，能够实现对密钥的恢复，是一种高效的密码分析方式。针对基于 NTRU 算法的密码系统，Atici 等人[9]首次给出能量攻击方式，Lee 等人[10]给出了简单能量攻击、差分能量攻击的方法并针对所提攻击方法给出三种不同的防御措施。王安等人[11]对基于NTRU 的无线体域网进行能量分析并提出相应的防御措施，通过结合选择密文攻击对 Lee 等人提出的防御措施进行攻击，取得良好的攻击效果。目前关于 NTRU 算法的分析得到了广泛的研究[12-15]。 在 NTRU 算法的实现过程中，密钥生成过程存在格攻击的安全问题[16]，且存在选择密文攻击及能量攻击等问题。同态是公钥密码算法的一种常见性质，同态算法可以对密文进行操作，并能实现密文间的掩码。掩码技术包含布尔掩码和算术掩码，通过掩码技术，可以掩盖算法执行过程中的中间变量和中间数值，运算操作中的数据在被掩盖状态下运行，进而可以防范侧信道攻击，保障数据安全。截止目前，还没有看到基于同态掩码来防范侧信道攻击方案的提出。 本文通过对 NTRU 算法进行分析，在密钥生成部分，通过采用格上的高斯抽样算法生成密钥对，从而避免格攻击，并且不改变密钥的分布。为了防御选择密文攻击，利用算法的同态特性对密文进行改造，对所处理密文进行随机化，同时该方法能有效的抵抗零值攻击、二阶差分能量攻击。 计算机学报计  算  机  学  报      2019 年  2 NTRU 算法介绍 NTRU 算法是在多项式环 [ ] / ( 1)NZ x x - 的基础上实现的，环上的多项式 f 可以表示成一个多项式或者向量的形式： 10 1 10[ , ,..., ]Nii Nif f x f f f--== å=  环上的乘法运算* 是卷积乘，假设： 0 1 10 1 10 1 1[ , ,..., ][ , ,..., ][ , ,..., ]---===NNNf f f fg g g gh h h h 则多项式 f 和 g 的卷积 h 定义如下： h =f *g  其中， 110 1mod  (0 1)k Nk i k i i N ki i ki ji j k Nh f g f gf g k N-- + -= = ++ º= += £ £ -å åå 因为 NTRU 算法只涉及多项式环上的乘法和求模运算，与传统公钥密码算法的模幂运算相对比，其运算速度有大幅度提高。同时，NTRU 的密钥产生算法相对简单，使得它有着十分广阔的应用范围及应用场景。NTRU 算法由密钥生成、加密算法及解密算法三部分组成，如下所述： 1.密钥产生 Key Gen ： NTRU 算法涉及到三个公开参数 (N, p, q) ，其中，一般选取 3, 2kp =q = , N -1是多项式的最高次 数 。 该 算 法 构 建 在 商 环 [ ] / ( 1)NZ x x - 上 ；L( a, b)表示环中满足 a 个系数为 1， b 个系数为-1，其他系数均为 0 的所有整系数多项式。 首先，随机提取两个多项式 ( 1, )f ff ∈L d +d和 ( , )g gg ∈L d d ，其中 ,f gd d ÎZ 且需要保证 f存 在 逆 元pf 和qf ， 使 得 1( m o d )pf *f =p ，1(mod )qf *f =q ； 然 后 ， 计 算( ) (mod )qh x =pf *g q ； 最 后 ， 根 据 参 数 生 成NTRU 的公钥为 (N, p, q, h) ，私钥为 f 和pf ，且私钥可以表示为 f1 pf= +¢的形式。 2.加密算法 Enc ： 首先，将明文消息 m 编码为对应的多项式m(x) ； 然 后 ， 用 户 选 取 随 机 多 项 式( , ),r rr ∈L d d r ÎZ ； 最 后 ， 计 算 ：c =[ pr *h +m(x)](mod q) ,则 c 即为所求密文。 3.解密算法 Dec ： 首 先 ， 解 密 者 得 到 密 文c =[ p *r +(h)m] (xm o qd；然后，利用私钥)f 计算 a(x)≡c*f(modq) ； 其 次 ， 计 算( ) ( )pm¢x=a*x ；f最 后 ， 计 算 明 文 ：m(x) m(x)(mod p)≡¢ 。 3 NTRU 算法分析 NTRU 密码算法自被提出以来，受到了广泛的研究和分析，针对其攻击分为理论上的攻击如格攻击，实现上的攻击如简单能量攻击、差分能量攻击等。下面分类对其进行分析。 3.1 格攻击 文 献[16]指 出 由'( m o d )qh =f *g q可 得' ' ', [ ] / ( 1 )Nqf *h =g +q *a aÎZ x x-，那么向量集：2{( , ) : ' (mod ), , }N NL =u v u *h =v q u v ÎZ ÎZ 中肯定包含向量 ( f,g)，为使解密能够成功，需要|| || 2 1ff =d - 和|| || 2gg =d 都是远小于 N ，因此，如果能够从 L 中找出最短向量，就有可能恢复出( f, g) ，为了能够获得向量，利用 LLL 算法可以提高找到最短向量的概率。 3.2 简单能量攻击 在 NTRU 算法的解密过程中，其核心运算为： (mod ) (1 ) (mod )(mod )f c q pf c qc pf c q* = +¢ *= +¢* 因此，只要知道 f ¢ 的值，就可以实现对算法的破解，因此对算法的破解转化为求解t =f ¢*c 。假设 N=8，f¢ =[10011010]，则卷积运算过程如图1 所示，其中 Add 表示多项式系数取模相加。 在简单能量攻击（Simple Power Attack，SPA）过程中不需要使用任何的统计分析方法，攻击者只要观察目标操作运算执行过程中的能量消耗即可实现对算法的破译。假设在 SPA 过程中，对于非零整数 a 和b ，计算 a +b 和 a +0 的能量消耗是不同的。因此，攻击者能够选取系数都非零的密文多项式对算法进行攻击，根据能量消耗的变化确定相应的值。在上述的卷积运算过程中，对于第 2 行而言，下面的每一行与前面的行相加都是两个非零值相加，而第一行与初始化的内存单元值相加则是零值与非零值相加，因此攻击者能够根据能量的消耗情况确定出第一行的值，同理，逐行递推，最后利用穷搜的方法就能得到整个 f ¢ 的值。计算机学报 计   算   机   学   报  Vol. 42 2019  论文在线出版号 No.30  CHINESE JOURNAL OF COMPUTERS  2019Online Publishing No.30  （Initial）1 4 1 3 1 2 1 1 1 0 9 8 7 6 5 4 3 2 1 0                            ||     ||    ||    ||    ||    ||    ||    ||   ||   ||   ||   ||    ||   ||   | |0    0    0    0    0    0   0   0    0  0   0  0   0   t t t t t t t t t t t t t t t0   07 6 5 4 3 2 1 0c       c c c c c c c7 6 5 4 3 2 1 0c       c c c c c c c7 6 5 4 3 2 1 0c       c c c c c c c7 6 5 4 3 2 1 0c       c c c c c c c（Final）1 4 1 3 1 2 1 1 1 0 9 8 7 6 5 4 3 2 1 0t                            t t t t t t t t t t t t t tAdd 图 1 卷积运算过程 3.3 相关能量攻击 相关能量攻击(Correlation Power Attack，CPA)是比 SPA 更加有效的一种方式。在 CPA 攻击中，攻击者首先使用同一密钥进行多次解密运算，采集其能量曲线并求平均；然后，计算能量迹与多项式系数之间的关系。由图 1 可知，假设第一行中的5c被加到某一个寄存器上，则当第二行中的2c 也被加到该寄存器上时，因为能量消耗与寄存器值的变化相关，因此，在收集大量的能量迹之后，可根据计算所得的相关系数对密钥进行破译。 3.4 差分能量攻击 在一般的差分能量攻击过程中，攻击者首先使用同一密钥进行多次解密运算，采集其能量曲线并求平均；然后，使用猜测的密钥对同一密文进行多次计算并采集能量求平均；最后，根据能量迹的差值进行判断，若出现峰值，则说明相应的比特位值猜测正确，反之，则说明猜测错误。如此反复进行猜测实验，最终可以实现对密钥的破译。 选择密文攻击是指攻击者能够伪造合法数据，结合算法具体运算过程，利用运算过程中泄露的中间值信息，实现对算法的攻击。下面结合选择密文与差分能量攻击的思想，给出一种针对 NTRU 算法更加有效的分析方法： 假设用户选择密文 c =[0,0,...,0]并进行多次运算，求得其平均曲线，用1T 表示；然后，用户再选择一个密文 c =[a,0,...,0]进行多次运算，求得其平均曲线，用2T 表示；最后，对1 2T,T 做差得1 2DT=T-T ，值不同的位置便会出现峰值。其中值为 a 的位置能够被有效的恢复出来。计算过程如图2 所示：  （Initial）14 13 12 11 10 9 8 7 6 5 4 3 2 1 0                            ||     ||    ||    ||    ||    ||    ||    ||   ||   ||   ||   ||    ||   ||   ||0    0    0    0    0    0   0   0    0  0   0  0   0   t t t t t t t t t t t t t t t0   00 0 0 0 0 0 0 0（Final）0  0  0  0  0  0  0  0  0  0  0  0  0  0Add0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0 （Initial）14 13 12 11 10 9 8 7 6 5 4 3 2 1 0                            ||     ||    ||    ||    ||    ||    ||    ||   ||   ||   ||   ||    ||   ||   ||0    0    0    0    0    0   0   0    0  0   0  0   0   t t t t t t t t t t t t t t t0   00  0  0  0 0 0 0 a （Final）0  0  0  0  0  0  0  a  0  a  a  0  0  a Add0  0  0  0 0 0 0 a0  0  0  0 0 0 0 a0  0  0  0 0 0 0 aTrace 差分Trace 图 2 针对 NTRU 算法的差分攻击过程 计算机学报发展基金（No.MMJJ20170110）资助. 杨亚涛（通信作者），男，1978 年生，博士，副教授，硕士生导师，主要研究方向为密码学与通信安全.Email:yy2008@163.com. 刘博雅（通信作者），男，1991 年生，主要研究方向为密码协议、信息安全.Email:lby330613263@163.com. 孙亚飞（通信作者），男，1992 年生，硕士生，主要研究方向为密码学.Email:yfsun0112@163.com. 李子臣，1965 年生，男，博士，教授，博士生导师，主要研究方向为密码学、信息安全、后量子密码、数字水印等。 NTRU 全同态掩码防御方案  杨亚涛1),3)  刘博雅1)  孙亚飞3)  李子臣2)  1)(北京电子科技学院电子与通信工程系，北京 100070) 2)(北京印刷学院 信息工程学院，北京 102600) 3)(西安电子科技大学 通信工程学院，西安 710071)  摘要：为了抵抗量子计算机的攻击，相关的后量子密码算法被先后提出。NTRU (Number Theory Research Unit)密码算法是基于格理论的典型算法之一，在 NTRU 密码方案的硬件设计及实现过程中，主要会面临格攻击、简单能量攻击、差分能量攻击及相关能量攻击等风险。为了解决 NTRU 算法在实现过程中的侧信道攻击安全隐患，提出一种新的全同态掩码防御方案，并给出电路设计参考模型，所提出方案能够对 NTRU 算法所有系数执行掩码操作并防范能量攻击。本方案的密钥生成部分采用高斯抽样算法，解密部分采用同态加密实现密文间的全同态运算。设计的全同态掩码方案电路模型中，根据算法功能分为数据采样区、存储区及运算区。本方案通过高斯取样生成密钥，能防范格攻击；通过密文之间的同态运算，可以实现多项式所有系数同时掩码；通过分析算法的同态性，验证了本方案的正确性；通过分析方案的实现过程，论证了该方案能够有效防御选择密文攻击、差分能量攻击、零值攻击及相关能量攻击。 关键词：NTRU，能量攻击，选择密文攻击，掩码，同态加密 中图分类号：TP393  Fully Homomorphic Masking Defense Scheme based on NTRU Yang Yatao1),3)，Liu Boya1)，Sun Yafei3)，  Li Zichen2) 1)( Department of Electronic and Communication Engineering,Beijing Electronic Science &Technology Institute, Beijing 100070, China) 2)( College of Information Engineering,Beijng Institute of Graphic Communication, Beijing 102600, China) 3)(College of Communication Engineering, Xidian University, Xi’an 710071, China)  Abstract：In  order  to  resist  the  attack  from  quantum  computer,  the  algorithms  and  protocols based  on post  quantum  cryptography (PQC) had been proposed one by one, generally speaking, post quantum cryptography mainly contained lattice based cryptosystem (LBC), Hash based cryptosystem (HBC), multivariate public key cryptosystem (MPKC), coding theory based cryptosystem (CBC), LBC  has  been  widely  researched  for  its better  mathematical  properties  and  security.  However,  even  if  the  cryptographic  algorithm itself is secure, it is also probable to suffer various attacks during its implementation process inevitably. Among them, side channel attack has brought more and more threats to this kind of post quantum cryptographic algorithm. NTRU (Number Theory Research Unit) cryptosystem is one of the typical LBC algorithms; the security of this scheme is based on the shortest vector problem (SVP), it has been the IEEEP1363 standard and finance service industrial standard in USA. During the hardware design and implementation process  of  NTRU  cryptography,  there  are  many  potential  risks  such  as  Lattice  Attack,  Simple  Power  Attack,  Differential  Power Attack and Related Power Attack and so on. Lee et.al has implemented the Power Attacks for NTRU cryptosystem in 2010; Wang et.al has implemented the attack through combining Chosen Ciphertext Attack and Power Attack in NTRU-Based wireless body area networks  in  2013.  Up  to  now,  there  is  still  no  any  research  achievement  or  paper  about  defense  scheme  based  on  Homomorphic Masking technology to resist side channel attack of NTRU cryptosystem. Masking technology is one of common countermeasures to resist  side  channel  attack.  By  masking  the  intermediate  values  and  variables,  the  calculating  operations  are  executed  under  the 计算机学报 计   算   机   学   报  Vol. 42 2019  论文在线出版号 No.30  CHINESE JOURNAL OF COMPUTERS  2019Online Publishing No.30  4  基于 NTRU 算法的全同态掩码方案 Lee 等人[10]在提出对 NTRU 算法的攻击的同时，还提出针对侧信道攻击的防御策略。分为如下三种： 1.随机化初始寄存器。在简单能量攻击中，假设寄存器的初始值都是零，因此可以根据计算a +b 和 a +0 的能量消耗的不同来实现破译。为了抵抗简单能量攻击，在算法开始前对每个寄存器都进行随机赋值，在算法执行完后再把随机数从对应的寄存器中减去，从而使得整个算法的执行过程中没有 a +0 的操作，从而使得 SPA 无效。 2.随机盲化密文多项式。通过引入随机整数 r ，计算 ( 0,1..., 1)ic +r i =N - 。在解密的最后将每个寄存器中的值减去 drmod q 即可恢复原始值。 3.随机化存储密钥。密钥是固定的，因此针对密钥的计算，每比特都是固定的，为了抵抗其攻击，将密钥的比特存储进行随机化，使得每次运算中取值顺序是不固定的，因此攻击者无法利用统计方法恢复密钥值。 Lee 等人的方法二是通过引入一个随机数，然后对某一比特进行掩码运算，如果需要同时对所有比特位均实施掩码时，则会导致需要生成大量的随机数，增加资源存储开销，降低方案的性能。本节在此方法的基础上，通过改变密钥的生成方式来抵抗格攻击[17]，利用 NTRU 密码算法本身的同态特性[18-23]对密文进行随机化处理，实现对多项式所有系数进行多重掩码，能够有效的防御选择密文攻击、差分能量攻击、零值攻击及相关能量攻击。 4.1 基于 NTRU 的实现方案 新的方案基于原有的 NTRU 方案，并在此基础上引入 R-LWE 思想，设计一种全同态掩码防御方案 。 其 中 生 成 的 密 文 可 参 考 文 献 [19] 提 出 的BitDecomp 技术转换为 l ´l 的密文矩阵，具体改进如下： 1.密钥生成 Key Gen ： （1）选择标准差s ，生成密钥 f 且可以表示为： f pf1=¢+ ，其中 f ¢ 是从离散高斯分布中取样而来的多项式。 （2）从离散高斯分布中取样 g ，使其满足modqg q ÎR 。 （3）输出私钥ks =f ，公钥 1kp h pgf-= = 。 2.加密算法 Enc ： 加密运算为：c =hs +pe +m。对于明文消息m ，首先将其映射为环上的元素，其次，随机抽样选取多项式 s,e ，然后，根据加密运算步骤实现对消息 0 的加密，即*c =hs +pe ，最后，计算密文(Bit Decomp( ))l lc Flatten I m c´= × +¢ 。 其中，Flatten 函数是用于将矩阵转化为0 /1矩阵。其详细用法参考文献[19]。 3.解密算法 Dec ： 首先，随机生成消息1 2m, m ，根据加密算法对其进行加密运算得密文1 2c, c ，由于不是所有的随机消息都是可用的，也不是所有的随机消息都是可靠的，通常情况下，要确保生成的密文系数是随机的、非空的。 其次，对密文进行运算得1 2C =(c +c) ×c ；然后，计算 f C ，如下： 1 21 222 1 11 2 1 21 2(( ) )(2 2 )( )2 4 2 22 ( ) ( )( ) ( ) (mod )( )= + ×= + + + + += + + ++ + + + ++ + = += +fC f c c cf hs pe m m hs pe mfhshs fhspe fhsm fpepefpem hfs m m fpe m mf m m m f m m m pm m m 最后，根据随机消息1 2m, m ，求出消息 m 。 4.2 全同态掩码方案电路设计 针对上述所提方案，设计一种可实现的加解密电路。 加密电路：在上述新的方案中，加密运算为c =hs +pe +m ，其中 s, e 为高斯抽样随机多项式，h 为公钥， p 为整数，m 为待加密消息。整个加密电路主要分为采样区、数据区、控制运算区。具体实现电路如图 3 所示： 计算机学报 计   算   机   学   报  Vol. 42 2019  论文在线出版号 No.30  CHINESE JOURNAL OF COMPUTERS  2019Online Publishing No.30  Gauss SamplerUniform SamplerRNGPublic KeyGauss DataUniform DataCipherSampler Data Storage ProcessorMultMultAdd ModhspemController 图 3 改进的 NTRU 加密电路设计 其中，各部分对应的功能如下： 1）采样区： Uniform Sampler：产生多项式最高次数 N -1，模数 p 。这些参数在每次加密过程中保持不变，可以在生成之后直接存储至 ROM 中，因此在实际实现的时候可以将此部分忽略。 RNG ： 产 生 随 机 数 ， 可 以 采 用2log N bits 的 LFSR 实现。 Gauss Sampler：山城满足离散高斯分布的序列，组成加密过程中要用到的多项式 s,e ，其中高斯采样过程中需要引入随机数。 2）数据区： Public Key：只读存储器 ROM，用于实现对公钥的存储； Uniform Data：只读存储器 ROM，存储模数； Gauss Data：读写存储器 RAM，用于在每次运算时进行高斯多项式的读写操作； Cipher：读写存储器 RAM，用于存储加密结果。 3）控制运算区： Mult：乘法器，用于实现卷积运算； Add：加法器，对两个乘法器结果进行求和运算； Mod：对运算结果进行取模运算； Controller：对电路的各个模块进行控制。包括采样及数据的读写等。 解密电路：在新的方案中，通过引入随机数的方式实现了对数据的掩码，从而保证了算法的安全性。在设计电路的时候需要一个单独的寄存器用于存储生成的随机数，以便在解密之后对数据进行去掩码操作。解密电路如图 4 所示： 计算机学报计  算  机  学  报      2019 年  Gauss SamplerUniform SamplerRNGPublic KeyGauss DataUniform DataTemp DataSampler Data Storage ProcessorMultMultAdd ModhspemControllerPlaintextcr2cr1cMult AddMult Add 图 4  改进的 NTRU 解密电路设计 其中，取样区与加密电路一致，数据存储区增加一个随机数的寄存器 Temp Data 及存储明文信息的寄存器 Plaintext，两者均采用读写存储器 RAM。重点不同的地方为数据处理区，下面详细介绍其处理过程： 首先，采样区生成随机数并将其读写在 Temp Data 区域； 然后，对随机产生的消息进行加密运算，其加密过程与加密电路保持一致； 其次，将需解密的密文与随机生成的密文进行同态运算，对运算后的密文解密； 最后，使用随机数寄存器中的数据进行去掩码操作，获得有效的明文。 5  基于 NTRU 算法的全同态掩码方案分析 在上述设计的方案中，我们改变了其密钥生成方式以防范格攻击，改变密文的计算流程以防范选择密文攻击及差分能量攻击，其中，为了实现对密文的改进，使用了方案本身的同态特性，下面分析该方案的同态正确性及安全性[20]。 5.1 正确性分析 在解密过程中，使用到同态加和同态乘的运算，下面分别从加法同态特性和乘法同态特性两个方面进行验证，说明方案的正确性。 加法同态特性： 首先，对于每个密文都可以表示如下形式：将对 0 加密所得的密文表示成比特形式： ( 1, 1) ( 1, 2) ( 1,0)*( 2, 1) ( 2, 2) ( 2,0)(0, 1) (0, 2) (0,0)l l l l ll l l l ll lc c cc c ccc c c- - - - -- - - - -- -æ öç ÷ç ÷=ç ÷ç ÷ç ÷è ø 其中，(l,l)c 表示密文的比特位。然后，计算： *( 1, 1) ( 1, 2) ( 1,0)( 2, 1) ( 2, 2) ( 2,0)(0, 1) (0, 2) (0,0)( 1, 1) ( 1, 2) ( 1,0)( 2, 1) ( 2, 2) ( 2,00 00 00 0ll l l l ll l l l ll ll l l l ll l l l lc I m cmc c cmc c cmc c cc m c cc c m c- - - - -- - - - -- -- - - - -- - - - -= × +æ öæ öç ÷ç ÷ç ÷ç ÷= +ç ÷ç ÷ç ÷ç ÷ç ÷è ø è ø++=)(0,l1) (0,l2) (0,0)c c c m- -æ öç ÷ç ÷ç ÷ç ÷ç ÷+è ø 其中，矩阵的对角线表示密文比特位与明文相加。对于生成的两个最终密文1 2c, c 进行同态验证：计算机学报 计   算   机   学   报  Vol. 42 2019  论文在线出版号 No.30  CHINESE JOURNAL OF COMPUTERS  2019Online Publishing No.30  1 21( 1, 1) 1 1( 1, 2) 1( 1,0) 2( 1, 1) 2 2( 1, 2) 2( 1,0)1( 2, 1) 1( 2, 2) 1 1( 2,0) 2( 2, 1) 2( 2, 2) 2 2( 2,0)1(0, 1) 1(0, 2) 1(0,0) 1 2- - - - - - - - - -- - - - - - - - - -- -+æ+ ö+ç ÷+ +ç ÷= +ç ÷ç ÷ç ÷+è øl l l l l l l l l ll l l l l l l l l ll lc cc m c c c m c cc c m c c c m cc c c m c(0, 1) 2(0, 2) 2(0,0) 21( 1, 1) 1 2( 1, 1) 2 1( 1, 2) 2( 1, 2) 1( 1,0) 2( 1,0)1( 2, 1) 2( 2, 1) 1( 2, 2) 1 2( 2, 2) 2 1( 2,0) 2( 2,0)1(0, 1)- -- - - - - - - - - -- - - - - - - - - --æ öç ÷ç ÷ç ÷ç ÷ç ÷+è ø+ + + + ++ + + + +=+l ll l l l l l l l l ll l l l l l l l l llc c mc m c m c c c cc c c m c m c cc2(0, -1) 1(0, -2) 2(0, -2) 1(0,0) 1 2(0,0) 2æ öç ÷ç ÷ç ÷ç ÷ç ÷+ + + +è l l løc c c c m c m 在解密时，任取密文矩阵中的某一行，例如取最后一行进行如下计算： 1(0, 1) 2(0, 1) 1(0,0) 1 2(0,0) 211 2 1(0, ) 2(0, )01 2 1(0) 2(0), ,2 ( )l llii iic c c m c mm m c cm m c cc- --=+ + + += + + += + + +=¢å 其中，1(0) 1(0) 1(0)c =hs +pe，2(0) 2(0) 2(0)c =hs +pe 。 然后，计算： 1 2 1(0) 1(0)2(0) 2(0)11 2 1(0) 1(0)12(0) 2(0)1 2mod() mod() modc f pm m hs pehs pe f p= m m pgf s pepgf s pe f p= m m--ë¢ ù= + + ++ ++ + ++ ++ 由上述可知，加法同态成立。 乘法同态特性： 首先，对密文进行乘法操作运算： 1( 1, 1) 1 1( 1, 2) 1( 1,0)1( 2, 1) 1( 2, 2) 1 1( 2,0)1 21(0, 1) 1(0, 2) 1(0,0) 12( 1, 1) 2 2( 1, 2) 2( 1,0)2( 2, 1) 2( 2, 2) 2 2( 2,0)2- - - - -- - - - -- -- - - - -- - - - -æ+ öç ÷+ç ÷× =ç ÷ç ÷ç ÷+è ø++×l l l l ll l l l ll ll l l l ll l l l lc m c cc c m cc cc c c mc m c cc c m cc(0, -1) 2(0, -2) 2(0,0) 2æ öç ÷ç ÷ç ÷ç ÷ç ÷+è l løc c m 上述乘法所得矩阵的最后一行的元素为： 1(0, 1) 2( 1, 1) 2 1(0, 2) 2( 2, 1) 1(0,0) 1 2(0, 1)1(0, 1) 2( 1, 2) 1(0, 2) 2( 2, 2) 2 1(0,0) 1 2(0, 2)1(0, 1) 2( 1,0) 1(0, 2) 2( 2,0) 1(l l l l l l ll l l l l l ll l l lc c m c c c m cc c c c m c m cc c c c c- - - - - - -- - - - - - -- - - -×é +ù + × + +é +ù×ë û ë û× + ×é +ù + +é +ù×ë û ë û× + × + +0,0) 1 2(0,0) 2é +m ù ×éc +m ùë û ë û     将其进行比特串与二进制转换可得：  1 1 11(0, 1) 2( 1, 1) 1(0, 2) 2( 2, 1) 1(0,0) 2(0, 1)2 2 21(0, 1) 2( 1, 2) 1(0, 2) 2( 2, 2) 1(0,0) 2(0, 2)1(0, 1) 2( 1,0) 1(0, 2) 2( 2,0) 1(02 2 22 2 2l l ll l l l l l ll l ll l l l l l ll l l lc c c c c cc c c c c cc c c c c- - -- - - - - - -- - -- - - - - - -- - - -× + × + + ×+ × + × + + ×+ + × + × + +,0) 2(0,0)1 11(0, 1) 2 2(0, 1) 12 21(0, 2) 2 2(0, 2) 11(0,0) 2 2(0,0) 11 21 11(0, 1) 2( 1, ) 1(0, 2) 2( 2, )0 111(0,0) 2(0, ) 1(02 22 2= 2 22 2l ll ll ll ll li il l i l l ii ili iiicc m c mc m c mc m c mm mc c c cc c c- -- -- -- -- -- - - -= =-=×+ × + ×+ × + ×+ + × + ×+ ×× + × ++ × +å åå1 10, ) 2 2(0, ) 1 1 20 01(0, 1) 2( 1) 1(0, 2) 2( 2) 1(0,0) 2(0)1(0) 2 2(0) 1 1 22l lii ii il l l lm c m m mc c c c c cc m c m m mc- -= =- - - -× + × + ×= × + × + + ×+ × + × + ×=¢å å计算机学报10  计  算  机  学  报      2019 年  击者也有可能构造出精心的数据来避免该掩码的保护。在上述 2 节的分析中，我们得到两组数据，一 组 是 密 文 c =[ 0 , 0 , . . . ,及0 ]另 外 一 组 密 文c =[a, 0,..., 0] ，在经过计算之后的解密结果为[0, 0, 0, 0, 0, 0, 0, 0] 及 [a, 0, 0, a, a, 0, a, 0] 。假设在某次只使用加法同态掩码过程中，得到两组解密结果为： 1 1 1 1[r, 0, 0, r, r, 0, r, 0] 2 2 2 2[a+ r, 0, 0, a+ r, a+ r, 0, a+ r, 0]  则攻击者依然可以根据上述的差分能量攻击方法实现对算法的破译。即差分结果为： 2 1 2 12 1 2 1[ , 0, 0, ,, 0, , 0]D = + - + -+ - + -T a r r a r ra r r a r r 在相应的密钥位上依然是有可能出现峰值，从而对算法造成威胁。因此，通过双重掩码可以有效的避免上述两种可能存在的风险，使得方案的实现过程更加安全。 此外，在原始 NTRU 密码方案中，生成的公钥具有较好的分布性质，但是其并不完全服从均匀分布，因此其不满足密码学上的伪随机性，因此，原始密钥生成算法部分有可能存在有效的格攻击，从而对方案的安全性产生威胁。本文所提方案的密钥生成部分采用文献[17]给出的方法，通过高斯取样的方法，在不改变密钥分布空间的基础上，能够有效的避免格攻击。 本方案利用算法的同态特性构造了一种全同态的掩码防御方案，一般而言，为了抵抗二阶能量攻击，仅需要执行一次加法和乘法同态运算即可。若对系统的安全性有更高的要求，可执行多次全同态运算。由于高阶能量分析存在诸多的受限因素，一般而言，对三阶以上的分析即为困难不可行的，因此，该全同态掩码防御方案可在执行两次同态运算之后，即可抵抗上述攻击，且操作次数较少。 5.3 实验及效率分析 上述 NTRU 算法的解密核心运算为卷积，为了能够更加直观的说明 NTRU 算法存在的缺陷以及本文所提防御方案的优越性，下面通过图示说明：首先，选取 NTRU 解密过程中需要的参数N=25， L=(14, 0) ，密钥值设置为： [0,1, 0, 0,1,1, 0,1,1,1, 0,1,1, 0, 0,1, 0,1, 0,1, 0,1,1, 0,1]f= 图 2 中表明，在实际的分析中通过采取选择密文与差分能量攻击的方式能够有效地对 NTRU进行破译，我们能够得到如图 5 所示的能量波形图：  图 5 未受保护的 NTRU 差分能量攻击 由于不同的操作会消耗不同的能量，从图 2的密文差分结构中可知，当密钥值为 1 时，对应的能量消耗较高，反之能量消耗较少，我们能够从波形上实现对密钥的分析，图 5 中的每个峰值代表密钥位为 1。针对 Lee 等人提出的防御方案二，对某一比特进行掩码处理，如ic +r 。现假设攻击者能够选定两组密文，分别为： +1 1[ , ,..., ]Nc a c c-= ， ++1 1[ , ,..., ]Nc a r c c-= +  其中，掩码值 r 的选取使得 a 与 a +r 之间的汉明重量尽可能的大，根据图 2 所示差分能量攻击方法对两组密文进行计算。由于两组密文之间只有一比特存在差异，且其汉明重量相差很大，因此，在排除噪声的干扰之后，依然能够根据能量曲线实现对密钥的破译。如图 6 所示：  图 6 针对 Lee 的防御策略二的攻击效果 与图 5 对比，由于随机数的掩码参与，使得部分密钥位的能量消耗减少，但是对比其他密钥位的能量信息，密钥有效位的能量消耗依然会有峰值显露。因此，图 6 表明针对 Lee 的保护方案依然可以有效地实施差分能量攻击。在本文提出的防御方案中，假设密文表示为1 2C =(c +c) ×c ，其中1 2c, c 为随机生成的密文，则图 1 中所示比特位表示为相应系数相加。由于密文之间的运算使得多项式的所有系数都随机化，造成无法实施差分能量攻击。如图 7 所示：  图 7 针对全同态掩码防御方案的攻击效果 计算机学报计  算  机  学  报      2019 年       其中，1(i) 1(i) 1(i)c =hs +pe ,2(i) 2(i) 2(i)c =hs +pe ， 然后，计算： 1(0, 1) 2( 1) 1(0, 2) 2( 2)1(0,0) 2(0) 1(0) 2 2(0) 11 2 1 2mod[] modl l l lc f pc c c cc c c m c mm m f p m m- - - -ë¢ ù= × + × ++ × + × + ×+ × = × 由上述可知，乘法同态成立。 为了确保在经过同态掩码之后的密文能够正确解密，需要保证乘法同态掩码时采用的掩码值是可逆的，因此，在每次选取掩码值时，需要对其进行判断，如果不存在逆元，则应该舍弃并重新选择。在去掩码的时候，应当按照先去除乘法掩码，然后去除加法掩码，最后再进行取模运算的顺序执行。 对 掩 码 后 的 密 文 进 行 解 密 可 得 明 文1 2(m +m) ×m ，由于1 2m, m 是由解密电路在本地产生，攻击者无法获取该信息，解密电路首先根据2m 求得其逆12(m)-，然后计算： 11 2 2 1((m m) m(m) ) m m-+ × × - = 最终可以实现正确的去掩码，获取真正的明文消息。 5.2 安全性分析 本节设计的掩码方案主要用于防御选择密文攻击和差分能量攻击，下面主要从这两个方面进行安全性分析。 抗选择密文攻击：在对 NTRU 算法的分析中指出，攻击者可以利用选择密文的方式实现对算法的破译。为了防御选择密文攻击，我们结合算法本身的同态特性对密文进行改造，即假设所有的密文都是不可信的，凡是需要解密的消息都应使用同态算法进行计算，从而实现对密文的掩码，破坏特殊密文与密钥之间的关系，从而达到防御选择密文攻击的目的。 在上述的选择密文攻击中，我们选择一组密文 c =[0,0,...,0] 及另外一组密文 c =[a,0,...,0]进行运算，通过利用密文与密钥之间的关系对算法实现破译。在我们提出的防御方案中，我们引入了随机密文，改变密文的结构，使得攻击者无法构造密文，消除选择密文攻击的隐患。假设攻击者提交给解密电路的密文是 c ，解密电路检查密文的合法性之后，生成随机密文rc ，对密文 c 与随机密文rc 进行运算得密文 ( , )rc c ，因为rc 对于攻击者来说是随机不确定的且取样范围较大不可预测，所以，攻击者知晓rc 的概率可以忽略，也就是说 ( , )rc c 没有泄露有关中间值的消息，并且在每一次解密运算过程中，该密文都是随机生成，防止攻击者通过重复大量实验获取有效信息。解密电路对运算后的密文进行解密，得到加掩码后的明文消息，再利用随机消息进行去掩码操作即可获得真正的明文消息。 抗差分能量攻击：差分能量攻击是在选择密文的基础上，通过精心构造合法密文，利用数据之间的关系对算法进行破译。本文提出的防御策略通过同态运算实现对密文的改进，使得差分运算无法正常获取密钥信息。 对于密文 c ，第一次解密运算时，随机生成密文r1c 和r2c ，进行计算得1 2( )r rc +c ×c ，第二次解密运算时，随机生成密文r1c¢和r2c¢，计算得1 2( )r rc c c+¢ ×¢，根据上述差分思想，假设攻击者构造出合法密文c ，经计算后，进行差分计算得： 1 2 1 22 1 2 2 1 22 2 1 2 1 2( ) -( )= + - -= ( - )+ -+ × +¢ ×¢× × ×¢ ¢ ×¢×¢ ×¢ ×¢r r r rr r r r r rr r r r r rc c c c c cc c c c c c c cc c c c c c c 其中，攻击者已知密文 c ，而其他中间值均是不可知的，且在每次计算过程中该中间值是随机变化的，因此，攻击者无法通过重复大量实验获取能量曲线，进而通过差分能量攻击的方式进行对算法的破译，即该方案能够有效的抵抗 DPA攻击。 在该方案中采用对数据进行二重掩码，即同时进行加法掩码和乘法掩码。为的是能够使数据充分随机化，同时还能避免由于单一掩码带来的安全隐患，如零值攻击。 零值攻击是假设处理数据值 0 所需的能量消耗小于处理其他值的能量消耗。即，如果所需处理的被掩码数据为 0，则无论掩码值是多少，其计算结果均为 0，此时，该过程的能量消耗明显低于其他情况下的能量消耗，同时对应位上的能量迹总是表现为低能量。例如，对于计算 m×r ，这里 m 为被掩码数据， r 为掩码值。则零值模型的形式化定义如下： 0, 01, 0mh m rmì== × = í¹î 假设采取乘法同态进行掩码处理，即rc ×c ，若 c =0 ，则rc ×c 恒为 0，而如果 c ¹0 ，则rc ×c不为 0，因此，攻击者可以根据零值模型进行破译。而通过双重掩码的方式对数据进行处理，使得即使攻击者根据零值攻击方式获取中间值，该中间值也是经掩码处理的，即rc +c ； 若只采取加法同态掩码对数据进行处理，攻计算机学报