python椭圆曲线加密信息_ECC椭圆曲线加密算法：ECDH和
ECDSA
Hi all，这⾥是整个椭圆曲线系列的第三部分。原⽂链接如下：Elliptic Curve Cryptography: ECDH and ECDSA
想全⾯了解椭圆曲线的朋友可以先看看前两个部分，翻译得很棒：Avery：ECC椭圆曲线加密算法：介绍z huanlan.zhihuAvery：
ECC椭圆曲线加密算法：有限域和离散对数z huanlan.zhihu
在之前的⽂章中，我们已经认识了什么是椭圆曲线，并且为了更好得使⽤数学⽅法来处理椭圆曲线上的点，我们定义了「」，接着我们⼜进⼀步将椭圆曲线限制在了整数取模素数的有限域上，椭圆曲线上的点在有限域上形成了循环⼦，并且我们也介绍了「基点」、「阶」和「辅因⼦」的概念。
最后，我们知道在有限域上计算标量积是⼀个容易的过程，但是离散对数问题却是⾮常难的，现在我们就来看看这些理论是如何应⽤在密码学上的。
主要参数
椭圆曲线算法将会运⽤在有限域上的椭圆曲线所形成的循环⼦上，因此，我们的算法需要以下⼏个参数：素数 p，⽤于确定有限域的范围
椭圆曲线⽅程中的a，b 参数
⽤于⽣成⼦的的基点G
⼦的阶 n
⼦的辅助因⼦h
所以，我们算法的主要参数可以定义为⼀个六元组 (p, a, b, G, n, h)
随机曲线
「离散对数问题很困难」这种说法其实不完全正确，有⼀类椭圆曲线特别的弱以⾄于⼀些不怀好意的算法可以有效率的求解离散对数问题。例如，具有 p = hn(这意味着有限域的阶等于椭圆曲线的阶) 性质的所有曲线对于 smart 攻击是脆弱的，这就可以被⽤来在经典计算机上，多项式时间内解决离散对数问题。
现在，假设我给你⼀个曲线的主要参数，有可能我发现了⼀种新的没⼈知道的弱曲线，⽽且我已经在我给你的曲线上构建了⼀个快速算法，可以⽤来求解离散对数问题，我怎么样能让你确认我给你的曲线是安全的(换句话说，它不能被我⽤来做⼀些特殊攻击)？
为了解决这个问题，有时候我们需要另⼀个参数：种⼦ S，这是⼀个⽤来⽣成参数 a， b 或者基点 G，或者三个参数都⽣成的随机数，这些参数是通过计算种⼦ S 的哈希值得到的。哈希值，我们知道的，是正向计算容易，反向计算困难的。种⼦是怎样⽣成⼀个随机曲线的：随机数的哈希值被⽤于计算曲线的不同参数如果想要通过主要参数推导出种⼦ S 的值，就需要解决⼀个困难问题：逆向哈希
通过种⼦⽣成的曲线是可验证随机性的，使⽤哈希来⽣成参数的原则是众所周知的「Nothing-up-my-sleeve number」，这个原则也被运⽤在密码学中。
种⼦ S 可以提供⼀种保证，使提供曲线的⼈不会知道⼀些特殊的攻击漏洞。如果我将种⼦ S 和曲线⼀起提供给你，这就意味着我不会任意地选择参数 a 和 b，你也就可以相对确认我不能够发起⼀些特数⽬的的攻击，为什么是「相对」的呢，这个稍后解释。
⽣成和检查随机曲线的标准算法在 ANSI X9.62 中有描述，这是⼀个基于 SHA-1 的算法。如果你感兴趣，可以了解⽤于在 SECG 规范上⽣成可验证随机曲线的算法(到 "Verifiably Random Curves and Base Point Generators")
我写了⼀个 python 脚本来验证当前所有随 OpenSSL 提供的随机曲线，强烈建议⼤家看看！
椭圆曲线密码学
花了好长的时间终于到了关键部分，我们简单来描述：私钥是⼀个范围在
中的随机整数 d，其中 n 是⼦的阶
公钥是点 H，H = dG，其中 G 是⼦的基点
你看，如果我们知道了 d 和 G(还有主要参数中的其他参数)，求得 H 是很容易的。但是如果我们知道 H 和 G，想要求得私钥 d 很困难，因为这要求我们解决离散对数问题。
接下来我们讨论两种基于椭圆曲线密码学的两种公钥算法：⽤于加密的 ECDH(Elliptic curve Diffie-Hellman)和⽤于数字签名的
ECDSA(Elliptic curve Diffie-Hellman)
ECDH
ECDH 是椭圆曲线的笛福赫尔曼算法的变种，它其实不单单是⼀种加密算法，⽽是⼀种密钥协商协议，
也就是说 ECDH 定义了(在某种程度上)密钥怎么样在通信双⽅之间⽣成和交换，⾄于使⽤这些密钥怎么样来进⾏加密完全取决通信双⽅。
我们需要解决的问题通常是这样的：Alice 和 Bob 想要安全通信，中间⼈可能会窃听消息，但是没办法解密消息
那么 ECDH 是这样的：Alice 和 Bob ⽣成各⾃的私钥和公钥，Alice 的私钥为
，公钥为
。Bob 的私钥为
，公钥为
，注意，Alice 和 Bob 需要使⽤⼀样的主要参数：在同⼀条曲线的同⼀个有限域上选择⼀样的基点 G。
Alice 和 Bob 通过不安全信道交换各⾃的公钥
和
，中间⼈可以窃听到
和
，但是在⽆法攻破离散对数难题的情况下⽆法得到
和
。
Alice 计算
(使⽤⾃⾝的私钥和 Bob 的公钥)，Bob 计算
(使⽤⾃⾝的私钥和 Alice 的公钥)，双⽅求得的 S 是⼀样的，因为
中间⼈只知道
和
以及椭圆的公共参数，是⽆法算出共享密钥 S的，这其实就是笛福赫尔曼问题：给定三个点 P，aP，bP，那么 abP 的结果是什么？
或者我们可以这么理解：给定三个整数
，
，
，那么
的结果是什么？
(这种形式被⽤在了最原始的基于模运算的笛福赫尔曼算法上)笛福赫尔曼密钥交换：Alice 和 Bob 可以很容易的计算出共享密钥，中间⼈就
必须解决数学困难问题才能求解
笛福赫尔曼原理的介绍可以看这个视频，视频⾥解释了基于模运算的笛福赫尔曼算法(不是椭圆曲线)。
虽然没有数学证明直接说明椭圆曲线上的笛福赫尔曼问题是困难的，但是这个问题已经被公认为是个困难问题，因为⼈们相信这个问题的困难性是基于离散对数问题的困难性。但是可以肯定的是，这个问题的难度就到此为⽌不会更难了，因为只要解决了离散对数问题，笛福赫尔曼问题也就解决了。
现在 Alice 和 Bob 已经获得共享密钥，他们可以使⽤对称加密算法进⾏通信了。
举个栗⼦，他们可以使⽤ S 的 x 轴坐标作为 AES 或者 3DES 的密钥来加密信息，这多少有点像是 TLS 的操作，不同点是 TLS 将 x 轴坐标和⽹络连接相关的其他参数串联起来，然后计算这个串的哈希值。
实践 ECDH
我写了另⼀个 python 脚本来⽣成基于椭圆曲线的公私钥和共享密钥。种子哈希转换链接
不同于我们之前看到的例⼦，这个脚本⽤的是标准化的椭圆曲线，⽽不是在⼀个⼩的域内的简单曲线。我选择的曲线是 secp256k1，由SECG 发表，这是⽐特币⽤来做数字签名的曲线，下⾯是曲线的主要参数： = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
fffffffe fffffc2f
= 0
= 7
= 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
= 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
= 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
= 1
你也可以使⽤其他的曲线和主要参数，但需要保证素数域和曲线的正确性，否则脚本将不能运⾏
这个脚本特别简单，它包含了⼀些到⽬前位置我们讨论到的算法：点加、点乘、ECDH，建议⼤家看看然后跑⼀跑脚本，它将产⽣类似这样的⼀个输出：Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677,
0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342 Bob's
public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a,
0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd,
0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)
ECDHE
你可能听过 ECDHE ⽽没听过 ECDH，ECHDE 中的 E 代表着「短暂的」，是指交换的密钥是暂时的动态的，⽽不是固定的静态的。
举个栗⼦，在 TLS 中就使⽤了 ECDHE，连接建⽴时，服务器和客户端都动态⽣成公私钥，这些密钥在之后会⽤于 TLS 认证和通信双⽅之间的信息交换。
使⽤ ECDSA 签名
假设这样⼀个场景：Alice 想要使⽤她的私钥
来签名，Bob 想⽤ Alice 的公钥
要验证签名，只有 Alice 才能提供正确的签名，⽽每个⼈都可以验证签名。
ECDSA 是 DSA 作⽤于椭圆曲线的⼀个变种算法。Alice 和 Bob 仍然使⽤同样的曲线，ECDSA 需要使
⽤明⽂的哈希结果，⽽不是明⽂本⾝。哈希函数的选择取决于使⽤者，但是需要明确的是必须选择加密安全的哈希函数，为了使哈希结果的⽐特长度和 n (⼦的阶)的⽐特长度⼀致，消息的哈希结果需要被截断，被截断后的哈希值会是⼀个整数，我们⽤
来表⽰。
Alice 使⽤算法来签名的步骤如下：在
范围内选取⼀个随机数
(
是⼦的阶)
计算点
(
是⼦的基点)
计算数字
(
是
的
轴坐标)
如果
，另选⼀个
并重新计算
计算
(
是 Alice 的私钥，
是
的乘法逆元)
如果
，另选⼀个
并重新计算
就是签名。Alice ⽤⾃⼰的私钥和随机数 k 签名了哈希值 z。Bob ⽤ Alice 的公钥来验证签名的正确性
通俗的说，这个算法⼀开始⽣成了 k，得益于点乘(这是⼀个数学困难问题)k 被隐藏在了 r 中，然后通过等式
将 r 绑定到了消息散列值上。
为了计算 s，我们必须计算 k 的逆 mod n，在之前的⽂章中说过只有在 n 是素数的情况下才能保证这⼀过程，如果⼦的阶不是⼀个素数，ECDSA 将不起作⽤。⼏乎所有标准的曲线都是素数阶的，这肯定不是巧合，⾮素数阶的那些曲线是不能被 ECDSA 使⽤的。
验证签名
为了验证签名，我们需要 Alice 的公钥
，被截断的哈希值 z，还有签名
计算整数
计算整数
计算点
只有当
的时候，签名才被成功验证
算法的正确性
算法的逻辑⼀开始看不是很容易理解，如果我们把前⾯⽤到的公式整合联⽴⼀下，就变得清晰了
我们从
开始，通过公钥的定义我们知道
(
是私钥)，所以我们得到：
使⽤
和
的定义，可以得到：
这⾥为了简单先忽略
，因为由
⽣成的循环⼦的阶为
，所以这⾥的
其实也是没必要的。
再往前，我们定义了
，
式⼦两边同乘以
再同除
，也就是：
，把这个结果带到上⾯关于 P 的等式中得到：
这不就是我们在签名时候的第⼆个步骤得到的等式吗！在⽣成签名和验证签名的时候，我们使⽤了不同的等式计算了同样的点 P，这就是这个算法能够使⽤的原因。
实践 ECDSA
我仍然写了个⽣成和验证签名的python 脚本，这个脚本中的代码和之前 ECDH 中的代码有⼀部分相同，特别是主要参数和公私钥对⽣成算法。
脚本产⽣类似这样的⼀个输出：Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a,
0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)
Message: b'Hello!'
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478,
0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。