毕业设计论文基于椭圆曲线的数字签名研究与仿真.doc

《毕业设计论文基于椭圆曲线的数字签名研究与仿真.doc》由会员分享，可在线阅读，更多相关《毕业设计论文基于椭圆曲线的数字签名研究与仿真.doc（67页珍藏版）》请在三一办公上搜索。

1、（输入章及标题）毕业设计（论文） 基于椭圆曲线的数字签名研究与仿真学 院 年级专业 电子信息工程 学生姓名 指导教师 专业负责人 答辩日期 2007-6-24 III毕业设计（论文）任务书学院：里仁学院 系级教学单位：电子信息工程 学号学生姓名专 业班 级电信1班课题题 目基于椭圆曲线的数字签名研究与仿真来 源电子信息工程主要内容大量搜集、阅读有关数字签名技术的资料、专著，了解、掌握数字签名技术的发展趋势及现状。研究数字签名的产生、工作原理、各类典型算法的特点及其在保密通信领域的应用。 自学MATLAB仿真语言，并用MATLAB对某种典型的数字签名进行仿真，对其安全性能指标进行分析。基本要求

2、搜集、查阅资料，掌握数字签名的产生、工作原理、各类典型算法的特点及其在保密通信领域的应用。 自学MATLAB仿真语言的一种版本。用MATLAB仿真数字签名，分析安全性能指标。参考资料1、数字签名原理及技术.张先红 北京：机械工业出版社2、赖溪松等.计算机密码学及其应用.国防工业出版社3、张志涌.精通MATLAB6.5版.北京航空航天大学出版社周 次14周58周912周1316周1718周应完成的内容查阅资料读专著分析原理过程。确定仿真方案，自学语言，设计编程。编程，仿真分析。仿真调试。仿真写论文答辩。指导教师：田澈系级教单位审批： 摘要摘 要随着信息技术的不断发展和应用，信息的安全性变得越来越

3、重要，数字签名技术是当前网络安全领域的研究热点。自从N.Koblitz和Miller提出将椭圆曲线应用于密码算法以来，椭圆曲线密码体制己得到了很大的发展，己经成为密码学的重要研究热点之一。目前国内对于椭圆曲线公钥的快速实现、智能卡应用等研究较多。由于它本身的优点也特别适用于无线Modem、Web服务器、集成电路卡等方面，随着网上交易的频繁，这将成为今后研究的热点。然而，在现有的研究中它在进行大型安全交易的电子商务领域中研究比较有限。本文主要是对椭圆曲线密码体制的研究，并在此基础上实现了一种基于椭圆曲线的数字签名体制，主要完成了以下几个方面的工作:在查阅大量文献资料的基础上，分析了密码学领域里的

4、对称加密体制和非对称体制,并对二者进行了对比，指出了公钥加密体制的优点所在；深入分析ECDSA椭圆曲线数字签名算法的理论基础及算法原理，研究了随机生成有限域上的椭圆曲线方程算法；研究了基于椭圆曲线的数字签名方案，探讨了椭圆曲线密码算法的优点及其特别适用的领域；并简单了解了下椭圆曲线密码体制中的一些基本算法，如快速取模算法、快速模加算法、快速模逆算法等；同时设计了一种基于ECDSA算法的数字签名系统，分析了其系统架构，并对ECDSA数字签名进行了成功的仿真。关键词椭圆曲线密码体制；数字签名；仿真；ECDSA59AbstractAlong with the continuous developme

5、nt and application of Information Technology, the security of information has become Currently, there is much research on rapid realization and smart card application of elliptical curve public key. Because of its own advantages, it also can be applied to Wireless Modem, Web Services, and integrated

6、 circuit cards and so on. However, in Ongoing study, there search of mass security transactions in the area of e- business is so limited. With the online transactions become more frequent, this research filed will become hot spots in future.Access to a large number of literatures, the symmetric and

7、a symmetric encryption system has been analyzed in cryptography field structure. And a comparison that the public key encryption system has the advantage between them has been proposed. On this basis, commonly digital signatures algorithm systems have been advanced.In-depth analysis of ECDSA ellipti

8、cal curve digital signature algorithm theoretical basis and algorithm theory, a random on the limited jurisdiction of the elliptical curve equation algorithms has been generated, and its validity has been analyzed. On the basis of previous research, a system based on elliptical curve proxy signature

9、 and the signature threshold agent system has been proposed, and an analysis of their safety certification of its safety performance is reliable. Meanwhile this paper designed a digital signature system based on the ECDSA algorithms, an analysis of its system. And the digital signature system based

10、on the ECDSA has been successfully simulated.Keywords Elliptical Curve Encryption System digital signatures simulation ECDSA目录目 录摘 要IAbstractII第1章 绪论11.1 课题背景11.1.1 研究现状11.1.2数字签名技术选题依据和意义21.1.3论文结构与内容3第2章 密码学基本理论及基本概念52.1密码学基本概念52.2公钥加密体制62.2.1 公钥密码基本概念62.2.2 公钥密码原理72.2.3 利用公钥密码体制进行数字签名82.2.4公钥密码体制

11、的数学基础92.3对称加密体制92.4常用数字签名算法10第3章 椭圆曲线密码算法的研究113.1群（Groups）113.2有限域（Finite Field）133.3数据完整性与散列函数133.3.1 散列函数原理143.3.2 散列函数的一般结构143.4 SHA算法163.5椭圆曲线密码体制数学原理183.51 椭圆曲线的数学定义183.5.2 椭圆曲线上的离散对数问题193.5.3 有限域上安全椭圆曲线的选取19第4章 基于椭圆曲线数字签名的实现214.1 数字签名214.2 椭圆曲线代理签名体制224.2.1 主要参数的选择224.2.2 密钥的生成224.2.3 代理签名协议22

12、4.3 椭圆曲线数字签名的计算机实现244.3.1 椭圆曲线数字签名方案的建立244.3.2椭圆曲线数字签名算法254.3.3椭圆曲线验证算法254.3.4 椭圆曲线数字签名方案及仿真实现264.4 椭圆曲线加密体制的安全性分析27结 论29参考文献31附录1 开题报告33附录2文献综述37附录3 英文翻译41附录4 程序55致谢61第1章 绪论第1章 绪论1.1 课题背景当今社会是信息化社会，电子计算机和通信网络己经广泛的应用于社会的各个领域，以此为基础建立起来的各种信息系统，给人们的生活、工作带来了巨大变革。大型信息系统将众多的计算机和只能化设备连在一个四通八达的通信网络中，共享丰富的数据

13、库信息和计算机资源，储存大量的数据文件，完成异地之间的数据交换与通信。信息系统的应用，加速了社会自动化的进程，减轻了日常繁杂的重复劳动，同时也提高了生产率，创造了经济效益。信息安全技术在信息化迅速发展的今天己进入了高速发展的新时期，形成了密码技术、可信计算技术、电磁辐射泄露防护技术、系统入侵检测技术和计算机病毒检测消除技术等多个安全防护技术门类。数字签名又称之为数字签字、电子签名、电子签章等。其提出的初衷就是在网络环境中模拟日常生活中的手工签名或印章；而要使数字签名具有与传统手工签名一样的法律效力，又催生了数字签名法律的出现。数字签名具有许多传统签名所不具备的优点，如签名因消息而异，同一个人对

14、不同的消息其签名结果是不同的，原有文件的修改必然会反映为签名结果的改变，原文件与签名结果两者是一个混合不可分割的整体等。所以，数字签名比传统签名更具可靠性。1.1.1 研究现状目前，密码理论与技术主要包括两部分，即基于数学的密码理论与技术(其中包括公钥密码、分组密码、流密码、认证码、数字签名、Hash M数、身份识别、密钥管理、PKI技术等卿非数学的密码理论与技术(包括信息隐形、量子密码、基于生物特征的识别理论与技术)。实现数字签名有很多方法，目前数字签名采用较多的是公钥加密技，如基TRSA Data Security中的PKCS(Public Key Cryptography Standar

15、ds)，DSA (Digital Signature Algorithm), x.509, POP (Pretty Good Privacy)。1994年美国标准与技术协会公布了数字签名标准(DSS)而使公钥加密技术广泛应用。同时应用散列算法(Hash)也是实现数字签名的一种方法。而关于椭圆曲线数字签名的研究正处于开始状态，所以很多问题都没能有效解决。在个别领域，我国开始尝试采用新的椭圆曲线数字签名算法(包括192位椭圆曲线算法、224位椭圆曲线算法和256位椭圆曲线算法)。目前影响最大的三类公钥密码是RSA公钥密码、ElGamal公钥密码、椭圆曲线公钥密码。其中RSA公钥密码的安全性依赖于数

16、学中大整数因子分解问题的难度，而ElGamal公钥密码与椭圆曲线公钥密码分别基于一般有限域离散对数问题（DLP）和椭圆曲线离散对数问题（ECDLP）。在以上三类公钥系统中，椭圆曲线公钥系统最具有优势。因为：(1) 在有限域上的椭圆曲线很多，为我们用椭圆曲线构造密码系统提供了丰富的资源。(2) 椭圆曲线公钥密码系统中的主要计算量是计算Q=，且Q很容易求出1,而知道Q、，求十分困难。(3) 要获得同样安全强度，比RSA用的参数规模小得多2，开销较少且速度快。(4) 椭圆曲线离散对数问题（ECDLP）比有限域离散对数问题（DLP）困难得多。基于具有无可比拟的优势，椭圆曲线公钥密码系统被认为是新一代公

17、钥密码系统。无论在数据加密和数字签名上，椭圆曲线公钥密码系统已成为人们非常感兴趣的研究方向之一，从而在这方面涌出了很多有价值的成果。目前国内对于椭圆曲线公钥的快速实现、智能卡应用等研究较多。由于它本身的优点也特别适用于无线Modem, Web服务器、集成电路卡等方面。但是综合浏览后，发现关于在要进行大量安全交易的电子商务领域中研究比较有限。随着网上交易的频繁，这将成为今后研究的热点。1.1.2数字签名技术选题依据和意义信息时代虽然给我们带来了无限商机与方便，但同时也充斥着隐患与危险。由于网络很容易受到攻击，导致机密信息的泄漏，引起重大损失。由于信息技术已经成为综合国力的一个重要组成部分，因此信

18、息安全己成为保证国民经济信息化建设健康有序发展的保障。网络安全技术众多，目前在电子商务、电子政务、电子邮件系统、电子银行等方面必备的关键技术就是数字签名。数字签名又称为数字签字，电子签章等。“数字签名”用来保证信息传输过程中信息的完整和提供信息发送者的身份认证和不可抵赖性，数字签名技术的实现基础是公开密钥加密技术，是用某人的私钥加密的消息摘要用于确认消息的来源和内容。目前普遍采用的数字签名算法，都是基于下面三个数学难题的基础之：(1)难题1 整数的因式分解(Integer Factorization)问题，如RSA算法；(2)难题2 离散对数(Discrete Logarithm)问题，如El

19、Gamal , DSA , 等算法；(3)难题3 椭圆曲线(Elliptic Curve)问题，如ECDSA算法；而在众多算法中，椭圆曲线密码体制由于具有密钥长度短、数字签名快、计算数据量小、运算速度快、灵活性好等特点，已经广泛地被应用。由于ECC能实AIR高的安全性，只需要较小的开销和延迟，较小的开销体现在如计算量、存储量、带宽、软硬件实现的规模等;延迟体现在加密或签名认证的速度方面。所以ECC特别使用于计算能力和集成电路空间受限(如工C智能卡)、带宽受限(如高速计算机网络通信)等情况。1.1.3论文结构与内容本文在阅读了国内外大量的参考文献资料的基础上，进行了如下布局结构:首先对密码学技术

20、的发展现状及其发展趋势进行了分析和综述。其次，介绍了密码学的基本理论及基本概念，并详细介绍了公钥密码算法，给出了一些典型的公钥加密体制的简要分析。第三，探讨了椭圆曲线密码算法的基本概念及理论基础，包括群和域、散列函数及SHA算法、椭圆曲线的基本概念、有限域椭圆曲线的运算等，同时分析了有限域上安全椭圆曲线的生成。第四，研究了基于ECDSA数字签名算法，并对其安全性作了分析，简要介绍了椭圆曲线密码算法的优点及适用的领域。最后，深入探讨了基于椭圆曲线的数字签名体制，同时设计了一种基于ECDSA算法的数字签名系统，分析了其系统架构，并对ECDSA数字签名进行了成功的仿真。第2章 密码学基础理论及基本概

21、念第2章 密码学基本理论及基本概念密码学是网络信息安全的基础，公钥密码体制是密码学的只要组成部分，数字签名的基础就是公钥密码体制。网络信息安全是密码学的重要应用领域，公钥密码体制的主要应用之一就是数字签名。2.1密码学基本概念1949年，Shannon发表了著名论文保密系统的通信理论，把古老的密码学置于坚实的数学基础之上。1977年，美国联邦政府正式颁布了数据加密标准(DES)，这是密码学历史上的一个创举，由此，过去神秘的密码学逐步走向公开的学识殿堂。1976年，Whitfield Dife与Martin Hellman的开创性论文密码学新方向，首次提出了公钥密码的概念，建立了公钥密码体制基础

22、。密码学包括两个方面：密码编码学和密码分析学。密码编码学就是研究对数据进行变换的原理、手段和方法的技术和科学。密码分析学是为了取得秘密的消息，而对密码系统及其流动数据进行分析，是对密码原理、手段和方法进行分析、攻击的技术和科学。密码学的理论基础是数学，其基本思想是隐藏、伪装信息，使未经授权者不能得到消息的真正含义。伪装(变换)之前的信息是原始信息，成为明文(plaintext)； 伪装之后的消息，看起来是一串无意义的乱码，称为密文(cipher text)。把明文伪装成密文的过程称为(encryption)，该过程使用的数学变换就是加密算法。把密文还原成明文的过程称为解密(decryption

23、)，该过程使用的数学变换，通常是加密时数学变换的逆变换，就是解密算法。加密与解密通常需要参数控制，我们把该参数称为密钥，有时也称为密码。加密时使用的为加密密码(加密密钥)，解密时使用的为解密密码(解密密钥)。加密密钥与解密密钥可能相同也可能不同。相同时称为对称型或单钥的，不相同时称为非对成型或双钥的。那么一个密码系统或称其为密码体制，是由明文空间、密文空间、密第2章 密码学基本理论及基本概念钥空间、加密算法与解密算法五个部分组成。明文、密文、密钥空间分别表示全体明文、全体密文、全体密钥的集合；加密与解密算法通常是一些公式、法则或程序，规定了明文与密文之间的数学变换规则。下面用字母分别表示这个概

24、念，密钥K=，Ke表示加密密钥，Kd表示解密密钥，设明文M，密文c，加密算法E，解密算法D。把明文加密为密文: C=E(M,Ke)把密文解密为明文：M=D(C,Kd)=D(E(M,Ke),Kd)上述的讲解可用图2-1表示加密算法解密算法Interner（不安全信道）传输的内容密码分析攻击者目的：求明文与密码明文明文空间明文明文空间明文明文空间加密密钥密钥空间解密密钥（用安全信道传输密钥）图2-1 加密过程与密码分析2.2公钥加密体制2.2.1 公钥密码基本概念公钥密码概念是由Whitfield Diffie和MartinH ellma于1976年提出的，它是密码学历史上的一个重大成就。公钥密码

25、与以前所有的密码方法都大相径庭:一是以前的密码算法都基于代换与置换操作，而公钥密码使用数学函第2章 密码学基本理论及基本概念数进行变换；二是公钥密码体制使用非对称的方式，使用两个密钥(加密密钥与解密密钥)，而传统密码算法仅仅使用一个密钥。公钥密码体制的提出首先是为了解决利用传统密码体制进行密钥分发时遇到的问题，数字签名也是其重要应用之一。从1976年起，学者们提出了许多种公钥加密方法，它们的安全性都是基于复杂的数学难题。根据所基于的数学难题来分类，有以下三类系统目前被认为是安全和有效的：(1) 基于大整数因子分解的：RSA和Rabin-Williams。(2) 基于离散对数问题的：DSA和EI

26、Gamal。(3) 基 于椭圆曲线离散对数问题的：椭圆曲线密码系统。公开密钥加密算法与对称密钥加密算法相比来说，安全性能更好，密钥管理、分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相对于对称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。2.2.2 公钥密码原理公开密钥密码理论是1976年美国发表的RSAl41算法，它是以三个发明人的名字命名的，后来又有椭圆算法ECC，但常用的、成熟的公钥算法是RSA。它与传统的对称密钥算法有本质的区别，对称密钥算法常用的是DES算法，加/解密时用的是同一个密钥。而公钥算法利用的是非对称的密钥，即利用两个足够大的质数与被加密原文相乘生产

27、的积来加/解密。这两个质数无论是用哪一个与被加密的原文相乘(模乘)，即对原文件加密，均可由另一个质数再相乘来进行解密。但是，若想用这个乘积来求出另一个质数，就要进行对大数分解质因子，分解一个大数的质因子是十分困难的，若选用的质数足够大，这种求解几乎是不可能的。因此，将这两个质数称密钥对，其中一个采用私密的安全介质保密存储起来，应不对任何外人泄露，简称为“私钥”；一个密钥可以公开发表，用数字证书的方式发布在称之为“上黄页”的目录服务器上，用LDAP协议进行查询，也可在网上请对方发送信息时主动将该公钥证书传送给对方，这个密钥称之为“私钥”。公、密钥对的用法是，当发方向收方通信时发方用收方的公钥对原

28、文进行加密，收方收到发方的密文后，用自己的私钥进行解密，其中他人是无法解密的，因为他人不拥有自己的私钥，这就是用公钥加密，私钥解密用于通信;而用私钥加密文件公钥解密则是用于签名，即发方向收方签发文件时，发方用自己的私钥加密文件传送给收方，收方用发方的公钥进行解密。但是，在实际应用操作中发出的文件签名并非是对原文本身进行加密，而是要对原文进行所谓的“哈希”(Hash)运算，即对原文作数字摘要。该密码算法也称单向散列运算，其运算结果称为哈希值，或称数字摘要，也有人将其称为“数字指纹”。哈希值有固定的长度，运算是不可逆的，不同的明文其哈希值是不同的，而同样的明文其哈希值是相同并且是唯一的，原文的任何

29、改动，其哈希值就要发生变化。数字签名是用私钥对数字摘要进行加密，用公钥进行解密和验证。公钥证书和私钥是用加密文件存放在证书介质中，证书是由认证服务机构CA所签发的权威电子文档，CA与数字证书等是公钥基础设施PKI的主要组成机构和元素。公钥密码算法使用两个密钥，其中一个用于加密(加密密钥)，另外一个用于解密(解密密钥)。公钥密码算法具有如下特征：加密密钥与解密密钥时本质上不通的，也就是说如果仅仅知道密码算法和加密密钥，而要确定解密密钥，在计算上是不可行的；大多数公钥密码算法的加密密钥与解密密钥具有互换的性质。如RSA算法，密钥对中的一个用于加密，另一个用于解密。2.2.3 利用公钥密码体制进行数

30、字签名下面举例简单介绍用户i把消息x签名，然后传送给用户j的过程。用户i首先产生签名；然后把(,)送给用户j即可。用户j接受到(,)后，验证是否为用户i的签名：首先计；然后通过比较，r=x表示是用户i数字签名，否则不是。因为，所以可以通过比较r与x来判断签名的有效性。因为是保密的，所以除了用户i之外，他人不能产生x对应的正确的第2章 密码学基本理论及基本概念；也就是说，他人不能假冒用户i进行数字签名。2.2.4公钥密码体制的数学基础通观公钥密码算法，它们的数学基础是比较狭窄的。大多数公钥密码算法都是基于以下三种数学难题之一的：一是背包问题：给定一个互不相同的数组成的集合，要找出一个子集，其和为

31、N。二是离散对数问题：如果P是素数，9和M是整数，找出x，使得；还有一种方法，就是基于椭圆曲线的离散对数问题。三是因数分解问题：设N是两个素数的乘积，则：（1） 分解N；（2） 给定整数M（明文）和C（密文），寻找d满足；（3） 给定整数e和C，寻找M满足；（4） 给定整数x，判定是否存在整数y满足；2.3对称加密体制对称加密算法，又称私钥加密算法，就是加密密钥能够从解密密钥中推出来，反过来也成立，在大多数对称算法中，加密解密密钥是相同的。对称算法的加密和解密表示为: （2-1）对称加密算法的典型代表有:DES，AES，3DES，RC2，RC4，RCS，RC6，IDEA等。以DES为代表的对称

32、密钥加密算法的设计原则主要基于信息论的混乱和扩散。混乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分组间的统计规律，通常依靠多轮迭代来实现；扩散则应使密钥和明文的每一位影响密文中尽可能多的位数，这样可以防止逐段破译，并通过S盒的非线性变换来实现。实际上，所有的对称密钥加密算法都采用Feistel网、S盒及多次迭代等思想。对称加密有速度上的优点，用软件实现，对称密钥比非对称密钥快100-1000倍。然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法安全传输密钥。对称加密系统用键长来衡量加密强度，40比特的键长被认为比较脆弱，128比特比较健壮。对称加密算法的缺点则是密钥

33、分发困难，密钥管理难，无法实现数字签名。2.4常用数字签名算法早在1979年，GJ.Simmons就将数字签名讨论应用于美苏两国的禁止核试验条约的验证工作中。在1991年，美国NIST公布了其数字签名标准，DSS(Digital Signature Standard)，于1994年正式采用为美国联邦信息处理标准；DSS标准中采用的签名算法称为DSA。随后其他一些国家也颁布了自己的数字签名标准，如俄罗斯1994年颁布的GOST R34.10-94标准等。较早出现的数字签名算法，如1978年前后提出的RSA，Rabin等数字签名算法，至今还在使用。第3章 椭圆曲线密码算法的研究第3章 椭圆曲线密码

34、算法的研究3.1群（Groups）抽象代数不但是数学的一个重要分之，同时在其他学科如量子力学、结晶学、原子物理学等中都己经称为研究者的有力武器；群论因为是研究对称性问题的基础，例如其在物理学中在诸如时间和空间的对称性研究、乃至超对称性问题等研究中都有应用。在密码学中，抽象代数也己经扮演重要角色，如在椭圆曲线密码体制中，群以及域上的多项式理论等都是其理论基础。设有一个由任意元素a，b，c.组成的非空集合G，即。在G上有一个针对其中元素进行组合操作的二元运算规则*，同时满足下列四个条件，则G对于运算*称为群，并称二元运算*为群的运算。(1) 封闭性 对于任意，有。(2) 结合律成立 对于任意，有(

35、ab)c=a(bc)。(3) 有单位元e 对任意，有，使得ae=ea=a。(4) 存在逆元 对任意，有,使；称互为逆元。上述四个条件是构成群的充分必要条件，通常被称为群的公理。若仅满足条件(1)和(2)，则被称为半群(Semigroup)；满足条件(1)，(2)和(3)者，称么半群(Monoid)、弱群或类群。若群G对运算还满足交换律，即对于任意的，都有=成立，则称群G为交换群或阿贝尔群(Abel Groups)。此时，通常用符号“+”来代替“”称群运算“+”为“加法”，称a+b为a与b的和，称单位元素。为零元素O，称逆元素为元素a的负元素，并一记作-a。相应的，称群运算“”为“乘法”，称ab

36、为a与b的积，简写为ab。第3章 椭圆曲线密码算法的研究例如：全体整数的集合在通常的加法运算下构成一个阿贝尔交换群。设n为任意正整数，对于任意的，定义：则对于任意整数m，有。定义表示所有的的集合，则也构成一个有限群。特别的，若G中一个元素a，得=G成立，则称G为循环群。显然，循环群G都是阿贝尔群。例如：由集合1，-1对于乘法运算所构成的群就是二阶循环群。设n为任意正整数，对于任意的，称满足的最小正整数n为群元a的阶数。显然，对于有限群G而言，其每一群元的阶都是有限正整数。例如：在由集合1，-1对于乘法运算所构成的群中，群元一1的阶数为2。自19世纪中叶由拉格朗日、阿贝尔、伽罗瓦等人引入群的概念

37、以来，经过一百多年的发展，群论己经成为现代代数学的重要分支，其内容非常丰富。下面介绍一些与椭圆曲线密码学有关的群的重要性质：（1）广义结合律：对群中的任意n个元素g1，g2，g3，.gn，其积g1g2.gn唯一确定。由自然归纳法和结合律很容易得到此结论。（2）单位元e都是唯一的。用反证法。若e1和e2都是群G的单位元，则根据群的公有：。（3）存在，若ab=ac，则b=c；若ab=cb，则a=c。先证明第一条。若ab=ac，用互乘等式两端得:根据结合律，可知 ,所以，b=c（4）每一元素的逆元是唯一的。用反证法。若不然，设群元G存在两个逆元，则依据群的公理，有ab=ac=e由上述的性质(3)可知

38、b=c，所以群元的逆元唯一。3.2有限域（Finite Field）只含有有限多个元素的域叫有限域。由于它首先由E.伽罗瓦所发现，因而又被称为伽罗瓦域(Galois Field)。在同构意义下，对任一素数P和正整数n，存在且仅存在一个含厂个元素的有限域，记作。有限域的特征为P，其阶为域中元素的个数，即。另一方面，对q1整数而言，q阶有限域GF(q)存在的充要条件是q是某一素数的整次幂(以下简称素数幂)。设有限域GF(q)上的多项式为： ,用表示系数取自域GF(p)的一切多项式的集合。中的任何多项式不一定有乘法逆元，所以只能组成一个有单位元的无零因子环，这与整数环Z完全相似。与Z环上的素数相对应

39、，在域上有既约多项式。设f(x)是次数大于0的多项式，若除了常数、常数与本身的乘积以外，不能再被域GF(p)上的其他多项式除尽，则称f(x)为域GF(p)上的既约多项式。所以，一个常数总是多项式的因子，f(x)是否既约与讨论的域有很大关系。3.3数据完整性与散列函数散列(Hash)函数，又称为哈希函数、杂凑函数。其运算结果就像数字式的指纹，即用一小段数据来识别大的数据对象。散列函数是密码学，也是认证理论研究的主要内容之一。数据完整性服务确保：接收到的信息如同发送的消息一样，其在传输过程中没有被攻击或者插入、篡改、重排等。破坏数据完整性是一种主动攻击；而加密可以保护信息的机密性，是为了抵御被动攻

40、击。散列函数是目前保护数据完整性的主要技术手段。常见的散列函数攻击方法有：生日攻击、中途相遇攻击和穷举攻击等。一个安全的散列函数应该对这些已知的攻击法有很好的抗攻击性。3.3.1 散列函数原理散列函数H(M)，就是把任意长度的消息M，通过函数H，将其变换为一个固定长度的散列值h: h=H(M)。消息M的散列值h，就像该消息的数字指纹，可以用来保证数据的完整性，我们在前面称其为数据摘要。散列函数是公开的，一般不涉及保密密钥。少量有密钥的散列函数，可以作为计算消息的认证码等其他用途，因其有密钥而具有一定的身份鉴别功能。目前我们指的散列函数都是单向散列函数h=H(M)，即函数H是单向函数。它有弱单向

41、散列函数和强单向散列函数之分。单向散列函数是建立在压缩函数(compression function)的想法之上的：给一个输入n位长消息，得到一个较短的散列值。单向散列函数的性质：（1）函数H适用于任何大小的数据分组；（2）函数H产生一定长度输出；（3）对于任何数据M，计算H(M)是容易实现的；（4）对于任何给定的散列值h，要计算出M使H(M)=h，这在计算上是不可行的；（5）对于任意给定的数据x，要计算出另外一个数据Y，使H(x)=H(y),这在计算上是不可行的；（6）要寻找任何一对数据(x，y)，使H(x)=H(y)，这在计算上也是不可行的；其中前面3个性质是散列函数应用于报文(数据)鉴别

42、的基本要求；性质4是单向函数性质；性质5也可称其为弱抗冲突(weak collision resistance)，就是在给定x之后，考察与本特定的x相冲突的情况:性质6也可称其为强抗冲突(strong collision resistance)，是考察任意两个元素x，y相冲突的情况。3.3.2 散列函数的一般结构散列函数是建立在压缩函数的基础之上的，它通过对消息分组的反复迭代压缩，生成一个长度固定的散列值。一般在迭代的最后一个分组中，还包含有消息的长度，从而在散列值中引入消息长度的影响。下面介绍的散列函数结构是Merkie提出的，如图3-1所示。本结构符合大多数散列函数的结构，如MD5，SHA

43、-1，RIPEMD-160等。它接受一个消息，并把消息分为L个分组，每个分组长度为b比特。如果最后一个分组长度不足b比特，可以强制将其填充为长b比特；并且包含消息a的总长度值，从上面讲述可知，添加消息的总长度值，可以提高散列函数的安全强度。由图3-1可知，散列函数重复使用相同的压缩函数f重复处理分组。f有两个输入:一个是前一步的n比特输出，称为链接变量；另一个是b比特的分组数据Y。在算法开始时，链接变量是一个初始化向量IV。最后的链接变量就是散列值。一般情况是bn,所以称f为压缩函数。（注释） bnnfbnfbnnf图3-1 散列函数总体结构可以把散列函数总结如下： （3-1）其中散列函数的输

44、出是如果压缩函数是抗冲突的，那么迭代函数的合成值也是抗冲突的，也就是说散列函数也是抗冲突的。所以设计安全的散列函数的关键就是设计安全的、抗冲突的压缩函数。散列函数的密码分析的着重点在于压缩函数f的内部结构，并基于这种尝试来寻找对f单次运行后就能产生冲突的高效技术。总的说来，任何散列函数必定存在冲突，因为将长度至少等于分组长度b的数据映射为长度n的散列值，其中bn，所以冲突是肯定存在的。而需要做的是要把寻找冲突在计算上变为不可能。3.4 SHA算法安全散列算法(SHA：Secure Hash Algorithm)是美国NIST和NSA共同设计的一个标准，用于作为数字签名标准(DSS)的散列函数，

45、产生数据摘要。当然也可以用到其他需要散列函数的场合。该算法于1993年公布为联邦信息处理标准FIPS PUB 180;于1995年又颁布了一个修订版FIPS PUB 180-1，常记作SHA-1。SHA的要求是消息长度小于bit,输出的散列值长度为160bit，分组长度是512bit。该算法是基于MIT的Ronald.L .Rivest教授设计的MD4算法原理，并模仿了该算法。下面介绍一下该算法的主要步骤。(1)附加填充比特 对于末尾分组，要求其是512bit长度，并且包含64bit的消息长度值。所以要求填充，填充比特串为100.0，即填充的最高位为I，后续各位是0。填充串的长度满足:末尾分组

46、剩余的剩余比特长度+填充串比特长度=512-64=448，也就是在分组的最后，预留了64bit填写消息长度。此外，如果消息的最后分组刚好512bit，此时由于需要加入64bit的消息长度，所以还是要再新增加一个分组，前面填充100.0共448bit；如果消息最后分组数据长度大于448bit，此时用100.0填满512bit，再新增加一个分组；在新分组前面填充000.0共448bit，最后填写消息长度。(2)附加长度值 由上面一步知道，末尾分组在最后64bit还没有填写，它就是用来填写消息长度的，所以要求消息长度小于比特。填写的64bit长度被看作无符号整数，高字节优先。(3)设置初始化向量 压缩函数f产生160bit的结果，可以用五个32bit的缓存寄存器A,B,C,D,E来保存这些中间结果和最终结果。初始化向量IV也装入这五个机器存，它们的值是:A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476，E=