大数模幂算法的分析与研究.pdfVIP

l6 计算机与数字工程 第 34卷 大数模幂算法的分析与研究 张海平 (杭州电子科技大学计算机学院 杭州 310018) 摘 要 大数模幂在密码学领域有广泛的应用，它是公钥密码的基础。文章对 目前比较典型的各种大数模幂算法的 设计思想进行了深入剖析，从基本设计原理和实现角度对这些模幂算法进行了整理和分类，归纳给出了各种算法的优缺 点、实现方法和使用环境。 关键词 大数模幂 二元算法 m—ary算法 滑动窗KI算法 BGMW算法 指数重编码算法 中图分类号 TN301．6 ResearchingonFastM odularExponenfiafionofLarger—numberwithLargeExponents ZhangHaiping (ComputerCollege，nnagzhouDianziUniversityofScienceandTechnology，Hangzhou 310018) Abstract Modularexponentiationoflarger-numberhasuniversalapplicationincryptography，naditisthebaseoperationinmost public—keyeLyptographyalgorithms．Alltypicalmodularexponentiationshavebeennaalyzeddeeplynadclassedintoseveralkindsaccord- ingtotheirbasicdesign0rinciplesnadimplementation．Finally，themeritsnadshortcomingsimplementationmethods，applieableconditions aleconcluded． Keywords FastModularExponenfiafionof LargeNumbers，Bi~mryArrayAlgorithm ，M—aryAlgorithm ，Slide—WindowsAlgorithm， BGMW Algorithm ，ExponentiationReeodingAlgorithm Classnumber TP30】．6 的所有次幂，因此可以更快的计算 。 l 引言 2— 3— 6— — — 5 — 在信息系统安全中，特别是在数字签名、认证 上式计算只需6次模乘，该方法称为二元法或 和密钥分配与管理中，公钥密码都扮演着必不可少 平方乘算法，1969年 Knuth¨J指出早在公元前 200 的角色。公钥密码体制虽具有许多优点，但仍有缺 年，就 已经出现该算法了。 点存在 ，最大的缺点就是加解密运算复杂，速度缓 本文首先在讨论二元算法 、m—ary算法、滑动 慢，因此如何快速实现公钥密码算法已成为密码学 窗口算法、BGMW算法和指数重编码算法等，并对 界普遍关注的问题，公钥密码加解密算法的速度主 它们的复杂度进行较详细分析；最后介绍了各种算 要取决于模幂与模乘算法的效率高低。 法的优缺点和适用的环境。