RSA算法的研究及其在数字签名技术中的应用

燕山大学本科生毕业论文(论文)

本科毕业设计(论文)

RSA 算法的研究及其在数字签 名技术中的应用

2010 年 6 月

I

燕山大学本科生毕业论文(论文)

本科毕业设计(论文)

RSA 算法的研究及其在数字 签名技术中的应用

学院(系) 专 业:

学生 姓名: 学 号:

指导 教师: 答辩 日期:

II

燕山大学本科生毕业论文(论文)

摘要
RSA算法是目前公认的在理论和实际应用中最为成熟和完善的一种公 钥密码体制,它是第一个既能用于数据加密也能用于数字签名的算法,是公 钥密码体制的代表。 RSA数字签名体制使用的是RSA公开密钥密码算法进行 数字签名。 研究的主要内容包括:对RSA算法进行了全面系统的研究,包括RSA算 法的应用现状和原理—大素数的产生、密钥对的产生、对明文的加密运算和 密文的解密运算,为具体实现打下了理论基础;研究了RSA数字签名的一些 基本概念和数字签名的理论实现过程;对哈希算法基本原理的研究;研究了 RSA数字签名的设计与实现,主要实现的模块包括RSA密钥的产生,RSA加 密算法和解密算法的实现, 消息摘要的生成以及利用RSA算法实现数字签名 和签名的验证;分析了RSA数字签名的安全性。 关键词 RSA 算法;哈希算法,MD5;数字签名

III

燕山大学本科生毕业设计(论文)

Abstract
RSA algorithm is considered as the most mature and consummate public key cryptography in the theory and practical apply, and it is the first algorithm that can not only be used in data encoding but also be used in digital signature. Moreover, it is the representative of public key cryptography. The main research content of this paper contains: the comprehensive and systematic research of RSA algorithm, which contains the current apply situation and principle of RSA algorithm-- the generation of prime number, the generation of key pair, the encoding operation of plaintext and the decoding of the ciphertext, and the research lays the theoretical foundation for concrete practice; the research of some basic concept of RSA digital signature and the realizing process of digital signature; the research of the basic theory of haxi algorithm; the design and realization of RSA digital signature, and the main realizing module contains the generation of RSA key, the realization of RSA encoding algorithm and decoding algorithm, the generation of message summary and the realization of digital signature and the verification of signature; the analysis of security of RSA digital signature. Keywords RSA algorithm; hash algorithm; MD5; digital signature

II

目录
摘要 .................................................................................................................... III Abstract ................................................................................................................ II 第 1 章 绪论 ........................................................................................................ 1 1.1 课题背景 ............................................................................................... 1 1.2 国内外研究现状 .................................................................................... 1 1.2.1 研究主要成果 ................................................................................ 2 1.2.2 发展趋势 ........................................................................................ 2 1.3 课题的意义与目的 ............................................................................... 2 1.4 论文的主要结构与安排 ........................................................................ 3 第 2 章 RSA 密码体制的研究 ........................................................................... 4 2.1 公钥密码体制的研究 ........................................................................... 4 2.2 RSA 密码体制的研究 ........................................................................... 6 2.3 RSA 数字签名体制的研究 ................................................................... 7 2.4 HASH 函数的研究 .................................................................................. 9 2.5 本章小结 ............................................................................................. 10 第 3 章 RSA 算法的仿真 ................................................................................. 11 3.1 RSA 算法的参数的选择 ...................................................................... 11 3.1.1 参数 p,q 的选择 ......................................................................... 11 3.1.2 参数 e 的选择 ............................................................................... 11 3.1.3 参数 d 的选择 ............................................................................... 11 3.2 RSA 算法的仿真 .................................................................................. 11 3.2.1 产生消息摘要的设计 ................................................................... 11 3.2.2 RSA 算法的仿真 .......................................................................... 16 3.3 RSA 算法的安全性分析 ..................................................................... 20 3.3.1 RSA 的安全性分析 ...................................................................... 20
III

3.3.2 对 RSA 分解模数 n 攻击 ............................................................. 20 3.3.3 对 RSA 算法的明文部分信息安全性 ......................................... 21 3.3.4 RSA 的小指数攻击 ....................................................................... 21 3.3.5 耗时攻击 ....................................................................................... 22 3.4 本章小结 .............................................................................................. 22 第 4 章 RSA 算法在数字签名中的应用 ......................................................... 23 4.1 RSA 数字签名的过程描述 .................................................................. 23 4.2 研究结果 .............................................................................................. 24 4.3 RSA 数字签名的安全性分析与前景展望 .......................................... 25 4.3.1 RSA 数字签名的安全性分析 ....................................................... 25 4.3.2 RSA 数字签名的前景展望 ........................................................... 26 4.4 本章小结 .............................................................................................. 26 结论 .................................................................................................................... 27 参考文献 ............................................................................................................ 28 致谢 .................................................................................................................... 29 附录 1 ................................................................................. 错误!未定义书签。 错误!未定义书签。 附录 2 ................................................................................. 错误!未定义书签。 错误!未定义书签。 附录 3 ................................................................................. 错误!未定义书签。 错误!未定义书签。 附录 4 ................................................................................................................. 30 附录 5 ................................................................................................................. 42

IV

燕山大学本科生毕业设计(论文)

第 1 章 绪论
1.1 课题背景
密码体制按密钥可以划分为传统密码体制和公钥密码体制两种。 传统密 码体制中,加密、解密使用相同的密钥。公钥密码体制中加密算法和解密算 法是公开的,加密、解密使用两个不同的密钥。传统密码体制不利于密钥管 理也不利于数字签名,但速度快。公钥密钥体制证实了从发送端到接收端无 密钥传输的保密通信是可行的,从而非常适合于计算机网络的保密通信。公 钥密码体制既可用于密钥传递又可用于数字签名,用途十分广泛,但速度较 低,可以说,速度是其最显著的缺陷。因此,目前密码系统大多采用混和密 码体系,即用公钥密码体制实现密钥管理和数字签名,用传统密码体制实现 大量信息的加解密。这样既增强了密码系统的安全性,又可以比较快速地进 行加解密,效果非常好。 著名的RSA公钥密码体制是1978年由麻省理工大学的三位学者Rivest、 Shamir和Adleman三人共同提出的[1]。RSA是最具代表性的公钥密码体制, 即 可用于数据加密,又可用于数字签名,安全性良好,易于实现和理解,RSA 已成为一种应用极广的公钥密码体制。 但是由于RSA算法所采用的大数模幂 乘运算耗时太多,这一直是制约其广泛应用的瓶颈问题。

1.2 国内外研究现状
目前影响较大的制订信息安全相关标准的组织有:ISO和国际电子技术 委员会(IIEC) ,美国国家标准与技术委员会(NIST)制订的美国联邦信息处理 标准(FIPS)系列,Internet研究和发展共同体制订的标准,IEEE制订的标准, RSA公司制定的PKCS系列等等[2]。 对于数字签名,比较有代表性的有:美国NIST制定的数字签名标准 (DSS:Digital Signature Standard),对应的数字签名算法是DSA。公钥密码学标 准(PKCS:Public-Key Cry Standard)是RSA数据安全公司制定的公钥密码学的 工业标准接口,也是第一个公钥密码学的工业标准接口,其中PKCS#7对用 RSA数字签名的算法的通用语法及数字信封作出了规定[2]。
1

燕山大学本科生毕业设计(论文)

1.2.1 研究主要成果
当今世界公认RSA算法是目前最好的密码算法, 它不仅可以作为加密算 法使用,而且还可以用作数字签名和密钥分配与管理。该算法的加密密钥和 加密算法分开,使得密钥分配更为方便。而且它特别符合计算机网络环境, 对于网上的大量用户,可以将加密密钥用电话薄的方式印出。如果某用户想 与另一用户进行保密通信,只需从公钥薄上查出对方的加密密钥,用它对所 传送的信息加密发出即可。对方收到信息后,用仅为自己所知的解密密钥将 信息脱密,了解报文的内容。由此可看出,RSA算法解决了大量网络用户密 钥管理的难题,这是公钥密码系统相对于对称密码系统最突出的优点。

1.2.2 发展趋势
今些年, RSA主要专注信息安全市场的几个领域, 也是各有特色的领域。 在身份认证领域,RSA关注到很多网上交易企业包括金融、搜索等行业,用 户对身份认证关注的程度明显不一样。另外钓鱼、木马比以前更加猖狂。网 上的身份认证、反欺诈增长趋势很强劲。此外,企业内控方面,目前,中国 还在不断成熟的过程中。 在防数据泄露方面RSA有一些新的防木马服务提供 给社会,对强身份认证方面,也有一些新的业务上的突破。 金融行业在世界上任何一个地方,都是存在最高安全风险的行业,不论 是现实中的犯罪还是网络犯罪, 金融都是一个香饽饽。 随着网络银行的发展, 金融行业对信息安全解决方案的需求始终非常旺盛, 金融行业正是RSA最大 的发展空间,并且在未来一段时间仍然会是。如何保障金融行业信息安全, 防止数据泄露,同时应对新的金融服务,成为RSA今后业务发展的重点。

1.3 课题的意义与目的
随着电子商务的发展,网络上资金的电子交换日益频繁,如何防止信息 的伪造和欺骗成为非常重要的问题。在计算机通信系统中,维护电子文档的 安全也成为至关重要和非常敏感的问题。为保护信息的安全,数字签名应运 而生,它是现代密码学主要研究的内容之一。目前关于数字签名的研究主要 集中点是基于公钥密码体制的数字签名。在公钥密码体制中,解密和加密密 钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通
2

燕山大学本科生毕业设计(论文)

信,因此它较好地解决了传统密码体制在网络通信中出现的问题。手写签名 的每一项业务都是数字签名的潜在用场。数字签名可以提供数据完整性、真 实性和不可否认性。因而当需要对某一实体进行认证、传输具有有效性的密 钥以及进行密钥分配时,便可以借助数字签名来完成任务。数字签名技术在 身份识别和认证、数据完整性、抵赖等方面具有其它技术无法替代的作用, 它在军事、 电子商务和电子政务等领域有着极广泛的应用。 而在公钥体制中, RSA是一个较为完善的公钥密码算法,不仅能够同时用于加密和数字签名, 而且易于理解和操作,是被广泛研究的公钥密码算法。因此,基于RSA的数 字签名具有较强的研究性和实际应用意义。

1.4 论文的主要结构与安排
针对RSA数字签名体制为研究对象, 讨论了RSA算法的原理和实现过程 中,以及在数字签名领域的应用,实现了RSA系统在c++语言的仿真。并对 其安全性能指标进行了分析。论文具体结构如下: 第1章为绪论部分,首先简要的介绍了课题背景及公钥密码体制发展的 概况,之后深刻地描述了RSA系统的目的和意义,最后对论文结构安排进行 说明。 第2章简要研究了公钥密码体制以及数论的一些基本概念,着重研究了 RSA密码体制的基本原理以及Hash算法的基本原理等内容。 第3章研究了RSA系统各个参数的选取, 仿真实现了MD5算法, 并对RSA 算法进行了仿真,讨论了RSA算法的安全性能。 第4章研究了RSA算法在数字签名技术中的应用,描述了RSA数字签名 的过程并对其安全性能指标进行分析。

3

燕山大学本科生毕业设计(论文)

第 2 章 RSA 密码体制的研究
2.1 公钥密码体制的研究
上个世纪70年代中期, 美国斯坦福大学的研究生Wltitfield Difie和Martin Hellman教授一般性地研究了密码学,特别研究了密钥分发问题。他们提出 了一个方案,由此能够通过交换公开信息建立一个共享的秘密。他们可以在 公开的信道上通信,以密码分析者可获得的形式来回传送信息;同时,生成 一个不公开的密码数值。 然后通信双方能够使用这个秘密数值作为对称会话 密钥。这个方案称为Difie—Hellman,或者DH。由此在密码学这个领域出现 了一种新的见解:密钥可以成对出现,即一个加密密钥和一个解密密钥,并 且两个密钥之间不能相互生成。Difie和Hellman首次在1976年的全美计算机 会议上正式提出公钥密码学的概念,并在IEEE上发表[3]。 从这个时候开始,人们提出了大量的公钥密码算法,其中许多是不安全 的,认为是安全的算法中又有许多是不实用的,不是密钥太大,就是密文比 明文长的多。只有一部分是既安全又实用的。在这些既安全又实用的公钥算 法当中,有的只适合于密钥分发,有的只适合于加密,有的只适合于数字签 名。目前,只有RSA算法既适合于加密也适合于数字签名。
可行 x 不可行 (除非知道陷门) f(x)

图 2-1

单向陷门函数示意图

对于私钥密码系统,我们很容易明白它的工作过程。通过使用密钥,按 照加密算法打乱明文。解密的时候,只要按照相反的顺序再操作一遍即可, 也就是说加密和解密的变换是“互逆的” 。但对于公钥密码系统来说,简单 地颠倒步骤无法解密密文。这是因为私钥密码系统把数据作为比特来处理, 而公钥密码系统则把数据作为数字进行函数运算处理, 并且这种数学函数是
4

燕山大学本科生毕业设计(论文)

单向地: 在一个方向上是容易的, 另一个方向上却非常困难。 如图2-1所示[5]。 公钥算法都是基于单向陷门函数的, 即对于其他任何部分来说函数都是单向 的,但是私钥可以作为一个陷门使得授权者能够恢复出明文,这样的单向陷 门函数是存在的。 公钥密码算法使用一个密钥进行加密, 用另一个不同但是有关的密钥进 行解密,有以下重要特性: (1)特征1 是不可能的; (2)特征2 两个相关密钥中任何一个都可以用作加密而另一个用作解 密(这点RSA算表现尤其明显); 图2-2就是公钥密码算法的加解密过程。 仅仅知道密码算法和加密密钥而要确定解密密钥,在计算上

明文 输入

加密算法 (比如 RSA)

解密算法(加 密的逆过程)

明文 输出

Ke

Kd

密钥对 产生源 图 2-2 公钥密码系统的加解密过程示意图

系统中的任何一个用户端都产生一对用于它将接受的明文(或密文)进 行加解密的密钥(通常都有密钥对产生源产生);每个系统都通过把自己的加 密密钥公布,就是公开密钥。另一个密钥自己保有;如果A想给B发送一个 信息, A就用B的公开密钥加密这个信息; B收到这个加密后的信息后就用自 己保有的私有密钥解密密文,其他收到这个密文的人都无法解密,因为他们 没有私有密钥; 这种系统当中,不再具有私钥密钥体制中繁琐的密钥分配步骤。只要一 个系统控制住它的私有密钥,它收到的信息内容就是安全的,而且任何时候
5

燕山大学本科生毕业设计(论文)

都可以随时更改它的私有密钥并公开相应的公开密钥来替代原来的密钥。
表 2-1 为公钥密码体制与私钥密码体制的比较 运行条件 私 钥 密 码 体 制 公 钥 密 码 体 制 (1)条件 1 用同一个算法进行加密和解 (1)条件 1 加密和解密使用同一个密钥和 同一个算法 (2)条件 2 发送方和接收方必须共享密钥 和算法 安全条件 (1)条件 1 密钥必须保密 (2)条件 2 如果不掌握其他信息要

想解密报文是不可能的或者至少是 不现实的 (3)条件 3 知道所用的算法加上密

文的样本必须不足以确定密钥 (1)条件 1 保密 (2)条件 2 如果不掌握其他信息要 两个密钥中的一个必须

密,而密钥有一对,其中一个用于加密, 另一个用于解密 (2)条件 2 发送方和接收方每个拥有一对 相互匹配的密钥中的一个(不是同一个)

想解密报文是不可能的或者至少是 不现实的 (3)条件 3 知道所用的算法加上一

个密钥加上密文的样本必须不足以 确定另一个密钥

2.2 RSA 密码体制的研究
RSA公钥密码体制过程描述如下 (1)步骤1 (2)步骤2 (3)步骤3 (4)步骤4 (5)步骤5 随机选取两个大素数p和q。 计算n=pq,Φ(n)=(p-1)(q-1)(欧拉函数)。 随机选取正整数e,1<e<Φ(n),满足gcd(e,Φ(n))=1,e是公 计算d,满足de≡1(modΦ(n))。d是保密的解密密钥。 加密变换:对明文m c=me(modn)
6

开的加密密钥。

燕山大学本科生毕业设计(论文)

(6)步骤6

解密变换:对密文c m=cd(modn)

如果第三者进行窃听时,他会得到几个数:m,e,n(=pq),c…他如果要解 码的话,必须想办法得到d。所以,他必须先知道p,q,即对n作素因子分解, 而分解1024位的素数n却是非常困难的。

2.3 RSA 数字签名体制的研究
RSA数字签名体制使用了RSA公开密钥密码算法进行数字签名,鉴于 RSA算法在实践中已经被证明了的安全性, RSA数字签名体制在许多安全标 准中得以广泛应用。ISO/IEC 9796和ANSI X9.30-199X以及美国联邦信息处 理标准FIPS 186-2已经将RSA作为推荐的数字签名标准算法之一[5]。 RSA数字签名算法,包括签名算法和验证签名算法。它是利用的RSA算 法的加密和解密算法的原理进行的一种数字签名,实际上是通过一个Hash 函数来实现的产生消息摘要(MD)来实现的所需加密的对象。 数字签名的特点是它代表了消息的特征,消息如果发生改变,数字签名 的值也将发生改变,不同的消息将得到不同的数字签名。安全的数字签名使 接收方可以得到保证:消息确实来自发送方。因为签名的私钥只有发送方自 己保存, 他人无法做一样的数字签名, 如果第三方冒充发送方发出一个消息, 而接收方在对数字签名进行解密时使用的是发送方的公开密钥, 只要第三方 不知道发送方的私有密钥, 加密出来的数字签名和经过计算的数字签名必然 是不相同的,这就提供了一个安全的确认发送方身份的方法,即数字签名的 真实性得到了保证。 数字签名通过认证技术来辨认真伪。认证技术主要包括数字签名认证、 身份认证以及公开密钥证明等。 数字签名认证机制提供了一种对数字签名进 行鉴别的方法;身份认证机制提供了辨别和确认通信双方真实身份的方法; 公开密钥证明机制则对密钥进行验证。网络时代中,人们验证数字签名来确 定你正在和谁打交道,验证你的文件是否已被黑客篡改。数据的安全性和真 实性已成为网络安全中至关重要的一部分。 数字签名类似手书签名,它具有以下的性质:能够验证签名产生者的身
7

燕山大学本科生毕业设计(论文)

份,以及产生签名的日期和时间;能用于证实被签消息内容;数字签名可由 第三方验证,从而能够解决通信双方的争议[10]。 为了实现数字签名的以上性质,它就应满足下列要求: (1)条件1 (2)条件2 名是困难的; (3)条件3 签名是不可复制的:对一个消息的签名不能通过复制变为另 一个消息的签名。如果一个消息的签名是从别处复制得到的,则任何人都可 以发现消息与签名之间的不一致性,从而可以拒绝签名的消息; (4)条件4 (5)条件5 签名的消息是不可改变的:经签名的消息不能篡改,一旦签 签名是不可抵赖的:签名者事后不能否认自己的签名。可以 名的消息被篡改,任何人都可以发现消息与签名之间的不一致性; 由第三方或仲裁方来确认双方的信息,以做出仲裁。 为了满足数字签名的这些要求,例如,通信双方在发送消息时,既要防 止接收方或其他第三方伪造,又要防止发送方因对自己的不利而否认,也就 是说,为了保证数字签名的真实性。 数字签名的原理是:(发送方和接收方根据要求各自产生自己的一对公 钥和私钥) (1)步骤1 被发送文件采用某种算法对原始消息进行运算,得到一个固 定长度的数字串,称为消息摘要(MD),不同的消息得到的消息摘要各异, 但是对相同的消息它的消息摘要却是唯一的; (2)步骤2 (3)步骤3 (4)步骤4 消息摘要; (5)步骤5如果计算出来的消息摘要和发送方发送给他的消息摘要(通过
8

签名是可信的:任何人都可以验证签名的有效性; 签名是不可伪造的:除了合法的签名者外,任何人伪造其签

发送方生成消息的消息摘要,用自己的私钥对摘要进行加密 这个数字签名将作为消息的附件和消息一同用接收方的公 接收方首先把接收到的密文用自己的私钥解密,得到原始消

来形成发送方的数字签名; 钥进行加密,将加密后的密文一起发送给接收方; 息和数字签名,再用发送方的公钥解密数字签名,随后用同样的算法计算出

燕山大学本科生毕业设计(论文)

解密数字签名得到的)是相同的,这样接收方就能确认数字签名确实是发送 方的,否则就认为收到的消息是伪造的或是中途被篡改的。

2.4 Hash 函数的研究
Hash函数是一种将任意长度的消息压缩为某一固定长度的消息摘要函 数。Hash函数的输入为任意长度的消息,其输出为固定长度的消息。一个 Hash函数是一个多对一的映射。Hash函数可以用于数字签名,将Hash函数 应用于数字签名有许多好处。一方面加快签名的速度;另一方面是可以破坏 被攻击者用于消息伪造的数学结构。 Hash函数除了应用于数字签名之外, 还可以用于其他方面, 比如消息的 完整性检测。为了保证消息的完整性,及时发现消息是否被非法篡改,可以 在消息传输之前对消息做Hash变换, 然后对消息进行传输, 对于接收到的消 息也做Hash变换,将传输前的消息的Hash变换值与接收到的消息的Hash变 换值作比较,如果两者相同,则可以认为消息在传输过程中没有被篡改,否 则消息一定被非法篡改。 常见的Hash函数有Hash函数MD4, MD5和安全Hash 算法SHA等[13]。 首先对 MD5 的算法进行研究,MD5 消息摘要算法是由 Rivest(公开密 钥密码 RSA 算法的设计者之一)所设计的单向散列函数,MD5 不基于任何 假设和密码体制,它采用了直接构造的办法,速度很快,非常实用。MD5 算法的典型应用是对一段信息(message)产生信息摘要(MD),以防止被篡改。 MD5 将整个文件当作一个大文本信息,通过其不可逆的字符串变换算 法, 产生了这个唯一的 MD5 信息摘要。 如果在以后传播这个文件的过程中, 无论文件的内容发生了任何形式的改变(包括人为修改或者下载过程中线路 不稳定引起的传输错误等), 只要你对这个文件重新计算 MD5 时就会发现信 息摘要不相同,由此可以确定你得到的只是一个不正确的文件。如果再有一 个第三方的认证机构,用 MD5 还可以防止文件作者的“抵赖”,这就是所 谓的数字签名应用。MD5 还广泛用于加密和解密技术上。比如在 unix 系统 中用户的密码就是以 MD5(或其它类似的算法)经加密后存储在文件系统中。 当用户登录的时候,系统把用户输入的密码计算成 MD5 值,然后再去和保
9

燕山大学本科生毕业设计(论文)

存在文件系统中的 MD5 值进行比较,进而确定输入的密码是否正确。通过 这样的步骤, 系统在并不知道用户密码的明码的情况下就可以确定用户登录 系统的合法性。 这不但可以避免用户的密码被具有系统管理员权限的用户知 道,而且还在一定程度上增加了密码被破解的难度。 MD5 算法以任意长度的消息作为输入,产生一个 128 比特消息散列值 (或称消息摘要)作为输出。具体的算法步骤如下: (1)步骤 1 (2)步骤 2 (3)步骤 3 附加填充比特,对消息进行填充,使消息的长度(比特数)与 附加消息长度值, 将用 64 比特表示的初始消息(填充前)的长 初始化 MD 缓存,MD5 算法使用了一个 4 个字(128 比特, 448 模 512 同余,即恰好为一个比 512 比特的倍数仅小 64 位的数。 度(比特数)附加在步骤 1 的结果后。 MD4 中每个字 32 比特)的缓存来计算消息摘要, 它们主要用来存放 MD5 的 中间及最终结果。缓存可以看成是 4 个 32 比特的寄存器(A,B,C,D)。 (4)步骤 4 以 512 比特(16 个字)分组处理消息,这一步是 MD5 算法的 主循环,以 512 比特作为分组,在后面有详细的介绍。

2.5 本章小结
本章详细研究了公钥密码体制中应用最广泛的RSA密码体制的基本原 理,RSA数字签名体制的基本原理,Hash函数的基本原理,这些是后面在c++ 语言中实现的基础。

10

燕山大学本科生毕业设计(论文)

第 3 章 RSA 算法的仿真
3.1 RSA 算法的参数的选择
为保证算法的安全性,必须要认真的选择RSA算法的参数。

3.1.1 参数 p,q 的选择
(1)要求1 p和q必须为强素数,且通常p和q的位数相等。 只有p和q足够大,n=pq才能足够大,才能抵抗因子分解的攻击。根据目 前因子分解的能力,应当选择n为1024位或2048位。这样就要求p和q的选择 应为512位或1024位左右。 (2)要求2 p和q差值必须较大,最好与p、q位数接近。 由[(p+q)2/4]-n=[(p+q)2/4]-pq=(p-q)2/4,如果p和q的差值较小,则(p-q)2/4 也小,因此(p-q)2/4稍大于n,(p-q)/2稍大于 n 。可得n的如下分解法:顺序 检查大于 n 的每一个整数x,直到找到一个x使得x2-n是某一整数(记为y)的 平方。有x2-n=y2,得n=(x+y)(x-y)。 (3)要求3 (4)要求4 p-1和q-1的最大公因数应该很小。 p和q应大到使用因子分解n为计算上的不可能。

3.1.2 参数 e 的选择
(1)要求1 (2)要求2 e不能太小。 e应使其在模Φ(n)下的阶为最大。

3.1.3 参数 d 的选择
应使d>4n且越大越好,如n为1024位时,d的长度应大于256位。总体考 虑,尽量降低e的长度,不要降低d的长度。

3.2 RSA 算法的仿真
3.2.1 产生消息摘要的设计
在MD5算法中,首先需要对信息进行填充,使其字节长度对512求余的 结果等于448。因此,信息的字节长度(Bits Length)将被扩展至N*512+448,
11

燕山大学本科生毕业设计(论文)

即N*64+56个字节(Bytes),N为一个正整数。填充的方法如下,在信息的后 面填充一个1和无数个0,直到满足上面的条件时才停止用0对信息的填充。 然后,在在这个结果后面附加一个以64位二进制表示的填充前信息长度。经 过这两步的处理,现在的信息字节长度=N*512+448+64=(N+1)*512,即长度 恰好是512的整数倍。 这样做的原因是为满足后面处理中对信息长度的要求。 MD5 中 有 四 个 32 位 被 称 作 链 接 变 量 的 整 数 参 数 , 他 们 分 别 为 : A=0x01234567,B=0x89abcdef,C=0xfedcba98,D=0x76543210。 当设置好这四个链接变量后,就开始进入算法的四轮循环运算。循环的 次数是信息中512位信息分组的数目。 将上面四个链接变量复制到另外四个变量中:A到a,B到b,C到c,D 到d。 主循环有四轮,每轮循环都很相似。第一轮进行16次操作。每次操作对 a、b、c和d中的其中三个作一次非线性函数运算,然后将所得结果加上第四 个变量,文本的一个子分组和一个常数。再将所得结果向右环移一个不定的 数,并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。以一 下是每次操作中用到的四个非线性函数(每轮一个)。 第一轮(操作0至15):F(X,Y,Z)=(X∧Y)∨((?X)Z) 第二轮(操作16至31):G(X,Y,Z)=(X∧Z)∨(Y∧(?Z)) 第三轮(操作32至47):H(X,Y,Z)=X⊕Y⊕Z 第四轮(操作48至63):I(X,Y,Z)=Y⊕(X∨(?Z)) 其中,⊕使逐位异或,∧是按位与,∨是按位或,?是按位取反。 这四个函数的说明:如果X、Y和Z的对应位是独立和均匀的,那么结果 的每一位也应是独立和均匀的。F是一个逐位运算的函数。即,如果X,那 么Y,否则Z。函数H是逐位奇偶操作符。 假设Mj表示消息的第j个子分组(从0到15), FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti) GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti) HH(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti) II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)
12

燕山大学本科生毕业设计(论文)

这四轮(64步)是: 第一轮 FF(a,b,c,d,M0,7,0xd76aa478) FF(d,a,b,c,M1,12,0xe8c7b756) FF(c,d,a,b,M2,17,0x242070db) FF(b,c,d,a,M3,22,0xc1bdceee) FF(a,b,c,d,M4,7,0xf57c0faf) FF(d,a,b,c,M5,12,0x4787c62a) FF(c,d,a,b,M6,17,0xa8304613) FF(b,c,d,a,M7,22,0xfd469501) FF(a,b,c,d,M8,7,0x698098d8) FF(d,a,b,c,M9,12,0x8b44f7af) FF(c,d,a,b,M10,17,0xffff5bb1) FF(b,c,d,a,M11,22,0x895cd7be) FF(a,b,c,d,M12,7,0x6b901122) FF(d,a,b,c,M13,12,0xfd987193) FF(c,d,a,b,M14,17,0xa679438e) FF(b,c,d,a,M15,22,0x49b40821) 第二轮 GG(a,b,c,d,M1,5,0xf61e2562) GG(d,a,b,c,M6,9,0xc040b340) GG(c,d,a,b,M11,14,0x265e5a51) GG(b,c,d,a,M0,20,0xe9b6c7aa) GG(a,b,c,d,M5,5,0xd62f105d) GG(d,a,b,c,M10,9,0x02441453) GG(c,d,a,b,M15,14,0xd8a1e681) GG(b,c,d,a,M4,20,0xe7d3fbc8) GG(a,b,c,d,M9,5,0x21e1cde6) GG(d,a,b,c,M14,9,0xc33707d6)
13

燕山大学本科生毕业设计(论文)

GG(c,d,a,b,M3,14,0xf4d50d87) GG(b,c,d,a,M8,20,0x455a14ed) GG(a,b,c,d,M13,5,0xa9e3e905) GG(d,a,b,c,M2,9,0xfcefa3f8) GG(c,d,a,b,M7,14,0x676f02d9) GG(b,c,d,a,M12,20,0x8d2a4c8a) 第三轮 HH(a,b,c,d,M5,4,0xfffa3942) HH(d,a,b,c,M8,11,0x8771f681) HH(c,d,a,b,M11,16,0x6d9d6122) HH(b,c,d,a,M14,23,0xfde5380c) HH(a,b,c,d,M1,4,0xa4beea44) HH(d,a,b,c,M4,11,0x4bdecfa9) HH(c,d,a,b,M7,16,0xf6bb4b60) HH(b,c,d,a,M10,23,0xbebfbc70) HH(a,b,c,d,M13,4,0x289b7ec6) HH(d,a,b,c,M0,11,0xeaa127fa) HH(c,d,a,b,M3,16,0xd4ef3085) HH(b,c,d,a,M6,23,0x04881d05) HH(a,b,c,d,M9,4,0xd9d4d039) HH(d,a,b,c,M12,11,0xe6db99e5) HH(c,d,a,b,M15,16,0x1fa27cf8) HH(b,c,d,a,M2,23,0xc4ac5665) 第四轮 II(a,b,c,d,M0,6,0xf4292244) II(d,a,b,c,M7,10,0x432aff97) II(c,d,a,b,M14,15,0xab9423a7) II(b,c,d,a,M5,21,0xfc93a039) II(a,b,c,d,M12,6,0x655b59c3)
14

燕山大学本科生毕业设计(论文)

II(d,a,b,c,M3,10,0x8f0ccc92) II(c,d,a,b,M10,15,0xffeff47d) II(b,c,d,a,M1,21,0x85845dd1) II(a,b,c,d,M8,6,0x6fa87e4f) II(d,a,b,c,M15,10,0xfe2ce6e0) II(c,d,a,b,M6,15,0xa3014314) II(b,c,d,a,M13,21,0x4e0811a1) II(a,b,c,d,M4,6,0xf7537e82) II(d,a,b,c,M11,10,0xbd3af235) II(c,d,a,b,M2,15,0x2ad7d2bb) II(b,c,d,a,M9,21,0xeb86d391) 常数ti可以如下选择:在第i步中,ti是4294967296*abs(sin(i))的整数部分,i 的单位是弧度。(4294967296等于2的32次方)所有这些完成之后,将A、B、 C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法,最后的输 出是A、B、C和D的级联。计算消息摘要产生的框图如图3-1所示: MD5 使用了四轮而不是三轮,运算速度比 MD4 慢了大约 30%。MD5 和 MD4 相比,主要作了以下六点改进: 增加了第四轮,第四轮所使用的函数I(X,Y,Z)=Y⊕(X∨(?Z));第二 轮的函数G从(X∧Y)∨(X∧Z)∨(Y∧Z)变为(X∧Z)∨(Y∧(?Z))以减少对称 性;第二轮和第三轮的输入字的次序被改变;每一轮中的移位数己改变,并 且各轮中的移位数互补相同;每一步有一个唯一的加法常数;每一步加上了 上一步的结果,以增加“雪崩效应” 。 前4点改进, 为了抵抗某些攻击, 比如同构攻击, 而后两点为了加强MD5 的安全性。 在c++语言实现MD5算法的仿真得到了数据摘要。如果:我们输入 “digital message”时经过MD5算法的填充、附加长度、四轮非线性计算之 后,便可以得到的仿真的结果为:632b110516c6395538e95060b233c33。当 输 入 “ yanshan university ” 时 可 以 得 到 仿 真 结 果 为 :

ab657856c69e91f19f6cd311ca096ab9,可以验证不同的输入时得到不同的结
15

燕山大学本科生毕业设计(论文)

果,这样就可以用MD5算法对数据进行加密。

初始化 MD5 所需的常量

计算所需的追加长度

对原始信息进行补位

将输入分成 512 位的块

循环处理块

得到消息摘要

图 3-1

消息摘要产生框图

3.2.2 RSA 算法的仿真
在这里仍然采用C++语言进行仿真,绘制程序流程图及编写程序,根据 上一章所进行的讨论,可以选择两个大素数,这里我们选取p=47,q=59,这 样,就可以得到 n=p*q=2773, t=(p-1)(q-1)=2668, 我们选取e=63,可以根据RSA加密算法得到加密的信息。如果选取要加 密的信息是244,加密后是465;同样,想解密时,输入465,便可以得到原 始信息244。
16

燕山大学本科生毕业设计(论文)

程序流程图如下图3-2所示:
初始化

输 入 p和 q

计 算 n和 t

输入e 是

e<1或 e>t 否

计算d

输入1

输入2

输入明文

输入密文

加密

解密

输出

图 3-2

RSA 算法程序流程图
17

燕山大学本科生毕业设计(论文)

部分主要程序如下所示: void main() { int p,q,e,d,m,n,t,c,r; char s; printf("please input the p,q: "); scanf("%d%d",&p,&q); n=p*q; printf("the n is %3d\n",n); t=(p-1)*(q-1); printf("the t is %3d\n",t); printf("please input the e: "); scanf("%d",&e); if(e<1||e>t) { printf("e is error,please input again: "); scanf("%d",&e); } d=1; while(((e*d)%t)!=1) d++; printf("then caculate out that the d is %d\n",d); printf("the cipher please input 1\n"); printf("the plain please input 2\n"); scanf("%d",&r); switch(r) { case 1: printf("input the m: "); /*输入要加密的明文数*/ scanf("%d",&m); c=candp(m,e,n);
18

燕山大学本科生毕业设计(论文)

printf("the cipher is %d\n",c);break; case 2: printf("input the c: "); /*输入要解密的密文数字*/ scanf("%d",&c); m=candp(c,d,n); printf("the cipher is %d\n",m);break; } return; } } 此程序可以验证上面所举例子正确性。比如要加密的话,首先输入“1”, 然后输入要加密的信息:477,则加密后的结果如下所示: please input the p,q: 47 59 the n is 2773 the t is 2668 please input the e:63 then calculate out that the d is 847 the cipher please input 1 the plain please input 2 1 input the m:477 1886 the cipher is 1886 Press any key to continue 要解密时则首先输入“2”,在输入要解密的密文:1886,则可以得到解密后 的信息: please input the p,q:47 59 the n is 2773 the t is 2668 please input the e:63
19

燕山大学本科生毕业设计(论文)

then calculate out that the d is 847 the cipher please input 1 the plain please input 2 2 input the c:1886 477 the cipher is 477 Press any key to continue 通过这个程序,就可以将一些基本的信息进行加密和解密运算了。

3.3 RSA 算法的安全性分析
3.3.1 RSA 的安全性分析
理论上,RSA的安全性取决于因式分解模n的困难性。从严格的技术角 度上来说这是不正确的, 在数学上至今还未证明分解模数就是攻击RSA的最 佳方法。事实情况是,大整数因子分解问题过去数百年来一直是令数学家头 疼而未能有效解决的世界性难题。 人们设想了一些非因子分解的途径来攻击 RSA体制,但这些方法都不比分解n来得容易。因此,严格地说,RSA的安 全性基于求解其单向函数的逆的困难性。 RSA单向函数求逆的安全性没有真 正因式分解模数n的安全性高,而且目前人们也无法证明这两者等价。许多 研究人员都试图改进RSA体制使它的安全性等价与因式分解模数n。 RSA算法从提出到现在己经有很多年的时间了, 广泛的应用证明RSA体 制的安全性是相当可靠的。但是在特定的条件下,RSA的实现细节的漏洞会 导致对RSA算法的攻击。但是,通过精心考虑RSA体制实现的细节是可以避 免这些安全性缺陷的。

3.3.2 对 RSA 分解模数 n 攻击
分解模数n是最直接的攻击方法,也是最困难的方法。攻击者可以获得 公开密钥e和模数n;如果模数n=pq被因式分解,则攻击者通过p、q便可计 算出f(n)=(p-1)(q-1),进而de≡1(modf(n))而得到解密密钥d。如果密码分析者 能够不分解n而直接求得f(n),则可根据de≡1(modf(n))求得解密密钥d,从而
20

燕山大学本科生毕业设计(论文)

破译RSA。又因为: p+q=n-f(n)+1,
p ? q = ( p + q ) 2 ? 4n ,

所以知道f(n)和n就可以容易地求得p和q,从而成功地分解n。目前已经 出现了不对n进行因子分解而直接估算f(n)的攻击方法,但还没证明,直接计 算f(n)比对n进行因子分解更容易。 大整数分解研究一直是数论与密码理论研 究的重要课题,随着计算能力的增强和因子分解算法的不断完善,为保证
RSA的安全性,在实际应用中对p和q的选取要求也越来越高[11]。

3.3.3 对 RSA 算法的明文部分信息安全性
同RSA算法一样, 大多数的公钥密码体制的安全性是建立在单向函数之 上的,即所谓的单向函数模型密码体制。 RSA 算法使用的单向函数 f(x) ≡
xe(modn)的安全性是基于大数分解的困难性,即攻击者在多项式时间内不能

分解模数n。但这并不能保证攻击者很难使用概率方法由f(x)来推算明文x的 某些特征或用二进制表示某个或某些比特的值(即明文的部分信息)。攻击者 通过获取明文消息的部分信息,进而可以破译或者恢复整个明文消息。这就 是RSA算法的安全性的另一个重要方面,可以称之为比特安全性,即RSA算 法中密文所泄漏的有关明文二进制表示的某些有效位 (比特 )的部分信息安 全性。 关于RSA体制部分信息安全性的最好结果是由W.Aiexi等人得出的。他 们 证 明 了 任 何 由 密 文 E(x)( 这 里 E 为 RSA 的 加 密 函 数 ) 一 不 小 于 1 1 + 的正确概率猜对明文最末有效位的算法F,都可诱导出一种 2 poly (log N ) 由密文E(x)破译出x的相对于算法F的没确定多项式算法, 即所谓的最末有效 1 1 + 位安全性[13]。 2 poly (log N )

3.3.4 RSA 的小指数攻击
这类攻击专门针对RSA算法的实现的细节。采用小的e、d可以加快加密 和验证签名的速度,而且所需的存贮空间小,但是如果e、d太小,则容易受 到小指数攻击(Low Encryption/Decryption Exponent attack),包括低加密指数
21

燕山大学本科生毕业设计(论文)

攻击和低解密指数攻击[13]。 通过独立随机数字对明文消息x进行填充,这样使得 x e (mod n) ≠ x e ,可 以有效地抗击小指数攻击。

3.3.5 耗时攻击
这种攻击是通过监视一台计算机解密消息所花费的时间来确定解密指 数。RSA的基本运算是乘方取模,这种运算的特点是耗费时间精确,这样如 果破译者能够监视到RSA解密的过程,并对它计时,他就能算出d。关于如 何防御这种攻击,最简单的方法莫过于使RSA解密时花费均等的时间,而与 解密指数d无关。其次在加密前对数据做一个变换(花费恒定时间),在解密 时做逆变换,这样总时间也不再依赖于解密指数d。另外,耗时攻击对攻击 者资源的要求太高,目前还不实用,但从理论上说是一个崭新的思路。

3.4 本章小结
本章主要研究了RSA系统各个参数的选取,MD5的仿真,RSA数字签名 的仿真RSA,并对其安全性能指标进行分析。

22

燕山大学本科生毕业设计(论文)

第 4 章 RSA 算法在数字签名中的应用
4.1 RSA 数字签名的过程描述
RSA公钥密码体制过程描述如下 (1)步骤1 (2)步骤2 (3)步骤3 (4)步骤4 (5)步骤5 (6)步骤6 随机选取两个大素数p和q。 计算n=pq,Φ(n)=(p-1)(q-1)(欧拉函数)。 随机选取正整数e,1<e<Φ(n),满足gcd(e,Φ(n))=1,e是公 计算d,满足de≡1(modΦ(n))。d是保密的解密密钥。 加密变换:对明文m c=me(modn) 解密变换:对密文c m=cd(modn) 从上面的 RSA 算法原理可以看出,它的加密和解密变换互为逆变换, 所以它可以用于数字签名系统。下面给出该数字签名系统的实现过程[13]。 设有用户 A 和 B,A 的公钥为{na,ea},私钥为{na,da},A 的加密和解密 变换为 Da 和 Ea,B 的公钥为{nb,eb},私钥为{nb,db},B 的加密和解密变换 为 Eb 和 Db,A 要向 B 发送消息 M,则: A 先对消息 M 进行签名, 即用自己的私钥{na,da}对消息 M 进行加密。 V = Da (M ) ,也即 V = ( Mda ) mod na
A 再用 B 的公钥{nb,eb}对 V 进行加密。 C = Eb(V ) ,也即 C = (Veb) mod nb

开的加密密钥。

然后,A 再把加密后的消息 C 发送给 B。 B 接收到消息 C 后,先用自己的私钥{nb,db}对消息 M 进行解密。 V = Db(C ) ,也即 V = (Cdb) mod nb
B 再用 A 的公钥为{na,ea}对 V 进行解密。 M = Ea (V ) ,也即 M = (Vea ) mod na

这样,B 就成功接收到了 A 发送过来的签名消息。 对 A 和 B 的通信过程做一个仔细的分析, 便会发现基于 RSA 算法的消 息加密系统完全实现了数字签名技术的三个基本功能。因为 A 对消息 M 签 名用的密钥{na,da}是私有的,别人不知道,也就无法伪造 A 的签名。又因
23

燕山大学本科生毕业设计(论文)

为只有 A 的公钥{na,ea}才能解开 A 对消息 M 的签名, 就无法抵赖其对消 A 息 M 的签名。一旦 A 和 B 发生了纠纷,仲裁机构也能够很容易地解决。 基于 RSA 算法数字签名技术的基本过程如图
发送方的 RSA 私钥

报文

MD5

摘要

RSA 解密 算法

数字签名

图 4-1

基于 RSA 算法数字签名技术的签名过程

发送方的 RSA 公钥

数字签名

RSA 加密算 法

摘要 A 验证 结果

比较 接收报文 MD5 摘要 B

图 4-2

基于 RSA 算法数字签名技术的签名验证过程

4.2 研究结果
经过对 RSA 数字签名体制的研究以及利用 c++进行仿真得到如下结果: 消息 m:061304021088 密文变成对应的 ASCI 码:48 54 49 51 48 52 48 50 49 48 56 21 56 对消息进行签名:15 218 49 77 51 221 214 158 56 212 66 120 96
24

92

16

82

114

85

40

燕山大学本科生毕业设计(论文)

发送方的密钥对:公钥[5 119],私钥[77 119] 接收方的密钥对:公钥[71 221],私钥[119 221] 加密后的密文稿:<mM¨3iv      t[    I 本次研究课题在仿真过程中实现了利用 RSA 进行数字签名的过程,达 到了课题要求的基本目的,但还存在着一些不稳定和局限性。 在这其中出现障碍的主要原因是由于采用的仿真的计算机计算范围有 限,使得系统只适用于参数较小的情况,但在实际应用中,参数过小会在很 大程度上影响 RSA 数字签名体制的安全性。因此,此次研究结果只能证明 RSA 加密算法的可行性及其优点以及所用算法的正确性,而不能够投入到 实际的应用中去。

4.3 RSA 数字签名的安全性分析与前景展望
4.3.1 RSA 数字签名的安全性分析
对于一个完整的数字签名系统而言,安全性是其要求的第一位,RSA 体制的安全性决定于 RSA 公开密钥密码算法的安全性, 在设计 RSA 数字签 名系统时为了保证其安全性,应注意以下几点: (1)注意 1 根据被加密文件的重要程度和加密时间的要求来选择 n 的长 度。因为 RSA 的安全性则是依赖于分解大素数的难度。随机选择足够大且 相互之间差别比较大的素数 p 和 q 来提高系统的安全性 (目前应在 512 位以 上) ,解密密钥 d 相对模 n 不应过小。因为若 d 达到 n 的 1/4 大小,且 e 比 n 小,则有方法可以恢复 d; (2)注意 2 在使用 RSA 的通信网络协议中,不应该使用公共模 n,这 是因为已经知道了对于一个加密/解密密钥指数对,攻击者就能分解这个模, 也就可以不分解 n 来计算出别的加密/解密对; (3)注意 3 (4)注意 4 (5)注意 5 不要让攻击者得到原始的解密结果; 相关的消息不要用相同的密钥加密; 在实际运用中不要对一个陌生人提交的随机消息解密, 不对

自己一无所知的信息签名,要先利用一个单向散列函数对消息进行散列 Hash 处理,尽管 Hash 算法是公开的,但是根据 Hash 值计算出明文在统计 学上是不可能的。因此仅重视 RSA 的实现是不够的,实现细节也很重要。
25

燕山大学本科生毕业设计(论文)

总之,对一个数字签名系统而言,重要的是从整体上研究,而不应局限 于系统的一部分。仅有一个安全的算法是不够的,整个密码系统必须是安全 的。

4.3.2 RSA 数字签名的前景展望
基于 RSA 算法的数字签名在 2000 年的第六届国际密码学会议上被推荐 为公钥密码系统的加密算法中的一种,由于 RSA 数字签名有较好的发展空 间, 对于未来的加密、 生成和验证数字签名的工具还需完善, 只有用 SSL(安 全套接层)建立安全连接的 Web 浏览器,才会频繁使用数字签名,公司要对 其员工在网络上的行为进行规范,就要建立广泛协作机制来支持数字签名, 支持数字签名是 Web 发展的目标,确保数据保密性、数据完整性和不可否 认性才能保证在线商业的安全交易[6]。 数字签名作为一项信息加密和安全传送技术,越来越得到人们的重视, 其中它涉及到的关键技术也很多,并且很多新的协议,如网上交易安全协议 SSL、SET 协议都会涉及到数字签名,因此数字签名将得到广泛的应用和人 们的首选。但是运用越来越广泛的网络安全技术数字签名,今后也很可能导 致毫无私密可言。

4.4 本章小结
本章主要研究了 RSA 算法在数字签名技术中的应用,仿真实现了 RSA 数字签名的过程,并对 RSA 数字签名的安全性进行了分析。

26

燕山大学本科生毕业设计(论文)

结论
在当今的信息社会中, 每天都有大量的信息在传输、 交换、 存储和处理, 而这些处理过程几乎都要依赖强大的计算机系统来完成。 一旦计算机系统发 生安全问题,就可造成信息的丢失、篡改、伪造、假冒、失密,以及系统遭 受捣乱、破坏等严重后果,轻者造成计算机系统运行效率低下,重者造成计 算机系统的彻底瘫痪。因此,如何保证计算机系统的安全是当前一个需要立 即解决的十分严峻的问题。 密码学的基本目的是使在不安全信道中通信的两 方以一种使他们的对手不能明白和理解的通信内容的方式进行通信。 RSA算法是一种安全技术,但是RSA算法的安全性只是一种计算安全 性,绝不是无条件的安全性,这是由它的理论基础决定的。因此,在实现 RSA算法的过程中,每一步都应尽量从安全性考虑,而该设计中它的安全性 则依赖于素数的选择。 RSA数字签名提供了一个安全的确认发送方身份的方 法,即数字签名的真实性得到了保证,防止了第三方的冒充和篡改,肯定了 数字签名的真实性。本文研究了RSA算法的基本原理、基本实现和消息摘要 产生所需要的MD5算法以及如何利用RSA算法实现数字签名。具体内容为: 综合已有的研究成果,阐述了RSA算法研究的目的和意义。研究了公钥 密码体制的基本原理,加解密的过程。研究了RSA密码体制的基本原理, RSA数字签名体制的基本原理;还对Hash函数做了详细的研究。 研究了 RSA 算法参数的选取, MD5 算法进行了仿真, 对 实现了消息摘 要的产生,仿真实现了 RSA 算法;并对 RSA 算法的安全性进行了分析。 研究了 RSA 算法在数字签名技术中的应用, 描述了 RSA 数字全面的过 程,对 RSA 数字签名的安全性进行了分析,并对讨论了 RSA 数字签名的前 景。 综上所述,论文研究了 RSA 算法及其在数字签名技术中的应用,本文 所作的只是 RSA 数字签名技术中的很小一部分。由于计算机能力有限不能 对较大位数的 RSA 算法进行仿真。

27

燕山大学本科生毕业设计(论文)

参考文献
1 吕浩勇.RSA 公钥密码系统算法研究与实现.(硕士学位论文).武汉:中南民族大 学,2007,12~46 2 周升力.RSA 密码算法的研究与快速实现.(硕士学位论文).江西:南昌大学,2008,16~50 3 张丽媛.RSA 密码算法的研究与实现.(硕士学位论文).山东:山东科技大学,2005,20~51 4 宋 树 军 .RSA 算 法 在 数 字 签 名 中 的 应 用 .( 硕 士 学 位 论 文 ). 山 东 : 中 国 石 油 大 学,2007,5~52 5 贾杰.基于 RSA 的概率公钥密码算法.(硕士学位论文).北京:中央民族大学,2009,10~46 6 冯素琴.RSA 公钥密码算法的研究与实现.忻州:忻州师范学院学报,2006,22(2):47~50 7 李青,李雄伟,金涛.RSA 算法的研究与简单实现.北京:人民邮电出版社,2007,88~91 8 朱文余,孙琦.计算机密码应用基础.北京:科学出版社,2008.8,92~221 9 王宝杏,杨菲菲,王冬.RSA 大素数的快速生成方法研究.长沙:长沙通信职业技术学院 学报,2008.7,12(3):13~20 10 曹建国,王丹,王威.基于 RSA 公钥密码安全性的研究.西安:计算机技术与发展杂志 社,2007.17,9~33 11 Daemen Jrijmen V.高级加密标准(AES)算法—Rinjndael 的设计.北京:清华大学出版 社,2003,42~86 12 卢开澄.计算机密码学—计算机网络中的数据保密与安全(第三版).北京:清华大学出 版社,2003,24~48 13 徐术坤.哈希算法的研究及应用(硕士学位论文).湖北:湖北工业大学,2006.5,1~4 14 宋晓莉.RSA 算法的研究与实现.安徽:安徽理工大学出版社,2005,12,1~46 15 张先红.数字签名原理及技术.北京:北京机械工业出版社,2004:108~109 16 JIA Zongpu,LI Qing chao,LI Zichen.Secure Batch Verification Protocol Signature Scheme.biejing :Chinese Journal of Electronics,2005,14(1):54~57 17 Niimura M.A high-speed processing LSI for RSA cryptograms using an improved adder circuit.New York:IEEE Transactions on Computers,2004,1(12):175~178 18 W.Diffie,M.E Hellman.New directions in cryptography.New York:IEEE Transactions on Infermation Theory,2004,22:644~654
28

for RSA

燕山大学本科生毕业设计(论文)

致谢
本文是在老师的热情关心和指导下完成的, 她渊博的知识和严谨的治学 态度使我受益匪浅,对顺利完成本课题起到了极大的作用。在此向她表示我 最衷心的感谢! 最后向在百忙之中评审本文的各位老师表示衷心的感谢!

29

附录 4

本科毕业设计 (论文) 外文翻译

燕山大学本科生毕业设计(论文)

31

燕山大学本科生毕业设计(论文)

32

燕山大学本科生毕业设计(论文)

33

燕山大学本科生毕业设计(论文)

34

燕山大学本科生毕业设计(论文)

对 RSA 签名方案的批量检测安全的议定书 JIA Zongpu,LI Qingchao and LI Zichen (1.计算机科学与技术部门,河南理工大学,焦作 454003,中国) (2.焦作大学计算机工程教研室,焦作 454003,中国) 摘要—Harn,于 1998 年,提出了多种有效的 RSA 数字签名批量检测方 案。 然而, 这些方案有一个弱点, 这个弱点是一个签名者可以生成多个签名, 他们都可以通过批量检测方案,但这些签名不是有效的签名。为了避免这个 缺点,我们提出了一种改进的批量检测方案。 关键词—批量检测密码学,数字签名,RSA。 一 介绍 在一些大型商业中心或计算中心会产生带有巨大金额的数据, 对于这些 中心来说这些数据的传输和操作, 信息安全和传输的高效性是非常重要的问 题。数字签名技术是上述中心提供信息安全的主要方法之一。因此,数字签 名是最重要的研究课题。基于一些数字难题,例如因式分解问题,有人曾提 议一些数字签名方案可以保证商业中心的安全。 为了快速有效地传输和处理 上述中心的那些海量的巨大金额的数据信息, 一些数字签名和批量检测已经 采用预计算理念的设计。 除了一般的功能,数字签名批量检测方案有以下优点。(1)检验工作的 简化(2)在一个操作人的一些签名中的平行检测(3)高效验证签名 这些数字签名方案提出了相应的规则。可以在线产生非常有效的签名。 然而,签名检测效率非常低。最近,为了加快数字签名验证 Naccache 等。 首先提出了两个中型批量交易协议。数字签名的批量检测,在这些计划中, 不是一次一个的核实签名,而是一次验证多个签名。由于这一优势,在此之 后,关于这一主题的许多调查已经完成,一些批量检测方案已经通过 EIGareal 和 RSA 签名方案的建议。批量检测数字签名方案不仅可以提高验 证数字签名的效率,也有批量检测的优点。 但在另一方面, 有些安全问题被提出。 批量检测方案的关键问题是, “批 量检测的多元签名”可能不等于“个别核查的每一个签名” 。最近,Han 建
35

燕山大学本科生毕业设计(论文)

议批量检测算法 RSA 数字计划。 使用这种算法可以一次验证多重 RSA 签名。 然而,在 Han 的批量检测方案中有一个弱点:一个签名者可以生成多个签 名,在批量检测时这些签名都是有效的但他们中的每一个是无效的签名。在 本文中,我们首先提出 Han 的 RSA 签名批量检测方案的由签名者欺骗的弱 点。然后,为了避免这个缺点,我们提出一个改进的批量检测议定书。在最 后,我们得到的结论是,新的改进的批量检测议定书比原来的 RSA 签名验 证计划的效率更高。 二 Han 批量检测算法的审查 在本节中,我们首先简要介绍了 Han 批量检测算法。 系统参数 n:RSA 的模数,n=pq,其中 p 和 q 是两个秘密的大素数。 h(.):单向散列函数。 公钥和私钥 e 和 d 分别为公钥和私钥,其中 ed = 1 mod( p ? 1)(q ? 1) 。 签名生成 对于消息 mi,计算 si = h(mi ) d mod n ,其中 si 是对消息 mi 的签名,
i=1,2,··t。 ·

批量检测算法 在收到多个签名之后,si,(i=1,2,· t)。验证计算 ··
S = ∏ si mod n , M = ∏ h(mi ) mod n
i =1 i =1 t t

然后检测式(1)的正确性:
S e = M mod n (1)

如果方程成立,si 是消息 mi 的有效签名,否则,至少存在一个 si 不是 与 mi 一致的有效签名。 三 签名者的欺骗方法 对于任何批量消息(mi,i=1,2,· t),签名者进行下面的步骤。 ··
(1)对每个消息 mi,其中 i=1,2,· (t-1),签名者随机选择 si 作为消息 ··

签名。很明显,si 对于消息 mi 是不合法的签名。
36

燕山大学本科生毕业设计(论文)

(2)对于消息 mi,签名者计算签名用下面的公式。
S t = ∏ h(mi ) d ∏ ( s i ) ?1 mod n
i =1 i =1 t t ?1

然后,签名人发布 si 作为消息 mi 的签名,其中 i=1,2,· t。 ·· 定理 1 随着 Han 的批量检测算法,这些多重签名 si,(i=1,2,· t), ·· 通过上述步骤生成消息 mi,(i=1,2,· t),的有效签名。 ·· 证明 首先分别计算验证 S 和 M。
S = ∏ si mod n
i =1 t

M = ∏ h(mi ) mod n
i =1

t

然后, S e = ∏ ( si ) e mod n = ∏ ( s i ) e ( s t ) e mod n 。
i =1 i =1

t

t ?1

因为 S t = ∏ h(mi ) d ∏ ( s i ) ?1 mod n 和 ed = 1 mod( p ? 1)(q ? 1) ,等式(1)是
i =1 i =1

t

t ?1

正确的。 因此,定理 1 证明多个签名 si,(i=1,2,· t)是消息 mi(i=1,2,· t) ·· ·· 的有效签名。 然而,很明显,每个人的签名 si 并不是其相应的消息 mi 的有效签名, 为了避免这个弱点, 在下一节, 我们将提出一个新的批量检测方案的议定书。 四 改进的 RSA 签名批量检测协议 同批量检测 RSA 签名方案包括三个阶段:初始化,多签名生成和验证, 多批量的签名。在我们新的改进方案中,第一和第二阶段与著名的 RSA 签 名方案是相同的。 初始化
n:RSA 的模数,n=pq,其中 p 和 q 是两个秘密的大素数。 h(.):单向散列函数。

公钥和私钥
e 和 d 分别为公钥和私钥,其中 ed = 1 mod( p ? 1)(q ? 1) 。

多重签名生成 对于消息 mi,计算 si = h(mi ) d mod n ,其中 si 是对消息 mi 的签名,
37

燕山大学本科生毕业设计(论文)

i=1,2,··t。 · 多重签名的批量检测 在接收到 si 之后,验证程序,随机选择 li∈(1,2,3,· 15)并执行以 ··2 下步骤,其中(i=1,2,· ··t) (1) S = ∏ ( s i ) li mod n ;
(2) M = ∏ h(mi ) li mod n ;
i =1 i =1 t t

·· (3)检测等式(1): S e = M mod n 。如果它认为,si(i=1,2,· t),是用 于消息 mi(i=1,2,· t)的签名。否则,在 si 中必须有一个签名对于消息 mi ·· 是无效的 定理 2 通过上述 RSA 签名机制可以一次成功验证签名者所产生的多重 签名。 证明 假设 si 是消息 mi 的签名,其中(i=1,2,· t),他们是由签名者 ·· 用以上签名生成方案产生的,我们有 S i = h(mi ) d mod n
S = ∏ ( s i ) li mod n = ∏ h(mi ) li d mod n
i =1 i =1 t t

S e = ∏ h(mi ) li ed mod n
i =1

t

众所周知, = 1 mod( p ? 1)(q ? 1) 。 ed 因此 S e = ∏ h(mi ) li mod n = M mod n
i =1

t

由于满足等式(1),上述批量检测过程可以通过多个签名,证明定理 2 是正确的。 五 安全性及性能分析 下面的定理给出了新的批量检测方案的安全性分析。 定理 3 在第三节中签名者的欺骗方法对于新的批量检测方案是无效 的。 证明 通过上述新的批量检测,签名者需要解决一下方程:

∏ (s )
i i =1

t

eli

= ∏ h(mi ) li mod n
i =1

t

38

燕山大学本科生毕业设计(论文)

在上面的方程中,对于任意的消息 mi(i=1,2,· ··t),签名者可以计算

∏ h( m )
i i =1

t

li

·· mod n 。然而,li(i=1,2,· t)是随机选择的,而多重签名的验证

时已知签名者的验证。因此,签名者是不可能解开这个等式的。签名者不能 产生对于消息 mi 有效的多重签名,定理 3 是正确的。 无论在密码学还是在计算机科学的基本领域, 多指数运输的一种特殊形 式 ∏ ( M i ) li mod n 是一个特别重要的课题。在新的改进的批量检测中,我们
i =1 t

还需要评估这个多幂形式。到目前为止,许多计算这个多幂形式的快速算法 已经被提出。 进来,Yen 和 Laih 提出了快速多幂算法 Ref.[11]。我们称之为 Y-L’s 算 法。我们也使用 M(Φ,t,w)来表示评估中所需的乘法数。

∏ (M
i =1

t

i

) li mod n

其中Φ=max{∣bi∣,(i=1,2,· t)},w 是滑动窗口的大小。 ·· 为简便起见,我们只考虑幂运算总数,并没有考虑乘法的运算方面。 由 Ref.[11]的定理,我们有关于多指数运算中需要改进的批量检测议定 书的特殊形式 ∏ ( M i ) li mod n 的以下两个结果
i =1 t

推论 1 Y-L’s 算法的最坏情况的性能要求为Φ>>W 和 w≥2
M(Φ,t,w)=[(2t)w-(2t)w-1]+[(Φ-w)+(Φ/w)-1],

其中Φ=max{∣li∣,(i=1,2,· t)},w 是滑动窗口的大小。 ··

推论 2 Y-L’s 算法的一般情况的性能要求为Φ>>W 和 w≥2 ? ? 1 + w ? w2 t + ( 2 t ) w 1 M (? , t , w ) = [( 2 t ) w ? ( 2 t ) w ?1 ] + (? ? w ) + { ? 1 ? [[ ] + t w ]} t w t w ( 2 ) ( 2 ? 1) (2 ) 其中Φ=max{∣li∣,(i=1,2,· t)},w 是滑动窗口的大小。 ·· 下一步,我们将比较改进的批量检测议定书的有效性与原 RSA 签名核 查议定书的有效性。 改进的批量检测方案,在收到这些签名 si(i=1 , 2 , · t) ,需要计算 ··

∏ (s )
i i =1

t

li e

以验证其有效性, 其中 e 是 RSA 公钥, i∈(1, , ,· 215) l 2 3 ·· mod n ,

是由选定的随机整数秘密验证的在原来的 RSA 签名验证方法中,需要一个 一个的验证每个人的签名。需要计算验证 sie mod n ,其中 i=1,2,· t。 ··
39

燕山大学本科生毕业设计(论文)

我们首先考虑 Y-L’s 算法最坏情况的性能。 为了不失一般性,我们假定 RSA 公钥有 1024 位,即∣e∣=1024。我们 有Φ=max{∣lie∣,(i=1,2, · · ·t)}=1024+15=1039。设 t=4,w=2,评估

∏ (M
i =1 t i =1

t

i

) li e mod n , 幂 乘 的 次 数 M( Φ ,t,w)=M(1039,4,2)=1796 。 计 算
li i

∏ h( m )

·· mod n 其中Φ =max{ ∣ li ∣, (i=1 , 2 , · t)}=15 ,幂乘的次数

M( Φ ,t,w)=M(15,4,2)=259 。 如 果 用 TNM 表 示 总 幂 乘 的 次 数 , TNM=1796+359=2055。然而,最初的 RSA 签名验证方法是,计算 sie mod n ,

具 有 相 同 的 RSA 公 钥 , 设 t=4 , 最 优 值 w=6 , 幂 乘 的 次 数 M( Φ ,t,w)=M(1024,6,1)=1220 。 总 幂 乘 次 数 TNM(RSA)= M(Φ,t,w)*t=120*4=4880。 其次,我们考虑 Y-L’s 算法一般情况下的性能。如果∣e∣=1024,t=4, 最优值 w=2,评估 ∏ ( M i ) li e mod n ,幂乘的次数 M(Φ,t,w)=M(1039,4,2)≈
i =1 t

1756。计算 ∏ h(mi ) li mod n ,幂乘的次数 M(Φ,t,w)=M(15,4,2)≈258。因此,
i =1

t

TNM≈1756+258=2054。然而,在最初的 RSA 签名验证方案中,设 t=4 最 优 值 w=6 , 我 们 可 以 得 到 总 幂 乘 次 数 , TNM=(RSA)= M(Φ,t,w)*t=1192*4=4768。

总之,我们有以下两种情况如下表所示: 表 1 性能比较 从上表,我们得到的是,在改进的批量检测议定书的乘法运算次数少于
改进方案 最坏情况 一般情况 2055 2054 RSA 的核查 4880 4768

需要多个个人签名作为认证的原始 RSA 签名核查议定书。因此,改进的批 量检测方案比原始的 RSA 核查多个签名的效率更高。 我们对改进的批量检测议定书有以下结论。
40

燕山大学本科生毕业设计(论文)

(1)签名者在第三节中的欺骗方法是无效的; (2)比原来的 RSA 核查多个签名的效率高; (3)它具有批量检测功能。 六 结论 在本文中,我们首先提出了签名者的欺骗方法,Han 批量验证 RSA 签 名算法。利用这种欺骗方法,签名者可以创建一个可以通过批量检测过程接 受核查的无效签名序列。因此,签名者可以否认他/她已签署的消息。为了 避免这种签名者的欺骗行为,我们提出了新的改进的 Han 批量检测议定书。 我们也提出了证明新的协议能够承受签名者的欺骗方法。通过性能分析,我 们得到的结论是, 新的改进的批量检测议定书比原 RSA 验证签名的效率高。

41

附录 5

本科毕业设计(论文)程序

燕山大学本科生毕业设计(论文)

MD5 算法程序 /* * MD5 制作函数 */ #include <stdio.h> #include <stdlib.h> #include <string.h> /* * Convert an array of little-endian words to a hex string. */ int binl2hex( int *src, char *dst, int nsize) { if( src == 0 ) return 1; if( dst == 0 ) return 1; if( nsize < 32 ) return 1; char hex_tab[] = "0123456789abcdef"; int j = 0; for(int i = 0; i < 16; i++) { dst[j++] = hex_tab[(src[i>>2] >> ((i%4)*8+4)) & 0xF]; dst[j++] = hex_tab[(src[i>>2] >> ((i%4)*8 )) & 0xF]; } dst[j] = 0; return 0; } /* * Convert a string to an array of little-endian words * If chrsz is ASCII, characters >255 have their hi-byte silently ignored. */
43

燕山大学本科生毕业设计(论文)

int str2binl(char * src,int *pndst, int nsize) { if(src == 0) return 1; if(pndst == 0) return 1; int nloop = strlen(src) * 8; if( (nloop >> 5) >= nsize ) return 1; for(int i=0; i<nsize; i++ ) pndst[i] = 0; int mask = (1 << 8) - 1; for(int j = 0; j < nloop; j += 8) { pndst[j>>5] |= ( src[j / 8] & mask) << (j%32); } return 0; } /* * Add integers, wrapping at 2^32. */ int safe_add(int x, int y) { int lsw = (x & 0xFFFF) + (y & 0xFFFF); int msw = (x >> 16) + (y >> 16) + (lsw >> 16); return (msw << 16) | (lsw & 0xFFFF); } /* * Bitwise rotate a 32-bit number to the left. */ int bit_rol(unsigned int num, unsigned int cnt) { //old // return (num << cnt) | (num >>> (32 - cnt));
44

燕山大学本科生毕业设计(论文)

return (num << cnt) | (num >> (32 - cnt)); } /* * These functions implement the four basic operations the algorithm uses. */ int md5_cmn(int q, int a, int b, int x, int s, int t) { return safe_add(bit_rol(safe_add(safe_add(a, q), safe_add(x, t)), s),b); } int md5_ff( int a, int b, int c, int d, int x, int s, int t) { return md5_cmn((b & c) | ((~b) & d), a, b, x, s, t); } int md5_gg( int a, int b, int c, int d, int x, int s, int t) { return md5_cmn((b & d) | (c & (~d)), a, b, x, s, t); } int md5_hh( int a, int b, int c, int d, int x, int s, int t) { return md5_cmn(b ^ c ^ d, a, b, x, s, t); } int md5_ii( int a, int b, int c, int d, int x, int s, int t) { return md5_cmn(c ^ (b | (~d)), a, b, x, s, t); } /* * Calculate the MD5 of an array of little-endian words, and a bit length */ int core_md5( int *x, int len, int * dst) { if( x == 0) return 1; if( len <= 0 ) return 1; if (dst == 0) return 1; /* append padding */
45

燕山大学本科生毕业设计(论文)

x[len >> 5] |= 0x80 << ((len) % 32); //old //--x[(((len + 64) >>> 9) << 4) + 14] = len; unsigned int ntemp = len + 64; x[(((ntemp) >> 9) << 4) + 14] = len; int a = 1732584193; int b = -271733879; int c = -1732584194; int d = 271733878; int ncurrlen = (((ntemp) >> 9) << 4) + 14 + 1; for(int i = 0; i < ncurrlen; i += 16) { int olda = a; int oldb = b; int oldc = c; int oldd = d; /*第一轮*/ a = md5_ff(a, b, c, d, x[i+ 0], 7 , -680876936); d = md5_ff(d, a, b, c, x[i+ 1], 12, -389564586); c = md5_ff(c, d, a, b, x[i+ 2], 17, 606105819); b = md5_ff(b, c, d, a, x[i+ 3], 22, -1044525330); a = md5_ff(a, b, c, d, x[i+ 4], 7 , -176418897); d = md5_ff(d, a, b, c, x[i+ 5], 12, 1200080426); c = md5_ff(c, d, a, b, x[i+ 6], 17, -1473231341); b = md5_ff(b, c, d, a, x[i+ 7], 22, -45705983);

a = md5_ff(a, b, c, d, x[i+ 8], 7 , 1770035416); d = md5_ff(d, a, b, c, x[i+ 9], 12, -1958414417); c = md5_ff(c, d, a, b, x[i+10], 17, -42063); b = md5_ff(b, c, d, a, x[i+11], 22, -1990404162); a = md5_ff(a, b, c, d, x[i+12], 7 , 1804603682); d = md5_ff(d, a, b, c, x[i+13], 12, -40341101); c = md5_ff(c, d, a, b, x[i+14], 17, -1502002290); b = md5_ff(b, c, d, a, x[i+15], 22, 1236535329);
46

燕山大学本科生毕业设计(论文)

/*第二轮*/ a = md5_gg(a, b, c, d, x[i+ 1], 5 , -165796510); d = md5_gg(d, a, b, c, x[i+ 6], 9 , -1069501632); c = md5_gg(c, d, a, b, x[i+11], 14, 643717713); b = md5_gg(b, c, d, a, x[i+ 0], 20, -373897302); a = md5_gg(a, b, c, d, x[i+ 5], 5 , -701558691); d = md5_gg(d, a, b, c, x[i+10], 9 , 38016083); c = md5_gg(c, d, a, b, x[i+15], 14, -660478335); b = md5_gg(b, c, d, a, x[i+ 4], 20, -405537848); a = md5_gg(a, b, c, d, x[i+ 9], 5 , 568446438); d = md5_gg(d, a, b, c, x[i+14], 9 , -1019803690); c = md5_gg(c, d, a, b, x[i+ 3], 14, -187363961); b = md5_gg(b, c, d, a, x[i+ 8], 20, 1163531501); a = md5_gg(a, b, c, d, x[i+13], 5 , -1444681467); d = md5_gg(d, a, b, c, x[i+ 2], 9 , -51403784); c = md5_gg(c, d, a, b, x[i+ 7], 14, 1735328473); b = md5_gg(b, c, d, a, x[i+12], 20, -1926607734); /*第三轮*/ a = md5_hh(a, b, c, d, x[i+ 5], 4 , -378558); d = md5_hh(d, a, b, c, x[i+ 8], 11, -2022574463); c = md5_hh(c, d, a, b, x[i+11], 16, 1839030562); b = md5_hh(b, c, d, a, x[i+14], 23, -35309556); a = md5_hh(a, b, c, d, x[i+ 1], 4 , -1530992060); d = md5_hh(d, a, b, c, x[i+ 4], 11, 1272893353); c = md5_hh(c, d, a, b, x[i+ 7], 16, -155497632); b = md5_hh(b, c, d, a, x[i+10], 23, -1094730640); a = md5_hh(a, b, c, d, x[i+13], 4 , 681279174); d = md5_hh(d, a, b, c, x[i+ 0], 11, -358537222); c = md5_hh(c, d, a, b, x[i+ 3], 16, -722521979); b = md5_hh(b, c, d, a, x[i+ 6], 23, 76029189); a = md5_hh(a, b, c, d, x[i+ 9], 4 , -640364487); d = md5_hh(d, a, b, c, x[i+12], 11, -421815835); c = md5_hh(c, d, a, b, x[i+15], 16, 530742520); b = md5_hh(b, c, d, a, x[i+ 2], 23, -995338651);
47

燕山大学本科生毕业设计(论文)

/*第四轮*/ a = md5_ii(a, b, c, d, x[i+ 0], 6 , -198630844); d = md5_ii(d, a, b, c, x[i+ 7], 10, 1126891415); c = md5_ii(c, d, a, b, x[i+14], 15, -1416354905); b = md5_ii(b, c, d, a, x[i+ 5], 21, -57434055); a = md5_ii(a, b, c, d, x[i+12], 6 , 1700485571); d = md5_ii(d, a, b, c, x[i+ 3], 10, -1894986606); c = md5_ii(c, d, a, b, x[i+10], 15, -1051523); b = md5_ii(b, c, d, a, x[i+ 1], 21, -2054922799); a = md5_ii(a, b, c, d, x[i+ 8], 6 , 1873313359); d = md5_ii(d, a, b, c, x[i+15], 10, -30611744); c = md5_ii(c, d, a, b, x[i+ 6], 15, -1560198380); b = md5_ii(b, c, d, a, x[i+13], 21, 1309151649); a = md5_ii(a, b, c, d, x[i+ 4], 6 , -145523070); d = md5_ii(d, a, b, c, x[i+11], 10, -1120210379); c = md5_ii(c, d, a, b, x[i+ 2], 15, 718787259); b = md5_ii(b, c, d, a, x[i+ 9], 21, -343485551); //主循坏结束 a = safe_add(a, olda); b = safe_add(b, oldb); c = safe_add(c, oldc); d = safe_add(d, oldd); } dst[0] =a; dst[1] =b; dst[2] =c; dst[3] =d; return 0; } /* * This is the function you'll usually want to call * They take string arguments and return either hex or base-64 encoded strings */ int hex_md5( char *src, char *dst, int nsize)
48

燕山大学本科生毕业设计(论文)

{ if( dst == 0 ) return 1; if( nsize < 32 ) return 1; int nbuffsize1 = ((strlen(src) * 8) >> 5) + 1; int nbuffsize2 = (((strlen(src) * 8 + 64) >> 9) << 4) + 15; int nbuffsize = nbuffsize1 > nbuffsize2 ? nbuffsize1 : nbuffsize2; int* buff = new int[nbuffsize]; if( buff == 0 ) return 1; int ptemp[4]; for(int i=0; i<4; i++) { *ptemp = 0; } if( str2binl(src,buff,nbuffsize) == 1 ) { delete buff; return 1; } if( core_md5(buff,strlen(src) * 8, ptemp ) == 1) { delete buff; return 1; } delete buff; if( binl2hex(ptemp, dst, 32) == 1) { return 1; } return 0;
49

燕山大学本科生毕业设计(论文)

} //for example:input a string and get a md5 string. int main() { char src[1024]; char md5[32] = {0}; strcpy(src,"message digest "); hex_md5(src, md5, 32); printf("\nmd5:%s\n",md5); return 0; } RSA 算法程序 void main() { int p,q,e,d,m,n,t,c,r; char s; printf("please input the p,q: "); scanf("%d%d",&p,&q); n=p*q; printf("the n is %3d\n",n); t=(p-1)*(q-1); printf("the t is %3d\n",t); printf("please input the e: "); scanf("%d",&e); if(e<1||e>t) { printf("e is error,please input again: "); scanf("%d",&e);
50

燕山大学本科生毕业设计(论文)

} d=1; while(((e*d)%t)!=1) d++; printf("then caculate out that the d is %d\n",d); printf("the cipher please input 1\n"); printf("the plain please input 2\n"); scanf("%d",&r); switch(r) { case 1: printf("input the m: "); /*输入要加密的明文数*/ scanf("%d",&m); c=candp(m,e,n); printf("the cipher is %d\n",c);break; case 2: printf("input the c: "); /*输入要解密的密文数字*/ scanf("%d",&c); m=candp(c,d,n); printf("the cipher is %d\n",m);break; } return; } }

51

燕山大学本科生毕业设计(论文)

52


相关文档

基于RSA算法的数字签名技术研究
RSA算法在数字签名中的应用
RSA算法实现数字签名的研究与应用
RSA数字签名算法在电子病历中的应用
RSA数字签名算法在软件加密中的应用
基于RSA算法的数字签名技术在电子商务安全中的应用
RSA非对称加密算法在数字签名中的应用研究
基于RSA算法实现的网络办公系统数字签名技术
RSA数字签名技术在电子公文流转中的应用
RSA数字签名在电子商务中的应用
电脑版