基于格的第三方移动支付加密模型ECC-NTRU

宁 卓,石 伟,孙知信

(南京邮电大学 物联网学院，江苏 南京 210003)

基于格的第三方移动支付加密模型ECC-NTRU

宁 卓,石 伟,孙知信

(南京邮电大学 物联网学院，江苏 南京 210003)

随着移动互联网以及移动智能终端的普及，移动支付成为越来越频繁的支付方式。针对量子计算给传统的公钥加密系统带来的威胁，利用NTRU算法的抗量子计算以及高效性加解密的特点，同时为了避免NTRU在签名算法上的失效，结合ECC具有高效的签名算法的优势，采用哈希链进行身份认证，设计出一种ECC-NTRU的移动支付加密方案。通过理论分析对比，表明该方案增强了移动支付加密的安全性，可以抗击量子攻击以及中间人攻击,同时对比性能可知该方案可以提高加解密速率，优化系统流畅度。虽然ECC-NTRU相对ECC模型增加了115 KB左右的系统开销，但是相对现在智能手机GB级别的内存，增大的开销完全可以承受，运行速度相比ECC快了几百倍，这极大地提高了智能终端程序的流畅度，因而具有很强的实用性。

移动支付；RSA；ECC；NTRU；量子计算

1 概 述

移动支付是指通过手机、平板或者PDA等移动终端，利用无线网络实现的商业交易。第三方移动支付属于移动支付平台的第三种运营模式，指的是非金融机构、非电信运营商的第三方承建的移动支付平台。

具备相应实力和信誉保障的第三方与各大银行签订协议，建立自己的支付平台，是为各个角色做到技术保障和信用担保的平台。传统的模型是一种银行系统一种支付模型，不利于跨行交易以及小额支付，而该模型打破了银行系统之间的壁垒，便于小额支付。

但是在这个模型中，由于移动终端与第三方平台之间通过无线网络通信，所以在这个过程中最容易受到攻击。例如A和B之间进行通信，其会话密钥是通过RSA公钥加密进行协商，窃听者通过窃听收集到经过RSA加密的数据，如果运用量子算法[1]进行破解，即可很容易获取A和B的会话密钥，因而安全问题最为显著。

第三方支付一般模型如图1所示。

图1 第三方支付一般模型

针对上述存在的安全性问题，提出了一种ECC-NTRU方案。该方案结合ECC快速签名以及NTRU[2]算法抗量子计算的特点，解决了传统支付模型不具备抗量子计算以及效率低的问题。

2 第三方移动支付的安全现状

常见的基于第三方的移动支付主要分为两种技术方案：第一种是基于Wap的移动支付模式；另一种是基于J2ME的第三方移动支付。

2.1 基于Wap的第三方移动支付

Wap是一种针对手机和PAD等移动设备有限的计算资源，适用于无线网较低带宽、高延迟应用特点的标准协议。Wap安全架构由无线标记语言脚本(WML Script)、无线公钥基础设施(Wireless Public Key Infrastructure，WPKI)、无线个人身份模块(Wireless SIM，WIM)和无线传输层安全(Wireless Transport Layer Security，WTLS)四部分组成，而WPKI和WTLS是安全保障的核心。

WPKI从本质上来说采用的是轻量级的公钥加密算法的PKI，即安全强度较低的RSA以及ECC[3]。如前所述，随着量子计算的深入研究，这些传统公钥密码算法的安全性都将受到挑战，其在无线网络上的轻量级实现的安全性更受到质疑。

WTLS类似于Internet中的TLS安全套接层，但是考虑到无线网络性能的局限性，因而对其进行了简化和压缩，导致的结果是Wap协议栈没有提供可靠的传输层，所以存在多种攻击，包括可选择明文攻击、中间人攻击以及重放攻击[4-5]。

2.2 基于J2ME的第三方移动支付

J2ME是一种高度优化的Java运行环境，主要为智能手机、PAD、汽车导航系统等消费类电子设备提供Java语言平台。由于J2ME技术能实现跨平台运行，即便是在不同的移动终端平台上，开发的应用程序也能实现同一功能。J2ME还解决了低速带宽下Wap方式不能访问的HTML文件和各种多媒体信息等问题，进一步推广了无线Internet的各项应用。

但是利用J2ME平台设计第三方移动支付方案，就必须考虑到加密协议的问题。现有用于J2ME平台的加密技术主要有XML加密技术[6]以及SET协议[7]。XML加密结合了XML技术以及现有的加密算法，实现了对XML节点或者不同元素加密的操作。XML加密技术的特点是结合了对称加密(包括DES、AES算法)与非对称加密(包括RSA或ECC加密算法)的优势，先通过生成的公钥加密会话密钥，再以高效的对称密码算法实现对信息的加密保护。XML具有良好的可读性、扩展性、跨平台性等优点，这都为基于XML的加密带来了广阔的应用前景。但是究其本质，XML加密只是XML技术与传统型加密技术的结合，因此J2ME平台的安全性也是建立在RSA和ECC公钥的加密的基础之上，在量子攻击下同样不安全。

综上所述，现有的第三方移动支付加密协议存在的共有缺陷就是不具有抗量子计算能力，且一旦提高安全等级，密钥尺寸和计算量就会大幅提高，其算法的实现性能将会制约其在移动支付环境下的实用性。因而，研究一种高效且具有抗量子效应的基于第三方的移动支付加密模型成为当务之急。

2.3 抗量子计算的格加密技术

随着量子计算的研究深入，国内外掀起了研究抗量子计算密码的高潮。而基于格上困难问题设计的加密方案，作为后量子时代的典型代表，是最有希望解决保密性问题的途径之一。

1996年，Ajtai给出了一个结论[8]：基于某些格问题的任意一个密码体制，其安全性等价于最难情况下的密码体制的安全性，并提出了基于格中最难情况下的u-SVP(unique Shortest Vector Problem)的AD加密体制。该方案具备可证明安全性，但系统效率很低，达不到实用要求(具体数据见表1)。

表1 基于格的公钥方案的效率的对比

GGH[9]方案是第二类方案的代表，该方案没有安全性证明，且已经被攻破。后来Regev首次提出机器学习中奇偶性学习问题(Learning from parity With Error，LWE)，并且在此基础上建立公钥算法。该体系算法安全性高，但是也存在密钥尺寸大、效率低的问题[10-11]。

NTRU[2]是基于多项式环的公钥密码方案，是迄今为止最实用的基于格的公钥密码方案。该体制建立在多项式环的基础上，加密算法避免了大整数幂的模运算，只涉及多项式的加减和乘运算，因而效率很高。但是NTRU的安全性证明没有得到有效解决。2009年，Hirschhorn推荐了一组参数选择和填充方案[12]，使NTRU可以抵抗绝大部分攻击，因而至今还没有一种针对它的有效攻击方案出现。然而NTRU还没有比较理想的签名方案，现有的基于NTRU两个典型签名方案包括R-NSS[13]和NTRUSign[14]。其中R-NSS已经被攻破[15]，而NTRUSign存在致命攻击[16]。

综上所述，针对NTRU在实用中尚缺乏实用的签名算法的困境，文中拟结合现有的ECC算法高效签名以及NTRU算法高效加解密且抗量子计算的优点，设计一种基于第三方的移动支付加密模型ECC-NTRU。

3 一种结合NTRU与ECC算法的加密支付模型(ECC-NTRU)

由于NTRU暂时没有比较出色的签名算法，因而需要结合其他公钥加密算法来保障支付过程的保密性以及不可否认性。在同等安全条件下，ECC加密以及解密速度均比RSA要快很多，所以文中选择ECC作为签名算法。NTRU算法具有较高的加解密速率且抗量子计算，因而选择NTRU为整个过程数据加密，同时为抗击中间人攻击，设计了一种哈希链的用户认证模型。具体过程如下所示：

第一阶段：账号申请，即安装证书(见图2(a))。

(1)使用第三方支付模型之前首先得下载支付客户端。

(2)根据客户端指示申请第三方账号。

图2 第三方移动支付安全模型

第二阶段：认证过程(见图2(b))。

(1)用户把自己的IDA以及hashN-1(yA)并运算IDA||hashN-1(yA)发送给第三方平台，第三方根据用户的IDA，计算hash(hashN-1(yA)),判断hash (hashN-1(yA))是否等于对应的尾链值hashN(yA),如果相等则表示该用户认证成功。

(2)步骤(1)完成后把该用户哈希链的尾链值改为hashN-1(yA)，并发送给第三方平台。若N≤2则重新生成哈希链并把对应的尾链值发送给第三方平台。

第三阶段：支付过程(见图2(c))。

(1)客户端要发送信息m给第三方，首先C1=HASH(m)形成消息摘要。

(4)客户端将第三步加密信息发送给第三方。

该方案是利用NTRU效率和安全性高的优点，并弥补NTRU在数字签名方面的缺陷，但是引进两种公钥加密算法增加了系统开销，对于移动终端来说也是不利的。

4 ECC-NTRU性能分析

由于移动终端的通信方式是易于被攻击的无线信号，因而需要分析其终端是否能够抵抗中间人攻击。此外考虑到该加密模型在移动终端的实用性，还需要分析其效率和系统开销。

抗中间人攻击：该方案中引入哈希链来对用户身份进行认证，若非法用户截取用户数据，想获取身份认证，但其缺乏哈希链的验证，因而无法冒取；此外用户与第三方通信的数据包都是通过NTRU加密的密文，非法用户即使截取到数据包也不能获取有用的信息。

不可否认性：该方案中为了避免了NTRU在签名算法上的不足，引入ECC签名算法确保支付过程的不可否认性。ECC算法的安全性高于RSA,因而其安全可以得到有效保障。

ECC-NTRU的安全强度：ECC-NTRU模型中，终端与第三方平台的数据都要通过NTRU公钥进行加密后传输，因而其安全性等价于NTRU的安全性。利用LLL[17]算法及其改进算法可以求解低维度NTRU格中难题，但是如果格的维数很大，LLL算法也不能解决。文献[18]给出了破解NTRU粗略时间算法。NTRU公钥密码体制估计的破解时间如表2所示。

表2 NTRU公钥密码体制估计的破解时间

注：MIPS-years 表示以每秒处理100万条指令的处理器运算一年为单位。整个实验在400 MHz的Celeron处理器上进行，所使用的攻击算法为LLL算法。

上述攻击方法是指数时间算法，攻击者不能对NTRU密码体制实施有效攻击。因此，在现阶段NTRU公钥密码体制具备足够高的安全性。

ECC-NTRU的系统开销：用哈希链作为身份认证相对于其他方法的优势就是效率很高，其速度是基于复杂问题签名算法的10 000倍[19]。该模型中通信的数据包都需要NTRU加密，因而其加解密的速度主要看NTRU的效率。表3为NTRU与ECC的模型对比，可知NTRU加解密速度是ECC的几百倍。

表3 ECC-NTRU模型与ECC模型对比

注：硬件环境为1 GHz的Pentium III处理器，软件环境为NTRU加密包和ECC加密包。

但是在ECC-NTRU模型中，为了避免NTRU算法在签名方面的缺陷，加入ECC算法做签名，这样带来的缺陷是，移动终端会运行两套公钥加密算法，必然会增加系统开销，这对移动终端来说是不利的。若开发移动终端的NTRU加解密模块采用NTRU官网给出的ntru-1.2.jar版本的开发包，其大小为115 KB，那么ECC-NTRU相对于ECC加密模型只增加了约115 KB的系统消耗，但是其加解密速度增加了近几百倍。

综上所述，虽然ECC-NTRU相对ECC模型增加115 KB左右的系统开销，但是相对现在智能手机GB级别的内存，增大的开销完全可以承受。此外ECC-NTRU其运行速度相比ECC快了几百倍，这极大地提高了智能终端程序的流畅度。

5 结束语

研究了现有基于第三方的移动支付的技术，分析了这些技术的特点，并针对这些技术的缺陷以及无线支付的特点提出了一种基于格的ECC-NTRU加密模型。分析表明该方案具有抗量子计算、效率高、安全等优点，但也增大了系统开销。未来的研究方向是：改进现有的NTRU签名算法，提高其效率和安全性；把NTRU加密算法融入WAB技术或者XML加密技术。

[1] Shor P W.Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[EB/OL].(1995-08-27).http://lanl.arxiv.org/pdf/quant-ph/9508027.

[2] Hoffstein J,Pipher J,Silverman J.NTRU:a ring-based public key cryptosystem[C]//Algorithmic number theory symposium.Portland:Springer,1998:267-288.

[3] Schoof R.Elliptic curves over finite fields and the computation of square roots mod p[J].Mathematics of Computation,1985,44(170):483.

[4] 何毅俊.WAP中WTLS安全性研究[D].长沙:中南大学,2007.

[5] 刘辉洲.WTLS分析与设计[D].济南:山东大学,2010.

[6] 车 葵,牛晓太, 邢书涛. XML加密方法的研究与实现[J].计算机工程与设计,2008,29(20):5180-5183.

[7] 张若岩.基于SET协议的移动支付系统的研究与实现[D].西安:西北大学,2008.

[8] Ajtai M.Generating hard instances of lattice problems[C]//Proceedings of the 28th annual ACM symposium on theory of computing.New York:ACM,1996:99-108.

[9] Goldreich O,Goldwasscr S,Halevi S.Public-kcryptosystcms from lattice reduction problems[C]//Crypto'97.Santce Barbara:Springer,1997:112-131.

[10] Lyubashevsky V,Peikert C,Regev O.On ideal lattices and learning with errors over rings[J].Journal of ACM,2013,60(6):1-23.

[11] Wei Ping,Wu Liqiang,Yang Xiaoyuan,et al.A public cryptosystem from R-LWE[C]//IEEE 3rd international conference on communication software and networks.[s.l.]:IEEE,2011:508-513.

[12] Jaulmes É,Joux A.A chosen-ciphertext attack against NTRU[C]//Advances in cryptology.Berlin:Springer,2000:20-35.

[13] Hoffstein J，Pipher J，Silverman J H.NSS:an NT-RU lattice-based signature scheme[C]//Advanced in cryptology-Eurocrypt’01.Berlin:Springer-Verlag,2001:123-127.

[14] Hoffstein J,Pipher J,Silverman J H,et al.NTRUSign:digital signatures using the NTRU lattice[C]//Proceedings of CTRSA’03.San Francisco:[s.n.],2003:122-140.

[15] Gentry C,Szydlo M.Cryptanalysis of the revised NTRU signature scheme[C]//Advances in cryptology-Eurocrypt’02.Berlin:Springer-Verlag,2002:299-320.

[16] Nguyen P Q,Regev O.Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures[M]//Advances in cryptology-Eurocrypt’06.Berlin:Springer-Verlag,2006:271-288.

[17] Lenstra A K,Lenstra H W,Lovasz L.Factoring polynomials with rational coefficients[J].Mathematische Analen,1982,261(4):515-534.

[18] Silverman J H.Estimated breaking times for NTRU lattices[EB/OL].1999-03-09.http://www. ntru.com.

[19] 施荣华,翁丽萍,王国才.基于单向哈希链的Ad Hoc网络密钥协商协议[J].湖南大学学报:自然科学版,2011,38(3):77-81.

A Secure M-payment Model Combing NTRU with ECC

NING Zhuo,SHI Wei,SUN Zhi-xin

(School of Internet of Things,Nanjing University of Posts and Telecommunications, Nanjing 210003,China)

With the popularity of wireless Internet and smart phones,mobile payment has become more and more frequent.For the threat of quantum computation to the traditional public-key encryption system,using the features of anti-quantum computing and high efficiency for encryption and decryption of NTRC algorithm and avoiding the failure of NTRU in signature,combined with ECC with the advantages of efficient signature algorithm,adopting Hash chain to identity authentication,a mobile payment encryption scheme of ECC-NTRU is designed.By comparison with theoretical analysis,it shows that the scheme is to enhance the security of the encryption mobile payment and fight the attack of quantum and middle.At the same time comparative performance shows this scheme can improve the encryption speed and fluency.Although the ECC-NTRU increases system overhead by about 115 KB compared with ECC,the increasing cost can afford in comparison with smart phones with level of GB of memory,running faster than ECC hundreds,which greatly improves the fluency of intelligent terminal program with very strong practicability.

mobile payment;RSA;ECC;NTRU;quantum attack

2015-06-05

2015-10-14

时间：2017-01-04

国家自然科学基金资助项目(60973140,61170276,61373135);江苏省产学研项目(BY2013011);江苏省科技型企业创新基金项目(BC2013027);江苏省高校自然科学研究重大项目(12KJA520003)

宁 卓(1975-),女,博士,研究方向为入侵检测技术、网络安全、网络行为学；孙知信，教授，研究方向为网络安全理论与技术、保密通信、网络环境下的软件与安全技术。

http://www.cnki.net/kcms/detail/61.1450.TP.20170104.1017.018.html

TP301

A

1673-629X(2017)01-0084-05

10.3969/j.issn.1673-629X.2017.01.019