对TLS1.3中用到的ECC相关算法,比如ECDH, ECDSA, X25519等进行一下基础说明,起码知道group、curve之类的是什么意思。
1. 椭圆曲线(Elliptic Curves)
椭圆曲线的Weierstrass标准形式:
定义0表示椭圆曲线上的无限远点,这样组成的椭圆曲线是这样的:
2. 群(Group)
"加"
,用+
表示,集合中两个元素a和b,"加"
操作表示为
- 闭合性closure: a, b是
的元素, 也是; - 结合性associativity:
- 存在单位元identity element 0, 有
- 每个元素都有一个相反数,对每个元素a都存在b使
, b就是a的相反数,可以表示为
如果再加一条特性:
- 交换律:
这样的群就要阿贝尔群(Abelian Group)
这个”加+”操作,也可以用”乘*”来表示,这个操作只是表示集合上两个元素的一个操作,此时
也是 上的一个元素;- 单位元1,
, b可以表示为
在讨论ECC的时候,一些旧的文献通常用+
,新的通常用*
,另外,在密码学中讨论加密强度的时候,通常按照指数(幂)、读书来讨论,比如长听到取离散对数问题。本文都用+
来表示。
3. 椭圆曲线上的群
可以定义一个在椭圆曲线上的群
- 一个椭圆曲线上的点是
中的元素; - 单位元定义为无穷远处的点0
- 一个点P的相反数是关于x轴对称的点
加
定义为: 是斜率相同的点(一条直线跟椭圆曲线相交的3个点),有
这样就有
记
则:
这样,就能根据
4. 标量乘法
叫做标量乘法
.
有个快速算法:double and add
,
比如
就可以很方便的用计算机去算了。
5. 对数
对
如果用*
来表示,那就是
6. 有限域(Finite Field)
有限域,就是域中元素是有限个数的域,整个实数域是无限的,如果对实数取
域中多一个操作乘,符合结合律:
先了解mod运算
因为在域23上,
7. mod p 除法
要计算
取一个数的倒数用扩展欧几里得算法可以很简单算出来。
8. 有限域 中的椭圆曲线
先前的椭圆曲线是实数域上的,现在挑选其中在有限域
9. 有限域上的椭圆曲线的加法
还是
这样,有限域上的加法用计算机计算,公式是这样的
这样就可以用计算机计算
10. 一个椭圆曲线群的阶order
首先,一个群上的点的元素个数,叫做这个群的阶。
定义在一个有限域上的一个椭圆曲线的元素个数是多少呢?有个快速的算法可以计算: Schoof’s algorithm
。可以方便计算椭圆曲线在有限域上的元素个数。
11. 标量乘法和曲线子群
标量乘法是这样的
但在有限域上,我们可以想象出
得出的结果最终会形成一个循环,而且循环中的所有结果都在有限域上,这样,我们根据
现在我们梳理一下:
- 一开始我们有实数群
, - 我们取椭圆曲线,得出椭圆曲线上的点,形成一个小一点的群
- 接着定义有限域,然后将椭圆曲线限制到有限域上,这样框出来的椭圆曲线上的点,形成一个更小一点的群
- 最后,我们取其中一个点作为基准点,取基准点的向量倍数,生成一个再小一点的子群,这个群,就是我们的ECC要用的群了。
12. 子群的阶
我们想知道,由基准点Schoof’s
算法,它是工作在整个椭圆曲线上,而不是其中的一个子群。
要算子群的阶,需要知道:
- 子群的阶就是子群中的元素个数,等价于
,其 是正整数,且 是其中最小的1个,这个 就是子群的阶。 - 根据拉格朗日定理,子群
的阶,是父群阶的一个因子,比如一个椭圆曲线有 个元素,它的一个子群有 个元素, 能整除
接着我们开始算子群P的阶:
- 用
Schoof's
算法计算椭圆曲线的阶 - 找出
的所有因子 - 对
的每一个因子 ,计算 - 找出使
的最小的 ,这个 就是子群的阶.
比如对
那么就说,
13. 找一个基准点
对ECC算法来说,我们希望子群拥有更高的阶。
我们先计算椭圆曲线的阶
也就是说,我们先找子群的阶,再根据子群的阶找其中的基准点。而不是先找基准点,再算子群的阶。
再加一个信息:根据拉格朗日定理,
对一个椭圆曲线上的任意一点来说,
也就是
取
这样,我们就根据选择的阶
14. 离散对数
在连续的椭圆曲线上,我们如果知道
那么,
在有限域上的椭圆曲线,这个也是很多难的,叫做椭圆曲线的离散对数问题。
ECC有意思的一点是,这个离散对数问题“更难”,也就是要达到相同的加密强度,
15. 定义一个ECC的域需要的参数
- 有限域的大小是个素数
- 椭圆曲线中的系数
- 子群基准点
- 子群的阶
- 子群的协因子
所以,定义一个我们ECC需要的问题域需要6个因子
16. 随机曲线
并不是所有的椭圆曲线上的离散对数都那么难,比如Smart
方法攻击。而且我们也不知道还有没有哪些椭圆曲线的攻击方法我们没发现。
一个更具密码学强度的方法是,我们选一个随机因子
但是,NIST规定了一些
17. ECC算法
- 私钥就是从
( 是子群的阶)中随机挑选的一个整数 - 公钥就是点
( 是子群的基准点)
知道
这是个非对称加密算法,基于此,衍生出两个算法ECDH(用于密钥交换),ECDSA(用于签名)
18. ECDH
- Alice和Bob各自生成自己的公私钥,Alice的私钥是
, 公钥是 ,Bob的是 和 。注意Alice和Bob用的是同一个有限域上的同一个椭圆曲线的同一个基准点 - Alice和bob在一个未加密的通道上交换公钥
和 , - Alice计算
, Bob计算 , 两个计算出来的 是一样的
这样Alice和Bob就得出了同一个
一个例子
= 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f = 0 = 7 = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798 = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8 = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141 = 11
2
3
4
5
6Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bob's public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)
PS:每次都生成新的公私钥,就叫ECDHE,E表示Ephermeral,瞬时的,短暂的
19. ECDSA
Alice使用私钥
ECDSA需要对消息的摘要进行签名,而不是对任意长度的消息签名。消息摘要需要截断到跟子群的阶
签名:
- 从
( 是子群的阶)中随机选择一个整数 - 计算
( 是子群的基准点) - 计算
( 是 的x坐标) - 如果
,重新选择 - 计算
( 是Alice的私钥, 是 的乘法倒数 mod n) - 如果
,重新选择
验签:
- 计算
- 计算
- 计算点
如果 , 就说明签名正确
例子
1 | Curve: secp256k1 |
参考:
- https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ : 这个系列非常好,基本是翻译了这篇原文.
- RFC8442-Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS) Versions 1.2 and Earlier: 定义了TLS1.2及以前的协议使用的ECC曲线都有哪些,比如X25591,secp256r1等.
- RFC7748-Elliptic Curves for Security: 具体定义了X25519,X448曲线算法.
- RFC6090-Fundamental Elliptic Curve Cryptography Algorithms: ECC基本定义.
- Elliptic Curve Cryptography: openssl对ECC的解释,简单明了,值得一看