毕业论文《RSA公开密钥密码体制的研究及实现》

1、当今世界信息技术获得了前所未有的大发展，因而信息的安全性必将变得越来越受 到人们的重视。而数字签名技术是目前网络安全领域的研究热门方向。rsa算法是第一个能同时用于加密和数字签名的算法，易于应用和理解。rsa从提出 一直到现在，它经历了各种考验。它通过认证技术来分辨真与假。rsa数字签名体制使 用地是rsa公开密钥算法进行得数字签名。本文主要是对rsa公开密钥密码体制的研究，并在此基础上实现了rsa的数字签名的 体制。本文的主要内容包括：第一：在查阅大量文献资料的基础上，分析了密码学领域里，公钥加密体制的优点 所在及其rsa数字签名的安全性（攻击性）；第二 简述了dsa以及椭圆曲线数字签名，

2、深入分析rsa算法的理论基础及算法原理，包括rsa大素数的产生，密钥对的产生，以 及对明文的加密和解密：第三：对md5算法基本原理的详细介绍。第从 阐述了rsa数字 签名的设计与实现，其屮包括rsa公钥和私钥的产生，rsa加密与解密算法的实现，消息 摘要的生成，还有就是利用rsa加密算法实现数字签名以及签名的验证。第五，简要陈 述数字签名的用途。关键词：加密 解密rsa算法 rsa数字签名abstractnow the information of the world is developing fastly.so the security of the information is beco

3、ming 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.lt can be understood easily by people.rsa has undergone various tests when it is put out.rsa as the public key cryptosystem representative a

4、pproved 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

5、 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 rs a,including how to generat a prime number

6、,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 an

7、d decryption algorithm, producing message digest and realizing digital signature and verification by rsakey words: rsa algorithm; encryption; decryption; rsa digital signature目录摘要iabstract ii1绪论11研究背景21.2研究现状32密码学基本概念42公钥密码基本概念52.1.1公钥密码原理52.1.2公钥密码的理论基础62.2对称加密体制63数字签名的基本概念和理论83数字签名概念83.2数字签名理论83.3

8、数字签名过程93.3.1. 发送方签名过程93.3.2. 接收方验证过程104数字签名常见的算法及其数字签名124dsa数字签名算法124dsa数字签名实现的三个步骤124.1.2 dsa的安全性134.2椭圆曲线代理签名体制13421椭圆曲线数字签名ecdsa134.2.2椭圆曲线数字签名的安全性145 rsa算法及其数字签名155rsa简述155.2 rsa加密的可行性165.3 rsa算法的介绍16531 rsa中素数的选取175.3.2 rsa用到的公式和定理175.3.3 rsa安全性的分析175.3.4 rsa 的攻击185.3.5 rsa 的缺点195.3.6 rsa 的优点20

9、5.4 rsa数字签名205.4.1 rsa数字签名的过程205.4.2 rsa数字签名算法实现步骤205.4.3散列函数的原理215.4.4 md5算法的简介226 rsa数字签名设计与实现246开发环境的介绍246.1.1 c#语言概述246.1.2 c#语言特点246.2. net类的介绍256.3 rsa数字签名所需实现的功能266.4本软件的总体要求和设计266.5主要实现代码及软件运行结果27结论31致谢错误！未定义书签。参考文献33附录1341绪论1.1研究背景当今社会是信息化社会，电子计算机和通信网络己经广泛的应用于社会的各 个领域，以此为基础建立起来的各种信息系统，给人们的生

10、活、工作带来了巨大 变革。大型信息系统将众多的计算机和只能化设备连在一个四通八达的通信网络 中，共享丰富的数据库信息和计算机资源，储存大量的数据文件，完成异地之间 的数据交换与通信。信息系统的应用，加速了社会自动化的进程，减轻了口常繁 杂的重复劳动，同时也提高了生产率，创造了经济效益。信息时代虽然给我们带来了无限商机与方便，但同时也充斥着隐患与危险。由 于网络很容易受到攻击，导致机密信息的泄漏，引起重大损失。由于信息技术已 经成为综合国力的一个重要组成部分，因此信息安全己成为保证国民经济信息化 建设健康有序发展的保障。当今网络社会技术众多，目前在电子商务、电子政务、电子邮件系统、电子 银行等方

11、面必备的关键技术就是数字签名。数字签名又称为数字签字，电子签章 等。“数字签名”用来保证信息传输过程中信息的完整和提供信息发送者的身份 认证和不可抵赖性，数字签名技术的实现基础是公开密钥加密技术，是用某人的 私钥加密的消息摘要用于确认消息的来源和内容。为保证数据在网络传递中的安全性和完整性从技术上，主要考虑一下情况：(1) 如果需要使用一种方法验证数据在传输过程中是否被修改，可以使用哈 希值。(2) 如果需要证明实体知道机密但不来回发送机密，或者想使用简单的哈希 值以防止在传输过程屮被截获，可以使用加密的哈希值。(3) 如果要隐藏通过不安全的媒介发送的数据或者永久保留数据，可以使用 加密(4)

12、 如果要验证声称是公钥所有者的人员的身份，可以使用证书。(5) 如果双方事先共享密钥，可以使用对称加密以提高速度(6) 如果想通过不安全的媒介安全的交换数据可以使用非对称加密(7) 如果要进行身份验证和实现不可否认性，可以使用数字签名(8) 如果为了防范穷举搜素而进行的攻击,可以使用加密技术产生的随机数 rsa公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也十分流行。随着越来越多的商业应用和标准化工作，rsa 已经成为最具代表性的公钥加密技术。visa、mastercards ibm、microsoft等 公司协力制定的安全电子交易标准(secure elect

13、ronic transactions, set)就采 用了标准rsa算法，这使得rsa在我们的生活中几乎无处不在。网上交易加密 连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡 的验证功能芯片等，大多数使用rsa技术。1.2研究现状实现数字签名的算法有很多，目前数字签名釆用较多的是公钥加密技术，如 dsa (digital signature algorithm), x.509, pop (pretty good privacy)0 1994 年美国 标准与技术协会公布了数字签名标准(dss)而使公钥加密技术广泛应用。rsa已经成为最具代表性的公钥加密技术。visa、ma

14、stercards ibm、 microsoft等公司协力制定的安全电子交易标准(secure electronic transactions, set)就采用了标准rsa算法，这使得rsa在我们的生活中几乎无处不在。网 上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电 话和存储卡的验证功能芯片等，大多数使用rsa技术。(1) 研究主要成果rsa作为最重要的公开密钥算法，在各领域的应用数不胜数。rsa在硬件 方面，以技术成熟的ic应用于各种消费类电子产品。rsa在软件方面的应用，主要集屮在internet ±o加密连接、数字签名和数 字证书的核心算法广泛使用rs

15、aorsa算法是第一个能同时用于加密和数字签名的算法，也易于理解利操作。 rsa是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻 击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。rsa 0 前是最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击， 已被iso推荐为公钥数据加密标准。rsa的缺点主要有：(1) 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。(2) 分组长度太大，为保证安全性，n至少也要600 bits以上，使运算代价 很高，尤其是速度较慢，较对称密码算法慢儿个数量级。(2) 发展趋势当今社会是信息化社会，电子计算机和通信

16、网络己经广泛的应用于社会的各 个领域，以此为基础建立起来的各种信息系统，给人们的生活、工作带来了巨大 变革。信息系统的应用，加速了社会自动化的进程，减轻了日常繁杂的重复劳动,同时也提高了生产率，创造了经济效益。信息安全技术在信息化迅速发展的今天己进入了高速发展的新时期，形成了 密码技术、可信计算技术、电磁辐射泄露防护技术、系统入侵检测技术和计算机 病毒检测消除技术等多个安全防护技术门类。(3) 存在问题目前普遍采用的数字签名算法，都是基于下面三个数学难题的基础z上：(1) 整数的因式分解(integer factorization)l'nj题，如rsa算法。离散对数(discrete

17、logarithm)问题,女口 elgamal,dsa,schnorr 等算法;(3)椭圆曲线(elliptic curve) 问题，如ecdsa算法。习2密码学基本概念密码学包括两个方面：密码编码学和密码分析学。密码编码学就是研究对数 据进行变换的原理、手段和方法的技术和科学。密码分析学是为了取得秘密的消 息，而对密码系统及其流动数据进行分析，是对密码原理、手段和方法进行分析、 攻击的技术和科学。密码学的理论基础是数学，其基本思想是隐藏、伪装信息，使未经授权者不 能得到消息的真正含义。伪装(变换)之前的信息是原始信息，成为明文；伪装之 后的消息，看起来是一串无意义的乱码，称为密文。把明文伪装

18、成密文的过程称 为(encryption),该过程使用的数学变换就是加密算法。把密文还原成明文的过程 称为解密(decryption),该过程使用的数学变换，通常是加密时数学变换的逆变换, 就是解密算法。加密与解密通常需要参数控制，我们把该参数称为密钥，有吋也 称为密码。加密时使用的为加密密码(加密密钥)，解密时使用的为解密密码(解密 密钥)。加密密钥与解密密钥可能相同也可能不同。相同时称为对称型或单钥 的，不相同时称为非对成型或双钥的。那么一个密码系统或称其为密码体制，是 由明文空间、密文空间、密钥空间、加密算法与解密算法五个部分组成。明文、 密文、密钥空间分别表示全体明文、全体密文、全体密

19、钥的集合；加密与解密算 法通常是一些公式、法则或程序，规定了明文与密文之间的数学变换规则。下面用字母分别表示这个概念，密钥k二vke,kd>, ke表示加密密钥，kd表 示解密密钥，设明文m,密文c,加密算法e,解密算法d。把明文加密为密文:c=e(m,ke)密文解密为明文：m=d(c,kd)=d(e(m,ke),kd)o上述的讲解可用下图攻击者目的：求明文与密明文空间密码分析明文明文空间明文传输的内容 * 明文空_k加密算法interner (不安全信道)+解密算法+ 间加密密钥密钥空间解密密钥图2-1加密过程与密码分析2.1公钥密码基本概念公钥密码与以前所有的密码方法都大相径庭:一是

20、以前的密码算法都基于代 换与置换操作，而公钥密码使用数学数进行变换；二是公钥密码体制使用非对 称的方式，使用两个密钥(加密密钥与解密密钥)，而传统密码算法仅仅使用一个 密钥。公钥密码体制的提出首先是为了解决利用传统密码体制进行密钥分发时遇 到的问题，数字签名也是其重要应用z-o 3从1976年起，学者们提出了许多种公钥加密方法，它们的安全性都是基于 复杂的数学难题。根据所基于的数学难题来分类，有以下三类系统目前被认为是 安全和有效的：(1) 基于大整数因子分解的:rsa和rabin-williamso(2) 基于离散对数问题的：dsa和eigamal(3) 基于椭圆曲线离散对数问题的：椭圆曲线

21、密码系统。公开密钥加密算法与对称密钥加密算法相比来说，安全性能更好，密钥管理、 分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对 称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。2.1.1公钥密码原理公开密钥密码常用的、成熟的公钥算法是rsao它与传统的对称密钥算法 有本质的区别，对称密钥算法常用的是des算法 加/解密时用的是同一个密钥。 而公钥算法利用的是非对称的密钥，即利用两个足够大的质数与被加密原文相乘 生产的积来加/解密。这两个质数无论是用哪一个与被加密的原文相乘(模乘)，即 对原文件加密，均可由另一个质数再相乘来进行解密。但是，若想用这个乘积来 求岀另

22、一个质数，就要进行对大数分解质因子，分解一个大数的质因子是十分困 难的，若选用的质数足够大，这种求解几乎是不可能的。公、密钥对的用法是，当发方向收方通信时发方用收方的公钥对原文进行加 密，收方收到发方的密文后，用自己的私钥进行解密，其中他人是无法解密的， 因为他人不拥有自己的私钥，这就是用公钥加密，私钥解密用于通信;而用私钥 加密文件公钥解密则是用于签名，即发方向收方签发文件吋，发方用自己的私钥 加密文件传送给收方，收方用发方的公钥进行解密。但是，在实际应用操作中发出的文件签名并非是对原文本身进行加密，而是 要对原文进行所谓的“哈希"(hash)运算，即对原文作数字摘要。该密码算法也

23、 称单向散列运算，其运算结果称为哈希值，或称数字摘要，也有人将其称为“数 字指纹”。哈希值有固定的长度，运算是不可逆的，不同的明文其哈希值是不同 的，而同样的明文其哈希值是相同并且是唯一的，原文的任何改动，其哈希值就 要发生变化。数字签名是用私钥对数字摘要进行加密，用公钥进行解密和验证公钥密码算法使用两个密钥，其中一个用于加密(加密密钥)，另外一个用于 解密(解密密钥)。公钥密码算法具有如下特征：加密密钥与解密密钥时木质上不 通的，也就是说如果仅仅知道密码算法和加密密钥，而要确定解密密钥，在计算 上是不可行的；大多数公钥密码算法的加密密钥与解密密钥具有互换的性质。如 rsa算法，密钥对屮的一个

24、用于加密，另一个用于解密。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)是容易的。如果当不知道参数i是，计算的f逆函数是难解的，但但知 道参数t时，计算f的逆函数是容易的，则称f是一个单向陷门函数，参数称为 陷门。

25、2.2对称加密体制对称加密算法，乂称私钥加密算法，就是加密密钥能够从解密密钥中推出来, 反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称算法的加密 和解密表示为：e 认 m) = c,dg = m(2-1)对称加密算法的典型代表有:des, aes, 3des, rc2, rc4, rcs, rc6, idea等。以des为代表的对称密钥加密算法的设计原则主要基于信息论的混乱 和扩散。混乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分 组间的统计规律，通常依靠多轮迭代来实现；扩散则应使密钥和明文的每一位影 响密文屮尽可能多的位数，这样可以防止逐段破译，并通过s盒的非线性

26、变换来 实现。实际上，所有的对称密钥加密算法都采用feistel网、s盒及多次迭代等思 想。对称加密有速度上的优点，用软件实现，对称密钥比非对称密钥快100-1000 倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安 全传输密钥。对称加密系统用键长来衡量加密强度，40比特的键长被认为比较 脆弱，128比特比较健壮。对称加密算法的缺点则是密钥分发困难，密钥管理难，无法实现数字签名。 对称加密算法的优点是保密强度高，加解密速度快，适合加密大量数据。攻击 者 如果对加密后的数据进行破译，唯一的办法就是对每个可能的密钥执行穷搜索。 而采用这种加密技术，即使使用最快的计算机执行这种

27、搜索，耗费的时间也是相 当的长。如果使用较大的密钥，破译将会更加的困难。3数字签名的基本概念和理论3.1数字签名概念数字签名是一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域 的技术实现，用于鉴别数字信息的方法。一套数字签名通常定义两种互补的运算, 一个用于签名，另一个用于验证。数字签字由公钥密码发展而來，它在网络安全, 包括身份认证、数据完整性、不可否认性以及匿名性等方面有着重要应用。特别 是在大型网络安全通信中的密钥分配、认证以及电子商务系统中都有重要的作 用，数字签名的安全性日益受到高度重视。数字签名是指用户用自己的私钥对原始数据的哈希摘要进行加密所得的数 据。信息接收方使用信息

28、发送方的公钥对附在原始信息后的数字签名进行解密后 获得哈希摘要，并通过与自己用收到的原始数据产生的哈希摘要对照，便可确信 原始数据信息是否被篡改。这样就保证了消息来源的真实性和数据传输的完整 性。3.2数字签名理论数字签名的实现通常采用非对称密码与对称密码体系。不同的是，非对称密 码体系的加密利解密过程分别通过两个不同的密钥来实现，其中一个密钥以公 开，称为公开密钥，简称公钥，另一个有用户自己秘密保管，称为保密密钥，简 称私钥。只有相应的公钥能够对用私钥加密的信息进行解密，反之亦然。以现在 的计算机运算能力，从一把密钥推算出另一把密钥是不大可能的。所以，数字签 名具有很大的安全性，这是它的一个

29、优点。数字签名的基本方式主要是：信息发送方首先通过运行散列函数生成一个欲 发送报文的信息摘要，然后用其私钥对这个信息摘要进行加密以形成发送方的数 列签名，这个数字签名将作为报文的附件和报文一起发送给报文的接收方。接收 方在收到信息后首先运行和发送相同的散列函数牛成接收报文的信息摘要，然后 再用发送方的公钥进行解密，产生原始报文的信息摘要，通过比较两个信息摘要 是否相同就可以确认发送方和报文的准确性。当然，上述过程只是对报文进行了 签名，对其传送的报文本身并未保密。为了同时实现数字签名和秘密通信，发送 者可以用接收方的公钥对发送的信息进行加密，这样，只有接收方才能通过自己 的私钥对报文进行接么，

30、其它人即使获得报文并知道发送者的身份，由于没有 接收方的密钥也无法理解报文。3.3数字签名过程为了实现网络环境下的身份鉴别、数据完整性认证和抗否认的功能，数字签 名应满足以下要求：(1) 签名者发出签名的消息后，就不能再否认自己所签发的消息；(2) 接收者能够确认或证实签名者的签名，但不能否认；(3) 任何人都不能伪造签名；(4) 第三方可以确认收发双方z间的消息传送，但不能伪造这一过程，这样, 当通信的双方关于签名的真伪发生争执时，可由第三方来解决双方的争执。对于一个典型的数字签名体系而言，它必须包含2个重要的组成部分：即签 名算法(signature algorithm)和验证算法(ver

31、ification algorithm)为了满足上述 4 点要求，数字签名体系必须满足2条基本假设：(1) 签名密钥是安全的，只有其拥有者才能使用。(2) 使用签名密钥是产生数字签名的唯一途径。3.3.1.发送方签名过程(1) 为保证签名的速度，a先将原文进行单向hash运算生成定长的消息 摘要a图31生产摘要(2) 利用自己的私钥加密消息摘要得到数字签名a,并将数字签名附在原 消息后面图3-2加密摘要（3）通讯时用户a将自己的名文一起通过网络送给通讯对方即用户b图3-3发送原文和摘要3.32接收方验证过程接收方b接收到发送方a的签名消息后，对a的签名消息进行验证的过程如下：（1）将消息中的原

32、消息与数字签名分离出来原文用户b分离数字签名图34分离明文和数字签名（2）使用a的公钥解密数字签名得到摘要图3-5得到摘更（3）利用与发送方a相同的散列函数重新计算原消息的摘要图3-6接受方计算摘要（4）比较解密后获得的消息摘要a与重新计算产生的消息摘要b,若相等则说明消息在传输过程中没有被篡改，否则消息不可靠。图3-7验证数字签名333数字签名过程图38数字签名流程图4数字签名常见的算法及其数字签名数字签名的方法有很多，现在主要应用的数字签名主要有：rsa, dsa以 及椭圆曲线数字签名。4.1 dsa数字签名算法.dsa是schnorr和elgamal签名算法的变种，被美nist作为dss

33、是一 种公开密钥算法，它不能用作加密，只能用作数字签名。dsa使用公开公钥， 为接受者验证数据的完整性和数据发送者的身份。它也用作于由第三方去确定签 名和所签收数据的真实性。信息交流中，接受方希望收到的信息未被篡改，还希 望收到的信息确实是自己认定的发送方所发，那么接受方和发送方就可以约定， 共同使用dsa来实现。4.1.1 dsa数字签名实现的三个步骤(1) 参数与密钥生成(2)签名的算法(3)签名的验证算法1 初始过程(1) 系统参数:大素数p,q且q为pl的因子，并满足2a511<p<2a1024, 2a159<q<2a160,以确保在zp中求解离散对数的困难性；

34、g u zp ,且满足g=h a(p-l)/q mod p,其中h是一整数，lvhvpl且 ha(p-l)/qmodp>l o p,q,g作为系统参数，供所有用户使用，在系统内公开。(2) 用户私钥:用户选取一个私钥x,lvxvq,保密。(3) 用户公钥:用户的公钥y,y = gax mod p,公开。2. 签名过程对待签消息m,设0<m<po名程如下：(1) 生成一随机整数k, k g zp* ;(2) 计算 r = (gak mod p) mod q;(3) 计算 s = ka-l*(h(m)+x：i：r) mod qo (r,s)为签名人对 m 的签名。3. 验证过程(

35、1) 首先检查r和s是否属于0,q,若不是，则(r,s)不是签名；(2) 计算 t= sa-lmod q , r,=(gah(m) t mod q (yar*t mod q )mod p) mod q ;(3) t较f=r是否成立?若成立，则(r,s)为合法签名，则(r,s)为签名人对m的签名4.1.2 dsa的安全性dsa的安全性主要依赖于整数有限域离散对数难题。其安全性与rsa相比 差不多，dsa的一个重要特点是两个素数公开，这样，当使用别人的p和q是, 即使不知道私钥，你也能确认他们是否是随机产生的，还是做了手脚的。rsa 算法是做不到的。素数p必须足够大，且pl至少包含一个大素数因子以

36、抵抗 pohlig&hellman算法的攻击。m般都应采用信息hash的值。dsa安全性主 要依赖于p和g,若选取不当则签名容易伪造，应保证g对于pl的大素数因子 不可约。dsa的一个主要特点是两个素数公开，这样，当使用别人的p和g,即 使不知道私钥，你也能确认他们是随机产生的。1914.2椭圆曲线代理签名体制4.2.1椭圆曲线数字签名ecdsa椭圆曲线签名算法ecdsa是基于椭圆曲线密码体制(ecc)的数字签名算 法。dsa是美国国家标准局制定的数字签名算法，他是建立在有限域乘法群上 的。对于有限域上的椭圆曲线密码系统，数字签名标准建议采用椭圆曲线数字签 名算法ecdsa,下面给岀该

37、算法的过程。假设一组椭圆曲线的参数组为(q, fr, a, b, g, n, h)。其屮q是域的阶, fr指示域中元素的表示方法，a, b是两个系数，g是基点，g的阶为n,余因 子h=#e(fq) / n,他是一个小的素数。1 ecdsa密钥对生成过程(1) 选择一个随机数d,d(l,n-l)o(2) 计算 q,q=d*g。(3) 那么公钥为q,私钥为整数d。2 ecdsa签名过程假设待签名的消息为，m；(1) 选择一个随机数k, ke(l, n-l)o(2) 计算 k*g=(xl,yl)o(3) 计算r=xl mod n；如果r=0,贝！)返回到步骤。(4) 计算s=ka-l(e+d*r)

38、mod n,如果s=o,贝!j返回到步骤。(5) 对消息的签名为(r, s),最后签名者把消息m利签名(r, s)发送给接收者。3 ecdsa密钥对验证过程获得发送者的公钥q开始验证：(1) 检查 r, s,要求 r, sw(l, n-l)o(2) 计算 e=shal(m)o(3) 计算 w=s-lmod no(4) 计算 ul=e*w mod n； u2=r*w mod no(5) 计算 x=ulg+u2qo(6) 如果x=o,表示签名无效；否则，x=(xl, yl),计算v=xl mod no(7) 如果vn,表示签名无效；否则表示签名有效。口4.2.2椭圆曲线数字签名的安全性ecdsa在

39、安全性方面的目标是能抵抗选择明文(密文)攻击。而攻击a的 攻击者的目标是在截获a的签名后，可以生成对任何消息的合法签名。尽管 ecdsa的理论模型很坚固，但是人们仍研究很多措施以提高ecdsa的安全性。 在ecdlp不可破解及哈希函数足够强的前提下，dsa和ecdsa的一些变形已 被证明可以抵抗现有的任何选择明文(密文)攻击。在椭圆曲线所在群是一般群 并口哈希函数能够抗碰撞攻击的前提下，ecdsa本身的安全性已经得到证明。ecdsa可能而临的攻击：1.对ecdlp的攻击。2.对哈希函数的攻击。3.其他攻击。ecdma的优点(1) 安全性能高(2)计算机量小和计算机速度快(3)存储空间占有量小(

40、4) 带宽要求低。5rsa算法及其数字签名5.1 rsa简述rsa加密体制是一种公开的密码体制。rsa公匙密码体制是又r.l.rivest, a.shamir和l.adelman于1978年提出的。由于rsa算法很完善，即可用于数据 加密，又可用于数字签名，安全性良好，易于实现和理解，所以已经成为一种应 用极广的公匙密码算法，目前，rsa在许多场合有广泛的应用。rsa公钥密码算法是迄今为止在理论上最为成熟、完善的公钥密 码体制。从提出到现在已经历了各种攻击的考验，逐渐为人们接受，普遍认为 是目前最优秀的公钥方案之一。它是第一个既能用于数据加密也能用于数字签名 和密钥分配与管理的算法。它易于理解

41、和操作，也很流行。因为它既可用于加 密,又可用于签名，并为用户的公开密钥签发公钥证书、发放证书、管理 证书等，提高了服务质量，所以，rsa公开密钥密码在当今的信息交换 过程中已得到广泛的应用和实践，rsa公钥密码体制在世界许多地方 已经成为事实上的标准。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。而且它特别符 合计算机网络环境。对于网上的大量用户，可以将加密密钥用电话簿的方式印出。 如果某用户想与另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用 它对所传送的信息加密发出即可。对方收到信息后,用仅为自己所知的解密密钥 将信息解密，了解明文的内容小由此可看出,rsa算法解决了大

42、量网络用户密钥 管理的难题,这是公钥密码系统相对于对称密码系统最突出的优点。rsa是一个基于数论的非对称密码体制，是一种分组密码体制，是一种基于 因子分解的指数函数作为单向陷门函数的公钥体制算法。它基础是数论的欧拉定 理，素数检测,它的安全性是基于大数分解，后者在数学上是一个困难问题。rsa的安全性基于复杂性理论中的计算安全性，依赖于大整数分解这一np 难题。可靠性与所用密钥的长度有很大关系，假如有人找到一种很快的分解因子 的算法，即从一个公钥中通过因数分解得到私钥，那么用rsa加密的信息 的可靠性肯定会极度下降。但由于其工作量巨大，按目前计算机的处理能力 是不可能实现的。实践证明，在当前的技

43、术和方法下，密钥不小于1 024 bit的rsa 算法仍然是安全的。这充分说明rsa系统具有良好的保密性能。因此，尽管先后出现了很多新的公钥体制算法，但rsa仍然在不同应用领域占 据了垂要的位置。随着计算机运算速度的提高以及因子分解算法的突破,rsa的 密钥长度将越来越大，其软硬件实现速度将成为制约其使用的重要因素。5.2 rsa加密的可行性虽然rsa加密运算的速度十分慢,但是在pc性能越来越好的今天，对于几千 字节的数据进行一次几百位密钥的rsa加密,所消耗的时间应该是可以接受的。 下面结合大数运算程序的调试，从理论上简单的分析消耗时间在一台普通配置 的pc机上对一个整数进行幕模运算，因为公

44、开密钥的e通常取的较小，所以指数 取一个小整数，比如c353,模一个70字节长的整数(140位十六进制,大数单元以线 性组方式实现，对应到rsa算法中，这相当于约560bit的n),调试一个函数测试，按 初等数论屮的知识对程序进行算法优化，最终在一台配置为amd athron2800+,外 频333mhz,物理内存512mb的pc上测试需要约45毫秒时间。如果按 种速度, 逐字节对1kb的数据进行同样的运算，所消耗的时间理论上为45毫秒的1024倍 即约45秒。个并不是非常,2l其实从一个简单的角度来说，既然rsa用于数字签名可行，那就完全可以用 于同样大小的普通文件于大的文件，如果分成与数字

45、签名同样大小的段(这 里假设数字签名较短，不分段一次计算加密完成),分开的各段逐一进行加密运算, 那所需要的时间也只是按文件大小线性的增长通常数字名几十字，加密 运算并不需要很长的等待，这就说明对于几百字节或一两k字节大小的文件来说, 如果进行rsa加密，并不会是非常漫长的工作。当然，如果文件更大,加密就显得十 分漫长了。比如按前面叙述的45毫秒大数运算程序推理，加密字节大小的文 件需要约1天的时间。所以，要在普通pc用几百位以上的长密钥rsa加密文件, 文件不能过大，一般可以接受的上限是几kb。如果要在短 内加密大文件，需 要缩短密钥长度以减小运算量，这将带来安全性隐患。5.3 rsa算法的

46、介绍rsa系统由以下几部分组成：(1) 随机选取的在素数p和q,还有n ,其屮n二p*q , p和q保密，n 公开。(2) 任取(d(n)= (p-1) *(q-1),其中(n)表示比n小的素数的个数,任取 2<=e<= (n),且(e, (n)=l,e为加密密钥，公开。(3) 计算d,使e*d=l(mod (n),称d为e对模(n)的逆,其中d为解密秘钥, 保密。在rsa系统中，设m为明文，且明文块的数值大于n,c为密文，则其加 密和解密算法如为：加密算法c=e(m)=mae(mod n)解密算法rrdyrcymod n)在rsa系统中(e,n)构成加密秘钥，即公钥，(d,n)构

47、成解密秘钥，即私钥。5.3.1 rsa中素数的选取在rsa中，因n=p*q,若p, q被知道，即能将n因子分解，则由®(n)= (p-1) *(q1)可以算出。由于e是公开密钥，且解密秘钥d关于e满足d*e=1 (mod(n)则d也不难求得，这样rsa系统便被完全攻破。rsa中的素数都是上面位的十进制数，怎样才能选择好的p和q,怎样才 能生成这样的数，并且判断它是否为素数，这是一个rsa系统关键的问题。针 对素数p和q的选择，1978年rivest等人在正式发表的rsa公开密钥的论文中， 就建议对素数p和q的选择应当满足：(1) p、q要足够在，在长度上应相差几位，且二者之差与p、q

48、位数相近;(2) p-1与q1的最大公约数gcd(p-1,q-1)就尽量小；(3) p1与q1均应至少含有一个大的素数因子。并把满足这些条件的素数称为安全素数。5.3.2 rsa用到的公式和定理(1) 数和互为素数任何大于1的整数a能被因式分解为如下唯一形式：a=plp2pl(pl,p2,pl 为素数)(2) 模运算 fa(modn) x b(mod n) modn = (a x b)(mod n) 如果(axb) = (axc) (mod n),a 与 n 互素，贝!) b=c(mod n)(3) 费马定理若p是素数，a与p互素，贝'j a a(p-l)=l mod p(4) 欧拉定

49、理欧拉函数"(n)表示不大于n且与n互素的正整数的个数。当n是素数，(i) (n)=n-lo n=p*q,p,q 均为素数时，则 4> (n)= (n) 4> (n)=(p-l)(q-l)0 对于互素的 a 和 n,有 aa (n)= 1 (mod n)5.3.3 rsa安全性的分析在公布rsa算法之后，在使用rsa密码体制和分析rsa算法发现了一系 列的算法本身脆弱性及其存在的问题。（1）rsa公钥密码体制在加密或解密中涉及大量的数值计算，其加密和解 密的运算吋间比较长，以致于实际使用rsa密码体制无法应用到软件产品，必 须用超大规模集成电路的硬件产品。（2）虽然提高n

50、位数会大大提高rsa密码体制的安全性，但其计算量呈指 数增长，以致使其实现的难度增大，实用性降低。（3）rsa公钥密码体制的算法完整性（指密钥控制加密或解密变换的唯一 性）和安全性（指密码算法除密钥本身外，不应该存在其它可破译密码体制的可 能性）沿有等进一步完善。（4）rsa算法面临着数学方法的进步和计算机技术飞跃发展带来的破译密 码能力日趋增强的严重挑战。rsa公开密钥密码算法在信息交换过程中使用比 较广泛，安全性比较高。以当前的计算机水平，如选择1024位长的密钥（相当 于300位十进制数字）就认为是无法攻破的。5.3.4 rsa的攻击rsa算法的安全性就是基于大整数的因子分解困难之上的，

51、到目前其还是安 全的，要分析rsa算法的安全性，我们从攻击rsa的角度来审视。总的来分， rsa算法攻击可以区分为三类：（1）蛮力攻击：它通过实验所用的可能私钥，来达到目的。（2）数字攻击：使用数学技巧，类似于分解n来达到目的。（3）吋间攻击：通过观察解密算法运行的时间来达到目的。其中抵抗蛮力攻击的方法，与其它加密系统是一致的，使用大的密钥空间，是穷 举无能无力，因此e和d的位数越长则越安全，但是加解密速度会越慢，所以e 和d位数的长度应与实际应用系统有综合的权衡。（1） rsa的选择密文攻击rsa在选择密文攻击面前很脆弱。所谓密码分析者并不知道解密的密钥， 但是给出任意的消息，密码分析者可以

52、将其加密，再解密。或者说，密码分析者 能获得解密服务。设攻击者为a,密文接受者为t,公钥对为（e,n），私钥为d,t 收到的密文为c, c对应的明文为m。现在a想知道m = cad mod n,但是他不想 分解n。于是t找了一个随机数r, r<nw他进行如下计算：x = rae mod n （对i用t的公钥加密，得到临时密文x） , y = （x * c） mod n （将临时密文x与密文c相乘）t = ra（-l）modno a利用了 rsa加密和解密过程 的特点，即：如果x = rae mod n,那么r = xad mod n现在a要做的是使t用d 对t签名：urtmmodn。a需

53、要获得u,然后计算m = （t * u） mod n计算结果是 这样推导的：t *u mod n = ra(-l) * yad mod n= ra(-l) * xad * cad mod n= cad mod n= m141(2) rsa的公共模数攻击若系统中共有一个模数，只是不同的人拥有不同的e利d,系统将是危险的。 最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那么该信 息无需私钥就可得到恢复。设p为信息明文，两个加密密钥为el和e2,公共模数是m贝山cl = p81 mod n c2 = pae2 mod n密码分析者知道n、el、e2、cl和c2,就能得到p。因 为el

54、和e2互质，故用euclidean算法能找到r和s,满足：r*el+s*e2= 1假 设 1为负数,需再用 euclidean 算法计算 c1a(-1),则(c1a(-1) )a(-r) * c2as = p mod n o5.3.5 rsa的缺点(1) rsa产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密(2) 安全性,rsa的安全性依赖于大数的因子分解，但并没有从理论上证明 破译rsa的难度与大数分解难度等价，而口密码学界多数人士倾向于因子分解 不是npc问题。目前，人们己能分解140多个十进制位的大素数，这就要求使 用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击rs

55、a的方法，如 选择密文攻击，一般攻击者是将某一信息作一下伪装(blind),让拥有私钥的实 体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同 一个弱点，即存在这样一个事实：乘幕保留了输入的乘法结构：xm )d = xd *md modn前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征-每 个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采 用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对 自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时 首先使用one-way hash function对文档作h

56、ash处理，或同时使用不同的签名 算法。除了利用公共模数，人们还尝试一些利用解密指数或4)(n)等等攻击.(3) 速度太慢，由于rsa的分组长度太大，为保证安全性，n至少也要600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级； 且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。0 前，set(secure electronic transaction)协议中要求ca采用2048比特长的密钥， 其他实体使用1024比特的密钥。为了速度问题,目前人们广泛使用单，公钥密码结 合使用的方法，优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件，然后用

57、rsa来给文件密钥加密，极好的解决了单钥密码的密钥分发问题。5.3.6 rsa的优点(1) 数学表达式简单。(2) rsa的安全性基于大数分解的困难性。(3) rsa公钥密码体制具有一些传统密码体制不能实现的一些功能，如认证, 鉴别和数字签名等,特别适合于现代密码通信。5.4 rsa数字签名541 rsa数字签名的过程首先产生密钥，过程如下：(1) 随机产生两个等长度为k/2位的素数p和q(2) 然后计算公钥publickey=p*q； (publickey是k位的长度)(3) 随机产生一个加密密钥 keye, 2<=keye<=0(n)-l 其gcd(keye,(n)=l; 注意这是保证解密密钥keye *keyd mod(n)=l有解的充要条件，(n)称为n 的欧拉函数，值为：®(n)=(p-l)*(q-l)(4) 求解解密密钥keyd=keye-l mod(n) ,keye-l为解密密钥keyd的逆元, 此公式原方程为(keye*keyd mod(n)=l)由此公钥，加密密钥，解密密钥全部产生。其次对明文加密或对密文进行 解密，过程如下；(1) 加密：c = mkeyae mod publickey；其屮m表示明文,c表