RSA数字签名毕业论文
摘要
当今世界信息技术获得了前所未有的大发展，因而信息的安全性必将变得越来越受到人们的重视。而数字签名技术是目前网络安全领域的研究热门方向。
RSA算法是第一个能同时用于加密和数字签名的算法，易于应用和理解。RSA从提出一直到现在，它经历了各种考验。它通过认证技术来分辨真与假。RSA数字签名体制使用地是RSA公开密钥算法进行得数字签名。
本文主要是对RSA公开密钥密码体制的研究，并在此基础上实现了RSA的数字签名的体制。本文的主要内容包括：
第一：在查阅大量文献资料的基础上，分析了密码学领域里，公钥加密体制的优点所在及其RSA数字签名的安全性（攻击性）；第二：简述了DSA以及椭圆曲线数字签名，深入分析RSA算法的理论基础及算法原理，包括RSA大素数的产生，密钥对的产生，以及对明文的加密和解密：第三：对MD5算法基本原理的详细介绍。第四：阐述了RSA数字签名的设计与实现，其中包括RSA公钥和私钥的产生，RSA加密与解密算法的实现，消息摘要的生成，还有就是利用RSA加密算法实现数字签名以及签名的验证。第五，简要陈述数字签名的用途。
关键词：加密解密RSA算法RSA数字签名
Abstract
Now the information of the world is developing fastly.So the security of the information is becoming more and more importantly. Digital signature filed will become hot spots in future.
It is the first algorithm for both data encryption and digital signature.It can be understood easily by people.RSA has undergone various tests when it is put out.RSA as the public key cryptosystem representative approved data integrity is a kind of information technology. It is through the authentication techniques to distinguish true and false. RSA digital signature system using a RSA public key algorithm for digital signature.
The text is about the study of RSA public key encryption,based on this generating RSA digital signature.including:
,Firstly on the basis of previous research, a system based on elliptical curve proxy signature, The advantage of public key encryption and the security of RSA digital signature(attack )Secondly,it analyzes the principle of RSA,including how to generat a prime number,how to generat the secret keys and how to encryption as well as decrypt, Thirdly,it states the principle of MD5 in detail.Fourthly, it states design and realization of RSA digital signature in detail. The main modules includes producing RSA secret keys, implementation of RSA encryption algorithm and decryption algorithm, producing message digest and realizing digital signature and verification by RSA.
Key words: RSA algorithm; encryption; decryption; RSA digital signature
目录
摘要............................................................. I Abstract......................................................... I I 1绪论. (1)
1.1 研究背景 (2)
1.2 研究现状 (3)
2密码学基本概念 (4)
2.1 公钥密码基本概念 (5)
2.1.1 公钥密码原理 (5)
2.1.2公钥密码的理论基础 (6)
2.2 对称加密体制 (6)
3数字签名的基本概念和理论 (8)
3.1数字签名概念 (8)
3.2 数字签名理论 (8)
3.3数字签名过程 (9)
3.3.1.发送方签名过程 (9)
3.3.2.接收方验证过程 (10)
4数字签名常见的算法及其数字签名 (12)
4.1 DSA数字签名算法 (12)
4.1.1 DSA数字签名实现的三个步骤 (12)
4.1.2 DSA的安全性 (13)
4.2 椭圆曲线代理签名体制 (13)
4.2.1椭圆曲线数字签名ECDSA (13)
4.2.2椭圆曲线数字签名的安全性 (14)
5 RSA算法及其数字签名 (15)
5.1 RSA简述 (15)
5.2 RSA加密的可行性 (16)
5.3 RSA算法的介绍 (16)
5.3.1 RSA中素数的选取 (17)
5.3.2 RSA用到的公式和定理 (17)
5.3.3 RSA安全性的分析 (17)
5.3.4 RSA的攻击 (18)
5.3.5 RSA的缺点 (19)
5.3.6 RSA的优点 (20)
5.4 RSA数字签名 (20)
5.4.1 RSA数字签名的过程 (20)
5.4.2 RSA数字签名算法实现步骤 (20)
5.4.3 散列函数的原理 (21)
5.4.4 MD5算法的简介 (22)
6 RSA数字签名设计与实现 (24)
6.1 开发环境的介绍 (24)
6.1.1 C#语言概述 (24)
6.1.2 C#语言特点 (24)
https://www.sodocs.net/doc/6e1186206.html,类的介绍 (25)
6.3 RSA数字签名所需实现的功能 (26)
6.4 本软件的总体要求和设计 (26)
6.5主要实现代码及软件运行结果 (27)
结论 (31)
致谢.......................................................................................... 错误！未定义书签。参考文献 (33)
附录1 (34)
1绪论
1.1 研究背景
当今社会是信息化社会，电子计算机和通信网络己经广泛的应用于社会的各个领域，以此为基础建立起来的各种信息系统，给人们的生活、工作带来了巨大变革。大型信息系统将众多的计算机和只能化设备连在一个四通八达的通信网络中，共享丰富的数据库信息和计算机资源，储存大量的数据文件，完成异地之间的数据交换与通信。信息系统的应用，加速了社会自动化的进程，减轻了日常繁杂的重复劳动，同时也提高了生产率，创造了经济效益。
信息时代虽然给我们带来了无限商机与方便，但同时也充斥着隐患与危险。由于网络很容易受到攻击，导致机密信息的泄漏，引起重大损失。由于信息技术已经成为综合国力的一个重要组成部分，因此信息安全己成为保证国民经济信息化建设健康有序发展的保障。
当今网络社会技术众多，目前在电子商务、电子政务、电子邮件系统、电子银行等方面必备的关键技术就是数字签名。数字签名又称为数字签字，电子签章等。“数字签名”用来保证信息传输过程中信息的完整和提供信息发送者的身份认证和不可抵赖性，数字签名技术的实现基础是公开密钥加密技术，是用某人的私钥加密的消息摘要用于确认消息的来源和内容。
为保证数据在网络传递中的安全性和完整性从技术上，主要考虑一下情况：（1）如果需要使用一种方法验证数据在传输过程中是否被修改,可以使用哈希值?
（2）如果需要证明实体知道机密但不来回发送机密,或者想使用简单的哈希值以防止在传输过程中被截获,可以使用加密的哈希值?
（3）如果要隐藏通过不安全的媒介发送的数据或者永久保留数据,可以使用加密
（4）如果要验证声称是公钥所有者的人员的身份,可以使用证书?
（5）如果双方事先共享密钥,可以使用对称加密以提高速度?
（6）如果想通过不安全的媒介安全的交换数据可以使用非对称加密
（7）如果要进行身份验证和实现不可否认性,可以使用数字签名
（8）如果为了防范穷举搜素而进行的攻击,可以使用加密技术产生的随机数[1] RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。
它易于理解和操作，也十分流行。随着越来越多的商业应用和标准化工作，RSA 已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。
1.2 研究现状
实现数字签名的算法有很多，目前数字签名采用较多的是公钥加密技术，如DSA (Digital Signature Algorithm), x.509, POP (Pretty Good Privacy)。1994年美国标准与技术协会公布了数字签名标准(DSS)而使公钥加密技术广泛应用。
RSA已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准（Secure Electronic Transactions，SET）就采用了标准RSA算法，这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等，大多数使用RSA技术。
（1）研究主要成果
RSA作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA在硬件方面，以技术成熟的IC应用于各种消费类电子产品。
RSA在软件方面的应用，主要集中在Internet上。加密连接、数字签名和数字证书的核心算法广泛使用RSA。
RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA目前是最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。
RSA的缺点主要有：
（1）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
（2）分组长度太大，为保证安全性，n 至少也要600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级。
（2）发展趋势
当今社会是信息化社会，电子计算机和通信网络己经广泛的应用于社会的各个领域，以此为基础建立起来的各种信息系统，给人们的生活、工作带来了巨大变革。信息系统的应用，加速了社会自动化的进程，减轻了日常繁杂的重复劳动，
同时也提高了生产率，创造了经济效益。
信息安全技术在信息化迅速发展的今天己进入了高速发展的新时期，形成了密码技术、可信计算技术、电磁辐射泄露防护技术、系统入侵检测技术和计算机病毒检测消除技术等多个安全防护技术门类。
（3）存在问题
目前普遍采用的数字签名算法，都是基于下面三个数学难题的基础之上：(1)整数的因式分解(Integer Factorization)问题，如RSA算法。(2)离散对数(Discrete Logarithm)问题，如ElGamal,DSA,Schnorr等算法；（3)椭圆曲线(Elliptic Curve)问题，如ECDSA算法。[2]
2密码学基本概念
密码学包括两个方面：密码编码学和密码分析学。密码编码学就是研究对数
据进行变换的原理、手段和方法的技术和科学。密码分析学是为了取得秘密的消息，而对密码系统及其流动数据进行分析，是对密码原理、手段和方法进行分析、攻击的技术和科学。
密码学的理论基础是数学，其基本思想是隐藏、伪装信息，使未经授权者不
能得到消息的真正含义。伪装(变换)之前的信息是原始信息，成为明文；伪装之后的消息，看起来是一串无意义的乱码，称为密文。把明文伪装成密文的过程称为(encryption)，该过程使用的数学变换就是加密算法。把密文还原成明文的过程称为解密(decryption)，该过程使用的数学变换，通常是加密时数学变换的逆变换，就是解密算法。加密与解密通常需要参数控制，我们把该参数称为密钥，有时也称为密码。加密时使用的为加密密码(加密密钥)，解密时使用的为解密密码(解密密钥)。[3]加密密钥与解密密钥可能相同也可能不同。相同时称为对称型或单钥的，不相同时称为非对成型或双钥的。那么一个密码系统或称其为密码体制，是由明文空间、密文空间、密钥空间、加密算法与解密算法五个部分组成。明文、密文、密钥空间分别表示全体明文、全体密文、全体密钥的集合；加密与解密算法通常是一些公式、法则或程序，规定了明文与密文之间的数学变换规则。
下面用字母分别表示这个概念，密钥K=
示解密密钥，设明文M ，密文C ，加密算法E ，解密算法D 。
把明文加密为密文: C=E(M,Ke) 密文解密为明文：M=D(C,Kd)=D(E(M,Ke),Kd)。
明文
明文空间
图2-1加密过程与密码分析
2.1 公钥密码基本概念
公钥密码与以前所有的密码方法都大相径庭:一是以前的密码算法都基于代换与置换操作，而公钥密码使用数学数进行变换；二是公钥密码体制使用非对称的方式，使用两个密钥(加密密钥与解密密钥)，而传统密码算法仅仅使用一个密钥。公钥密码体制的提出首先是为了解决利用传统密码体制进行密钥分发时遇到的问题，数字签名也是其重要应用之一。[3]
从1976年起，学者们提出了许多种公钥加密方法，它们的安全性都是基于复杂的数学难题。根据所基于的数学难题来分类，有以下三类系统目前被认为是安全和有效的：
(1) 基于大整数因子分解的：RSA和Rabin-Williams。
(2) 基于离散对数问题的：DSA和EIGamal。
(3) 基于椭圆曲线离散对数问题的：椭圆曲线密码系统。
公开密钥加密算法与对称密钥加密算法相比来说，安全性能更好，密钥管理、分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。
2.1.1 公钥密码原理
公开密钥密码常用的、成熟的公钥算法是RSA。它与传统的对称密钥算法有本质的区别，对称密钥算法常用的是DES算法，加/解密时用的是同一个密钥。而公钥算法利用的是非对称的密钥，即利用两个足够大的质数与被加密原文相乘生产的积来加/解密。这两个质数无论是用哪一个与被加密的原文相乘(模乘)，即对原文件加密，均可由另一个质数再相乘来进行解密。但是，若想用这个乘积来求出另一个质数，就要进行对大数分解质因子，分解一个大数的质因子是十分困难的，若选用的质数足够大，这种求解几乎是不可能的。
公、密钥对的用法是，当发方向收方通信时发方用收方的公钥对原文进行加密，收方收到发方的密文后，用自己的私钥进行解密，其中他人是无法解密的，因为他人不拥有自己的私钥，这就是用公钥加密，私钥解密用于通信;而用私钥加密文件公钥解密则是用于签名，即发方向收方签发文件时，发方用自己的私钥加密文件传送给收方，收方用发方的公钥进行解密。
但是，在实际应用操作中发出的文件签名并非是对原文本身进行加密，而是要对原文进行所谓的“哈希”(Hash)运算，即对原文作数字摘要。该密码算法也称单向散列运算，其运算结果称为哈希值，或称数字摘要，也有人将其称为“数
字指纹”。哈希值有固定的长度，运算是不可逆的，不同的明文其哈希值是不同的，而同样的明文其哈希值是相同并且是唯一的，原文的任何改动，其哈希值就要发生变化。数字签名是用私钥对数字摘要进行加密，用公钥进行解密和验证[4]
公钥密码算法使用两个密钥，其中一个用于加密(加密密钥)，另外一个用于
解密(解密密钥)。公钥密码算法具有如下特征：加密密钥与解密密钥时本质上不通的，也就是说如果仅仅知道密码算法和加密密钥，而要确定解密密钥，在计算上是不可行的；大多数公钥密码算法的加密密钥与解密密钥具有互换的性质。如RSA 算法，密钥对中的一个用于加密，另一个用于解密。
2.1.2公钥密码的理论基础
公钥密码体制的安全性主要取决于构造公钥算法所依赖的数学问题，通常要
求加密函数具有单向性，即求逆很困难。因此，公钥密码的理论基础是陷门单向函数。
1 单向函数
（1）对于所有属于f 定义域的任一x,可以很容易算出f(x)=y.
（2）对于几乎所有属于f 值域的任一y,则在计算上不可能求出x ，使得y=f(x).
2 单向陷门函数
设f 是一个函数，t 是与f 有关的一个参数，对于任一给定的x 。计算y ，使
得y=f(x)是容易的。如果当不知道参数t 是，计算的f 逆函数是难解的，但但知道参数t 时，计算f 的逆函数是容易的，则称f 是一个单向陷门函数，参数称为陷门。[5]
2.2 对称加密体制
对称加密算法，又称私钥加密算法，就是加密密钥能够从解密密钥中推出来，
反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称算法的加密和解密表示为：
M C D C M E k k ==)(,)( （2-1）
对称加密算法的典型代表有:DES ，AES ，3DES ，RC2，RC4，RCS ，RC6，
IDEA 等。以DES 为代表的对称密钥加密算法的设计原则主要基于信息论的混乱和扩散。混乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分组间的统计规律，通常依靠多轮迭代来实现；扩散则应使密钥和明文的每一位影响密文中尽可能多的位数，这样可以防止逐段破译，并通过S 盒的非线性变换来实现。实际上，所有的对称密钥加密算法都采用Feistel 网、S 盒及多次迭代等思
想。
对称加密有速度上的优点，用软件实现，对称密钥比非对称密钥快100-1000倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安全传输密钥。对称加密系统用键长来衡量加密强度，40比特的键长被认为比较脆弱，128比特比较健壮。
对称加密算法的缺点则是密钥分发困难，密钥管理难，无法实现数字签名。对称加密算法的优点是保密强度高，加解密速度快，适合加密大量数据。攻击者如果对加密后的数据进行破译，唯一的办法就是对每个可能的密钥执行穷搜索。而采用这种加密技术，即使使用最快的计算机执行这种搜索，耗费的时间也是相当的长。如果使用较大的密钥，破译将会更加的困难。[6]
3 数字签名的基本概念和理论
3.1数字签名概念
数字签名是一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算，一个用于签名，另一个用于验证。数字签字由公钥密码发展而来，它在网络安全，包括身份认证、数据完整性、不可否认性以及匿名性等方面有着重要应用。特别是在大型网络安全通信中的密钥分配、认证以及电子商务系统中都有重要的作用，数字签名的安全性日益受到高度重视。
数字签名是指用户用自己的私钥对原始数据的哈希摘要进行加密所得的数据。信息接收方使用信息发送方的公钥对附在原始信息后的数字签名进行解密后获得哈希摘要，并通过与自己用收到的原始数据产生的哈希摘要对照，便可确信原始数据信息是否被篡改。这样就保证了消息来源的真实性和数据传输的完整性。[7]
3.2 数字签名理论
数字签名的实现通常采用非对称密码与对称密码体系。不同的是，非对称密码体系的加密和解密过程分别通过两个不同的密钥来实现，其中一个密钥以公开，称为公开密钥，简称公钥，另一个有用户自己秘密保管，称为保密密钥，简称私钥。只有相应的公钥能够对用私钥加密的信息进行解密，反之亦然。以现在的计算机运算能力，从一把密钥推算出另一把密钥是不大可能的。所以，数字签名具有很大的安全性，这是它的一个优点。
数字签名的基本方式主要是：信息发送方首先通过运行散列函数生成一个欲发送报文的信息摘要，然后用其私钥对这个信息摘要进行加密以形成发送方的数列签名，这个数字签名将作为报文的附件和报文一起发送给报文的接收方。接收方在收到信息后首先运行和发送相同的散列函数生成接收报文的信息摘要，然后再用发送方的公钥进行解密，产生原始报文的信息摘要，通过比较两个信息摘要是否相同就可以确认发送方和报文的准确性。当然，上述过程只是对报文进行了签名，对其传送的报文本身并未保密。为了同时实现数字签名和秘密通信，发送者可以用接收方的公钥对发送的信息进行加密，这样，只有接收方才能通过自己的私钥对报文进行接么，其它人即使获得报文并知道发送者的身份，由于没有
接收方的密钥也无法理解报文。
3.3数字签名过程
为了实现网络环境下的身份鉴别、数据完整性认证和抗否认的功能，数字签名应满足以下要求：
（1）签名者发出签名的消息后，就不能再否认自己所签发的消息；
（2）接收者能够确认或证实签名者的签名，但不能否认；
（3）任何人都不能伪造签名；
（4）第三方可以确认收发双方之间的消息传送，但不能伪造这一过程，这样，当通信的双方关于签名的真伪发生争执时，可由第三方来解决双方的争执。[8]对于一个典型的数字签名体系而言，它必须包含2个重要的组成部分：即签名算法(Signature Algorithm)和验证算法(Verification Algorithm)。为了满足上述4点要求，数字签名体系必须满足2条基本假设：
（1）签名密钥是安全的，只有其拥有者才能使用。
（2）使用签名密钥是产生数字签名的唯一途径。
3.3.1.发送方签名过程
（1）为保证签名的速度，A先将原文进行单向HASH运算生成定长的消息摘要A
图3-1 生产摘要
（2）利用自己的私钥加密消息摘要得到数字签名A，并将数字签名附在原消息后面
图3-2 加密摘要
（3）通讯时用户A 将自己的名文一起通过网络送给通讯对方即用户B
图3-3发送原文和摘要 3.3.2.接收方验证过程
接收方B 接收到发送方Ａ的签名消息后，对Ａ的签名消息进行验证的过程
如下：
（1）将消息中的原消息与数字签名分离出来
图3-4分离明文和数字签名
（2）使用A 的公钥解密数字签名得到摘要
图3-5得到摘要
（3）利用与发送方A 相同的散列函数重新计算原消息的摘要
图3-6 接受方计算摘要
（4）比较解密后获得的消息摘要A 与重新计算产生的消息摘要B ，若相等
则说明消息在传输过程中没有被篡改，否则消息不可靠。
图3-7验证数字签名3.3.3数字签名过程
图3-8数字签名流程图
4 数字签名常见的算法及其数字签名
数字签名的方法有很多，现在主要应用的数字签名主要有：RSA，DSA以及椭圆曲线数字签名。
4.1 DSA数字签名算法
.DSA是SChnorr和ELGAmal签名算法的变种，被美NIST作为DSS是一种公开密钥算法，它不能用作加密，只能用作数字签名。DSA使用公开公钥，为接受者验证数据的完整性和数据发送者的身份。它也用作于由第三方去确定签名和所签收数据的真实性。信息交流中，接受方希望收到的信息未被篡改，还希望收到的信息确实是自己认定的发送方所发，那么接受方和发送方就可以约定，共同使用DSA来实现。
4.1.1 DSA数字签名实现的三个步骤
（1）参数与密钥生成（2）签名的算法（3）签名的验证算法
1.初始过程
（1）系统参数:大素数p, q且q为p-1的因子, 并满足2^511 2^159 g ∈Zp , 且满足g =h ^(p-1)/q mod p,其中h是一整数, 1< h < p-1且 h^(p-1)/q modp>1 。p,q,g 作为系统参数,供所有用户使用,在系统内公开? （2）用户私钥:用户选取一个私钥x,1 （3）用户公钥:用户的公钥y,y = g^x mod p,公开? 2.签名过程 对待签消息m,设0 （1）生成一随机整数k, k ∈Zp* ; （2）计算r = (g^k mod p) mod q; （3）计算s = k^-1*(h(m)+x*r) mod q?则(r,s)为签名人对m的签名? 3. 验证过程 （1）首先检查r和s是否属于[0,q],若不是,则(r,s)不是签名; （2）计算t= s^-1mod q , r’=(g^h(m) t mod q (y^r*t mod q )mod p) mod q ; （3）比较r’= r 是否成立?若成立,则(r,s) 为合法签名,则(r,s) 为签名人对m的 签名 4.1.2 DSA的安全性 DSA的安全性主要依赖于整数有限域离散对数难题。其安全性与RSA相比差不多，DSA的一个重要特点是两个素数公开，这样，当使用别人的P和Q是，即使不知道私钥，你也能确认他们是否是随机产生的，还是做了手脚的。RSA 算法是做不到的。素数P必须足够大，且p-1至少包含一个大素数因子以抵抗Pohlig&hellman算法的攻击。M一般都应采用信息HASH的值。DSA安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。DSA的一个主要特点是两个素数公开，这样，当使用别人的p和g，即使不知道私钥，你也能确认他们是随机产生的。[9] 4.2 椭圆曲线代理签名体制 4.2.1椭圆曲线数字签名ECDSA 椭圆曲线签名算法ECDSA是基于椭圆曲线密码体制(ECC)的数字签名算法。DSA是美国国家标准局制定的数字签名算法，他是建立在有限域乘法群上的。对于有限域上的椭圆曲线密码系统，数字签名标准建议采用椭圆曲线数字签名算法ECDSA，下面给出该算法的过程。 假设一组椭圆曲线的参数组为(q，FR，a，b，G，n，h)。其中q是域的阶，FR指示域中元素的表示方法，a，b是两个系数，G是基点，G的阶为n，余因子h=#E(Fq)／n，他是一个小的素数。 1 ECDSA密钥对生成过程 （1）选择一个随机数d,d∈(1,n-1)? （2）计算Q,Q=d*G? （3）那么公钥为Q,私钥为整数d? 2 ECDSA签名过程 假设待签名的消息为，m； （1）选择一个随机数k，k∈(1，n-1)。 （2）计算k*G=(x1,y1)。 （3）计算r=x1 mod n；如果r=O，则返回到步骤(1)。 （4）计算s=k^-1(e+d*r) mod n，如果s=O，则返回到步骤(1)。 （5）对消息的签名为(r，s)，最后签名者把消息m和签名(r，s)发送给接收者。 3 ECDSA密钥对验证过程 获得发送者的公钥Q开始验证： （1）检查r，s，要求r，s∈(1，n-1)。 （2）计算e=SHA1(m)。 （3）计算w=s-1mod n。 （4）计算u1=e*w mod n；u2=r*w mod n。 （5）计算X=u1G+u2Q。 （6）如果X=O，表示签名无效；否则，X=(x1，y1)，计算v=x1 mod n。 （7）如果v=r，表示签名无效；否则表示签名有效。[10] 4.2.2椭圆曲线数字签名的安全性 ECDSA在安全性方面的目标是能抵抗选择明文（密文）攻击。而攻击A的攻击者的目标是在截获A的签名后，可以生成对任何消息的合法签名。尽管ECDSA的理论模型很坚固，但是人们仍研究很多措施以提高ECDSA的安全性。在ECDLP不可破解及哈希函数足够强的前提下，DSA和ECDSA的一些变形已被证明可以抵抗现有的任何选择明文（密文）攻击。在椭圆曲线所在群是一般群并且哈希函数能够抗碰撞攻击的前提下，ECDSA本身的安全性已经得到证明。 ECDSA可能面临的攻击： 1.对ECDLP的攻击。 2.对哈希函数的攻击。 3.其他攻击。 ECDMA的优点 （1）安全性能高（2）计算机量小和计算机速度快（3）存储空间占有量小（4）带宽要求低。 5 RSA算法及其数字签名 5.1 RSA简述 RSA加密体制是一种公开的密码体制。RSA公匙密码体制是又R.L.Rivest，A.Shamir和L.Adelman于1978年提出的。由于RSA算法很完善，即可用于数据加密，又可用于数字签名，安全性良好，易于实现和理解，所以已经成为一种应用极广的公匙密码算法，目前，RSA在许多场合有广泛的应用。 RSA 公钥密码算法是迄今为止在理论上最为成熟、完善的公钥密码体制。从提出到现在已经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。它是第一个既能用于数据加密也能用于数字签名和密钥分配与管理的算法。它易于理解和操作，也很流行。因为它既可用于加密,又可用于签名,并为用户的公开密钥签发公钥证书、发放证书、管理证书等,提高了服务质量，所以, RSA 公开密钥密码在当今的信息交换过程中已得到广泛的应用和实践，RSA 公钥密码体制在世界许多地方已经成为事实上的标准。 该算法的加密密钥和加密算法分开,使得密钥分配更为方便。而且它特别符合计算机网络环境。对于网上的大量用户,可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信,只需从公钥簿上查出对方的加密密钥,用它对所传送的信息加密发出即可。对方收到信息后,用仅为自己所知的解密密钥将信息解密,了解明文的内容。[11]由此可看出,RSA 算法解决了大量网络用户密钥管理的难题,这是公钥密码系统相对于对称密码系统最突出的优点。 RSA 是一个基于数论的非对称密码体制,是一种分组密码体制，是一种基于因子分解的指数函数作为单向陷门函数的公钥体制算法。它基础是数论的欧拉定理,素数检测,它的安全性是基于大数分解,后者在数学上是一个困难问题。 RSA 的安全性基于复杂性理论中的计算安全性, 依赖于大整数分解这一NP 难题。可靠性与所用密钥的长度有很大关系, 假如有人找到一种很快的分解因子的算法, 即从一个公钥中通过因数分解得到私钥, 那么用RSA 加密的信息的可靠性肯定会极度下降。但由于其工作量巨大,按目前计算机的处理能力是不可能实现的。实践证明,在当前的技术和方法下,密钥不小于1 024 bit的RSA 算法仍然是安全的。这充分说明RSA 系统具有良好的保密性能。 因此,尽管先后出现了很多新的公钥体制算法,但RSA仍然在不同应用领域占 据了重要的位置。随着计算机运算速度的提高以及因子分解算法的突破, RSA 的密钥长度将越来越大, 其软硬件实现速度将成为制约其使用的重要因素。 5.2 RSA加密的可行性 虽然RSA加密运算的速度十分慢,但是在PC性能越来越好的今天,对于几千字节的数据进行一次几百位密钥的RSA加密,所消耗的时间应该是可以接受的?下面结合大数运算程序的调试,从理论上简单的分析消耗时间?在一台普通配置的PC机上对一个整数进行幂模运算,因为公开密钥的e通常取的较小,所以指数取一个小整数,比如C353,模一个70字节长的整数(140位十六进制,大数单元以线性组方式实现,对应到RSA算法中,这相当于约560bit的n),调试一个函数测试,按初等数论中的知识对程序进行算法优化,最终在一台配置为AMD Athron2800+,外频333MHZ,物理内存512MB的PC上测试需要约45毫秒时间?如果按这种速度,逐字节对1KB的数据进行同样的运算,所消耗的时间理论上为45毫秒的1024倍即约45秒?这个时间并不是非常长[12]? 其实从一个简单的角度来说,既然RSA用于数字签名可行,那就完全可以用于同样大小的普通文件?对于较大的文件,如果分成与数字签名同样大小的段(这里假设数字签名较短,不分段一次计算加密完成),分开的各段逐一进行加密运算,那所需要的时间也只是按文件大小线性的增长?通常数字签名为几十字节,加密运算并不需要很长的等待,这就说明对于几百字节或一两K字节大小的文件来说,如果进行RSA加密,并不会是非常漫长的工作?当然,如果文件更大,加密就显得十分漫长了?比如按前面叙述的45毫秒大数运算程序推理,加密1M字节大小的文件需要约1天的时间?所以,要在普通PC用几百位以上的长密钥RSA加密文件,文件不能过大,一般可以接受的上限是几KB?如果要在较短时间内加密大文件,需要缩短密钥长度以减小运算量,这将带来安全性隐患?[13] 5.3 RSA算法的介绍 RSA系统由以下几部分组成： （1）随机选取的在素数P和Q，还有N ，其中N=P*Q ，P和Q保密，N 公开。 （2）任取Φ(n)=（P-1）*(Q-1)，其中(n)表示比n小的素数的个数，任取2<=e<= (n),且(e, (n))=1,e为加密密钥，公开。 （3）计算d,使e*d=1(mod (n)),称d为e对模(n)的逆，其中d为解密秘钥，保密。在RSA系统中，设m为明文，且明文块的数值大于n,c为密文，则其加