4.5 椭圆曲线密码学ECC – lmn

好想告诉你

1年前发布

270

4.4 椭圆曲线密码学ECC

大部分人对 RSA 公钥密码学算法有基本的了解，从课本上、科普上等都能看到 RSA 的重要性，但是对椭圆曲线密码学了解就微乎其微，但是移动电子商务服务中，椭圆曲线密码学运用更多。

0x01 椭圆曲线加密算法概要

ECC（Elliptic curve cryptography），官方命名“椭圆曲线密码学”，也称为我们理解的椭圆曲线加密算法，是一种基于椭圆曲线数学的建立公开密钥加密的算法，也是一种非对称加密算法。

Address: https://i.ytimg.com/vi/-UcCMjQab4w/maxresdefault.jpg

在了解椭圆曲线加密算法前，首先先了解一下椭圆曲线。

椭圆曲线是域上亏格为1的光滑射影曲线，它的(仿射)方程，通常称为维尔斯特拉斯方程，可以写成

如果这个域的特征不等于2和3，则可以改写成

Address: https://avinetworks.com/wp-content/uploads/2020/02/elliptic-curve-cryptography-diagram.png

椭圆曲线上的点全体构成一个加法群，点与点之间的“加法”运算，正因为椭圆曲线存在加法结构，所以它包含了很多重要的数论信息。

总的来说，ECC 是一种公钥密码系统，就像之前的 RSA 一样。ECC 的设计和开发是为了克服 RSA 算法的弱点，即索引演算。指数微积分是一种算法的花哨的“数学语言”，它使用数学过程来降低素数分解计算的难度，从而降低或破坏 RSA 的效率。

1985 年，一位名叫维克多·米勒 (Victor Miller) 的数学家研究了密码学中的椭圆曲线，并假设指数微积分方法极不可能在椭圆曲线方面起作用，椭圆曲线密码算法在 2004 年到 2005 年开始广泛使用。

椭圆曲线密码学（ECC）是一种基于有限域上椭圆曲线代数结构的公钥密码学方法ECC，允许使用更小的密钥来提供等效的安全性。

椭圆曲线适用于密钥协商、数字签名、伪随机生成器等任务，它们可以通过将密钥协议与对称加密方案相结合来用于加密。椭圆曲线也用于几种基于椭圆曲线的整数分解算法，这些算法在密码学中的应用，例如Lenstra椭圆曲线分解。

0x02 椭圆曲线密码学深入理解

椭圆曲线是非奇异（不与自身交叉且没有尖点）三次曲线，至少有一个点称为中性元素“O”。字段的示例可以是：复数、实数或有理数，并且点 ‘O’ 具有这样的特性，即在使用数字执行函数时，会给出中性元素。

‘O’ 与无穷大有密切关系，它的性质是阿贝尔群函数的一部分。

阿贝尔群（Abelian Group），又称交换群或加群，它由自身的集合 G 和二元运算 * 构成。它除了满足一般的群公理，即运算的结合律、G 有单位元、所有 G 的元素都有逆元之外，还满足交换律公理。因为阿贝尔群的群运算满足交换律和结合律，群元素乘积的值与乘法运算时的次序无关。

阿贝尔群的概念是抽象代数的基本概念之一，其基本研究对象是模和向量空间。阿贝尔群的理论比其他非阿贝尔群简单。

0x02 椭圆曲线特性

椭圆曲线密码学优点：
采用更小的密钥，减少了存储和传输要求；

椭圆曲线组可以提供与基于RSA的系统所提供的相同级别的安全性，具有较大的模数和相应的较大密钥；
例如，256 位椭圆曲线公钥应提供与 3072 位 RSA 公钥相当的安全性。

0x03 椭圆曲线的加法

在曲线上，过 P、Q 两点画一条直线
找到直线与椭圆曲线的交点
交点关于x轴对称位置的点，定义为 P + Q ，即为加法
P + Q = R

Address: @peterreid_12788/part-2-is-elliptic-curve-cryptography-ecc-a-step-towards-something-more-understanding-ecc-3c933d3922e”target=”_blank””>https://medium.com/@peterreid_12788/part-2-is-elliptic-curve-cryptography-ecc-a-step-towards-something-more-understanding-ecc-3c933d3922e

0x04 椭圆曲线密码学与RSA区别

RSA 和 ECC 加密密钥之间存在显著的差异，下面列出了提供相同安全级别所需的密钥大小。
换言之，384 位的椭圆曲线加密密钥与 7680 位的 RSA 具有相同的安全级别。

RSA 密钥长度（位）

1024
2048
3072
7680
15360

ECC 密钥长度（位）

ECC 密钥和 RSA 密钥的大小之间没有线性关系。也就是说，两倍大的 RSA 密钥大小不会转换成两倍的 ECC 密钥大小，ECC 密钥的生成和签名比 RSA 快得多，而且 ECC 使用的内存比 RSA 少。

此外，与 RSA 中两者都是整数不同，在 ECC 中，私钥和公钥不能同等交换，公钥是曲线上的一个点，而私钥仍然是整数。

快速比较 ECC 和 RSA 算法的优缺点如下所示：

ECC 具有更小的密文、密钥和签名，以及更快的密钥和签名生成。它的解密和加密速度适中。
通过分两个阶段计算签名，ECC 实现了比反向吞吐量更低的延迟。
ECC 具有用于经过身份验证的密钥交换的强大协议，并且对该技术的支持非常强大。
ECC 的主要缺点是不易安全实施。与在验证和加密方面都简单得多的 RSA 相比，ECC 的学习曲线更陡峭，累积可操作结果的速度也稍慢一些。
RSA 的缺点是：RSA 的密钥生成速度很慢，解密和签名也很慢，这并不总是那么容易安全地实现。

0x05 椭圆曲线数字签名

椭圆曲线数字签名算法 (ECDSA)
使用 ECC 密钥来确保每个用户都是唯一的并且每笔交易都是安全的。
尽管这种数字签名算法 (DSA) 提供的结果在功能上与其他 DSA 没有区别，但它使用 ECC 所期望的较小密钥，因此效率更高。

0x06 椭圆曲线密码学的应用

ECC 是加密货币中数字签名最常用的实现技术之一。
比特币和以太坊都专门应用椭圆曲线数字签名算法 (ECDSA) 来签署交易。
然而，ECC 不仅仅用于加密货币。它是一种加密标准，由于其更短的密钥长度和效率，将被大多数 Web 应用程序使用。

0x07 椭圆曲线密码学安全性

椭圆曲线离散对数是支撑椭圆曲线密码学的难题。尽管进行了近三年的研究，数学家仍然没有找到一种算法来解决这个问题，改进了幼稚的方法。

换句话说，与因式分解不同，根据目前理解的数学，似乎没有捷径可以缩小基于此问题的陷门函数的差距。这意味着对于相同大小的数字，求解椭圆曲线离散对数比分解要困难得多。
由于计算量更大的难题意味着更强大的密码系统，因此椭圆曲线密码系统比 RSA 和 Diffie-Hellman 更难破解。

侧信道攻击

不同于大多数其他DLP系统，EC加法在2倍(P = Q)和一般加法(P≠Q)中明显不同，这取决于所使用的坐标系。
因此，使用固定模式窗口(又名comb)方法来对抗侧信道攻击是很重要的。也可以使用Edwards 曲线。

Edwards 曲线在密码学中的应用是由Daniel J. Bernstein和Tanja Lange开发的，Edwards 曲线是一类特殊的椭圆曲线，它的加倍和加法可以用相同的操作来完成ECC系统的另一个担忧是故障攻击的危险，特别是在智能卡上运行时

Address: https://en.wikipedia.org/wiki/File:Edward-curves.svg

后门

密码学专家对美国国家安全局在至少一个基于椭圆曲线的伪随机发生器中插入窃电后门表示担忧。前 NSA 承包商Edward Snowden泄露的内部备忘录表明，NSA 在Dual EC DRBG标准中设置了后门。对可能的后门分析得出的结论是，拥有算法秘密密钥的对手可以在仅给出 32 个字节的 PRNG 输出的情况下获得加密密钥。

量子计算攻击

Shor 算法可用于通过在假设的量子计算机上计算离散对数来破解椭圆曲线密码学。使用 Shor 算法破解RSA算法需要 4098 个量子位和 5.2 万亿个 Toffoli 门才能获得 2048 位 RSA 密钥，这表明 ECC 比 RSA 更容易成为量子计算机的目标。所有这些数字都大大超过了任何曾经建造的量子计算机，并且估计这些计算机的创建需要十年或更长时间。

References:
https://baike.baidu.com/
https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
https://zhuanlan.zhihu.com/p/101907402
https://avinetworks.com/glossary/elliptic-curve-cryptography/

评分

欢迎为Ta评分

赏点小钱