基于椭圆曲线的数字签名研究与仿真毕业设计论文(编辑修改稿)

基于椭圆曲线的数字签名研究与仿真毕业设计论文(编辑修改稿)内容摘要：

；加密与解密算法通常是一些公式、法则或 程序，规定了明文与密文之间的数学变换规则。 下面用字母分别表示这个概念，密钥 K=Ke,Kd， Ke表示加密密钥，Kd表示解密密钥，设明文 M，密文 c，加密算法 E，解密算法 D。 把明文加密为密文 : C=E(M,Ke) 把密文解密为明文： M=D(C,Kd)=D(E(M,Ke),Kd) 上述的讲解可用图 21表示 （用安全信道传输密钥） 图 21 加密过程与密码分析 公钥加密体制 公钥密码基本概念 公钥密码概念是由 Whitfield Diffie和 MartinH ellma于 1976年提出的，它是 密码学历史上的一个重大成就。 公钥密码与以前所有的密码方法都大相径庭 :一是以前的密码算法都基于代换与置换操作，而公钥密码使用数学函加密密钥 密钥空间 解密密钥 明文 明文空间 明文 明文空间 明文 明文空间 加密算法 解密算法 Interner（不安全信道） 传输的内容 密码分析 攻击者 目的：求明文与密码 第 2 章 密码学基本理论及基本概念 7 数进行变 换；二是公钥密码体制使用非对称的方式，使用两个密钥 (加密密钥与解密密钥 )，而传统密码算法仅仅使用一个密钥。 公钥密码体制的提出首先是为了解决利用传统密码体制进行密钥分发时遇 到的问题，数字签名也是其重要应用之一。 从 1976年起，学者们提出了许多种公钥加密方法，它们的安全性都是基于 复杂的数学难题。 根据所基于的数学难题来分类，有以下三类系统目前被认为 是安全和有效的： (1) 基 于大整数因子分解的： RSA和 RabinWilliams。 (2) 基于离散对数问题的： DSA和 EIGamal。 (3) 基 于椭圆曲线离散对数问题的：椭圆曲线密码系统。 公开密钥加密算法与对称密钥加密算法相比来说，安全性能更好，密钥管 理、分配都容易实现，其中有些加密算法还能应用在数字签名上，但是它们相 对于对称密钥加密算法运行速度要慢得多，所以不能加密大量的数据。 公钥密码原理 公开密钥密码理论是 1976年美国发表的 RSAl41算法，它是以三个发明人的 名字命名的，后来又有椭圆算法 ECC，但常用的 、成熟的公钥算法是RSA。 它 与传统的对称密钥算法有本质的区别，对称密钥算法常用的是 DES算法，加 /解密时用的是同一个密钥。 而公钥算法利用的是非对称的密钥，即利用两个足够大的质数与被加密原文相乘生产的积来加 /解密。 这两个质数无论是用哪一个 与被加密的原文相乘 (模乘 )，即对原文件加密，均可由另一个质数再相乘来进行解密。 但是，若想用这个乘积来求出另一个质数，就要进行对大数分解质因 子，分解一个大数的质因子是十分困难的，若选用的质数足够大，这种求解几 乎是不可能的。 因此，将这两个质数称密钥对，其中一个采用私密的安全介质 保 密存储起来，应不对任何外人泄露，简称为“私钥”；一个密钥可以公开发表，用数字证书的方式发布在称之为“上黄页”的目录服务器上，用 LDAP协 议进行查询，也可在网上请对方发送信息时主动将该公钥证书传送给对方，这 个密钥称之为“私钥”。 公、密钥对的用法是，当发方向收方通信时发方用收方的公钥对原文进 行加密，收方收到发方的密文后，用自己的私钥进行解密，其中他人是燕山大学本科生毕业设计（论文） 8 无法解 密的，因为他人不拥有自己的私钥，这就是用公钥加密，私钥解密用于通信。 而用私钥加密文件公钥解密则是用于签名，即发方向收方签发文件时，发方用自己的私钥加密文件 传送给收方，收方用发方的公钥进行解密。 但是，在实际应用操作中发出的文件签名并非是对原文本身进行加密，而 是要对原文进行所谓的“哈希” (Hash)运算，即对原文作数字摘要。 该密码算 法也称单向散列运算，其运算结果称为哈希值，或称数字摘要，也有人将其称 为“数字指纹”。 哈希值有固定的长度，运算是不可逆的，不同的明文其哈希值 是不同的，而同样的明文其哈希值是相同并且是唯一的，原文的任何改动，其 哈希值就要发生变化。 数字签名是用私钥对数字摘要进行加密，用公钥进行解 密和验证。 公钥证书和私钥是用加密文件存放在证书介质中，证书 是由认证服务机构 CA所签发的权威电子文档， CA与数字证书等是公钥基础设施 PKI的主要组成 机构和元素。 公钥密码算法使用两个密钥，其中一个用于加密 (加密密钥 )，另外一个用 于解密 (解密密钥 )。 公钥密码算法具有如下特征： 加密密钥与解密密钥时本质上不通的，也就是说如果仅仅知道密码算法和加密密钥，而要确定解密密钥，在计算上是不可行的；大多数公钥密码算法的加密密钥与解密密钥具有互换的性质。 如 RSA算法，密钥对中的一个用于加密，另一个用于解密。 利用公钥密码体制进行数字签名 下面举例简单介绍用户 i把消息 x签名 ，然后传送给用户 j的过程。 用户 i首先产生签名 )( xDx i ；然后把 (x ,x )送给用户 j即可。 用户 j接受到 (x , x )后，验证是否为用户 i的签名：首先计 )(xEr i ；然 后通过比较， r=x 表示是用户 i数 字 签 名 ， 否 则 不 是。 因 为xxDExE iii  ))(()( ， 所以可以通过比较 r与 x来判断签名的有效性。 因为 iD 是保密的，所以除了用户 i之外，他人不能产生 x对应的正确的第 2 章 密码学基本理论及基本概念 9 x ； 也就是说，他人不能假冒用户 i进行数字签名。 公钥密码体制的数学基础 通观公钥密码算法，它们的数学基础是比较狭窄的。 大多数公钥密码算法 都是基于以下三种数学难题之一的： 一是背包问题：给定一个互不相同的数组成的集合，要找出一个子集，其 和为 N。 二是离散对数问题：如果 P是素数， 9和 M是整数，找出 x，使得)(modpMgx  ；还有一种方法，就是基于椭圆曲线的离散对数问题。 三是因数分解问题：设 N是两个素数的乘积，则： （ 1） 分解 N； （ 2） 给定整数 M（明文）和 C（密文），寻找 d满足 )(mod NCM d  ； （ 3） 给定整数 e和 C，寻找 M满足 )(mod NCM e  ； （ 4） 给定整数 x，判定是否存在整数 y 满足 )(mod2 Nyx  ； 对称加密体制 对称加密算法，又称私钥加密算法，就是加密密钥能够从解密密钥中推出来，反过来也成立，在大多数对称算法中，加密解密密钥是相同的。 对称算法 的加密和解密表示为 : MCDCME kk  )(,)( （ 21） 对称加密算法的典型代表有 :DES， AES， 3DES， RC2， RC4， RCS，RC6， IDEA等。 以 DES为代表的对称密钥加密算法的设计原则主要基于信息论的混乱和扩散。 混乱指的是密钥和明文及密文之间的依赖关系应该尽量复杂，以破坏分组间的 统计规律，通常依靠多轮迭代来实现；扩散则应使密钥和明文的每一位影响密文中尽可能多的位数， 这样可以防止逐段破译，并通过 S盒的非线性变换来实现。 实际上，所有的对称密钥加密算法都采用 Feistel网、 S盒及多次迭代等思 想。 燕山大学本科生毕业设计（论文） 10 对称加密有速度上的优点，用软件实现，对称密钥比非对称密钥快1001000倍。 然而，如果一个消息想以密文的形式传到接收者，我们应该找到一个方法 安全传输密钥。 对称加密系统用键长来衡量加密强度， 40比特的键长被认为比 较脆弱， 128比特比较健壮。 对称加密算法的缺点则是密钥分发困难，密钥管理难，无法实现数字签名。 常用数字签名算法 早在 1979年， 讨论应用于美苏两国的禁止核试 验条约的验证工作中。 在 1991年，美国 NIST公布了其数字签名标准，DSS(Digital Signature Standard)，于 1994年正式采用为美国联邦信息处理标准； DSS标准中采用的签名算法称为 DSA。 随后其他一些国家也颁布了自己的数字 签名标准，如俄罗斯 1994年颁布的 GOST。 较早出现的数字签名算法，如 1978年前后提出的 RSA， Rabin等数字签名算法，至今还在使用。 第 3 章 椭圆曲线密码算法的研究 11 第 3 章 椭圆曲线密码算法的研究 群（ Groups） 抽象代数 ]11,10,9[ 不但是数学的一个重要分之，同时在其他学科如量子力学、结晶学、原子物理学等中都己经称为研究者的有力武器；群论因为是研究对称性问题的基础，例如其在物理学中在诸如时间和空间的对称性研究、乃至超对称性问题等研究中都有应用。 在密码学中，抽象代数也己经扮演重要角色，如在椭圆曲线密码体制中，群以及域上的多项式理论等都是其理论基础。 设有一个由任意元素 a， b， c...组成的非空集合 G，即 }{ igG。 在 G上有一 个针对其中元素进行组合操作的二元运算规则 *，同时满足 下列四个条件，则 G对于运算 *称为群，并称二元运算 *为群的运算。 (1) 封闭性 对于任意 Gba 、 ，有 Gab。 (2) 结合律成立 对于任意 Gcba , ，有 (ab)c=a(bc)。 (3) 有单位元 e 对任意 Ga ，有 Ge ，使得 ae=ea=a。 (4) 存在逆元 对任意 Ga ，有 Ga 1 ,使 eaaaa   ** 11 ；称aa,1 互为逆元。 上述四个条件是构成群的充分必要条件，通常被称为群的公理。 若仅满足 条件 (1)和 (2)，则被称为半群 (Semigroup)；满足条件 (1)， (2)和 (3)者，称 么半群 (Monoid)、弱群或类群。 若群 G对运算还满足交换律，即对于任意的 ig ， Ggi ，都有 ig ig =ig ig成立，则称群 G为交换群或阿贝尔群 (Abel Groups)。 此时，通常用符号“ +”来代替“ ”称群运算“ +”为“加法”，称 a+b为 a与 b的和，称 单位元素。 为零元素 O，称逆元素 1a 为元素 a的负元素，并一记作 a。 相应的，称群运算“”为“乘法”，称 a b为 a与 b的积，简写为 ab。 燕山大学本科生毕业设计（论文） 12 例如：全体整数的集合在通常的加法运算下构成一个阿贝尔交换群。 设 n为任意正整数，对于任意的 Ga ，定义： nnnn aaeaa aaa )(, 10,    个 则对于任意整数 m，有 nmnmmnnm aaaaa  ,)(。 定义 a表示所有的 ma的集合， 则 a也构成一个有限群。 特别的，若 G中一个元素 a，得 a=G成立，则称 G为循环群。 显然，循环群 G都是阿贝尔群。 例如：由集合 {1， 1}对于乘法运算所构成的群就是二阶循环群。 设 n为任意正整数，对于任意的 Ga ，称满足 Ean 的最小正整数 n为群元 a的阶数。 显然，对于有限群 G而言，其每一群元的阶都是有 限正整数。 例如：在由集合 {1， 1}对于乘法运算所构成的群中，群元一 1的阶数为2。 自 19世纪中叶由拉格朗日、阿贝尔、伽罗瓦等人引入群的概念以来，经过一百多年的发展，群论己经成为现代代数学的重要分支，其内容非常丰富。 下面介绍一些与椭圆曲线密码学有关的群的重要性质： （ 1） 广义结合律：对群中的任意 n个元素 g1， g2， g3， ..gn，其积g1g2...gn唯一确定。 由自然归纳法和结合律很容易得到此结论。 （ 2） 单位元 e都是唯一的。 用反证法。 若 e1和 e2都是群 G的单位元，则根据群的公有： 21221121 eeeeeeee  ，则，。 （ 3）存在 Gcba ， ， 若 ab=ac，则 b=c；若 ab=cb，则 a=c。 先证明第一条。 若 ab=ac，用 1a 互乘等式两端得 : )()( 11 acaaba   根据结合律，可知 caabaaaba )()()( 111   ,所以， b=c （ 4）每一元素的逆元是唯一的。 用反证法。 若不然，设群元 G存在两个逆元 Gcb , ，则依据群的公理，有 ab=ac=e 由上述的性质 (3)可知 b=c， 所以群元的逆元唯一。 第 3 章 椭圆曲线密码算法的研究 13 有限域（ Finite Field） 只含有有限多个元素的域叫有限域。 由于它首先由 ，因而又被称为伽罗瓦域 (Galois Field)。 在同构意义下，对任一素数 P和正整数 n，存在且仅存在一个含厂个元素的有限域 ，记作 )( npGF。 有限域 )( npGF的特征为 P，其阶为域中元素的个数，即 np。 另一方面，对 q1整数而言，q阶有限域 GF(q)存在的充要条件是 q是某一素数的整次幂 (以下简称素数幂 )。 设有限域 GF(q)上的多项式为： )(,)( 0111 pGFffxfxfxfxf innnn    ni ,2,0  ,。