Elliptic Curve Cryptography (ECC)
Table of Contents
1. 实数域上的椭圆曲线
在实数域上,椭圆曲线(Elliptic curve)的定义(“Weierstrass Normal Form”形式)如下:
当
Figure 1: 当
除 Weierstrass Normal Form 外,还有 Weierstrass Long Form,它可表示为
1.1. 椭圆曲线上的加法运算
前面我们已经展示过几个椭圆曲线的图像,但点与点之间好像没有什么联系。我们能不能建立一个类似于在实数轴上加法的运算法则呢?数学家们定义了一个这样的运算法则。
椭圆曲线上两个点“加法”算法的定义: 任意取椭圆曲线上两点
Figure 2: 加法实例(不同点相加):
Figure 3: 加法实例(相同点相加):
注 1:我们称
注 2:
Figure 4:
1.2. 加法运算公式
前面介绍了椭圆曲线上加法运算的定义,这节介绍它的计算公式。需要注意的是椭圆曲线上的加法不是实数中普通的加法,而是从普通加法中抽象出来的加法,他具备普通加法的一些性质,但其运算规则显然与普通加法不同。
设有椭圆曲线
把点
由椭圆曲线上加法运算的定义知,
求解方程组可得
当点
总结,椭圆曲线
上式中,当点
1.2.1. 加法运算实例
设有椭圆曲线
解:设
从而
Figure 5:
现在设
从而
Figure 6:
注:图 5 和图 6 摘自:https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html
2. 密码学中的椭圆曲线
前面介绍的椭圆曲线是连续的(点的两个坐标均定义在
这种连续的椭圆曲线并不适合用于加密(如连续的椭圆曲线中容易出现浮点数,可能有计算误差等问题)。在密码学中,我们把椭圆曲线定义在有限域
在密码学中,我们把椭圆曲线定义为:
注 1:
注 2: 上式定义的椭圆曲线是离散的点,一点都不像椭圆 ,下面给出几个具体的例子。
取
Figure 7: Elliptic curve
图 7 中取两点
再看一个例子,取
Figure 8: Elliptic curve
2.1. 从椭圆曲线到“群”
在近世代数中,“群”是集合再加上集合上一个二元运算(比如加法)满足下面条件后组成的代数结构:
- 封闭性:
- 结合律:
- 具有单位元:
- 都有逆元素:
把上一节中椭圆曲线所对应的离散点作为群的集合,仿照实数域椭圆曲线加法运算的定义(参见节 1.1 ),我们把群上的二元运算记为
当
设
现在考察椭圆曲线上是否具有“单位元”,即是否存在点
事实上, 椭圆曲线满足上面条件的点
现在考察椭圆曲线上每个点是否都有“逆元素”,即对每一个点
答案是肯定的,
比如,按上面公式可求椭圆曲线
2.2. Elliptic Curves over Finite Fields
2.2.1. 实例: 上的椭圆曲线
根据定义,我们容易计算出这 9 个点的加法表,如图 9 所示(摘自 An Introduction to Mathematical Cryptography, Second Edition 6.2 节 Elliptic Curves over Finite Fields)。
Figure 9: Addition table for E:
2.3. 椭圆曲线上有多少个点(群的阶)
椭圆曲线,如
对于有限素域
2.3.1. Hasse 定理
Hasse's theorem 表明有限素域
比如,前面介绍的
2.4. 标量乘法和循环子群
我们定义下面记号:
定义
我们可以发现,
可以证明
2.4.1. Generator 的选择
在循环子群中,除
2.4.2. 循环子群的元素个数(子群的阶)
拉格朗日定理(Lagrange's theorem):设
上面定理阐述了子群的阶和群的阶的关系。
实例 1:椭圆曲线群
实例 2:椭圆曲线群
注:设
2.5. 离散对数问题
在椭圆曲线的循环子群中(设循环子群的阶为
如果要暴力求解
注:在 Digital Signature Algorithm(DSA)或者 Diffie-Hellman Key Exchange 算法中,我们也会说到“离散对数问题”,它指的是另一个问题:
3. Elliptic Curve Cryptography
3.1. Domain Parameters
使用基于椭圆曲线的密码学算法时,各个参与方首先需要约定好椭圆曲线的各个参数,它们被称为 Domain Parameters。
下面是 ECC 的 Domain Parameters:
- The prime
that specifies the size of the finite field.(注: 一般取很大的素数) - The coefficients
and of the elliptic curve equation. 到此,我们可以确定椭圆曲线群 了,参见节 2.2 - The base point (generator)
that generates our subgroup. 有了 Generator 后,我们可以确定 上的一个循环子群了,参见节 2.4 - The order
of the subgroup. 就是上一步得到的循环子群的元素个数 - The cofactor
of the subgroup. 这里 ,即 是椭圆曲线群 所包含的所有点的个数,由拉格朗日定理(参见节 2.4.2)可知, 一定是一个整数。显然,当 时,由 确定的椭圆曲线的所有点就是椭圆曲线群 本身,比如曲线 Secp256k1 的 就是 1。曲线 Curve25519 的 cofactor ,所以它的 Generator 得到的循环子群的元素个数是椭圆曲线群 元素个数的 。需要说明的是,当 时,有一些安全问题需要注意:比如可能遭受 Small-Subgroup Attack,还可能存在 Non-injective behavior/Covert channels/Implementation-defined behavior/Nontrivial modifications 等问题,具体可参考:Decaf: Eliminating cofactors through point compression, 1.1 Pitfalls of a cofactor。区块链 Monero 上出现过由于 而引起的安全漏洞,参考:Disclosure of a Major Bug in CryptoNote Based Currencies
一般使用
3.1.1. Random Curves (seed )
前面说过,椭圆曲线离散对数问题的困难的。这不完全正确,如当满足条件
为了减少潜在的风险,我们可以增加一个随机种子
3.1.2. 选择合适的椭圆曲线
关于选择椭圆曲线有很多不同的“标准”,如:
- ANSI X9.62 (1999).
- IEEE P1363 (2000).
- SEC 2 (2000).
- NIST FIPS 186-2 (2000).
- ANSI X9.63 (2001).
- Brainpool (2005).
- NSA Suite B (2005).
- ANSSI FRP256V1 (2011).
如何选择一个“安全的”?可参考:SafeCurves: choosing safe curves for elliptic-curve cryptography (注:Bitcoin 使用的 secp256k1 ,在该网页中被标记为 Unsafe)。
3.1.3. Secp256k1
Bitcoin 使用的椭圆曲线是 secp256k1 ,它的参数如下:
3.1.4. Secp256k1 VS. Secp256r1 (NIST P-256)
美国国家安全局建议使用的椭圆曲线是 secp256r1(也被称为 NIST P-256),secp256r1 使用的参数是:
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b x_G = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 y_G = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5 n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 h = 0x1
曲线 secp256k1 和 secp256r1 的名称只有一字之差,k 和 r 的不同。其中 k 表示 Koblitz(他是 ECC 发明人);而 r 表示随机,即参数是随机选取的,但美国国家安全局并没有公布随机数的挑选规则,所以外界一直存在疑虑,怀疑 NSA 可能对随机数生成器动过手脚,让破解难度大幅降低。
注 1:secp256r1 曲线还有其它的别名:prime256v1 或者 nist256p1 或者 NIST P-256,参考:https://www.ietf.org/rfc/rfc4492.html#appendix-A
注 2:在区块链领域,Secp256k1 使用更广泛;不过在区块链以外的其它领域,Secp256r1 使用更广泛,比如 Android/iOS 的硬件安全密钥都支持 Secp256r1,而不支持 Secp256k1。
3.2. Elliptic Curve Diffie-Hellman (ECDH)
下面介绍使用椭圆曲线进行密钥交换(Key Exchange)的过程,它是 Diffie-Hellman algorithm 算法的变种,一般称为 Elliptic curve Diffie-Hellman (ECDH)。
Alice 和 Bob 想进行通信,为了加密(基于效率考虑往往会采用对称密钥算法,如 AES 等)通信的数据,他们需要约定同一个密钥(称为“Shared Secret”)。
使用 ECDH 算法约定“Shared Secret”的过程(和 Diffie-Hellman 密钥交换算法基本类似)如下。
第一步,选择一个椭圆曲线(即确定 Domain parameters),你可以从 Standards for Efficient Cryptography, SEC 2: Recommended Elliptic Curve Domain Parameters 中选择一个推荐的参数。
第二步,为 Alice 和 Bob 分别生成 private key/public key。比如,Alice 生成 private key/public key 的过程如下:
1、从
2、计算
类似的过程,Bob 生成一个 private key/public key,分别记为
第三步,Alice 和 Bob 分别把自己的公钥传送给对方,传递过程被别人偷看也没关系,由公钥无法容易地计算出私钥。
第四步, Alice 用自己的私钥和 Bob 的公钥计算
3.2.1. Ephemeral ECDH (ECDHE)
如果通信双方不使用固定的 private key/public key,而是在建立连接时才动态生成各自的 private key/public key(注:这次通信结束,下次连接时重新生成各自的 private key/public key),这称为 Ephemeral ECDH (ECDHE)。
3.3. 公钥表达形式(Uncompressed and Compressed)
在椭圆曲线中,私钥
我们容易验证这个公钥确实是 secp256k1 曲线上的一个点:
Python 3.6.8 (default, Oct 7 2019, 12:59:55) [GCC 8.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f >>> x = 0x50863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B2352 >>> y = 0x2CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6 >>> y**2 % p - (x**3 + 7) % p 0
一般地,我们往往用“一个数”来表达椭圆曲线中的公钥,如何用一个数来表达两个坐标呢?有两种方案:“Uncompressed format”和“Compressed format”(Compressed format 有 ansiX962_compressed_prime 和 ansiX962_compressed_char2 标准,这里不介绍它们)。
下面介绍一下“Uncompressed format”,它的规则很简单,把 0x04
前缀即可。例如有:
则公钥(十六进制)可表示为:
Q = 0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6
3.4. Elliptic Curve Digital Signature Algorithm (ECDSA)
前面介绍了使用椭圆曲线进行密钥交换(Key Exchange)的过程,这里将介绍如何使用椭圆曲线进行数字签名,简称 ECDSA。ECDSA 是椭圆曲线应用于 DSA 的成果,其基本思路和 DSA 很相似。
数字签名的场景为:Alice 用他的私钥
3.4.1. ECDSA 签名及验证过程
本节介绍 ECDSA 签名及验证的具体过程(下一节将证明其正确性)。
假设 Alice 的私钥为
- 对原始消息计算哈希(需要使用 Cryptographic hash function),得到
,把 当做一个大整数; - 如果
的比特长度大于 ( 在 Domain parameters 中指定的循环子群的阶)的比特长度,则把截断 ,只留下左边和 同样比特长的部分,后文直接用 表示经过这样处理后的摘要消息,它是一个大整数。
Alice 签名过程:
- 从
中随机选择一个数,记为 ; - 计算
(其中 是 Domain parameters); - 计算整数
(其中 是上一步计算的点 的横坐标); - 如果
,则随机选择另外一个 ,重新计算前面两步; - 计算整数
(其中 是 Alice 的私钥, 是满足 的整数); - 如果
,则随机选择另外一个 ,重新计算前面步骤。
经常上面步骤得到的 整数对
Bob 验证签名的过程:
- 计算整数
(其中 是满足 的整数); - 计算整数
; - 计算点
(其中 是 Alice 的公钥)。 - 如果
(这里 是上一步计算的点 的横坐标)成立,则验证签名通过,否则验证失败。
3.4.1.1. ECDSA 正确性证明
3.4.1.2. 重复使用随机数 k 会导致私钥泄露
随机数
假设对
把上面两个式子中,只有
3.4.1.3. ECDSA Signature Malleability(一个签名修改后还是有效签名)
当
解决“签名延展性”的办法:
- 对于签名生成者:在生成完
后,检查 是否成立,如果成立则 就是签名数据;如果不成立则输出 为最终的签名数据。这样保证了最终输出的签名数据 一定满足 ,从而 具备了唯一确定性。 - 对于签名验证者:在验证签名时,只接受满足
的 ,拒绝 时的 ,这样保证了签名不再具有延展性。
参考:
https://github.com/bitcoin/bips/blob/master/bip-0062.mediawiki
https://github.com/ethereum/EIPs/blob/master/EIPS/eip-2.md
3.4.2. 从 ECDSA 签名数据中恢复公钥
可以从 ECDSA 签名数据中恢复出公钥,具体的算法如图 10 所示,摘自 SEC 1: Elliptic Curve Cryptography 中的 4.1.6 节 Public Key Recovery Operation。
Figure 10: 从签名中恢复公钥
图 10 所示算法中,有两个嵌套的
编程时,如何计算 Recovery Id 呢?可采用下面公式:
recid = R.y & 1; // Where (R.x, R.y) = k * G; if (s > curve.n / 2) recid = recid ^ 1; // i.e. if (s > curve.n - s) recid = recid ^ 1;
在有的 ECDSA 实现中增加了一个额外的
从签名中恢复公钥在带宽受限的环境中比较实用。
参考:
https://bitcoin.stackexchange.com/questions/83035/how-to-determine-first-byte-recovery-id-for-signatures-message-signing
https://ethereum.stackexchange.com/questions/42455/during-ecdsa-signing-how-do-i-generate-the-recovery-id
3.4.3. Deterministic ECDSA
在前面介绍的 ECDSA 中,有个一次一用的随机数
在 RFC6979 中定义了一种“确定性的”ECDSA,这个模式下,随机数
3.4.4. ECDSA VS. EC-Schnorr
设签名者的私钥为
ECDSA signing | EC-Schnorr signing |
---|---|
1. 选择随机数 |
1. 选择随机数 |
2. 计算 |
2. 计算 |
3. 计算 |
|
4. 计算 |
3. 计算 |
5. 输出签名 |
4. 输出签名 |
验证签名:检查 |
验证签名:检查 |
表 1 中,只有用户的私钥
EC-Schnorr 签名验证的正确性:
3.4.4.1. EC-Schnorr 签名的优点
EC-Schnorr 签名方案有一些 ECDSA 所没有的优点,比如 批量验证(Batch Validation)。 假设有 1000 个签名需要验证,则无需挨个验证,仅验证下面一个式子即可:
EC-Schnorr 签名方案还有其它一些优点,详情可参考:https://medium.com/cryptoadvance/how-schnorr-signatures-may-improve-bitcoin-91655bcb4744
3.4.4.2. EC-Schnorr 签名有各种不同方案
EC-Schnorr 签名有各种不同方案,如:
上面例子中 first component/second component 分别指签名数据的第 1/2 部分。
参考:https://crypto.stackexchange.com/questions/34863/ec-schnorr-signature-multiple-standard
3.5. ECDSA 的 Python 实现
下面是 ECDSA 的 Python 实现(注:pip 上已有现成的库 ecdsa):
#!/usr/bin/env python3 # -*- coding: utf-8 -*- # 代码摘自:https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdsa.py import collections import hashlib import random EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t gcd, x, y = old_r, old_s, old_t assert gcd == 1 assert (k * x) % p == 1 return x % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 def point_neg(point): """Returns -point.""" assert is_on_curve(point) if point is None: # -0 = 0 return None x, y = point result = (x, -y % curve.p) assert is_on_curve(result) return result def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p) x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p) assert is_on_curve(result) return result def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: if k & 1: # Add. result = point_add(result, addend) # Double. addend = point_add(addend, addend) k >>= 1 assert is_on_curve(result) return result # Keypair generation and ECDSA ################################################ def make_keypair(): """Generates a random private-public key pair.""" private_key = random.randrange(1, curve.n) public_key = scalar_mult(private_key, curve.g) return private_key, public_key def hash_message(message): """Returns the truncated SHA512 hash of the message.""" message_hash = hashlib.sha512(message).digest() e = int.from_bytes(message_hash, 'big') # FIPS 180 says that when a hash needs to be truncated, the rightmost bits # should be discarded. z = e >> (e.bit_length() - curve.n.bit_length()) assert z.bit_length() <= curve.n.bit_length() return z def sign_message(private_key, message): z = hash_message(message) r = 0 s = 0 while not r or not s: k = random.randrange(1, curve.n) x, y = scalar_mult(k, curve.g) r = x % curve.n s = ((z + r * private_key) * inverse_mod(k, curve.n)) % curve.n return (r, s) def verify_signature(public_key, message, signature): z = hash_message(message) r, s = signature w = inverse_mod(s, curve.n) u1 = (z * w) % curve.n u2 = (r * w) % curve.n x, y = point_add(scalar_mult(u1, curve.g), scalar_mult(u2, public_key)) if (r % curve.n) == (x % curve.n): return 'signature matches' else: return 'invalid signature' print('Curve:', curve.name) private, public = make_keypair() print("Private key:", hex(private)) print("Public key: (0x{:x}, 0x{:x})".format(*public)) msg = b'Hello!' signature = sign_message(private, msg) print() print('Message:', msg) print('Signature: (0x{:x}, 0x{:x})'.format(*signature)) print('Verification:', verify_signature(public, msg, signature)) # 验证通过 msg = b'Hi there!' # 使用不同的消息,会验证失败 print() print('Message:', msg) print('Verification:', verify_signature(public, msg, signature)) private, public = make_keypair() # 使用不同的公钥,会验证失败 msg = b'Hello!' print() print('Message:', msg) print("Public key: (0x{:x}, 0x{:x})".format(*public)) print('Verification:', verify_signature(public, msg, signature))
3.6. Elliptic Curve 加解密方案
3.6.1. Elliptic Curve Integrated Encryption Scheme (ECIES)
ECIES is a hybrid encryption system proposed by Victor Shoup in 2001. ECIES has been standardized in ANSI X9.63, IEEE 1363a, ISO/IEC 18033-2, and SECG SEC-1.
ECIES 方案是一种框架,并不是某个具体算法,如图 11 所示(摘自:https://cryptobook.nakov.com/asymmetric-key-ciphers/ecies-public-key-encryption )。
Figure 11: ECIES encryption scheme
四种 ECIES 标准的比较如图 12 所示(摘自 A Comparison of the Standardized Versions of ECIES )。
Figure 12: 四种 ECIES 标准
例如,Apple 的 Secure Enclave 支持的 SecKeyAlgorithm.eciesEncryptionCofactorVariableIVX963SHA256AESGCM 就是一种 ECIES 方案,参考:https://darthnull.org/secure-enclave-ecies/
3.6.1.1. ECIES 伪代码实现
下面是 ECIES 的伪代码实现:
# 下面是 ECIES 加密数据的过程 # Input: # pub_key 是接收者的公钥 # msg 是等待加密的消息 # Output: # ephemeral_pub_key 是临时公钥,接收者用它进行 ECDH 可以得到 AES 对称加密所用的密钥(具体来说就是接收者私钥乘以这个临时公钥) # iv 是 AES 算法的初始化变量 # tag 是消息认证码 # ciphertext 是密文 encrypt(pub_key, msg): ephemeral_pri_key, ephemeral_pub_key = gen_key(); shared_secret = ephemeral_pri_key * pub_key; // 这是 ECDH 计算临时 shared_secret 的过程,ECIES 的 KA 过程 iv = gen_random(); // AES 算法需要的 iv 值 // 注意:在实现 ECIES 时一般不会直接把上面的 shared_secret 当作 AES 的密钥; // 而是使用 X9.63 KDF 或者 HKDF https://en.wikipedia.org/wiki/HKDF 等 KDF 函数处理后,把结果当作 AES 密钥 // 不过,这个例子中省略了这个步骤 // aes gcm 本身是一种 AEAD 算法(这样不需要分别进行 ECIES 的 MAC/ENC 操作了),它的 tag 就是消息认证所需的 mac 值 ciphertext, tag = aes_gcm_encrypt(shared_secret, iv, msg); return ephemeral_pub_key, iv, tag, ciphertext # 下面是 ECIES 解密数据的过程 # Input: # pri_key 是接收者的私钥 # ephemeral_pub_key/iv/tag/ciphertext 是加密过程的输出,这里作为解密过程的输入 # Output: # plaintext 是解密后的明文 decrypt(pri_key, ephemeral_pub_key, iv, tag, ciphertext): shared_secret = pri_key * ephemeral_pub_key // 这是 ECDH 计算临时 shared_secret 的过程 // 注意:在实现 ECIES 时一般不会直接把上面的 shared_secret 当作 AES 的密钥; // 而是使用 X9.63 KDF 或者 HKDF https://en.wikipedia.org/wiki/HKDF 等 KDF 函数处理后,把结果当作 AES 密钥 // 不过,这个例子中省略了这个步骤 plaintext = aes_gcm_decrypt(shared_secret, iv, tag, ciphertext) return plaintext
3.6.2. Provably Secure Elliptic Curve encryption (PSEC)
Provably Secure Elliptic Curve encryption (PSEC) 是日本 NTT 实验室提出的一种基于椭圆曲线的公钥加密方案。
关于 PSEC 的标准文档,可以参考 Specifications for PSEC-KEM 或者 ISO/IEC 18033-2 。
3.6.3. Hybrid Public Key Encryption (HPKE)
Hybrid Public Key Encryption (HPKE) 是一个关于公钥加密的新标准,于 2022 年在 RFC 9180 中被标准化。
已经有了 ECIES,为什么还需要 HPKE 呢?这是因为 ECIES 标准提出比较早,其中有一些算法已经过时;加密和认证是通过 ENC/MAC 两个过程分开处理的,它没有使用 AEAD 这种更安全的方法;而且不能证明满足 IND-CCA2 安全,RFC 9180 中对 ECIES 的缺点是这样描述的:
All these existing schemes have problems, e.g., because they rely on outdated primitives, lack proofs of indistinguishable (adaptive) chosen-ciphertext attack (IND-CCA2) security, or fail to provide test vectors.
参考:
RFC 9180 Hybrid Public Key Encryption
HPKE: Standardizing public-key encryption (finally!)
3.6.4. NaCl crypto_box
NaCl 提出的 crypto_box 和 ECIES 有些类似,不过它们在一些底层算法上有很多不同,如表 2 所示。
crypto_box | ECIES | |
---|---|---|
密钥交换 | X25519 | ECDH |
对称加密 | XSalsa20 | AES |
消息认证 | Poly1305 | HMAC |
3.7. 其它坐标系
3.7.1. Jacobian 射影坐标(避免求逆运算)
笛卡尔坐标(Cartesian Coordinates)是一种特殊的仿射坐标(Affine Coordinates),下面的讨论将不区分这两种坐标。
在仿射坐标下,把椭圆曲线上的两个点相加会涉及到“求逆运算”,一般采用扩展欧几里得算法,但比较低效。如果采用“雅可比射影坐标(Jacobian Projective Coordinates)”,则椭圆曲线上的两个点相加运算可以避免求逆运算。OpenSSL 也使用了雅可比射影坐标表示点,参见 https://github.com/openssl/openssl/blob/OpenSSL_1_1_1-stable/crypto/ec/ec_local.h#L295
“雅可比射影坐标”和“仿射坐标”的转换关系为:
参考:https://en.wikipedia.org/wiki/Jacobian_curve#Addition_and_doubling_in_projective_coordinates
3.7.2. Edwards Coordinates
2007 年,Harold Edwards 在论文 A NORMAL FORM FOR ELLIPTIC CURVES 中提出椭圆曲线的新形式
同一年,Daniel J. Bernstein 和 Tanja Lange 在论文 Faster addition and doubling on elliptic curves 中对 Edwards form 进行了扩展
参考:Elliptic Curves Number Theory And Cryptography, Second Edition, 2.6.3 Edwards Coordinates
4. 参考
http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/
http://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/
An Introduction to Mathematical Cryptography, Second Edition