密码学基础---椭圆曲线一文打尽
1.ECC简介及密钥生成
当前公认安全有效的三大类公钥密钥体制分别为基于大数因子分解难题(RSA)、离散对数难题(DSA)和椭圆曲线离散对数（ECC）难题的密码体制。
最初RSA由于其容易理解被广泛运用，但随着计算机性能的提升，要保证RSA的安全性，则必须要增加密钥长度，所以我们可以看到RSA密钥从1024bits慢慢来到了4096bits。
由于汽车网络安全近几年才兴起，专为密钥存储设计的硬件资源有限，如果用RSA算法，密钥存储数量有限，而ECC(Elliptic Curve Cryptography)的出现有效弥补了这方面的缺憾，实现了密钥效率上的突破，根据NIST.SP.800-57pt1r5描述，对称算法和非对称算法的安全强度如下图所示：
图 安全性对比
可以看到，160bits的ECC密钥长度实现的安全强度等同于RSA 密钥长度1024bits，所以汽车行业越来越倾向使用ECC来实现验签、会话密钥协商等。
椭圆曲线离散对数问题如下定义：已知椭圆曲线E和点G，随机选择一个整数d，容易计算Q = d*G，但给定Q和G计算d就很困难。
基于上述定义，密钥生成的方法如下：
- 确定拥有素数阶n的点G(xG,yG)，建议使用标准中推荐的椭圆曲线；
- 在[1, n-1]中随机选择整数d作为私钥；
- 计算Q = d * G，得到公钥；
- 因此公钥为点G(x,y)，私钥为d；离散对数难解性保证了已知公钥Q的情况不能计算出私钥d。
2.椭圆曲线汇总
椭圆曲线是一个具有两个变量x、y的三次方程，满足公式：
的所有点(x,y)的集合，以及一个无穷远点O(y趋于无穷)。该公式也叫魏尔斯特拉斯方程（Weierstrass function），所有的曲线均属于该方程的变体。
例如，
针对素数有限域GF(P)的椭圆曲线是针对固定a、b，满足方程为：
的所有点(x，y)的集合，外加无穷远点O。
其中，a、b、x和y均在有限域GF(p)({0,1,...,p-1})上取值，满足4a^2+27b^3≠0,；p是大于3的素数，因此用Ep(a,b)表示。
针对阶为2m的有限域GF(2m)上的椭圆曲线是针对固定a、b，满足方程：
的所有点(x,y)的结合，再加上无穷远点O，
其中，a、b、x和y均能在有限域GF(2m)上取值，该域上的元素是m位的二进制串。
很明显，基于素域GF(p)对于软件计算比较友好，而基于二元扩域的GF(2^m)明显是硬件更有效率。
密钥生成时提到标准中推荐的曲线，主要从如下标准进行整理：
- SEC 2：Recommended Elliptic Curve Domain Parameters
- NIST SP800-186：Recommendations for Discrete Logarithm-based Cryptography
- Brainpool：Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation
- SM2椭圆曲线公钥密码算法
2.1 SEC 2
SEC 2由1998年成立的行业联盟SECG发布，该联盟全称The Standards for Efficient Cryptography Group，旨在指定商业标准，促进在密码学的高效和易操作性。
该联盟主要输出的标准叫做SEC(Standards for Efficient Cryptography)，包括如下内容:
- SEC 1: Elliptic Curve Cryptography, Version 2.0
- SEC 2: Recommended Elliptic Curve Domain Parameteres, Version 2.0
- SEC 4: Elliptic Curve Qu-Vanstone Implicit Certificates
其中，SEC 2列出了SEC 1以及其他ECC标准(如ANSI X9.62、ANSI X9.63、IEEE 1363、IEEE 1363a等)的中常见椭圆曲线参数，如下表2、表3所示。
| 曲线参数 | Strength | Size | RSA/DSA | Koblitz\Random |
| secp192k1 | 96 | 192 | 1536 | k |
| secp192r1 | 96 | 192 | 1536 | r |
| secp224k1 | 112 | 224 | 2048 | k |
| secp224r1 | 112 | 224 | 2048 | r |
| secp256k1 | 128 | 256 | 3072 | k |
| secp256r1 | 128 | 256 | 3072 | r |
| secp384r1 | 192 | 384 | 7680 | r |
| secp521r1 | 256 | 521 | 15360 | r |
表 基于素数域GF(p)的椭圆曲线
其中，每列参数解释如下：
- 上述曲线命名方式如下：
- Sec：Standards for Efficient Cryptography的简称；
- P：表示参数在素数有限域GF(p)；
- 后续数字：表示p的比特长度，例如192表示p的长度为192bit；
- K\R：表示参数是与Koblitz曲线(k)相关还是随机生成(r)
- Strength：表示密钥强度的大致位数，一般来讲近似为阶数的一半；
- Size：密钥长度；
- RSA\DSA：对应同等强度的RSA\DSA的密钥长度
- Koblitz\Random：
- Koblitz Curve来自数学家Neal Koblitz，它是一种特殊的曲线，参数是精心挑选设置，可以通过优化大幅提升计算效率；
- Random：可验证的随机种子产生的参数
- 末位数字：表示在当前曲线下的参数配置有几种，例如1就为1种推荐配置。
上述域参数用公式T = (p,a,b,G,n,h)进行表示，其中p为素数，a、b为椭圆曲线参数，G为拥有素数阶n的点G(xG,yG)，n为阶N与点G的比，h= N/n。
如下为secp256k1和secp256r1的推荐参数设置：
secp256k1：
- p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F = 2^256 -2^32-2^9 -2^8 -2^7 -2^6-2^4-1
- a=0
- b=7
- G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
- 非压缩G=04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
- n=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
- h = 01
secp256r1：
- p = FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF
- = 2^224 (2^32-1)+2^192 +2^96 -1
- a=FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC
- b=5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B
- 随机数种子：S = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90
- G = 03 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296
- 非压缩G=04 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5
- n=FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551
- h = 01
| 曲线参数 | Strength | Size | RSA/DSA | Koblitz\Random |
| sect163k1 | 80 | 163 | 1024 | k |
| sect163r1 | 80 | 163 | 1024 | r |
| sect163r2 | 80 | 163 | 1024 | r |
| sect233k1 | 112 | 233 | 2240 | k |
| sect233r1 | 112 | 233 | 2240 | r |
| sect239k1 | 115 | 239 | 2304 | k |
| sect283k1 | 128 | 383 | 3456 | k |
| sect283r1 | 128 | 283 | 3456 | r |
| sect409k1 | 192 | 409 | 7680 | k |
| sect409r1 | 192 | 409 | 7680 | r |
| sect571k1 | 256 | 571 | 15360 | k |
| sect571r1 | 256 | 571 | 15360 | r |
表 基于GF(2^m)的椭圆曲线
同样的，基于GF(2^m)的椭圆曲线参数命名除了在sec后的字母为t，其余均类似。
2.2 NIST SP800-186
NIST SP800-186同样也是收集了一大堆各个标准的推荐曲线，其中包括了FIPS 186-4推荐曲线、SEC 2 secp256k1、Brainpool曲线等等，推荐曲线的安全强度总结如下：
| 安全强度 | 推荐曲线 |
| 112 | P-224、K-233、B-233 |
| 128 | P-256, W-25519, Curve25519, Edwards25519, K-283, B-283 |
| 192 | P-384, K-409, B-409 |
| 224 | W-448, Curve448, Edwards448, E448 |
| 256 | P-521, K-571, B-571 |
表 推荐曲线及安全强度
其中，
- 基于prime fields GF(p)的曲线，称为P-xxx曲线；
- 基于Binary fields GF(2m)的曲线，称为B-xxx曲线；
- Koblitz曲线，称为K-xxx曲线；
- 维尔斯特拉斯曲线，称为W-xxx曲线；
- 蒙哥马利曲线(Montgomery Cureves)，包括Curve448、Curve25519
各曲线使用范围如下：
图 特定曲线的使用推荐
特别的，上述部分曲线与SEC 2的曲线推荐参数完全一致，仅在命名上有所不同，如下表所示：
| NIST | SEC 2 |
| P-192 | secp192r1 |
| P-224 | secp224r1 |
| P-256 | secp256r1 |
| P-384 | secp384r1 |
| P-521 | secp521r1 |
| K-163 | sect163k1 |
| K-233 | sect233k1 |
| K-283 | sect283k1 |
| K-409 | sect409k1 |
| K-571 | sect521k1 |
| B-163 | sect163r2 |
| B-233 | sect233r1 |
| B-283 | sect283r1 |
| B-409 | sect409r1 |
| B-571 | sect521r1 |
表 4 NIST和SEC 2曲线
工具中的曲线命名采用SEC 2命名方式，如下图：
图 推荐椭圆曲线
2.3 Brainpool
Brainpool是由德国的电子支付系统研究中心（ECRYPT II）和德国电信（Deutsche Telekom）联合开发的一系列椭圆曲线。它主要想解决NIST\SEC 2曲线以下几个方面的问题：
- 参数以可验证的伪随机数方式生成（特别是对B-xxx、P-xxx的随机数种子的生成方式），并满足安全要求（例如Dual_EC_DRBG后门事件）；
- 指定的域参数不包括所指定的所有位长度对应于对称的常用密钥长度加密算法。特别没有512位曲线定义，只有一个521位长度的曲线；
- 抵御侧信道攻击等
Brainpool曲线域参数长度位数包括160、192、224、256、320、384、512，曲线分为 brainpoolP160r1\t1、 brainpoolP192r1\t1、 brainpoolP224r1\t1、 brainpoolP256r1\t1、 brainpoolP320r1\t1、 brainpoolP384r1\t1、 brainpoolP512r1\t1
其中t1表示twisted curve，用于抵御侧信道攻击。
本程序仅实现用于TLS V1.3上所需的ECC Brainpool曲线，包括brainpoolP256r1、brainpoolP384r1、brainpoolP512r1。
根据标准，brainpoolP256r1推荐参数如下：
图 brainpoolP256r1域参数
其中，
- p为基域的素数；
- A、B满足方程y^2 = x^3 + A*x + B mod p的系数；
- G(x,y)为基点；
- q为G群的素数阶；
- h为阶p与G的余数，例如E(GF(p))/q。
2.4 SM2
SM2是国家密码局推出的自主可控的算法。示例曲线包括：
素域GF(P)上椭圆曲线：Fp-192、Fp-256，满足方程y^2 = x^3+ax+b，域参数如下：
二元扩域GF(2^m)曲线F2m -193、F2m -257，满足方程y^2+xy=x^3+ax^2+b。示例如下：
3.数字签名
数字签名可以直接提供消息来源的真实性、消息的完整性、消息的不可否认性。
常见方案为发送方使用Hash函数对消息进行摘要计算，然后使用私钥对摘要进行加密生成一个特定的签名值，然后将消息和签名一起发送给接收方；接收方首先对消息进行Hash计算得到摘要，然后使用发送方公钥对签名值进行解密，得到摘要值1，将摘要和摘要值进行比对，保证了消息的完整性、消息来源未被伪造，同时具备不可抵赖性，因为理论上只有发送方才有私钥进行签名。
可用于数字签名的算法和方案包括RSA、DSA、ECDSA、EdDSA。
- RSA：有简称RSASSA(来源RFC3447)，主要基于大数因子分解的难点，是最早的公钥密码体制之一；
- DSA(Digital Signature Algorithm)：仅用于对消息进行签名，其安全性基于计算离散对数的难度；
- ECDSA(Elliptic Curve Digital Signature Algorithm)：基于椭圆曲线的签名；
- EdDSA：Edwards Curve Digital Signature Algorithm
- Ed25519：使用EdDSA算法和Curve25519曲线来进行签名的
- Ed448：使用EdDSA算法进行签名