整数表示在公钥密码体制中的应用

摘要

RSA 和椭圆曲线密码体制是保障电子商务安全的两种常用公钥密码体制。在这两种公钥密码体制上最基本的操作是计算模幂乘法和标量乘，它可以用普通的二进制算法实现。众所周知，具有较少非零数位的整数表示可以提高一些代数结构上基本操作(如计算标量乘)的效率。比如利用NAF算法，可以比普通的二进制算法减少大约1/6的椭圆曲线点加运算。然而利用低非零密度的整数表示计算点乘很容易受到边带信道攻击。这种攻击充分利用密码设备在运行过程中泄漏的计算时间、电量消耗曲线等敏感信息来获得一些秘密信息。因此本文主要研究各种整数表示在公钥密码体制上的应用和设计抵抗边带信道攻击的编码。 本文主要的研究内容如下： 1．从左到右的最优基数 r 的编码。近年来，基数 r 上的编码被用于特征为 r的椭圆曲线上有效点乘计算。Takagi等人在ISC 2004上提出一种从左到右的窗口为 w 的基数 r 的非邻接表示，即 wrNAF。我们提出一种新的带符号编码，该编码具有和wrNAF相等的非零数位密度((r-1)/(w(r-1)+1))。在相同数位集上，新的编码具有最小的Hamming重量，且可以用从左到右的编码算法实现。与wrNAF相比，新的编码算法可以结合从左到右的点乘算法实现同步计算从而减少编码的存储空间。 2．wrNAF编码的安全性分析和抵抗简单功耗分析的点乘计算。基数 r 上的编码被用于特征为 r 的椭圆曲线的有效点乘计算。但是利用密码设备在运行过程中泄漏的计算时间、电量消耗曲线等敏感信息对一些密码体制进行攻击的边带信道攻击已成为安全实施密码体制的巨大威胁。我们利用简单功耗攻击分析了wrNAF编码的安全性，表明wrNAF编码不具备抵抗SPA的性质。为此我们提出了两种不同数位集上抵抗SPA的固定计算模式编码(从左到右和从右到左)。与已有的Hart的编码算法相比，我们的方法可以减少大约16.7﹪到37.5﹪的预存储点个数，从而提高点乘计算的效率。 3．抵抗差错攻击的BOS算法安全性分析。在CCS 2003上，Blomer,Otto和Seifert．提出一种可抵抗差错攻击的CRT-RSA签名算法即BOS算法。不幸地是，一年后Wagner提出一种简单有效的真对BOS算法的差错攻击。我们又进一步分析了BOS算法的安全性，并提出了一种新的差错攻击方法。攻击者首先在私钥d<,p>上引入一固定错误，然后运行BOS算法生成四个错误的签名，最后利用这些信息和最大公因子算法即可得到RSA模数的分解。

目录

文摘

英文文摘

论文说明：符号说明和缩略词

原创性声明及关于学位论文使用授权的声明

第1章绪论

1.1.背景和意义

1.2研究的主要内容和创新点

1.2.1.研究的主要内容和存在的问题

1.2.2论文的主要创新点

1.2.3论文的组织结构

第2章背景知识

2.1同余和剩余系

2.2群 环 有限域

2.3概率和Markov链理论

2.4 RSA算法和椭圆曲线理论

第3章基数2上的整数表示

3.1背景介绍

3.2基数2上从右到左的带符号表示

3.2.1 NAF

3.2.2 wNAF

3.3基数2上从左到右的带符号表示

3.3.1 MOF

3.3.2最优从左到右带符号表示

3.4本章小结

第4章基数r上的整数表示

4.1背景介绍

4.2已有工作

4.2.1 GNAF

4.2.2 rNAF和wrNAF

4.3基数r上从左到右的带符号表示

4.3.1一种新的从左到右的最优类wrNAF表示

4.3.2算法分析

4.3.3算法性能比较

4.4本章小结

第5章边带信道攻击及抵抗算法

5.1主要的边带信道攻击类型

5.2一种高效的抵抗简单功耗攻击算法

5.2.1 SPA攻击分析模型及已有的抵御算法

5.2.2一种高效的抵抗SPA算法

5.3对一种新型的抗差错攻击算法的安全性分析

5.3.1 BOS算法和Wagner攻击

5.3.2一种新的攻击算法

5.4本章小结

第6章结论和将来的工作

6.1结论

6.2将来的工作

参考文献

致谢

攻读学位期间发表的主要学术论文