椭圆曲线密码学 (ECC) 是一种基于椭圆曲线数学的公开密钥加密算法。
它提供了一种执行密钥交换、数字签名和加密等加密操作的安全方式。 ECC 为 1977 年首次发布的 Rivest-Shamir-Adleman (RSA) 加密算法提供了一种替代性方案。
继续阅读，进一步了解椭圆曲线密码学，以及为何它被认为是最安全的加密形式。
ECC 和 RSA 之间有何区别？
在讨论 ECC 和 RSA 之间的区别之前，了解公钥加密算法的工作原理非常重要。
最基础的强加密算法是“活板门函数”。 虽然掉进一扇活板门非常容易，但重新回到外面却很难，因为活板门只朝一个方向摆动。
因此，要使加密算法有效且安全，用来加密信息的方法必须很简单，但几乎不可能在没有解密密钥的情况下解密。
ECC 和 RSA 都是利用高等数学函数实现的公钥加密算法。
公钥加密包括两个组成部分，公钥和私钥。
公钥对消息进行加密的方法是，通过数学算法将消息转换为一个极大的随机数字。
消息只能用私钥解密，私钥获取这一随机大数后，对其应用另一种不同的算法，相当于“撤销”了该原始消息。
ECC 和 RSA 背后的数学问题非常复杂，只能通过计算机解决。 RSA 算法背后的数学问题超出了本篇博文的涵盖范围，但重点在于 RSA 的安全性就建立在分解两个大素数乘积的的巨大难度之上。
让我们来复习一下，对 20 这样的数字进行因数分解的方法如下：
20 = 4 * 5 = 2 * 2 * 5 = 2^2 * 5
看起来很简单，对吧？
那么，现在来想象一下如何对一个长度超过 100 位的数字进行因数分解。
这就是为什么即使拥有公钥，要在素因数未知的情况下计算出私钥，所需的计算密集程度也是非常高的。
RSA 加密算法的问题
虽然 RSA 算法是非常强的加密方法，但并非没有问题。
对大数进行因数分解非常困难，但困难比过去小。
因数分解是微积分和其他高等数学的核心组成部分，因此数学家们已经花费了数个世纪的时间来寻找更简单的解法。
目前存在的有效的大数因数分解算法包括通用数域筛法 (General Number Field Sieve)，它是目前最著名的用于分解长度在 110 位以上的大数的算法。
与此同时，算力也在在以惊人的速度增长。 英特尔的联合创始人戈登·摩尔曾于 1965 年预测，芯片上的晶体管数量每两年就会增加一倍。 这一假说被称作“摩尔定律”，自 20 世纪 70 年代以来始终有效，甚至超额完成。 计算能力每两年翻一番 – 算力的价格也在不断下降。
由于分解极大整数所需的计算资源越来越容易获得，对普通人（包括网络犯罪分子）来说都处于可负担范围内，为适应变化的速度，RSA 密钥必须不断变大。
正因为如此，RSA 的加密和解密速度都相当慢，这使得它不适合加密大量信息，特别是在移动设备上。
于是 RSA 通常用于密钥交换和数字签名，而其中的实际数据则使用对称加密算法和较短的会话密钥进行加密。
与之相反，**椭圆曲线加密能够以更短的密钥长度提供更出色的安全性，**因而从计算和带宽需求来看具有更高的效率。 在下一节中，我们将介绍 ECC 的工作原理。
椭圆曲线加密算法的工作原理是什么？
ECC 基于另一个称为椭圆曲线的高等数学领域。 椭圆曲线是由方程 y2 = x3 + ax + b 描述的曲线，其中 a 和 b 为常量，且该曲线的定义域是有限域。 绘制出的图形如下：
椭圆曲线具有的一些特殊性质，使它们对于数学家和密码学家而言既有趣又实用。 首先，椭圆曲线具有水平对称性。 位于 x 轴（水平轴）两侧的部分一模一样，就如同镜像。
此外，任意不垂直于椭圆曲线的直线与曲线的交点总是不超过三个。 在下面的示例中，这些点被标记为 P、Q 和 R。
椭圆曲线加密算法的安全性基于求解椭圆曲线离散对数问题的难度。 在给定曲线上的点 P 和标量 k 的情况下，要确定一个能够令 Q = k*P 的点 Q 非常困难 – 比因数分解一个极大整数要困难得多。
这一特性意味着 ECC 可以在密钥大小远小于 RSA 的前提下，提供与 RSA 相当甚至更可靠的安全性。
椭圆曲线加密算法的优势
ECC 能够以较短的密钥提供极高的安全性，这一点使其优于 RSA 和其他公钥加密算法。
使用椭圆曲线加密算法有以下两个优势。
- ECC 生成密钥、加密和解密所需的计算资源和带宽都较低。
- 由于 ECC 的密钥大小较小，与 RSA 相比，ECC 的密钥生成、加密和解密等操作可以执行得更快，这意味着最终用户的延迟更小。
- 这些优势使 ECC 在资源有限的环境中尤其实用，例如手机和物联网 (IoT) 设备。
椭圆曲线加密算法的安全性如何？
虽然 RSA 加密算法具有极高的安全性，但 ECC 可以说是更胜一筹。
理论上，量子计算机或可有效解决 RSA 所依赖的因数分解问题，从而破解 RSA。 这种情况是否会很快成真，是一个很有争议的问题。 但我们可以肯定地说，考虑到 ECC 的复杂性，与 RSA 相比，它更能抵抗量子计算攻击。
有多大的抵抗能力？
荷兰数学家 Arjen Lenstra 在与他人合著的一篇研究论文中，将破解加密算法与烧水进行比较。
基本概念是计算出破解一个特定的加密算法需要多少能量，然后计算这些能量可以煮沸多少水。
通过这样的类比，破解一个 228 位 RSA 密钥所需的能量比煮沸一茶匙水所需的能量还少，但破解一个 228 位 ECC 密钥所消耗的能量可以煮沸地球上所有的水。
要达到相同的安全级别，RSA 密钥的长度需要达到 2380 位。
椭圆曲线加密算法的用武之地
如前所述，ECC 的密钥较小，因而尤其适合 CPU 和内存资源较低的设备，如移动设备和物联网设备。
这有助于 Web 和移动应用程序开发人员构建高性能、低延迟的网站和应用程序，同时为用户提供强大的数据安全性。 ECC 常常被用于保护蓝牙、Wi-Fi 和近场通信 (NFC) 等无线移动通信协议。
以下是一些更常见的 ECC 使用案例：
- 安全通信协议：ECC 被用于各种安全通信协议，以提供加密、数字签名和密钥交换。 例如，用于安全网页浏览的传输层安全性 (TLS)，用于安全远程登录的安全外壳 (SSH)，以及用于安全网络通信的虚拟专用网络 (VPN)。
- 加密货币和区块链技术：比特币、以太币和莱特币等许多加密货币都利用椭圆曲线加密来生成公钥和私钥对，以及签署交易。 ECC 能够提供保护数字资产和确保区块链网络完整性所需的加密安全性。
- 智能卡和嵌入式系统：ECC 通常被用于保护支付系统、门禁系统、电子护照和其他需要既安全又小巧的加密解决方案的应用。
- 数字签名和证书：ECC 可以用于生成数字签名，用于验证数字文档和消息的真实性和完整性。 基于 ECC 的数字签名还被部署在公钥基础设施 (PKI) 系统中，用于发放和验证数字证书。
- 虽然与 RSA 相比，ECC 的历史还很短，但已充分标准化，并得到来自私营部门组织和行业机构的广泛支持。 例如，美国国家标准与技术研究院 (NIST) 在其加密算法套件中对 ECC 进行了标准化。 此外，流行的加密库、编程语言和操作系统也为 ECC 提供支持。 这一接受度进一步促进了金融、医疗和政府服务等众多部门对其的采用。
考虑到这些因素，我们可以肯定地说，椭圆曲线加密算法广受欢迎，并在众多应用和行业中得到了普遍的采用。 它的效率、安全性和广泛的支持使其成为安全通信和加密操作的可靠选择。
ECC 密钥对生成
首先，跟 RSA 一样，让我们先看下怎么使用 openssl 生成一个使用 prime256v1 曲线的 ECC 密钥 对：
# 列出 openssl 支持的所有曲线名称 openssl ecparam -list_curves # 生成 ec 算法的私钥，使用 prime256v1 算法，密钥长度 256 位。（强度大于 2048 位的 RSA 密钥） openssl ecparam -genkey -name prime256v1 -out ecc-private-key.pem # 通过密钥生成公钥 openssl ec -in ecc-private-key.pem -pubout -out ecc-public-key.pem # 查看私钥内容 ❯ cat ecc-private-key.pem -----BEGIN EC PARAMETERS----- BggqhkjOPQMBBw== -----END EC PARAMETERS----- -----BEGIN EC PRIVATE KEY----- MHcCAQEEIGm3wT/m4gDaoJGKfAHDXV2BVtdyb/aPTITJR5B6KVEtoAoGCCqGSM49 AwEHoUQDQgAE5IEIorw0WU5+om/UgfyYSKosiGO6Hpe8hxkqL5GUVPyu4LJkfw/e 99zhNJatliZ1Az/yCKww5KrXC8bQ9wGQvw== -----END EC PRIVATE KEY----- # 查看私钥的详细参数 ❯ openssl ec -noout -text -in ecc-private-key.pem read EC key Private-Key: (256 bit) priv: 69:b7:c1:3f:e6:e2:00:da:a0:91:8a:7c:01:c3:5d: 5d:81:56:d7:72:6f:f6:8f:4c:84:c9:47:90:7a:29: 51:2d pub: 04:e4:81:08:a2:bc:34:59:4e:7e:a2:6f:d4:81:fc: 98:48:aa:2c:88:63:ba:1e:97:bc:87:19:2a:2f:91: 94:54:fc:ae:e0:b2:64:7f:0f🇩🇪f7:dc:e1:34:96: ad:96:26:75:03:3f:f2:08:ac:30:e4:aa:d7:0b:c6: d0:f7:01:90:bf ASN1 OID: prime256v1 NIST CURVE: P-256 # 查看公钥内容 ❯ cat ecc-public-key.pem -----BEGIN PUBLIC KEY----- MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAE5IEIorw0WU5+om/UgfyYSKosiGO6 Hpe8hxkqL5GUVPyu4LJkfw/e99zhNJatliZ1Az/yCKww5KrXC8bQ9wGQvw== -----END PUBLIC KEY----- # 查看公钥的参数 ❯ openssl ec -noout -text -pubin -in ecc-public-key.pem read EC key Private-Key: (256 bit) pub: 04:e4:81:08:a2:bc:34:59:4e:7e:a2:6f:d4:81:fc: 98:48:aa:2c:88:63:ba:1e:97:bc:87:19:2a:2f:91: 94:54:fc:ae:e0:b2:64:7f:0f🇩🇪f7:dc:e1:34:96: ad:96:26:75:03:3f:f2:08:ac:30:e4:aa:d7:0b:c6: d0:f7:01:90:bf ASN1 OID: prime256v1 NIST CURVE: P-256
可以看到 ECC 算法的公钥私钥都比 RSA 小了非常多，数据量小，却能带来同等的安全强度，这是 ECC
相比 RSA 最大的优势。
私钥的参数：
- priv: 私钥，一个 256bits 的大整数，对应我们前面介绍的 k 倍运算 k 倍运算k倍运算中的 $k
- pub: 公钥，是一个椭圆曲线（EC）上的坐标 x , y {x, y}x,y，也就是我们 well-known 的基点 $G
- ASN1 OID: prime256v1, 椭圆曲线的名称
- NIST CURVE: P-256
使用安全随机数生成器即可直接生成出 ECC 的私钥 priv，因此 ECC 的密钥对生成速度非常快。
八、椭圆曲线加解密算法原理
设私钥、公钥分别为d、Q，即Q = dG，其中G为基点，椭圆曲线上的已知G和dG，求d是非常困难的，也就是说已知公钥和基点，想要算出私钥是非常困难的。
- 公钥加密：选择随机数r，将消息M生成密文C，该密文是一个点对，C = {rG, M+rQ}，其中Q为公钥。
- 私钥解密：M + rQ - d(rG) = M + r(dG) - d(rG) = M，其中d、Q分别为私钥、公钥。
九、椭圆曲线签名算法原理
椭圆曲线签名算法(ECDSA)。设私钥、公钥分别为d、Q，即Q = dG，其中G为基点。
私钥签名：
- 选择随机数r，计算点rG(x, y)。
- 根据随机数r、消息M的哈希h、私钥d，计算s = (h + dx)/r。
- 将消息M、和签名{rG, s}发给接收方。
公钥验证签名：
- 接收方收到消息M、以及签名{rG=(x,y), s}。
- 根据消息求哈希h。
- 使用发送方公钥Q计算：hG/s + xQ/s，并与rG比较，如相等即验签成功。
原理：hG/s + xQ/s = hG/s + x(dG)/s = (h+xd)G/s = r(h+xd)G / (h+dx) = rG
10、签名过程
假设要签名的消息是一个字符串：“Hello World!”。DSA签名的第一个步骤是对待签名的消息生成一个消息摘要，不同的签名算法使用不同的消息摘要算法，而ECDSA256使用SHA256生成256比特的摘要。
摘要生成结束后，应用签名算法对摘要进行签名：
- 产生一个随机数k
- 利用随机数k，计算出两个大数r和s。将r和s拼在一起就构成了对消息摘要的签名。
这里需要注意的是，因为随机数k的存在，对于同一条消息，使用同一个算法，产生的签名是不一样的。从函数的角度来理解，签名函数对同样的输入会产生不同的输出。因为函数内部会将随机值混入签名的过程。
11、验证过程
关于验证过程，这里不讨论它的算法细节。从宏观上看，消息的接收方从签名中分离出r和s，然后利用公开的密钥信息和s计算出r。如果计算出的r和接收到的r值相同，则表示验证成功，否则，表示验证失败。
12、工具
推荐一个在线ECC加密解密且可生成公钥私钥对的工具：在线ECC公钥私钥对生成，公钥加密/私钥解密
