【毕业学位论文】（Word原稿）基于椭圆曲线的数字签名算法-计算机科学与工程

基于椭圆曲线的 数字签名算法 0 电 子 科 技 大 学 毕业设计（论文）任务书 拟题单位 计算机科学与工程学院 审题人 王庆先 题目全称 基于椭圆曲线的数字签名算法 主要任务： 描述 基于椭圆曲线的数字签名算 法，讨论相关的安全，实现等问题。 起止时间： 2005 年 3 月 1 日至 2005 年 6 月 12 日 学生姓名 周轶 专业 计算机科学与技术 （软件技术） 班次 21082010班 指导单位 计算机科学与工程学院 指导教师 王庆先 设计地点 电子科技大学 成果形式 论文 2005 年 6 月 12 基于椭圆曲线的 数字签名算法 I 目 录 摘要 . . 一章 引言 . 1 第二章 相关理论和背景 . 3 码学基本概念 . 3 钥密码体制 . 4 钥密码体制的原理 . 6 . 7 码体制和离散对数 . 8 圆曲线密码体制 . 10 种不同用途的数字签名 . 12 签名 . 12 可否认签名和可证实签名 . 13 限签名 . 14 签名 . 15 向安全数字签名 . 15 侵可抵抗签名 . 16 殊用途数字签名之间的比较分析 . 16 签名的特色 . 16 名验证者的身份 . 17 用于组织的数字签名 . 17 止秘密泄漏的数字签名 . 18 结 . 18 第三章 椭圆曲线密码 体制 . 20 限域 . 20 限域. 20 基于椭圆曲线的 数字签名算法 有 限域2. 20 项式基 . 21 规基 . 22 圆曲线 . 22 . 22 . 24 圆曲线数字签名算法 . 25 . 25 . 27 参数 . 27 成随机的椭圆曲线 . 28 参数的生成 . 29 参数的检验 . 30 . 31 钥对的产生 . 31 钥检验 . 32 有私钥的证明 . 32 . 33 . 34 . 34 它基于椭圆曲线的数字签名方案 . 35 案一 . 35 案二 . 36 案三 . 36 第四章 结束语 . 38 参考文献 . 39 致谢 . 58 基于椭圆曲线的 数字签名算法 于 椭圆曲线 的 数字签名算法 作者： 周轶 班级： 21082010班 指导老师：王庆先 指导单位：计算机科学与工程 学院 摘要 椭圆曲线数字签名算法（ 它早在 1998 年就成为了 1999年成为 2000年成为 不像 一般的离散对数 问题和整数因子分解问题， 此， 使用椭圆曲线的算法的单位长度密钥的强度要明显的高于其他算法。这篇文章将描述 论相关的安全，实现 等问题。 关键词： 椭圆曲线密码体制， 数字签名， 椭圆曲线数字签名算法，离散对数问题 ，椭圆曲线离散对数问题 基于椭圆曲线的 数字签名算法 is of It 998 as SO 999 as 000 no is is in an 于椭圆曲线的 数字签名算法 1 第一章 引言 信息作为一种重要的资源，在人类的各种活动中发挥着不可替代的作用。今天，世界正经历着以计算机网络技术为核心的信息技术革命，人类正在迈向一个崭新的时代 以知识经济 为主导的信息化时代。信息技术与社会各行业（如 ： 政府、企业、教育、医药、商务等）的结合带来了一个巨大的新市场，各种各样的 网络正以惊人的速度改变着人们的工作和生活方式，把来自世界各地的人们比以往任何时候都更紧密地联系在了一起，给社会、企业乃至个人带来了前所未有的便利，大大地提高了劳动生产率，给社会带来了无限的商机与财富， 以前需要几天，几个月，甚至几年才能送达的信息，现在却只需轻点鼠标，转瞬之间便出现在了你的电脑荧幕上。 然而，当你尽情享受信息 科技 带来的好处时 ，也需要防备 潜伏于其中的不安定因素。 事物都具有两重性，信 息技术的发展也一样。由于信息网络国际化、社会化、开放化、个人化的特点，使它在提供人们 “ 技术共享 ” 、 “ 信息共享 ” 的同时，也带来了不安全的阴影。信息社会并不安宁，网上信息的被泄露、篡改和假冒，黑客入侵， 网络 犯罪，计算机病毒传播等，对网络信息形成重大威胁 ，给社会带来巨大的经济损失和秩序动荡，甚至会使整个人类社会陷入危机 。 因此，网络安全是一个必须解决的问题，已引起了全球社会的极大关注。 网络安全从本质上来讲就是网络上的信息安全，信息安全技术是一门涉及信息论，计算机科学和密码学等多方面知识的综合性学科，它的主要任务是 研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全，保密，真实和完整。 如果信息安全不解决，信息社会就不能健康有序地发展，电子商务， 电子政务 ，网络银行等等，都将无法开展起来。 实现互联网上信息传输的安全，必须满足以下四个要求 ： 机密性、真实性、完整性、不可抵赖性。机密性就是确保信息不被未授权者获得：真实性就是鉴别信息发送者的身份是否真实，以及信息确实是来自发送者本人，不被别人伪造；完整性就是确保信息在传输过程中没有被修改；不可否认性就是发送信息的实体不能否认自己所发出的消息，接收信息的实体不能否认 自己所收到基于椭圆曲线的 数字签名算法 2 的消息。密码学和信息安全领域所研究的许多密码技术及安全策略成为解决这些问题的重要技术，它们能为信息社会的发展提供安全技术保障。 数字签名提供了用来验证信息内容和发件人身份的方法。作为密码学和信息安全领域中的重要技术之一，它使得 1)数字信息在传播过程中收到信息的实体可以确定发送实体的身份， 2)发送实体不能抵赖 （ 或者否认 ） 自己所发送过信息； 3)接收者 （ 或其他任何人 ） 都不能伪造发送实体的签名。满足这样要求的数字签名能够和传统的手写签名一样起到法律方面的作用。相比之下，手写签名在以计算机和互联网为基础的 信息时代显现出很大的局限性。因为，手写签名在计算机中无法安全存储，不能在互联网上安全传输，极易伪造。数字签名中包含签名者所使用的密钥信息，不知道该保密值的任何人都无法伪造密钥所有者的数字签名，因为得到保密值所付出的代价是巨大的，至少大于伪造签名可能带来的收益。因此，数字签名更适合于新时代的应用要求。人们可以通过网络进行远程文件签署，提高工作效率。 按照所使用的算法分类，常见的数字签名有： 们所基于的数学难题 分别是 整数因子分解问题、离散对数问题和椭圆曲线上的离散对数问题。 按照所具 有的特殊功能分类，常见的数字签名有 ： 群签名、前向安全数字签名、盲签名、门限签名、可证实签名、不可否认签名、入侵可抵抗签名等等。 基于椭圆曲线的 数字签名算法 3 第二章 相关理论和背景 密码学的发展历史大致可以划分为三个阶段：第一阶段是从古代到 1949年。在这一时期，密码学专家常常是凭直觉和信念来进行密码设计和分析的，而不是推理证明。第二阶段是从 1949 年到 1976 年。 1949 年发表了保密系统的信息理论 一文，将密码学的研究纳入了科学的轨道。第二个阶段是从 1976 年开始至今。 1976 年 表了 密码学的新方向 一文，使密码学发生了一场变革。他们首次证明了在发送端和接收端无密钥传输的保密通信是可能的。 1977 年由 出了第一个比较完善的公钥密码体制，这就是著名的 钥密码体制。从那时起，人们基于不同的计算问题提出了许多公钥密码体制，其中最著名的是基于离散对数问题的 钥密码体制，和基于椭圆曲线离散对数问题的椭圆曲线密码体制。 码学基本概念 密码简单地说就是一组含有参数 k 的变换 E 。设己知信息 m ，通过变换c ，即 ()kE m c这个过程称之为加密，参数 k 称之为密钥。加密算法 于密钥 k 不同，密文 c 也不同。当然不是所有含参数 k 的变换都可以作为密码，它要求计算 ()且若第三者不掌握密钥 k ，即使截获了密文 c ，他也无法从 c 中恢复信息 m ，也就是反过来从 c 求 m 极其困难。通常称 m 为明文。 传统的保密通信机理可用图 示。 图 统的保密通 信机理 加密 E 明文 m 密钥 k 密文 c 解密 D 明文 m 密钥 k 基于椭圆曲线的 数字签名算法 4 从密文恢复明文的过程称之为解密。解密算法 D 是加密算法 E 的逆运算，解密算法也是含有参数 k 的变换。传统密码加密用的密钥 k 与解密用的密钥 以有时也称对称密码。通信双方用的密钥 k 是通过秘密方式由双方私下约定的，只能由通信双方秘密掌握。如果丢失密钥，则密码系统不攻自破。 由图可见，数据加密所依据的密码系统包括以下四个方面： (1) 明文信息空间 M ：即信息本来的 原始空间。 (2) 密文信息空间 C ：即明文经过加密变换后成为难以识读的信息空间。 (3) 密钥空间 K ：它控制算法的实现，是由通信双方掌握的专门保密的信息空间。 (4) 密码算法：即数据的加解密变换，它规定了明文与密文之间的变换方式。它可以是数学问题求解的公式、法则或程序。密码算法包括： 加密算法，其中 ； 解密算法，其中 ； 在密码技术中密钥和密码算法是两个最重要的、最基本的因素。一般来说，密码算法是公开的、确定的；而密钥足可变的、保密的。从某种意义上来说，算法可以看作是常量，密钥可以看作是变量。在不改变算法时，只要采用不同的密钥，就可以将相同的明文加密成不同的密文。因此密码中关键问题是密钥的产生与密码算法的设计 。其基本要求是：一是用户方便；三是应具有较强的抗攻击能力，即具有较高的保密强度。也就是说，即使非通信双方的其他人知道了密文 C 甚至掌握了加密、解密的算法本身，也很难根据这些己知条件来推导出密钥来，因而无法从已知的密文得到原来的明文。 钥密码体 制 根据密钥的特点，密码体制可分为对称密码体制和非对称密码体制两种。 1. 对称密码体制 所谓对称密码体制，即加密和解密使用的密钥是相同的， 故该体制又称 单密钥密 码体制。它属于传统密码，在这种体制中，即使有时加密、解密密钥不基于椭圆曲线的 数字签名算法 5 同，但它们之间仍存在着一定的联系，是容易相互推导 出来的。 这种密码体制的代表。 对称密码体制存在着两个 主 要问题 ： 一是密钥的分配与管理方面的困难。加密与解密使用的是相同的密钥，收发双方必须知道同一个密钥，他们必须事先通过某种秘密途径商定密钥。另外当 n 个人通讯时，需要的密钥数为( 1) / 2个，若有 100 个人，所需要的密钥数就是 4950 个。因此，有关密钥的分配、安全传送、保密管理是一件很困难的事情。二是数据的完整性保护方面的困难，由于保密通信双方都具有共同的加 、解密密钥，信息的接受方可以很容易地篡改原文内容，而信息的发送方也可以否认 自 己所发的内容。对称密码体制在数字签名和身份认证方面的应用是相当困难和不现实的。 2. 非对称密码体制 所谓非对称密码体制，即加密和解密使用的密钥是不相同的，也称之为密钥 对 密码体制。非对称密码体制的基本思想是 ： 不仅公开加密算法，而且加密用的密钥也公开 ， 。即可以将每一用户的加密密钥作为公钥文件，像电话号码一样公开，只要解密密钥保密就可以了，而且各用户的解密密钥由各用户自己保密保管。若用户 A 要向用户 B 发送信息， A 可以从公钥文件中查到 B 的加密密钥，利用它向 B 发送密文， B 收到密文后利用只有自己知道的解密密钥解密得到明文。 当 n 个人通讯时，需要的密钥数为 2n 个，若有 100 个人，所需要的密钥数 仅为 200 个 。 这种密码体制在密钥管理与使用方面为用户带来了明显的好处，在数字签名与身份认证领域有着广阔的前景。 由于这种密码体制 的加密密钥是公开的，因此又称这种加密体制为公开密钥密码体制，简称公钥体制。 图 称密码体制和非对称密码体制的区别 对称密码体制需要每两个用户之间保存一对密钥 非对称密码体制只需每个用户保存一对密钥 基于椭圆曲线的 数字签名算法 6 钥密码体制的原理 公开密钥密码体制中，加密密钥与解密密钥互异且分离。虽然从理论上讲，解密密钥可由加密密钥计算出，但是这种密码体制建立的思想基础是使这种逆向计算在实际上成为不可行。也就是说，在实际中，解密密钥不 可能由加密密钥或加密信息、加密技术以及破译技术简单地产生或推算出来。如果解密密钥需要世界上最快的计算机运行数年才能算出，那么这种密码事实上就是安全的。公钥密码体制的加密算法都是基于一种特殊的数学函数，即单向陷门函数，因此公钥算法均满足以下三个条件 ： (1) D 是 E 的逆。 (2) E 和 D 都容易计算。 (3) 仅根据 E 去找出计算 D 的简单算法则是很困难的。 其数学描述不失一般性有 ： ( ( )( ( )s k p kp k s x x x其中 E 是公钥体制中每个用户的加密算法，即单向陷门函数， D 是解密算法，是 E 的逆变换函数。 E 和 D 具有等同性，也可以是不同的。 公开的加密密钥， 保密的私有密钥。 所谓单向函数，即从一个方面很容易求值，而其逆向计算却十分困难。比如说 ： 对于函数 ()Y F x ， 任意给定自变量 X ， 则能够很容易地计算出函数 而由任意给定的 Y 值，即使是按照已知的函数关系的性质也很难求出 钥密码体制取用单向陷门函数这一独特的性质，使得计算加密函数 而在没有给定的条件下仅仅根据己知的加密函数 E 去逆向求解解密函数 D ， 在计算上是极其困难的，甚至 是不可能的。这种条件 或者说是 专门信息 ，称作为陷门。所谓 陷门 是指一旦掌握了保密的陷门 信息，求其逆函数是容易的。公钥密码体制使不掌握 陷门 的破译者在解密过程中将不可避免地遇到特定的计算上的难题。因此，公钥密码体制的安全性依赖于这种单向陷门函数，但这种单向陷门函数是比较难以找到的。 在公钥密码体制下，任何人都可以使用其他用户的公开密钥来对数据进行基于椭圆曲线的 数字签名算法 7 加密，但是，只有拥有保密的私有密钥的用户才能对加密的数据解密。在这种体制下，即使知道了加密算法和加密密钥也不会因此泄露解密密钥。 1977 年， 出了著名的 钥密码体制。从此以后，人们基于不同的计算问题，提出了大量的公钥密码算法，这些加密方法的安全性都是基于复杂的数学难题。对于某种数学难题，如果利用通用的算法计算出密钥的时间越长，那么基于这一数学难题的公钥密码体制就被认为越安全。根据所基于的数学难题来分类，以下三类密码体制目前被认为是安全和有效的 ： (1) 基于整数因子分解的密码体制 (如 码体制 )。 (2) 基于离散对数问题的密码体制 (如 码体制 )。 (3) 基于椭圆曲线离散对数问题密码体制 (即椭圆曲线密码体制 )。 下面对这几种典型的密码体制进行分析讨论。 钥密码体制的理论基础是一种特殊的可逆模指数运算。它的安全性是基于大整数 因子分解 的困难性。以 下 是 法的描述 ： 设 n 是两个不同的素 数 p 和 q 之积，即 n ， ( ) ( 1 ) ( 1 )n p q ， K= ( , , , , )n p q a b | n ， p 和 q 是 素数， 1( m o d ( ) )a b n （其中 ()n 为欧拉函数，表示与 n 互素的小于 n 的正整数的数目（ n 1）。） 对每一个 ( , , , , )K n p q a b ，定义 加密变换为 ： ( ) ( m o d )x x n， 解密变换为 ： ( ) ( m o d )y y n， 公开 n 和 b ，保密 p ， q 和 a 。 为了建立密码系统，用户 B 需要完成以下步骤 ： (1) 随机选取两个大 素数 p 和 q (保密 )； 基于椭圆曲线的 数字签名算法 8 (2) 计算 n （ 公开 ）和 ( ) ( 1 ) ( 1 )n p q （ 保密 ）； (3) 随机选取 整 数 b ，使满足 g c d ( , ( ) 1 ； 且 0 ( ) 。将 b 公开，即为加密密钥。 (4) 计算 a ，满足 1( m o d ( ) )a b n 。 a 保密，即为解密密钥。 码体制的安全性依赖于两个大素数 p 和 q ，若 n 被因式分解，则 被击破。因为若 p ， q 己知，则 ( ) ( 1 ) ( 1 )n p q 便可算出，解密密钥 a 关于 b 满足 1(m o d ( )a b n ，故 a 也不难求得。因此 安全性依赖于因式分解的困难性。由于计算水平的提高，人们逐渐可以用计算机分解更大的数。因此 法的密钥也就越来越长。在电子商务的 议中，规定用户使用 1024 比特的 钥，认证中心 用 2048 比特的 钥。这样带来了两个问题，一是运算速度较慢，另一个是密钥存储和管理问题。 1. 离散对数问题 对实数来说，取幂运算 (计算 一 指定精度 )不比它的逆运算 (求 容易得多。但对有限域来讲，用快速取幂算法，可以相当快地对较大的整数 x 计算出 但如果给定一个元素 y 且已知存在一个整数 x ，使得对一固定的基 b ，有 ，如何求出 x ，则是一个非常困难的问题，这个问题就是离散对数问题 。 定义 ： 离散对数问题 (指给定一个素数 p ， 及一个元素 *pZ，寻找一个整数 ： x ， 02 ，使得 (m o d )x p 。通常用 来表示 x 。 一般地，如果仔细选择 p ，那么认为该问题是困难的。特别是，目前还没有找到计算离散对数问题的多项式时间算法。为了抵抗己知的攻击， p 应该至少是 150 位十进制整数， 并 且 1p 至少有一个大的素因子。之所以离散对数问题在密码环境中是有用的，是因为找离散对数是困难的。即对适当的素数 p ，模 p 指数运算是一个单向函数。 2. 码体制 法是在密码协议中有着大量应用的一类公钥密码算法，它的安基于椭圆曲线的 数字签名算法 9 全性是基于解离散对数问题的困难性。以 下 是 法的详细描述 ： 首先每个使用者 （ 用 A， B 表示 ） 按如下方法生成自己的一 对公钥和私钥 ： (1) 生成一个大的随机素数 p 和整数模 p 的乘法群 *。 (2) 选取一个随机整数 a ， 12 ，计算 (a p 。 (3) A 的公开密钥是 ( , , ) ； A 的私钥是 a . 假设 B 加密消 息 m 给 A， A 解密，用 制的加解密过程如 下： (1) B 执行如 下 步骤 ： a) 获取 A 的真实公开密钥 ( , , ) ； b) 将消息 m 表示成 0 到 1p 范围内的整数 ； c) 选取随机整数 k ， 12 ； d) 计 算 (m o d )k p 和 ( ) ( m o d ) ； e) 发送密文 ( , )c 给 A。 (2) 为从 c 中恢复出明文 m ， A 执行 ： a) 使用私钥 a 计算 1(m pa p （ 注 ：1 ( m o d )p a a a ）； b) 通过计算 ( ) (m o d )a p 恢复出 m 。 A 能够恢复出 m 是由于 ( ) ( m o d )a a k a km m p 。 攻击 码体制，即从给出的 p ， ， a ， 和 中恢复出 m ，等价于解离散对数问题。非常重要的一点是，要用不同的随机整数 k 来加密不同的消息。假设同一个随机整数 k 用来加密两个消息1得到的密文对分别是11( , )和22( , )，则1 2 1 2/，故当1 码体制的一个缺点是 消息扩展 ，即密文长度是所对应的明文基于椭圆曲线的 数字签名算法 10 长度的两倍。 圆曲线密码体制 椭圆曲线 密码算法是基于有限域上的椭圆曲线 上 的离散对数问题 。 比 整数 因子分解 问 题更难的问题，目前对椭圆曲线离散对数还没 有 发现 一般的亚 指数时间的算法 。这就意味着用椭圆曲线来实现的密码算法可以用小一些的数来达到使用更大的有限域所获得的安全性。从目前己知的最好求解算法来看， 163 比特的椭圆曲线密码算法的安全性相当于 1024 比特的 法。 图 密钥长度的比较 椭圆曲线密码体制 有以 下 两个明显的优点 ： (1) 具有短的密钥长度，这意味着小的带宽和存储要求，这些因素在某些应用场合十分有用，诸如在智能片系统中。 (2) 所有的用户可选择同一基域 F 上的不同的椭圆曲线 这可使所有的用户使用同样的硬件完成域算术，为保证安全性，只有椭圆曲线 下一章 将对椭圆曲线密码体制作详细分析，这里先简单介绍其加解密过程 。 1. 系统的建立和密钥 的生成 选取一个基域个定义在a 和 一个阶为素数 p ，点 p 的坐标用 ( , )有限域椭圆曲线方程，点 p 和阶 基于椭圆曲线的 数字签名算法 11 系统建成后，每个使用者 (简称实体 )进行 下 列计算 ： (1) 在 区间 1, 1n 中 随机选取一个整数 d ； (2) 计算点 Q ； (3) 实体的公开密钥包含点 Q ，实体的私钥是整数 d 。 2. 椭圆曲线加密体制 加密过程 ： 当实体 B 发送消 息 m 给实体 A 时 ， 实体 B 执行 下 列步骤 ： (1) 查 找 A 的公开密钥 Q ； (2) 将数据 m 表示成一个域元素 q ； (3) 在区间 1, 1n 中随机选取 一个整数 k ； (4) 计算点 11( , )x y ； (5) 计算点 22( , )x y ，如果 2 0x ，则回到第 3 步； (6) 计算 2c ； (7) 传送加密数据 11( , , )x y c 给 A。 解密过程 ： 当实体 A 解密从 B 收到的密文11( , , )x y A 执行 下 列步 骤 ： (1) 使用它的私钥 d ，计算点 2 2 1 1( , ) ( , )x y d x y (2) 通过计算 12，恢复出数据 m 。 上述过程中， Q 是公开的，如果除 A， B 外的第三者能解椭圆曲线基于椭圆曲线的 数字签名算法 12 上的离散对数问题，就能从 求出 d ，从而解密消息。 种不同用途的数字签名 数字签名作为网络中身份确认的重要技术，越来越多地被人们关注和研究。网络中的交易、通讯等等都需要进行双方的身份确认，以确保交易、通讯安全进行，并能够在网络信息化的时代中提供有力的法律证明。 随着 断的深入人们的生活，越来越多的需求被 提 出来，为了满足这种需求，研究者不断的努力寻找合适的技术和方法，为日常应用提供技术保障。特殊用途的签名方案应运而生，解决了或者部分解决了现实问题，如 ：盲签名、不可否认签名、可证实签名、群签名等。但是，目前存在的签名方案或多或少存在需要改进和完善的方面，比如群签名中的成员删除问题就是个急需解决的问题。随着社会的进步，还会出现更多不同种类的需求。因此，对特殊用途的知识签名进行大量的研究实践是必须的，满足人们的需求，推动社会的进步。 签名 1982 年， 文章 中提出了盲签名的概念。盲签名方案是一个有关两个实体的密码系统，包括发送实体和签名实体。盲签名允许发送实体能够 拥 有签名实体所签署的消息的签名，同时签名实体在签名过程中没有得到任何关 于 自 己签署的消息的任何信息 。 也就是，签名实体只提供发 送 实体的消息的数字签名，而不知道自己究 竟对什么内容签 了名。盲签 名 的运行特点如下 ： (1) 签名 者向发送者提供签名所需的关于签名 密钥 的 知识 ； (2) 发送者根据签名者提供的密码参数，计算消息的签名。 盲签名提供了某个实体的匿名性，这对于电子货币的安全支付是必需的，其在数字签名的发展中是个很重要的签名概念。随着研究的不断深入，盲签名有各种各样的方案被建议，如公平盲签名等。 基于椭圆曲线的 数字签名算法 13 可否认签名和可证实签名 电子出版物有其不可比拟的方便快捷的特点，但它也有自己的先天缺陷容易复制并随 意传播。 发展，对于电子出版物的知识产权产生了巨大的威胁，人们从 得免费资源的同时，也