论文部分内容阅读
摘要：为便于NTRU公钥密码教学，描述了NTRU公钥密码，通过简化实例演示了NTRU公钥密码的密钥生成算法、加密算法及解密算法的具体实现过程。
关键词：NTRU;公钥密码;可视化教学
中图分类号：G40-057文献标识码：A文章编号：2095-7394（2014）04-0090-03
0引言
在量子计算机上，基于大整数因式分解、离散对数、椭圆曲线等的公钥密码[1-3]已经被破解，基于格的NTRU公钥密码被认为能够抗量子计算机攻击[4]。NTRU[5]因其密钥产生方法简单，加密、解密的速度比RSA等公钥密码算法更快，使得NTRU公钥密码算法已经于2009年被接受为IEEE P1363.1标准。
NTRU公钥密码算法研究主要侧重于分析NTRU的安全性[6-7]。密码学界普遍认为NTRU的安全性是基于计算理想格中最短向量的困难问题，对NTRU的攻击方法主要是CS格归约攻击[6]。
由于NTRU公钥密码需要的数学背景知识较多，因此在讲授NTRU公钥密码时如何实现可视化教学目标就显得较为困难。本文将使用Shoup的NTL库[8]尝试研究NTRU公钥密码算法的可视化教学。
1NTRU公钥密码算法
设Z为整数集，Zn=Z/nZ={0，1，…，n-1}。设多项式环R=Z[x]/表示所有次数为N-1的一元整系数多项式集，Rn=Zn[x]/。R上多项式加法运算为普通多项式加法运算，用符号+表示;R上多项式乘法运算为模xN-1上乘法运算，用符号表示。多项式f∈R也表示为向量形式，即f=∑N-1i=0fixi=[f0，f1，…，fN-1]。
在模xN-1上乘法运算作用下，多项式f在R上形成循环格，即xf=[fN-1，f0，f1，…，fN-2]，xif=[fN-i，fN-i+1，…，fN-1，f0，f1，…，fN-i-1]。如果以xif，i=0，…，N-1作为列生成矩阵，记为Rot（f），则fr=Rot（f）×r。如果f在Rn上可逆，即存在逆元y满足（fy）modn=1，则在模n下y=（Rot（f））-1×[1，0，…，0]。因此，判定f在Rn是否可逆问题等价于判定矩阵F在模n上是否可逆，而在模n下Rot（f）是否可逆归约到Rot（f）的行列式|Rot（f）|与n是否互素。如果|Rot（f）|与n互素，则f在Rn可逆。
NTRU公钥密码由正整数参数集（N，p，q，df，dg，dr）和四个次数为N-1的多项式集Lf，Lg，Lr组成。这里N为素数，p为多项式或整数，q为整数，满足p，q互素，即gcd（p，q）=1。
设L（d1，d2）表示多项式集中元素有d1个系数为1，d2个系数为-1，其余系数为0。根据NTRU，则多项式集Lf=L（df，df-1），Lg=L（dg，dg），Lr=L（dr，dr）。明文多项式集Lm∈R表示集中多项式元素的系数位于区间[-（p-1）/2，（p-1）/2]。
1.1密钥生成算法：
（1）随机选择f∈Lf，使得f在Rp，Rq都存在逆元f-1p，f-1q，满足ff-1p=1modp，ff-1q=1modq。
（2）随机选择g∈Lg，并计算h=pf-1qgmodq。
（3）输出公钥pk={N，p，q，df，dg，dr，h}，私钥sk={f，f-1p}。
1.2加密算法：
（1）给定公钥pk和明文m∈Lm，随机选择r∈Lr。
（2）输出密文c=（rh+m）modq。
1.3解密算法：
（1）给定私钥sk和密文c，计算a=cfmodq
（2）将多项式a的系数映射到模q的绝对最小剩余系，即b=[a]q，使得系数bi∈（-q/2，q/2]。
（3）将b的系数进行模p以去除p（rg）项，得到e=（fm）modp。
（4）输出明文m=ef-1pp。
江苏理工学院学报第20卷
第4期
古春生：NTRU公钥密码的可视化教学
2NTRU可视化教学
在NTRU教学示例中，假设Alice产生的NTRU公钥密码的公钥和私钥分别为pk、sk。现在Bob需要发送信息给Alice，Bob使用Alice公钥pk加密需要发送给Alice的明文消息，并通过网络将密文发送给Alice。Alice使用私钥sk解密密文得到明文消息。
设NTRU公钥密码的正整数参数集（N，p，q，df，dg，dr）=（11，3，32，4，3，3），即Lf=L（4，3），Lg=L（3，3），Lr=L（3，3），Lm中多项式的系数属于{-1，0，1}。
2.1Alice生成密钥：
（1）随机选择f=-x-x5+x6+x7+x8-x9+x10∈Lf。因为|Rot（f）|=5 171与p，q互素，故f在Rp，Rq存在逆元f-1p，f-1q，满足ff-1p=1modp，ff-1q=1modq。计算f-1p，f-1q如下：
f-1p=2+2x+x2+x4+x5+2x6+x9，
f-1q=5+17x+14x2+22x3+11x4+16x5+14x7+24x8+19x919x10。
（2）随机选择g=-x-x3-x5+x7+x8+x10∈Lg，并计算h=pf-1qgmodq如下：
h=21+9x+30x2+25x3+20x4+7x5+23x6+5x7+31x8+13x9+8x10。
（3）输出公钥pk={N，p，q，df，dg，dr，h}，私钥sk={f，f-1p}。
2.2Bob加密明文 （1）给定公钥pk和明文m=-x+x2-x3-x4+x5+x7-x9-x10∈Lm，随机选择r=1-x6-x7+x8+x9-x10∈Lr。
（2）计算输出密文c=（rh+m）modq，并发送给Alice。
c=8+25x+5x2+30x3+28x4+x6+30x7+8x8+11x9+12x10。
2.3Alice解密密文
（1）给定私钥sk和密文c，计算a=（cf）modq如下：
a=1+30x+19x3+6x4+30x5+28x6+4x7+9x8+28x9+3x10。
（2）将多项式a的系数映射到模q的绝对最小剩余系b=[a]q如下：
b=1-2x-13x3+6x4-2x5-4x6+4x7+9x8-4x9+3x10。
（3）对b的系数进行模p运算以去除p（rg）项，得到e=（fm）modp如下：
e=1+x+2x3+x5+2x6+x7+2x9。
（4）输出明文m=[ef-1p]p=-x+x2-x3-x4+x5+x7-x9-x10。可以看出，解密明文m与Bob发送的消息相同。
3结语
为可视化教学NTRU公钥密码，本文在描述NTRU公钥密码算法基础上，通过简化实例演示了NTRU公钥密码的密钥生成算法、加密算法及解密算法的具体实现过程，也简要分析了公钥密码所使用的数学性质。
参考文献：
[1]Rivest R，Shamir A，Adleman L.A method for obtaining digital signatures and public-key cryptosystems[J].Communication of the ACM，1978，21（2）：120-126.
[2]ElGamal T.A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J].CRYPTO ，LNCS 1984，196：10-18.
[3]Koblitz N.Elliptic curve cryptosystems[J].Mathematics of Computation，1987，48：203-209.
[4]Shor P W.Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J].SIAM Journal Computing 26（5）：1 484-1 509.
[5]Hoffstein J，Pipher J，Silverman J H.NTRU.a ring based public key cryptosystem[C].Algorithmic Number Theory（ANTS III），LNCS 1998，1423：267-288.
[6]Coppersmith D，Shamir A.Lattice attacks on NTRU[J].Eurocrypt， LNCS 1997：52-61.
[7]Nguyen P Q ，Vallée B （editors）The LLL Algorithm：Survey and Applications.Information Security and Cryptography[M].Berlin：Springer，2009：349-390.
[8]Shoup V NTL.A Library for doing Number Theory[EB/OL].（2009-05-02）[2009-08-14].http：//shoup.net/ntl/，Version 5.
关键词：NTRU;公钥密码;可视化教学
中图分类号：G40-057文献标识码：A文章编号：2095-7394（2014）04-0090-03
0引言
在量子计算机上，基于大整数因式分解、离散对数、椭圆曲线等的公钥密码[1-3]已经被破解，基于格的NTRU公钥密码被认为能够抗量子计算机攻击[4]。NTRU[5]因其密钥产生方法简单，加密、解密的速度比RSA等公钥密码算法更快，使得NTRU公钥密码算法已经于2009年被接受为IEEE P1363.1标准。
NTRU公钥密码算法研究主要侧重于分析NTRU的安全性[6-7]。密码学界普遍认为NTRU的安全性是基于计算理想格中最短向量的困难问题，对NTRU的攻击方法主要是CS格归约攻击[6]。
由于NTRU公钥密码需要的数学背景知识较多，因此在讲授NTRU公钥密码时如何实现可视化教学目标就显得较为困难。本文将使用Shoup的NTL库[8]尝试研究NTRU公钥密码算法的可视化教学。
1NTRU公钥密码算法
设Z为整数集，Zn=Z/nZ={0，1，…，n-1}。设多项式环R=Z[x]/
在模xN-1上乘法运算作用下，多项式f在R上形成循环格，即xf=[fN-1，f0，f1，…，fN-2]，xif=[fN-i，fN-i+1，…，fN-1，f0，f1，…，fN-i-1]。如果以xif，i=0，…，N-1作为列生成矩阵，记为Rot（f），则fr=Rot（f）×r。如果f在Rn上可逆，即存在逆元y满足（fy）modn=1，则在模n下y=（Rot（f））-1×[1，0，…，0]。因此，判定f在Rn是否可逆问题等价于判定矩阵F在模n上是否可逆，而在模n下Rot（f）是否可逆归约到Rot（f）的行列式|Rot（f）|与n是否互素。如果|Rot（f）|与n互素，则f在Rn可逆。
NTRU公钥密码由正整数参数集（N，p，q，df，dg，dr）和四个次数为N-1的多项式集Lf，Lg，Lr组成。这里N为素数，p为多项式或整数，q为整数，满足p，q互素，即gcd（p，q）=1。
设L（d1，d2）表示多项式集中元素有d1个系数为1，d2个系数为-1，其余系数为0。根据NTRU，则多项式集Lf=L（df，df-1），Lg=L（dg，dg），Lr=L（dr，dr）。明文多项式集Lm∈R表示集中多项式元素的系数位于区间[-（p-1）/2，（p-1）/2]。
1.1密钥生成算法：
（1）随机选择f∈Lf，使得f在Rp，Rq都存在逆元f-1p，f-1q，满足ff-1p=1modp，ff-1q=1modq。
（2）随机选择g∈Lg，并计算h=pf-1qgmodq。
（3）输出公钥pk={N，p，q，df，dg，dr，h}，私钥sk={f，f-1p}。
1.2加密算法：
（1）给定公钥pk和明文m∈Lm，随机选择r∈Lr。
（2）输出密文c=（rh+m）modq。
1.3解密算法：
（1）给定私钥sk和密文c，计算a=cfmodq
（2）将多项式a的系数映射到模q的绝对最小剩余系，即b=[a]q，使得系数bi∈（-q/2，q/2]。
（3）将b的系数进行模p以去除p（rg）项，得到e=（fm）modp。
（4）输出明文m=ef-1pp。
江苏理工学院学报第20卷
第4期
古春生：NTRU公钥密码的可视化教学
2NTRU可视化教学
在NTRU教学示例中，假设Alice产生的NTRU公钥密码的公钥和私钥分别为pk、sk。现在Bob需要发送信息给Alice，Bob使用Alice公钥pk加密需要发送给Alice的明文消息，并通过网络将密文发送给Alice。Alice使用私钥sk解密密文得到明文消息。
设NTRU公钥密码的正整数参数集（N，p，q，df，dg，dr）=（11，3，32，4，3，3），即Lf=L（4，3），Lg=L（3，3），Lr=L（3，3），Lm中多项式的系数属于{-1，0，1}。
2.1Alice生成密钥：
（1）随机选择f=-x-x5+x6+x7+x8-x9+x10∈Lf。因为|Rot（f）|=5 171与p，q互素，故f在Rp，Rq存在逆元f-1p，f-1q，满足ff-1p=1modp，ff-1q=1modq。计算f-1p，f-1q如下：
f-1p=2+2x+x2+x4+x5+2x6+x9，
f-1q=5+17x+14x2+22x3+11x4+16x5+14x7+24x8+19x919x10。
（2）随机选择g=-x-x3-x5+x7+x8+x10∈Lg，并计算h=pf-1qgmodq如下：
h=21+9x+30x2+25x3+20x4+7x5+23x6+5x7+31x8+13x9+8x10。
（3）输出公钥pk={N，p，q，df，dg，dr，h}，私钥sk={f，f-1p}。
2.2Bob加密明文 （1）给定公钥pk和明文m=-x+x2-x3-x4+x5+x7-x9-x10∈Lm，随机选择r=1-x6-x7+x8+x9-x10∈Lr。
（2）计算输出密文c=（rh+m）modq，并发送给Alice。
c=8+25x+5x2+30x3+28x4+x6+30x7+8x8+11x9+12x10。
2.3Alice解密密文
（1）给定私钥sk和密文c，计算a=（cf）modq如下：
a=1+30x+19x3+6x4+30x5+28x6+4x7+9x8+28x9+3x10。
（2）将多项式a的系数映射到模q的绝对最小剩余系b=[a]q如下：
b=1-2x-13x3+6x4-2x5-4x6+4x7+9x8-4x9+3x10。
（3）对b的系数进行模p运算以去除p（rg）项，得到e=（fm）modp如下：
e=1+x+2x3+x5+2x6+x7+2x9。
（4）输出明文m=[ef-1p]p=-x+x2-x3-x4+x5+x7-x9-x10。可以看出，解密明文m与Bob发送的消息相同。
3结语
为可视化教学NTRU公钥密码，本文在描述NTRU公钥密码算法基础上，通过简化实例演示了NTRU公钥密码的密钥生成算法、加密算法及解密算法的具体实现过程，也简要分析了公钥密码所使用的数学性质。
参考文献：
[1]Rivest R，Shamir A，Adleman L.A method for obtaining digital signatures and public-key cryptosystems[J].Communication of the ACM，1978，21（2）：120-126.
[2]ElGamal T.A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms[J].CRYPTO ，LNCS 1984，196：10-18.
[3]Koblitz N.Elliptic curve cryptosystems[J].Mathematics of Computation，1987，48：203-209.
[4]Shor P W.Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J].SIAM Journal Computing 26（5）：1 484-1 509.
[5]Hoffstein J，Pipher J，Silverman J H.NTRU.a ring based public key cryptosystem[C].Algorithmic Number Theory（ANTS III），LNCS 1998，1423：267-288.
[6]Coppersmith D，Shamir A.Lattice attacks on NTRU[J].Eurocrypt， LNCS 1997：52-61.
[7]Nguyen P Q ，Vallée B （editors）The LLL Algorithm：Survey and Applications.Information Security and Cryptography[M].Berlin：Springer，2009：349-390.
[8]Shoup V NTL.A Library for doing Number Theory[EB/OL].（2009-05-02）[2009-08-14].http：//shoup.net/ntl/，Version 5.