椭圆曲线在密码学中的应用毕业论文(编辑修改稿)

椭圆曲线在密码学中的应用毕业论文(编辑修改稿)内容摘要：

1xm c c p。 m。 天津科技大学 2020届本科生毕业论文 12 密码的攻击方法 密码攻击者分析密码攻击密码的方法主要有三种：穷举攻击、统计分析攻击和数学分析攻击 [13]。 第一种 穷举分析攻击 ， 是尝试一切 密钥的可能性 对所获得的密文解密，一直到找到正确的密文为止，或者将全部可能的明文通过一个固定的密钥 加密，一直到找到与所获得的密文相同的明文为止，理论上来讲对于任何的密码都能通过这样的方式破解只要 有足够多的资源。 第二种 统计分析攻击 ， 是利用 前人对明文和密文总结 统计 的一定规律来破解密码，很多的古典密码都无法抵御这种攻击的方法 ，比如分析密 文中字母与字母组出现的次数 或者其它的统计参数，对于对抗这种攻击的有效方式就是使密文中找不到明文的统计特性，如此一来，密文中就没有明文的痕迹了，从而抵抗了统计分析攻击的可能，而这一点也成为了近代密码的一项基本要求 [5]。 最后一种 数学分析攻击 ，是想要破译 密码的人通过 数学分析的方法来分析密码， 针对 密码学一些基本的数学知识的特征，找到破解密码的 数学解决方案 [5]。 对于各类 主要的密 码攻击方式，其中数学分析攻击是最具有难度的，需要选取具有坚实数学基础，同时还要十分 复杂 难解的加解密算法 ， 才有可能与其对抗。 对于密码的分析者或者说破译人而言，可以利用数据信息的资源来分类，将密码的破解类型划 分为四种：仅知道密文的攻击，已经知道明文的攻击，选取明文来攻击或者选取 密文来攻击 [5]。 仅知道密文的攻击就是通过了解分析截获的密文来破解密码，因为此时自由密文可以作为资源来使用，所以这也是对密码破译者最不利的一种情况。 所谓的已经知道明文的攻击，就是指密码的破译人通过已经知道的某一些明文和密文对应着来破解， 比如说计算机程序檔经过加密后的密文中有大量的诸如“ IF”，“ BEGIN”，“ END”，“ THEN”等词，而这些词汇会非常规律地出现在密文之中，密码的破译者可以十分合理的推测出它们，所以近代密 码学认为只有能经受住已知明文攻击的密码才会是可取的密码。 选取明文来攻击就是在选取明文并且获得相对应的密文来攻击， 这是十分有利的情况，比如说计算机的数据库和文件系统就十分容易遭受这样的攻击 [5]，因为用户通过随意的选择明文并且获得相对应的密文数据库和密文文件。 最后一种类型也就是选择密文来攻击，这种情况对破译密码的人来说也是 非常有利的，破译者通过选择密文并且获得相对应的明文，再进行破解密码的工作。 最后的这种攻击方式主要是用来攻击公开密钥密码体制，尤其是攻击其数字签名。 假如有一个密码是无论密码的分析人获得了多少的密文和明文并使用了任何的技术方法对其进行攻击都不能被破解，就称其为绝对不可破译的，这种情况的出现需要满足三个条件： 密钥是随机序列 密钥最短也要和明文是一样长的长度 一个密钥就只可能是用一次，理论上这种密码是存在的，最为著名的就是“一次一密”密码， 密钥是一次性使用的，也正是因为这个原因导致 密钥管理十分困难， 所以 实际 上是不天津科技大学 2020届本科生毕业论文 13 能 广泛使用的 [5]。 所以，总的来说只要有充足的信息 就能破译实际上可以使用的任何密码。 密码的设计 由于通讯、计算机以及网络的技术 发展，使计算机网络得到了广泛应用 [4]，同时也将全世界的计算机连在了一起，由此形成了一种巨大的计算能力从而形成了非常大的一种破解密码的能力，是最初十分安全的密码变得不再安全。 有学者 曾发表论文，认为从信息论的角度出发，对密钥、加密、密码以及信息源进行详细地数学分析，使用唯一解距离及不确定性测试各类密码体制的安全性能 [6]，并且阐述纯密码、理论保密、 实际保密等相关重要的概念，将密码置于夯实的数学基础上。 同时阐明自己的观点，提议采取混淆、扩散及乘积迭代的方法 [6]，使设计出来的密码更安全。 混淆实际上就是让密钥与密文的关联变得复杂化，从而可以使明文密文及密文 密钥之间的联系减少也就是降低了它们之间的相关性，统计相关性 越小统计分析中的数据信息就越没有作用，从而提高了密码的安全性能； 所 说的扩散是将明文中每位明文和密钥形成在密文中最大程度的影响，即密文中的每一位都可以成为明文和密钥的一个函数，也 就达到了完备性。 一般来说设计一个比较复杂的密码是十分困难的，但是设计一 个相对简单的密码就很容易了，所以对 简单的密码使用乘积迭代的方法，将其简单密码进行组合迭代，然后获取一个预期的混淆及扩散，最后就能拥有 一个相对安全的密码 [6]。 其实设计一个相对比较安全的密码就是需要寻找一个非常复杂的难解的问题，利用这一问题就能设计出比较理想的密码了。 因为一个实用的理想的密码应该是一个不害怕公开加密算法的密码，也就是说一种密码的设计应该遵守公开设计的原则，这样才能使设计出来的密码 不会因为加密算法的暴露而功亏一篑 ， 只需要将密钥保密即可 ，算法公开的密码才能更适应未来的环境。 但是，密码中加密算法的公 开原则也并不是适用于所有的领域的，比如各国的军事政治核心，这类的密码就都不公开加密算法，所以设计密码和使用密码的正确方式还是在公开原则下对已经测试过安全性能的密码使用保密算法的方式更为稳妥。 密码学既是一门科学也是一门技术，运用科学的知识和理论将其运用到实际中，数据信息通过加密形成密文存储在计算机的文件之中，或者传输在网络信道之中，并只会给合法的用户分配密钥，当然这一切都是在密钥的控制下进行，实用又安全，尤其能适用于现在的网络安全中。 天津科技大学 2020届本科生毕业论文 14 3 椭圆曲线 概述 椭圆曲线的定义及点的加法运算 椭圆曲线 其实 并不是椭圆 形状，只是因为椭圆曲线的 方程和计算椭圆周长的方程类似， 所以称它为椭圆曲线， 椭圆曲线的方程是： 2 3 21 3 2 4 6y a x y a y x a x a x a      其中 , , , , , ( )1 2 3 4 5 6a a a a a a F F 是 一 个 域，而 F 域既可以是一个有理数域也可以是一个复数域还可以是有限域 ()GFp ，通常将满足上述方程的数 (, )xy 称为 F 域中椭圆曲线 E 上的点 [4]。 假设 P 点和 Q 是点椭圆曲线上的两个点并在椭圆曲线上定义加法运算 +PQR ， R 表示通过连接 P 点和 Q 点的直线 与椭圆曲线 E 相交，交点关于 x 轴对称的点称为 R 点。 如图 31。 P Q R 图 31 点 加 运 算 特别地，如果 P 点和 Q 点是重合的， R 就表示 P 点的切线与椭圆曲 线 E 的交点关于 x 轴对称的点，即 2P Q P P P R    。 这里定义的加法运算需要引进一个零元素，将 0 定义为一个无穷点即0（ ， ） ，那么 天津科技大学 2020届本科生毕业论文 15 0 + 0 = 0 0 0     （ ， ） （ ， ） 并且 0 , + = 0 ,P P P    （ ） （ x,y ） （ x,y ） + （ ） （ x,y ）， 假设 ( , )11Px y 和 ( , )22Qx y 是解点，如果 ,1 2 1 2x x y y  就有 ( , )+ Q ( , )= 01 1 2 2P x y x y， 当 ( , )11Px y 和 ( , )22Qx y 不相等的时候就有 ( , ) + Q ( , ) = ( , )1 1 2 2 3 3P x y x y R x y， 其中 23 1 2x x x   ， ()3 1 3 1y x x y  ， ( ) / ( )2 1 2 1y y x x   ， 如果 P 点和 Q 点是重合的，那么 2 231xx， ()3 1 3 1y x x y  ， 2(3 ) / (2 )11x a y。 由此可知椭圆曲线 E 在有限域 F 上的加法运算，构成了加法交换群并且加法单位元为 0[4]。 有限域上的 椭圆曲线 对有理 数、实数、复数等常见的数系和它们基本特征的抽象称为 域， 是由一个集合 和加法乘法两种运算来组成的 [4]。 一个集合域，域中除 0 以外的数位如果满足以下的特性： 域对加法封闭，并对加法运算构成加法交换群； 域 对乘法封闭，并对乘法运算构成乘法交换群； 使分配律成 立，对域中任意的数字 ,abc都有 ()a b c a c b c     成立，并且这个集合是有限集合，那就称这个域为有限域。 有限域中含有元素的个数被 称为这个有限域的阶。 如果在有限域 F 上定义出一条椭圆曲线 E ，那么椭圆曲线 E 的个数就称为在有限域 F 上椭圆曲线 E 的阶。 椭圆曲线 的离散 对数问题 椭圆曲线离散对数问题就是指在有限域 F 上定义出一条椭圆曲 线 E ，在 E 上给定一个基点 P 并计算出阶 N [4]即 0NP。 天津科技大学 2020届本科生毕业论文 16 然后在椭圆曲线 E 上寻找任意一点 Q ， 在 [0, 1]N 的范 围内找一个正整数 k 使 =QkP 成立，这时将正整数 k 称为点 Q 对点 P 的椭圆离散对数即将 k 表示为 logkQp。 已知椭圆曲线 E 的 离散对数 k 和 E 上的一个基点 P 可以比较容易将点 Q 计算出来，但是如果已知点 Q 和 E 上的一个基点 P 想要计算出 离散对数 k 是十分难的 ， 以至于迄今为止都 没有有效的方法来计算， 同时也正是因为有这样难解 的问题存在， Koblitz 和 Miller 就在这个基础上建立了椭圆曲线密码体制 ECC 而这也正是椭圆曲线密码的加密原理 [4]。 天津科技大学 2020届本科生毕业论文 17 4 椭圆曲线 密 码体 制 椭圆曲线 密 码体 制的概念 椭圆曲线 密 码体 制是属于 公 钥 密 码体 制 中的一种 ， 它 主要的 数学 理论 基 础 是源于 数论 的相关知识，它是通过有限域中 椭圆曲线上 的 点 构成的 Aebel 加法群，在 Aebel 群 中 计算 椭圆对数 [4]。 现 在 国际 上比较 流行的密 码体 制 都是以 三 种难解的 理论 为依据而设计的，其中 一 种 是基于大整 数因 子分解 问题 设计的 比 如 RSA 公钥密码体制，还有一种 是基于 离散对数 的难解问题而设计的 比如 ELGamal 公钥密码体制，最后一种就 是同样基于离散对数问题设计的 椭圆曲线密码体制 [4]。 下面简述一下椭圆曲线的离散对数问题，首先我们在有限域 Fp 上选取一条椭圆曲线 E ， p 是 ()EFp 上的点， p 是素数 n ，那么 集合  , , 2 ,3 , ,( 1 )P P P P n P    是 利用 P 生成的椭圆曲线循环子群， 其中的 素数 p ，椭圆曲线 E ，点 p 和阶 n 构成 一个 公开 的 参数组 [4]。 在区间 [1, 1]n 内随机 地选取一个 正整数 d 作为算法中的私钥 ，相 对 应的公钥 就是 Q dP。 而这种需要通过 公开 的 参数组和公钥 Q 求 得 私钥 d 的问题就是椭圆曲线 的离散对数问题 简称 ECDLP[4] (The elliptic curve discrete logarithm problem) [4]。 下面将详细地 介绍椭圆曲线 上 生成 密钥对 、 加密和 解密 的具体过程。 以二进制域作为例子，构造椭圆曲线具体见下表 ： 天津科技大学 2020届本科生毕业论文 18 表 41 在二 进 制域上 随 机 的生成 椭圆曲线 在二 进 制域2mF上： 输 入： 一个 正整 数 m 和 1比特 杂凑 函 数 [4]H。 输 出：种子2, mS ab F， 定 义 一条 椭圆曲线 [4] 2 3 2:E y xy x ax b   。 1．令 ( 1) /s m l， lms。 2. S选 取 一 个 随 机 的 二 进 制 串，其 长 度 g1bit。 算 ()h HS ，令 0b 是 h的 最 右 边 比 特 所 得 长 度 为 的 二 进 制 串。 z S是 与 二 进 制 表 示 相 等 的 整 数。 i 从 1到 s ， 执 行： is 为 整 数 ( )mod2gzi 的 g 位二 进 制表示。 算 ()iib H s。 0 1 0|| || || ||b b b b 。 0b ， 则 跳至步 骤 2。 任意的 2maF。 ( , , )Sab。 椭圆曲线 的 参数组 参数组的定义 椭圆曲线 的 参数组 是 描述 有限域 qF 上定义的 椭圆 曲线 [4] E ， E 上的 基点()qp EF 和 阶 n ， 其中选取的参数需要抵御全部 已知的密码攻击 使 ECDLP 的安全性高于其他。