Python中的椭圆曲线数字签名算法

比特币是一种运行在区块链技术上的虚拟货币。区块链是一个分布式数据库，它跟踪所有已发生的共享数字事件或交易。

大多数系统用户会验证每笔交易。每笔交易记录都包含在其中。最著名的加密货币和区块链的例子是比特币。以下是一些区块链的例子

1. 公共区块链： 它是一个无限制的、无需许可的公共账本版本，任何人都可以加入和进行交易，并且每个对等节点都拥有一个副本。此外，这意味着任何有互联网连接的人都可以连接到公共区块链。
2. 私有区块链： 区块链网络通常在一个企业或组织内部的本地网络上运行，而不是对任何想要提供计算能力的人开放。它们也可以在私有环境中运行，例如受限网络，或者由单个身份进行管理。
3. 混合区块链： 希望获得两者优势的企业可以使用混合区块链，它结合了公共区块链和私有区块链的优点。这些区块链允许企业创建具有私有授权系统的无许可公共系统，从而使他们能够控制哪些数据是公开的以及对谁公开。
4. 联盟链： 联盟链上的共识过程由指定的节点管理。启动、收集和验证交易的任务由验证节点负责。成员节点可以启动或完成交易。

什么是 ECDSA？

椭圆曲线数字签名算法 (ECDSA) 是一种数字签名算法 (DSA)，它使用椭圆曲线密码学密钥。这种使用公钥密码学的方程非常强大。ECDSA 是比特币安全的基础（比特币“地址”充当公钥），并且广泛用于加密消息应用程序。

椭圆曲线数字签名算法 (ECDSA) 是对当前标准密码系统（如离散对数问题和整数分解密码系统）的替代方案，近年来引起了极大的关注，特别是来自标准开发人员。在安全应用中，加密算法始终是最重要的基础工具。

ECDSA 的数字签名

数字签名是手写签名的电子对应物，它允许接收者向第三方证明通信确实是由预期的接收者发送的。与数字签名相比，手写签名安全性大大降低。数字签名不存在被伪造的可能性。数字签名覆盖了整个消息，这是它们相对于手写签名的另一个优势。

签名密钥会影响数字通信的各个方面。纸质文件在底部会有一个手写签名。没有什么可以阻止在保持签名不变的情况下更改写在签名上方的文本。数字签名不允许进行此类修改。现代数字签名技术的安全性可归因于可用于对其进行分类的数学问题。

• 整数分解 (IF) 方案： 它们的安全性依赖于整数分解问题的棘手性。RSA 签名方案是一个例子。
• 离散对数 (DL) 方案： 它们的安全性依赖于有限域中离散对数问题是无法解决的问题。
• 椭圆曲线 (EC) 方案： 它们的安全性基于椭圆曲线离散对数问题的棘手性。例如，在本研究中使用了椭圆曲线数字签名算法——无疑是各种设计中最现代的一种。

ECDSA 的域参数

定义在离散空间 Fq 上的、具有特征 p 和基点 G 的椭圆曲线 E。域参数可能属于单个用户或被多个实体共享。

生成域参数的技术

以下是生成密码安全域参数的一种方法：

• 步骤 1：使用随机技术，从 Fq 中选择可验证的系数 a 和 b。
• 步骤 2：确定 N 的值。
• 步骤 3：如果 N 不能被大素数整除，则转到步骤 1。
• 步骤 4：验证 N 不能被 1 到 20 之间的任何 k 的 qk -1 整除。
• 步骤 5：检查 N 是否等于 q；如果不相等，则转到步骤 1。
• 步骤 6：选择一个任意点 G'∈ Nq 后，将 G=(N/n)。

域参数验证

验证域参数的过程确保它们具有所需的算术特性。实际上，进行域参数验证有两个原因：

• 避免故意插入不正确的域参数，这可能导致某些攻击成为可能
• 查找无意的编码或通信错误。

如果使用了不正确的域设置集，所有预期的安全特性都可能失效。已证明，如果不对签名方案进行域参数验证，就可能进行实际的（尽管是不可能的）攻击。攻击的目标是利用 ElGamal 签名方法的密钥协商协议。

验证域参数的程序

• 步骤 1：使用特定算法显式执行域参数验证。
• 步骤 2：A 使用可靠的系统生成 D。
• 步骤 3：A 从认证机构 T 获得确认，T 已使用预定算法认证了 D 的显式域参数。
• 步骤 4：A 从可靠的第三方 T 获得 D 是由可靠系统生成的确认。

ECDSA 密钥对

特定的 EC 域参数集与 ECDSA 密钥对相关联。私钥是用于生成倍数点的整数，而公钥是基点的随机生成的倍数。

密钥对生成

实体 A 的密钥对与特定的 EC 域参数集 D = (q, FR, a, b, G, n, h) 相关联。这种关联可以通过上下文（例如，所有组织使用相同的域设置）或通过密码学（例如，使用证书）来保证。实体 A 在生成密钥之前必须确信类别参数是准确的。

建立一对 ECDSA 密钥。每个对象 A 执行以下操作：

• 从范围 [1, n1] 中选择一个伪随机数或整数 d。
• 计算 Q = dG。
• A 的公钥是 Q，私钥是 d。

ECDSA 公钥的显式验证算法

算法输入： Q=(xQ, yQ) 是与有效域参数 (q, FR, a, b, G, n, h) 相关的公钥。

算法输出： 接受或拒绝 h 的真实性。

• 验证 Q 和 O 不相等。
• 验证代表 xQ 和 yQ 的 Fq 元素是准确的（即，在 q = p 的情况下为 0 到 p-1 范围内的整数，在 q = 2 的 m 次方的情况下为长度为 A 位的位字符串）。
• 验证 h 位于由 a 和 b 定义的椭圆曲线上。
• 验证 nQ = O。
• 如果任何检查失败，Q 则无效，否则 Q 有效。

私钥所有权的证据

• 如果一个组织可以验证另一个实体的公钥是其自己的，那么它可以声称已签名的通信来自它。为避免这种情况，CA 应要求所有实体在确认公钥属于 A 之前，提供与其公钥相对应的私钥的所有权证据。
• 请注意，私钥拥有权的证据提供的保证与公钥验证的证据不同。前者证明公钥有效但您不持有相应的私钥，而后者证明私钥在您手中，即使它可能对应一个无效的公钥。两者都提供了高度的确定性。

ECDSA 签名的生成

本节介绍如何使用 ECDSA 创建和验证签名。要签名消息 m，具有域特征 D=(q, FR, a, b, G, n, h) 和相关密钥对 (d, Q) 的实体 A 执行以下操作。

• 选择一个伪随机或随机整数 k，范围从 1 到 n c - 1。
• 使用公式 kG = (x1, y1) 将 x1 转换为整数。
• 如果 r = 0，则计算 r = x1 mod n，然后转到步骤 1。
• 确定 k - 1 mod n。
• 必须计算 S = k - 1(e + dr) mod n。如果 s = 0，则转到步骤 1。
• (r,s) 是消息 m 的签名。

ECDSA 签名验证

要验证 A 对 m 的签名 (r, s)，B 需要获得 A 的域参数 D = (q, FR, a, b, G, n, h) 的真实副本以及相关的公钥 Q。建议 B 也验证 D 和 Q。然后，B 执行以下操作：

• 验证数字 r 和 s 是否在范围 [1, n - 1] 内。
• 将位字符串转换为 e 数字并执行 SHA-1(m)。
• 从 s-1 mod n 减去 w。
• 从 ew mod n 减去 rw mod n，得到 u2 = rw mod n，u1 = ew mod n。
• 通过 u1G + u2Q 乘以 X。
• 如果 X = O，则拒绝签名。如果不是，则计算 v = x1 mod n 并获取 X 的 x 坐标 x1 的整数表示。
• 仅当 v = r 时才批准签名。

安全注意事项

2013 年 8 月发现，Java 中某些类的安全随机数实现中的故障偶尔会导致 k 值冲突。黑客能够获取私钥，这使他们能够像真正的密钥所有者一样控制比特币交易，这种攻击方式与用于在某些使用 Java 并依赖 ECDSA 进行交易身份验证的 Android 应用程序实现中暴露 PS3 签名密钥的攻击方式相同。

• ECDSA 的安全目标是在选择消息攻击面前具有存在性不可伪造性。
• 发起此类攻击的对手针对合法公司，除了获取某些（不包括 A）通信的签名外，目标是获得对一条消息 A 的真实签名。

根据 Brown 的研究，只要使用的哈希函数是抗碰撞的，并且底层群是通用群，ECDSA 本身就是安全的。潜在的 ECDSA 攻击可以分为以下几类：

• 椭圆曲线离散对数问题的攻击。
• 对使用的哈希算法的攻击。
• 不同类型的攻击。

椭圆曲线离散对数问题攻击

• 婴儿步-大步算法可以解决穷举搜索策略。在最坏的情况下，它需要大约 个点的存储空间，并运行大约 步。
• POLLARD 的并行 Rho 算法 Pollard 的 Rho 算法并行化：Van Oorschot 和 Wiener 已证明 Pollard 的 Rho 算法可以并行化，当该过程在 H 个处理器上并行运行时，估计运行时间约为 16 步。也就是说，使用 H 个处理器可获得 H 倍的速度提升。
• 我们不包括其他类型的椭圆曲线的攻击。因此，通过确保椭圆曲线上的点数不等于底层域的属性值，可以很容易地验证 Semaev-Smart-Satoh-Araki 攻击不适用。

哈希算法攻击

• 如果 SHA-1 不是预象抗性，以下方法演示了攻击者 E 如何可能伪造 A 的签名。E 选择一个随机数 l，并计算 r 作为 Q+lG 模 n 的 x 坐标。E 设置 s=r，在确定 e=rl mod n 后。如果 E 能找到一个消息 m 使得 e=SHA-1(m)，则消息 m 有一个有效的签名 (r,s)。
• 利用 SHA-1 特性攻击 ECDSA 最快已知方法是找到 SHA-1 的碰撞。但请记住，此攻击将 ECDSA 安全级别的上限置于主要安全参数 n 的值之外。
• 在这种情况下，找到 H1 碰撞并攻击 ECDSA 所需的时间与解决 ECDLP 所需的时间几乎相同。新系列将具有 256、384 和 512 位的输出长度。

其他类型的攻击

• 选择重复签名密钥： 如果在域参数构造期间需要生成点是可验证随机选择的（使用类似于 5.2 中为可验证随机创建椭圆曲线的方法），则 ECDSA 不再具有 DSKS 功能。需要强调的是，签名方案并非不安全，仅仅因为它具有 DSKS 功能。
• 实现攻击： ANSI X9.62 没有涵盖可能用于 ECDSA 实现的攻击类型，包括时序攻击、差分故障分析、差分功耗分析以及利用弱随机数或虚假随机数的攻击。

ECDSA 实现

先决条件： 椭圆曲线密码学、密码学技术基础以及基本的Python 编程知识。

下面提供了实现 ECDSA 的 Python 代码：

程序说明

这个 Python 应用程序实现了一个基本的椭圆曲线数字签名算法 (ECDSA)。首先定义了椭圆曲线的素数和基点。然后，程序中包含了计算最大公约数、确定模逆、将字符串转换为整数以及执行模运算的函数。通过标量乘法基点，它使用这些方法从随机生成的私钥推导出公钥。之后，通过计算 R 和 s 来对消息进行哈希和签名，并通过比较计算出的点来验证签名。结果证明了签名的有效性。

输出

 
----------------------
Key Generation: 
Public Key: (45703697233224450869207279200119054502134678211271488154390651878993482862973, 5994464935082368334402190473328846237205883738928804283793674817197354625312)
----------------------
Signing:
Message: 5735816763073854953388147237921
Signature (R, s):
R: (45912781235192740506254875867642545687192111997373345760202071060102770516110, 6124614700109418394015479868364802242701607617022331053407860055904198372303)
s: 5913931568490670415167403882928995927013980682920257322018493566092996320335
----------------------
Verification:
P1: (40818680923608013749810479295591963176703886930564418008205554396446644319015, 44498286193320509267292912981592384981299875231358685914855908954560863574804)
P2: (22127732144030507281801558594873111142735100467255546766890243812610015646385, 31529345553934565193000742415962965486373501712473925645349609093291139946946)
----------------------
Result
Signature verification failed!   

说明

• Python 代码首先生成公钥和私钥。
• 接下来，将消息转换为整数并完成计算。
• r 和 s 的值是使用哈希方法找到的。
• 接下来，执行签名过程。
• 点 p1 和 p2 的值是使用 ApplyDoubleAndAdd 函数确定的。
• 如果点 p1 和 p2 相等，则签名有效；否则无效。

ECDSA 的一些优点

1. 更高的安全性： 它是一种基于公钥密码学 (PKC) 的非常强大的方程。ECDSA 广泛用于加密消息应用程序，是比特币安全的基础。小密钥比大密钥更好有几个原因。小密钥简化了数学运算，因此更快的算法可以生成签名。
2. 良好的应用功能： ECDSA 数字签名技术使用 ECC 来生成数字签名签发和验证所需的密钥对。由于其优于其他公钥方法的优点，ECC 常用于区块链应用程序中对交易或事件进行签名。
3. 高验证速度： 验证 ECDSA 签名的过程有三个输入：已签名消息 (msg)，签名 (r)（由签名算法生成），以及公钥 (pubKey)（相当于签名者的私钥）。结果是一个布尔值，有效或无效。
4. 鼓励遵守政府标准： 数字签名算法 (DSA) 标准包含在美国政府的联邦信息处理标准 (FIPS) 数字签名标准 (DSS) 中。离散对数问题 (DLP) 的安全性基于其在 Z 的素数阶子群中的计算不可解性。
5. 符合现代要求： ECC 符合 FIPS 标准，因为除了 RSA 和 DSA 之外，ECDSA 是 FIPS 140-2 中用于非对称密钥函数的 FIPS 批准方法之一。它是一种基于公钥密码学 (PKC) 的非常强大的方程。

ECDSA 的局限性

1. 标准曲线： 安全实现很难，尤其是在处理标准曲线时。与 ECDSA 相比，Schnorr 签名是一个 hack，而 ECDSA 是过时的现代标准之一。
2. 签名验证错误： 如果使用有缺陷或损坏的随机数生成器进行签名，则密钥会受到损害。仍然存在一些专利问题，尤其是在二元曲线方面。这可能花费很多钱。
3. 曲率问题： 它仍然存在一些专利问题，尤其是在二元曲线方面。这可能花费很多钱。量子计算研究的不断发展与椭圆曲线使用的日益增长发生了冲突。
4. 加密过程的范围： ECC 加密相对于 RSA 加密的主要缺点是加密的消息变得大得多。此外，与 RSA 相比，ECC 算法更难实现和复杂，这增加了实现错误的可能性，并降低了该方法的安全性。
5. 相同的随机值： 使用 ECDSA 签名获得的比特币私钥。缺点之一是多次消息中使用相同的 nonce 值。

ECDSA 应用

• 像比特币这样的依赖 ECDSA 的系统是一个很好的例子。每个比特币地址是通过密码学哈希一个 ECDSA 公钥生成的。账户的实际所有者是拥有 ECDSA 私钥的人。
• 这意味着 ECDSA 和 RSA 可以用更少的密钥提供同等的安全级别。小密钥比大密钥更好有几个原因。小密钥简化了数学运算，因此更快的算法可以生成签名。
• 更小的公钥意味着更小的证书；因此，为了建立 TLS 连接，需要传输的数据更少。这导致更快的网站加载速度和更快的连接速度。

结论

• 离散对数问题有解： ECDSA 的主要缺点是，对于正确椭圆曲线上的椭圆曲线，离散对数问题没有次指数解。因此，DSA 中的离散对数问题和底层的整数分解是最难解决的，需要完全指数时间。
• 更快的处理： 更小的密钥尺寸提供了多种优势，例如更快的计算时间以及更低的处理器、存储和带宽需求。因此，ECDSA 非常适合受限环境，例如寻呼机、PDA、手机和支付系统中的环境。在带宽、存储、CPU 性能或功耗受限的其他场景中，这些优势尤其值得注意。
• 更高的安全性： 在处理器性能、存储空间、带宽或功耗受限的其他场景中，优势也同样值得注意。由于上述特性，互联网通信更安全，可以用于电子商务和其他用途，而无需过多担心黑客活动。