基于RSA的数字签名算法及其快速实现.pdf

Computer Knowledge and Technology 电脑知识与技术 第 5 卷第 31 期 (2009 年 11 月) 基于RSA的数字签名算法及其快速实现 刘学清，李梅，宋超，朱艳琴 （苏州大学 计算机科学与技术学院，苏州 江苏 215006） 摘要：在基于 RSA 的数字签名算法中，直接决定实现效率的是大数模幂运算。 对基于二进制的 Montgomery 算法进行了改进，并将 其应用于大数的模幂运算中。 改进后的算法在保证算法快速实现的同时，又节省了算法运算空间。 关键词：数字签名；RSA；Montgomery 算法；模乘 中图分类号：TP312 文献标识码：A 文章编号：1009-3044(2009)31-8717-02 The Introduction and Fast Implementation of Digital Signature Algorithm Based on RSA LIU Xue-qing, LI Mei, SONG Chao, ZHU Yan-qin (School of Computer Science Technology, Soochow University, Suzhou 215006, China) Abstract: The efficiency of digital signature algorithm based on RSA depends on the modular exponentiation of large integer. We im- proved the binary Montgomery algorithm and use it in the modular exponentiation of large integer. On the foundation of fast speed,the improved way can also save operation space. Key words: digital signature; RSA; Montgomery algorithm; modular multiplication 随着网络技术的发展，各种网络通信服务应运而生。 在享受便捷网络通信服务的同时，各种安全问题也在困扰着人们。 由于不 是面对面的接触以及没有书面合同的支持，如何确认对方的身份就显得尤为重要。 在网络中传输的消息可以通过数字摘要技术来确保其在传输的过程中未被修改。 但仅仅做到这一步仍存在危险性。 假设用户 A 向 B 发送消息 M，数字摘要算法采用 SHA-1，A 对 M 进行 SHA-1 运算，将 M 和摘要值 S 一起发送给 B，但消息在途中被 C 截取 （并且 C 知道此次会话 AB 双方摘要算法选择的是 SHA-1），C 将消息 m 及其 SHA-1 摘要值 s 一起发送给 B，这样在 B 端显然能够 通过 SHA-1 的检验，B 就误以为接受到了来自 A 的消息。 解决上述问题的一个好方法就是使用数字签名技术。 数字签名技术类似 于纸张上的签名或者印章，是不可伪造的。 其标准定义为：“附加在数据单元上的一些数据，或是对数据单元所作的密码交换，这种 数据和变换允许数据单元的接受者用以确认数据单元来源和数据单元的完整性，并保护数据，防止被人（例如接收者）进行伪造。 ” 1 基于 RSA 数字签名算法简介 在各类数字签名算法中，基于 RSA 的数字签名算法是应用相当普遍的一种。 其原理简单，理论基础是数论的欧拉定理，它的安 全性依赖于大数的因数分解的困难性。 其签名产生和签名认证过程为： 1) 取两个大素数 p，q； 2) 计算 n=pq, φ(n)=(p-1)(q-1)； 3) 随机选择整数 e,并且满足 e 和 φ(n)互质； 4) 计算 d,使得 d*e≡1 mod φ(n)； 5) 对消息 M 进行数字摘要运算，得到摘要值 S； 6) 对摘要值 S 生成签名：V=Sd mod n； 7) 接收方验证签名:计算 s=Ve mod n，并对消息 M 用同一数字摘要算法进行摘要运算，得到摘要值 S。 若 S=s 则通过签名认证。 在上述过程中，计算得到 n，d 后应将 p，q, φ(n)销毁，将(n，e)公布作为 RSA 的公钥，将 d 必威体育官网网址作为 RSA 的私钥。 2 RSA 算法的快速实现