[电子电路]基于Openssl的数字签名算法的实现.doc

摘摘 要要 随着计算机和互联网技术的不断发展 电子商务的广泛应用 信息安全问题 变得越来越重要 而网络信息安全的核心在于密码技术 椭圆曲线密码体制 ecc 是一种公钥密码体制 相对于以往基于有限域上离散对数问题或大整数分 解问题的传统公钥算法 椭圆曲线密码算法具有安全性高 速度快 密钥短 实 现时所需占用资源少的特点 作为迄今为止每比特具有最高安全强度的密码系统 由于其算法的高效安全性 使其成为优于 rsa 的 pki 体系的核心公钥算法 其 224 位的 ecc 安全性相当于 2048 位的 rsa 安全性 所以 ecc 技术在信息安全 领域中的应用将会越来越广泛 本设计正是基于这样的背景 在 microsoft visual studio6 0 下的 microsoft visual c 6 0 编译环境中利用标准 c 语言并且借 助密码学领域的开放源代码库 openssl 设计与实现国家密码管理局 21 号公告 sm2 椭圆曲线公钥密码 中的数字签名算法 关键字关键字 椭圆曲线 sm2 microsoft visual c 6 0 c 语言 openssl 数字签名 abstract with the development and application of information technology and the electronic commerce the problem of information security becomes more and more important but the network information security core lies in the password technology elliptic curve cryptography ecc systems which is a public key systems is characterized by higher safety property faster speed shorter key lengths and fewer computational resources for implementation thanother former traditional public key algorithms based on the discrete logarithm infinite fields or the great integer factorization problem so far the ecc provides the highest strength per bit of any cryptosystem known because of its high efficiency of the algorithm some people think it is the best public key cryptosystem that is suitable for current use in future the security of 224 bit ecc is equal to 2048 bit rsa so the application of ecc technology in the field of information security will be more and more widely based on this background this design will use c language with open source library openssl of the field of cryptography to design and realize a complete system of digital signature of chinese sm2 elliptic curve public key crypto system key word elliptic curve sm2 microsoft visual c 6 0 c language openssl digital signature 目目 录录 摘 要 i abstract ii 目 录 iii 第一章 引言 1 第二章 数字签名的概念 2 第三章 椭圆曲线概述 8 3 1 有限域 8 3 2 射影平面和无穷远点 9 3 3 椭圆曲线 10 3 4 密码学中的椭圆曲线 13 第四章 椭圆曲线数字签名算法实现 15 4 1 椭圆曲线的参数选取 15 4 2 杂凑函数 17 4 3 数字签名算法流程 18 4 4 开放源代码工具 openssl 简介 22 4 5 基于 openssl 的椭圆曲线数字签名算法实现 26 第五章 数字签名结果验证 29 第六章 结论和感想 31 致谢语 32 参考文献 33 附录 a 34 附录 b 36 英文文献 39 第一章第一章 引言引言 随着计算机技术和网络技术的高速发展和广泛应用 社会的信息化程度越来越 高 大量的敏感信息通过公共通信设施和网络系统进行交换 尤其是互联网 电 子商务和电子政务的迅猛发展 国家 企业和个人的信息都要求严格保密 如 军事机密 企业财务 银行密码等 然而 网络很容易遭受攻击 攻击者可以窃 取网络信息 企图偷窥机密或是篡改和破坏信息从而使自身获利 这对网络的发 展和用户的利益构成了严重的威胁 因此 如何保护通信过程中信息的安全使之 不被窃取 篡改和破坏 已经成为当今备受关注的重大问题 在这样的背景下 网络安全技术应运而生 形成了密码技术 系统入侵检测技术 和计算机病毒检测消除技术等多种安全防护技术门类 其中 密码技术在信息保 护方面给人留下了深刻印象 说到密码技术 人们可能会马上想到加密技术 的 确 经过加密处理的信息在网络上传输能够使攻击者难以窃取通信双方的原文 从而避免了机密信息的泄漏 然而 接收方获取的信息有可能被攻击者恶意篡改 或破坏 如果不对收到的信息加以辨别将有可能会给通信双方带来巨大的损失 那么接收方要如何确认收到的信息的确是来自和他合作的对象呢 数字签名技术 就是能解决这类问题的关键技术 第二章第二章 数字签名的概念数字签名的概念 数字签名技术 digital signatures 是纸质手写签名的电子版本 是一种能够保 证交易者身份的确定性 数据交换的完整性 发送信息的不可否认性的有效的解 决方案 是电子商务安全性的重要部分 数字签名技术是密码技术的一个分支 要想充分了解数字签名的原理必须先了解密码学相关概念 密码体制可分为对称密码体制和公钥密码体制两种 对称密码的历史可以追溯到几千年前 它是一种加密密钥能够从解密密钥中 推算出来 同时解密密钥也可以从加密密钥中推算出来的加密技术 在大多数的 对称算法中 加密密钥和解密密钥是相同的 所以对称密码算法也称为秘密密钥 算法或单密钥算法 它要求发送方和接收方在安全通信之前 必须商定一个密钥 对称算法的安全性依赖于密钥 泄漏密钥就意味着任何人都可以对他们发送或接 收的消息解密 所以密钥的保密性对通信性至关重要 对称系统通常非常快速 却易受攻击 因为用于加密的密钥必须与需要对消 息进行解密的所有人一起共享 其优缺点如下 优点 优点 1 算法实现的效率高 速度快 2 满足大量信息的加密要求 缺点缺点 1 密钥量问题 在单钥密码系统中 每一对通信者就需要一对密钥 当用 户增加时 必然会带来密钥量的成倍增长 因此在网络通信中 大量密 钥的产生 存放和分配将是一个难以解决的问题 2 密钥分发问题 单钥密码系统中 加密的安全性完全依赖于对密钥的保 护 但是由于通信双方使用的是相同的密钥 人们又不得不相互交流密 钥 所以为了保证安全 人们必须使用一些另外的安全通道来分发密钥 例如用专门的信使来传送密钥 这种做法的代价是相当大的 甚至可以 说是非常不现实的 尤其在计算机网络环境下 人们使用网络传送加密 的档 却需要另外的安全通道来分发密钥 所以传统的对称密码算法 急需改进 虽然对称算法的缺点和优点一样明显 但作为对称算法的经典 由 ibm 公 司开发 并被美国国家标准局于 1977 年 2 月采纳作为 非密级 应用标准的 des 算法不仅在历史上曾发挥重要作用 到目前为止仍是大量信息加密的首选 方案 那么对称算法适用于数字签名吗 答案是不适用 因为有两个 或更多个 实 体共享密钥 这样一来利用密钥作用于消息产生的数字签名 无法区分出共享密 钥的不同实体的行为 也就是对称密码体系不能实现用于不可否认服务的数字签 名 公钥密码也称为非对称密码 它是相对于对称密码而言的 它突破性地解决 了对称密码面临的三个难题 密钥分发 密钥管理和提供不可否认性 公钥密码 体系与对称密码体系最大的不同是采用两个不相同但有着紧密联系的密钥进行加 密和解密 其中一个密钥是公开的称为公钥 另一个密钥是保密的称为私钥 这 两个密钥也称为密钥对 公钥密码体系的工作模式有两种 1 发送实体用公钥加密得到密文 接收实体用私钥把密文解密成明文 只有与 此公钥相对应的私钥才能够将该公钥产生的密文恢复成明文 2 发送实体用私钥加密得到密文 接收实体用公钥把密文解密成明文 只有与 此私钥相对应的公钥才能够将该私钥产生的密文恢复成明文 这种公私钥的关系是基于一种单向陷门函数 单向陷门函数是有一个陷门的 一类特殊单向函数 它首先是一个单向函数 在一个方向上易于计算而反方向却 难于计算 但是 如果知道那个秘密陷门 则也能很容易在另一个方向计算这个 函数 即已知 x 很容易计算出 f x 而已知 f x 却很难出计算 x 然而 一旦 给出 f x 和一些秘密信息 k 就很容易计算出 x 在公钥密码体系中 计算 f x 相 当于加密 陷门 k 相当于私钥 而利用陷门 y 求 f x 中的 x 则相当于解密 在公钥密码体系中 要实现这样一种单向陷门函数 密钥对的选择必须保证 从公钥求出私钥等价于要求解一个困难的计算问题 目前构成常用公钥密码基础 的困难问题有如下 3 种 1 大整数的因子分解问题 2 离散对数问题 3 椭圆曲线离散对数问题 有了适合于公钥密码体系用来构造公私钥关系的数学难题 公钥密码的应用 才能成为现实 对于公钥体系的工作模式 1 以公钥作为加密密钥 以用户私 钥作为解密密钥 可实现多个用户加密的消息只能由一个用户解密 适用于加密 因为私钥的保密性确保了只有一个实体能进行解密 对于公钥体系的工作模式 2 以私钥作为加密密钥 以公钥作为解密密钥 则可实现由一个用户加密的消息可 以由多个用户解密 适用于数字签名 因为同一个实体产生的多个签名应该能被 不同的接收实体验证 这也正是数字签名的基本要求 本设计研究的是数字签 名 以下就不对公钥密码的加密体系进行介绍了 数字签名技术是不对称加密算法的典型应用 数字签名的应用过程是 数据 源发送方使用自己的私钥对数据和其他与数据内容有关的信息进行加密处理 完 成对数据的合法 签名 数据接收方利用对方的公钥来解读收到的 数字签名 并将解读结果用于对数据来源和完整性的认证 以确认签名的合法性 最早的数字签名方案有 rsa 数字签名方案 dsa 数字签名方案和 ecdsa 数字签名方案 此三种签名方案于 2000 年 2 月 15 日被美国国家标准技术研究所 nist 在新标准法案 fipsl86 2 中指定为美国的数字签名标准 同时他们也是目 前世界上普遍使用的数字签名方案 都已经形成商业的签名软件供商家和个人使 用 其中 rsa 数字签名方案是由 rsa 公司提出的基于 rsa 公钥密码体制的签 名方案 其数学基础是大数因子分解的困难性 dsa 数字签名方案是基于 e1gamal 提出的 e1gamal 公钥密码体制 其数学基础是在有限域上求解离散对 数的困难性 ecdsa 数字签名方案是基于椭圆曲线密码体制的签名方案 它是 将 dsa 签名方案移植到椭圆曲线密码体制中来得到的 它的数学基础是求解椭 圆曲线上离散对数的困难性 目前由于椭圆曲线密码体制较其他公钥密码体制有 密钥短 速度快 安全性高的优点使得椭圆曲线密码体制和 ecdsa 数字签名方 案越来越受到更高的重视 下面对本设计采用的椭圆曲线密码体系进行详细介绍 人们对椭圆曲线的研究已有 100 多年的历史 而椭圆曲线密码是 neal koblitz 和 victor miller 于 1985 年提出来的 目前椭圆曲线密码已成为除 rsa 密 码之外呼声最高的公钥密码之一 它可以提供同 rsa 相同的功能 然而它的安 全性建立在椭圆曲线离散对数问题 ecdlp 的困难性之上 现在求解 ecdlp 的 最好算法具有全指数时间复杂度 与此不同 整数因子分解问题却有亚指数时间 算法 所谓亚指数算法就是其算法复杂度还未到达指数级别 这意味着要达到期 望的安全强度 椭圆曲线密码可以使用较 rsa 密码更短的密钥 普遍认为 224 位的椭圆曲线密码可提供相当于 2048 位 rsa 密码的安全强度 由于密钥短 所 以工程实现加解密速度较快 并且可节省能源 带宽和存储空间 正因为如此 一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准 由于椭圆曲线密 码具有上述优点 因此椭圆曲线密码特别适于在航空 航天 卫星及智能卡的系 统中的应用 在椭圆曲线密码体制的标准化方面 ieee ansi iso fips sec 等都作了大量的工作 它们所开发的椭圆曲线 标准的文档有 ieee p1363 2000 和 p1363a ansi x9 62 和 x9 63 iso iec15946 fips186 2 sec1 和 sec2 等 根据研究 以目前计算整数分解问题 离散对数问题和椭圆曲线离散对数问 题的最好算法进行计算 表 1 1 比较了 rsa dsa 和 ecc 在等价安全强度下所 需的密钥尺寸 其中 mips million instructions per second 年是每秒运算 100 万条 指令运行 1 年的时间 表2 1 三种典型的公钥密码体系性能比较 破解密钥时间 mips 年 rsa dsa 密钥长 度 bit ecc 密钥长度 bit rsa 与 ecc 密钥长 度比 1045121065 1 1087681326 1 101110241607 1 1020204822410 1 10782100060035 1 表 2 1 说明 在等价安全强度下 ecc 较 rsa 和 dsa 的密钥尺寸小的多 而且随着密钥长度的增加它们的比例将更为悬殊 以下从几个方面对三种公钥密码体系进行比较 1 安全性能 加密算法的安全性能一般通过该算法的抗攻击强度来反映 ecc 和其他几 种公钥系统相比 其抗攻击性具有绝对的优势 椭圆曲线的离散对数计算困难性 ecdlp 在计算复杂度上目前是完全指数级 而 rsa 是亚指数级的 这体现 ecc 比 rsa 的每 bit 安全性能更高 2 计算量和处理速度 在一定的相同的计算资源条件下 虽然在 rsa 中可以通过选取较小的公钥 可以小到 3 的方法提高公钥处理速度 即提高加密和签名验证的速度 使其在 加密和签名验证速度上与 ecc 有可比性 但在私钥的处理速度上 解密和签名 ecc 远比 rsa dsa 快得多 因此 ecc 总的速度比 rsa dsa 要快得多 同 时 ecc 系统的密钥生成速度比 rsa 快百倍以上 因此在相同条件下 ecc 有 更高的加密性能 3 存储空间 ecc 的密钥尺寸和系统参数与 rsa dsa 相比要小得多 160 位 ecc 与 1024 位 rsa dsa 具有相同的安全强度 224 位 ecc 则与 2048 位 rsa dsa 具有相同的安全强度 意味着它所占的存贮空间要小得多 这对于加密算法在资 源受限环境上 如智能卡等 的应用具有特别重要的意义 4 带宽要求 当对长消息进行加解密时 三类密码系统有相同的带宽要求 但应用于短消 息时 ecc 带宽要求却低得多 而公钥加密系统多用于短消息 例如用于数字签 名和用于对称系统的会话密钥传递 带宽要求低使 ecc 在无线网络领域具有广 泛的应用前景 此外 人们已经知道利用量子计算机进行整数因子分解 求解离散对数问题 和求解椭圆曲线离散对数问题的有效算法 然而 人们尚不知道大型量子计算机 是否能够实际制造出来 在传统计算机上求解 256 位的 ecdlp 实例大致相当于 3072 位的因数分解问题的实例 然而 前者可在 1448 qubit 量子计算机上求解 而后者需要 6144 qubit 量子计算机 到目前为止 最重大的实验结果是 2001 年 使用 vandersypen 等 464 建造的 7 qubit 量子计算机来以 shor 算法对整数 15 进 行因数分解 类似的实验能否大规模用于密码学意义的因数分解和求解 ecdlp 实例 还有待进一步研究 也就是说虽然量子计算机以其自身的优势对于以上 3 大难题的求解比普通大型计算机有更好的解决方案 但是目前的量子计算机技术 的发展还远未达到可以解决 3 大难题的规模 现在 普通的认为 2048 位的 rsa 才能保证信息的安全 而 224 位的 ecc 便能达到这一安全水平 随着大型计算机的不断发展 椭圆曲线密码凭借其密钥 长度短的优势将在未来的安全领域应用中越来越多的得到客户的青睐 目前 数字签名已经是一种十分成熟的技术 鉴于数字签名技术在各个领域 的重要性 国内外尤其是国外的研究发展水平一直很高 国外发明的数字签名方 法有很多 其中 dsa 是主流算法 椭圆密码体制的不断发展正在逐步挑战 rsa 在公钥密码学的地位 其更少的密钥长度和每比特更高的安全性 更适合数字签 名这类短消息加密需求 国外发明的基于椭圆曲线密码学的数字签名算法为 ecdsa 国家密码管理局也于 2010 年 12 月 17 日发布了 sm2 椭圆曲线公钥密 码 内容包括公钥加密算法 数字签名算法和密钥交换协议 其中的数字签名部 分给出了中国标准的基于椭圆曲线的数字签名方案 其与 ecdsa 原理一致 只 是在签名验证算法的实现上有所不同 数字签名技术已经广泛应用于各种电子政 务和电子商务等对安全性要求很高的领域中 从技术发展的水平来看 并没有存 在明显的问题 第三章第三章 椭圆曲线概述椭圆曲线概述 3 1 有限域有限域 在椭圆曲线密码体制中 我们关心的是基于有限域上的椭圆曲线 有限域上 的椭圆曲线加密算法涉及数论 群论 有限域理论及椭圆曲线等数学知识 域是对常见的数系 如有理数域 q 实数域 r 和复数域 c 及其基本特性的抽 象 域由一个集合 f 及两种运算共同组成 这两种运算分别为加法 用 表示 和 乘法 用 表示 且满足下列算术特性 1 f 对于加法运算构成加法交换群 单位元用 0 表示 2 f 0 对于乘法运算构成乘法交换群 单位元用 l 表示 3 分配律成立 对于所有的 a b c f 都有 a b c a c b c 若集合 f 是有限集合 则称此域为有限域 有限域算术运算的有效实现是实现椭圆曲线密码的重要先决条件 因为椭圆 曲线运算是基于有限域算术运算的 椭圆曲线密码体制的有效实现主要用到两大 特征的有限域 它们分别是素域和二进制域 3 1 1 素域素域 设 p 是一个素数 以 p 为模 则模 p 的全体余数的集合 0 1 2 p 1 关于模 p 的加法和乘法构成一个 p 阶有限域 并用符号 fp 表示 我们称 p 为 fp 的模 对于任意的整数 a a mod p 表示用 p 除 a 所得到的余数 r 0 r p 1 并称这种 运算为求模 p 的剩余 fp 中元素具有以下算术运算 1 加法 如果 a b fp 则 a b r 其中 r 是被 p 除所得的剩余 o r p 一 1 2 乘法 如果 a b fp 则 a b s 其中 s 是被 p 除所得的剩余 o s p 一 1 3 求逆 如果 a 是 fp 中的非零元素 a 模 q 的逆元 记为 是唯一 1 a 的整数 c fp c 满足 a c 1 3 1 2 二进制域二进制域 阶为的域称为二进制域或特征为 2 的有限域 构成的一种方法是采用 m 2 m f2 多项式基表示法 在这种方法中 域的元素是次数最多为 m 1 次的二进制多 m f2 项式 多项式的系数取自 0 1 的公式见公式 3 1 2 f m f2 公式3 1 m f2 1 0 01 2 2 2 2 1 1 i m m m m aazazazaza 选择一个二进制域上的 m 次既约多项式 f z 对任意的 m 这样的多项式一 定存在 并能够有效产生 f z 的既约性意味着 f z 不能被分解成次数低于 m 的 二进制域上的多项式的乘积 域元素的加法是两个多项式系数的模 2 相加 域元 素的乘法是两个多项式相乘后取模 f z 对于任意一个二进制域上的多项式 a z a z mod f z 表示一个次数低于 m 的余式多项式 r z 余式多项式 r z 可用 f z 辗 转相除 a z 得到 这一运算成为求模 f z 的余式 3 2 射影平面和无穷远点射影平面和无穷远点 通常情况下两条平行直线永不相交 但可以假设两条平行直线相交于一个无 穷远点 从而可以在原来平面坐标系的基础上建立射影坐标系 对于普通平面直角坐标系上的点坐标 x y 做如下变换 令 x x z y y z z 0 则 a 点可以表示为 x y z 这样就将二维的 坐标变成了三维的坐标 同时 对于平面上的点建立了一个新的坐标体系 同时 得到直线的方程 ax by cz 0 普通平面直角坐标系下直线一般方程是 ax by c 0 无穷远点是两条平行直线的交点 将两条平行线直线对应的方程联 立求解 ax by z 0 公式 3 2 1 c ax by z 0公式 3 3 2 c 解得z z ax by 因为 所以 z 0 即无穷远点可以用 x y 0 表示 1 c 2 c 1 c 2 c 注意 平常点 z 0 无穷远点 z 0 因此无穷远直线对应的方程是 z 0 下面列出无穷远点的几个性质 以统一平行与相交 1 1 直线 l 上的无穷远点只能有一个 2 2 平面上一组相互平行的直线有公共的无穷远点 3 3 平面上任何相交的两直线 l1 l2有不同的无穷远点 4 4 平面上全体无穷远点构成一条无穷远直线 5 5 平面上全体无穷远点与全体平常点构成射影平面 3 3 椭圆曲线椭圆曲线 3 3 1 椭圆曲线定义椭圆曲线定义 域 k 上的椭圆曲线 e 的方程定义见公式3 4 e 公式3 4 64 2 2 3 31 2 axaxaxyaxyay 其中k 且 是 e 的判别式 具体定义如下 64321 aaaaa 0 4 4 2 4 4 9278 2 4 2 32431626 2 18 6 2 36 3144 2 2 12 2 2 11 642 2 6 3 48 2 2 aaaaaaaaaad aad aaad aad aad ddddddd 方程 e 被称为 weierstrass 方程 我们称 e 是域 k 上的椭圆曲线 这是因为 系数均为域 k 的元素 条件是确保椭圆曲线是 光滑 的 64321 aaaaa0 即曲线的所有点都没有两个或两个以上不同的切线 椭圆曲线的形状 并不是椭圆的 椭圆曲线的一个典型图形如图 2 1 所示 只是因为椭圆曲线的描述方程 类似于计算一个椭圆周长的方程 定义在实数域 r 上的椭圆曲线 其点和xxye 32 1 4 5 4 1 32 2 xxye 1 re 画在图 3 1 中 其中为无穷远点 2 re 图3 1 r 上的椭圆曲线 若 e 是定义在域上的椭圆曲线 那么椭圆曲线 e 的点的个数记为 q f q f e 并称其为域上的椭圆曲线 e 的阶 q f q f 若椭圆曲线上的一点 p 存在最小的正整数 n 使得 np 则称 n 为 p 的阶 若 n 不存在 我们说 p 是无限阶的 事实上 在有限域上定义的椭圆曲线上所 有的点的阶 n 都是存在的 3 3 2 椭圆曲线的运算法则椭圆曲线的运算法则 设 p 和 q 是椭圆曲线 e 上的两个的点 若是不同的两点 则 l 是 p 和 q 的 连线 若是重合的点 则 l 是该点的切线 l 与曲线相交的另一个点 过 r r 作 y 轴的平行线 与曲线交另一点 r 定义点加运算 r p q 不同点和重合点的点加运算的图形描述分别图 3 2 和图 3 3 图3 2 不同点相加运算 图3 3 重合点倍点运算 椭圆曲线的运算法则如下 1 单位元 对于所有的 pe k p p p 点为单位元 2 负元素 若 p x y e k 则 x y x y 记点 x y 为 p 并称其为 p 的负 注意 p 也是 e k 上的一个点 此外 3 不同点相加 令 则 11 keyxp 22 keyxq qp 其中 33 yxqp 和 21 2 12 12 3 xx xx yy x 131 12 12 3 yxx xx yy y 4 相同点倍点 令 则 其中 11 keyxp pp 2 33 yxp 和 1 2 1 2 1 3 2 2 3 x y ax x 131 1 2 1 3 2 2 3 yxx y ax y 5 标量乘 椭圆曲线上的标量乘是椭圆曲线密码体制的核心操作 曲线 e 上的一点 p 其标量乘 q kp 定义为对 p 进行了 k 1 次的倍点运算 标量 乘是椭圆曲线密码体制中最耗时的运算 它决定着椭圆曲线密码体制的运算速度 3 3 3 射影平面坐标系下的椭圆曲线射影平面坐标系下的椭圆曲线 椭圆曲线在射影平面上的投影形式为 公式 3 5 3 6 2 4 2 2 32 31 2 zaxzazxaxyzaxyzazy 曲线 e 上唯一的一个无穷远点是 0 1 0 射影坐标的点加和倍点运算不涉 及域上的求逆 首先把点转化为仿射坐标 然后利用其运算法则进行点加 最后 去掉分母 便得到射影坐标点的计算公式 由于在普通平面直角坐标系下 域 k 上的求逆存在比乘法费时的情况 那 么采用射影坐标来表示点将是非常好的一种解决办法 3 4 密码学中的椭圆曲线密码学中的椭圆曲线 椭圆曲线密码体制基于的数学难题是椭圆曲线离散对数问题 前面提及的椭 圆曲线是连续的 并不适合加密 所以我们必须把椭圆曲线转化为离散的点 这 就需要将椭圆曲线定义在有限域上 并不是所有的椭圆曲线都适合加密 是一类可以用来加密的baxxy 32 椭圆曲线 也是最为简单的一类 本设计正是基于有限域上的这类曲线来实现加 解密算法的 下面我们就把 这条曲线定义在有限域 fp 上 baxxy 32 选择两个满足下列条件的小于 p p 为素数 的非负整数 a b 并且满足 mod p 则满足方程 mod p 的所有点 x y 再加0274 23 babaxxy 32 上无穷远点 构成一条椭圆曲线 其中 x y 属于 0 到 p 1 间的整数 并将这 条椭圆曲线记为 ep a b 令 p 29 a 4 b 20 考虑定义在素域上的椭圆曲线 e 29 f 公式 3 6204 32 xxye 注意 所以曲线 e 确实是椭圆 29 mod0176896 274 16 23 ba 曲线 椭圆曲线的点如下 29 fe 2 6 4 19 8 10 13 23 16 2 19 16 27 2 0 7 2 23 5 7 8 19 14 6 16 27 20 3 27 27 0 22 3 1 5 22 10 4 14 23 17 10 20 26 1 5 3 28 6 12 10 25 15 2 17 19 24 7 1 24 4 10 6 17 13 6 15 27 19 13 24 22 椭圆曲线在不同的数域中会呈现出不同的样子 但其本质仍是一条椭圆曲线 椭圆曲线在有限域上的运算法则同实数域上的运算法则类似 椭圆曲线离散对数问题 ecdlp 定义为 给定定义于有限域的椭圆曲线 p f e 基点 阶为 n 点 寻找一个整数使得 p feg gq 1 0 nllgq 整数 称为 q 的基于的离散对数 表示为 lg ql g log 椭圆曲线离散对数问题的困难性是所有椭圆曲线密码方案安全性的基础 但 需要注意的是 ecdlp 的难解并没有数学上的证明 目前还没有证明不存在求 解 ecdlp 的有效算法 然而 通过很多年的考验说明了 ecdlp 的难解性 自 从 1985 年椭圆曲线密码被提出来 该问题被许多学者研究 到目前为止还没有 发现亚指数时间的通用算法 第四章第四章 椭圆曲线数字签名算法实现椭圆曲线数字签名算法实现 4 1 椭圆曲线的参数选取椭圆曲线的参数选取 4 1 1 参数组参数组 为了抵抗所有已知的对 ecdlp 的攻击 密码方案中使用的椭圆曲线的参数 应该谨慎选择 最简单的求解 ecdlp 问题的算法是穷举搜索 连续计算一系列点 p 2p 3p 4p 直到得到 q 该方法最坏的情况下为 n 步 平均情况下为 n 2 步 因此可以通过选择参数 n 足够大的椭圆曲线 使得穷举攻击的计算量不可实际实 现 如 对于 ecdlp 已知最好的通用攻击方法是将 pohlig hellman 算 80 2 n 法和 pollard s rho 相结合 该方法的运行时间为完全指数时间 其中是 pop n 的最大素因子 为了抵抗该种攻击 椭圆曲线参数的选择要求 n 含有大素数因 子 应该足够大 以使得的计算量不可实现 如 另外椭圆曲ppp 160 2 p 线的参数选择还要防止其他所有的已知攻击方法 密码学中 描述一条上的椭圆曲线 参数组 d fr a b g n h 其中 p fp 域的阶 p 系数 a 和 b 用来确定一条椭圆曲线 fr 即 fp 中元素的表示 有穷 远点 g 为基点 n 为点 g 的阶 h 称为余因子 nfe p 为了避免针对 ecdlp 的 pohlig hellman 攻击和 pollard s 攻击 必须 p fe 能被足够大的素数 n 整除 最小应该保证 给定域 为了最大限度地 160 2 n p f 抵抗 pohlig hellman 攻击和 pollard s 攻击 应选择 e 使得为素数或者近 p fe 似素数 即 hn 其中 n 为素数 h 非常小 如 h 1 2 3 或 4 p fe 这几个参量取值的选择 直接影响了加密的安全性 参量值一般要求满足以 下几个条件 1 p 当然越大越安全 但越大计算速度越慢 200 位左右可以满足一般 安 全要求 2 p n h 3 pt 1 mod n 其中 1 tcd c openssl 0 9 8k 2 运行 configure perl configure vc win32 如不成功会有明显提示 3 创建 makefile 文件 ms do ms 推荐使用这种方式 另外两种方式 如果使用也必须保证本机有编译器才能使用 ms do masm 默认 vc 自带的编译器 也也以自己下载安装 ms do nasm 需要自己下载 4 配置 vc 环境变量 cd c program files microsoft visual studio vc98 bin vcvars32 bat 5 编译动态链接库 cd c openssl 0 9 8k nmake f ms ntdll mak 如果编译成功 最后的输出都在 out32dll 目录下 包括可执行文件 两个 dll ssleay32 lib libeay32 lib 和两个 lib 文件 ssleay32 dll libeay32 dll 6 为 vc 添加头文件和静态链接库路径 tools options directores 在 include files 中增加 c openssl 0 9 8k inc32 目录 在 libray files 中增加 c openssl 0 9 8k out32dll 7 编写 openssl 程序 可参考 c openssl 0 9 8k demos 1 包含相应头文件 include 2 添加静态链接库 pragmacomment lib libeay32 lib pragmacomment lib ssleay32 lib 或 project settings link object library modules 填写 libeay32 lib ssleay32 lib 3 将动态链接库 ssleay32 dll libeay32 dll 复制到 c windows system32 或 debug 目录下 确保动态链接库在正确的路径 附录附录 b 本附录给出了国家密码管理局21号公告 sm2椭圆曲线公钥密码算法 中的 数字签名算法章节的附录 a 英文文献英文文献 elliptic curve cryptosystems elliptic curve cryptosystems eccs were developed independently in 1985 by neal koblitz and victor miller eccs do not use new cryptographic algorithms they use existing algorithms e g the elgamal cryptosystem what changes is the operation recall that for the elgamal cryptosystem the exponentiation operation is based upon multiplication modulo a prime p n factors a paaapab n modmod for an ecc the exponentiation operation is based upon the multiplication of points on an elliptic curve that is defined over a finite field what does all this mean first it should be noted that an ellipse is not an elliptic curve elliptic curves are related to integrands of elliptic integrals and elliptic integrals first occurred in the calculation of the arc length of an ellipse elliptic integrals have been explored since early in the nineteenth century for eccs the elliptic curves are typically of the form with some baxxy 32 conditions on a and b to say that the curve is defined over a finite field just means that the input x and the output y come from a finite field see the appendix about finite fields so instead of being a continuous curve the ecc curve over a finite field is a collection of points but these points have the property that two points on the curve can be multiplied we will denote the operation and the result is a point on the curve i e the points on the curve form a group under elliptic curves have the property that most straight lines meet an elliptic curve in three points so given two points on an elliptic curve draw a line through the points that line should meet the curve in one point the product the fact that the points on an elliptic curve over a finite field form a group has been well known to algebraic geometers for a given elliptic curve an ecc based upon the elgamal cryptosystem replaces the usual multiplication with and the usual exponentiation with paaapab n modmod where a is a point on the elliptic curve the algorithm is otherwise not changed there is a little bit of work to do to implement the ecc however because it must be arranged that blocks of a plaintext message m can be converted to and from points on the curve see for example klima sigmon and stitzinger below why should ecc be considered since factoring and the discrete logarithm problem were implemented in public key cryptosystems in the 1970s much attention has been paid to the underlying mathematical problems steady progress has been made on factoring and on solving for discrete logarithms but neither problem is solved cryptographers have countered mathematical successes by increasing key sizes on the other hand little progress seems to have been made on the elliptic curve discrete logarithm problem rather than continuing to increase key sizes one can switch to second generation public key cryptosystems using elliptic curves and use smaller keys the nsa now recommends that vendors who incorporate public key cryptosystems consider the use of ecc in 2005 the nsa announced suite b which uses ecc suite b may be