0%

ECC算法

对TLS1.3中用到的ECC相关算法,比如ECDH, ECDSA, X25519等进行一下基础说明,起码知道group、curve之类的是什么意思。

1. 椭圆曲线(Elliptic Curves)

椭圆曲线的Weierstrass标准形式:
y2=x3+ax+b
4a3+27b2!=0

定义0表示椭圆曲线上的无限远点,这样组成的椭圆曲线是这样的:
Missing or unrecognized delimiter for \left

2. 群(Group)

G是一个集合,在集合中定义一个对两个元素的操作,记为"加",用+表示,集合中两个元素a和b,"加"操作表示为a+b,如果a+b这个操作满足一下4个特性,G就是一个群(Group):

  • 闭合性closure: a, b是G的元素,a+b也是;
  • 结合性associativity: (a+b)+c=a+(b+c)
  • 存在单位元identity element 0, 有a+0=0+a=a
  • 每个元素都有一个相反数,对每个元素a都存在b使a+b=0, b就是a的相反数,可以表示为a

如果再加一条特性:

  • 交换律:a+b=b+a
    这样的群就要阿贝尔群(Abelian Group)

这个”加+”操作,也可以用”乘*”来表示,这个操作只是表示集合上两个元素的一个操作,此时

  • ab 也是 G 上的一个元素;
  • (ab)c=a(bc)
  • 单位元1, a1=1a=a
  • ab=1, b可以表示为a1

在讨论ECC的时候,一些旧的文献通常用+,新的通常用*,另外,在密码学中讨论加密强度的时候,通常按照指数(幂)、读书来讨论,比如长听到取离散对数问题。本文都用+来表示。

3. 椭圆曲线上的群

可以定义一个在椭圆曲线上的群G

  • 一个椭圆曲线上的点是G中的元素;
  • 单位元定义为无穷远处的点0
  • 一个点P的相反数是关于x轴对称的点
  • 定义为: P,Q,R是斜率相同的点(一条直线跟椭圆曲线相交的3个点),有P+Q+R=0

这样就有R=(P+Q),如果要用计算机去算,需要转换成代数的方法计算R的x,y坐标

P=(xP,yP),Q=(xQ,yQ),R=(xR,yR)
则:
m=yPyQxRxQ
xR=m2xPxQ
yR=yP+m(xRxP)
这样,就能根据P,Q算出R了。

4. 标量乘法

nP=P+P++Pn times
叫做标量乘法.
有个快速算法:double and add
比如 n=151, 用2进制表示为10010111b,然后
151=127+026+025+124+023+122+121+120 =27+24+22+21+20
就可以很方便的用计算机去算了。

5. 对数

Q=nP,如果知道nP,可以很容易算出Q(double and add), 但如果知道QP,却很难算出n——数学上没有很快的算法。
如果用*来表示,那就是Q=Pn,知道QP,很难算出指数n,这就是取对数难题,也是密码学中的基石。

6. 有限域(Finite Field)

有限域,就是域中元素是有限个数的域,整个实数域是无限的,如果对实数取 mod p,就可以得到元素个数为p的有限域了,
域中多一个操作乘,符合结合律:x(y+z)=xy+xz

先了解mod运算
(18+9) mod 23=4
5 mod 23=18
91 mod 23=18
因为在域23上,91=18(因为 918 mod 23=1,991mod23=1, 域上1个元素有且只有1个倒数,所以91=18,9的倒数是18)

7. mod p 除法

要计算xy,需要计算xy1,也是就是我们要先找到y的倒数,然后再乘上x
取一个数的倒数用扩展欧几里得算法可以很简单算出来。

8. 有限域GF(p)中的椭圆曲线

先前的椭圆曲线是实数域上的,现在挑选其中在有限域GF(p)上的点,就组成了椭圆曲线上的有限域——或者有限域上的椭圆曲线。

9. 有限域上的椭圆曲线的加法

还是P+Q+R=0,但PQ,R在有限域上怎么斜率相同呢?——在一条直线上即可。但有限域上的直线跟是实数域上有些不同,只要有限域中的点(x,y)符合ax+by+c( mod p)=0( mod p),就说这些点在同一条直线上——这样的直线画出来可能有很多并行的条,都算同一条直线。

这样,有限域上的加法用计算机计算,公式是这样的
xR=(m2xPxQ) mod p
yR=[yP+m(xRxP)] mod p=[yQ+m(xRxQ)] mod p

这样就可以用计算机计算P+Q=R

10. 一个椭圆曲线群的阶order

首先,一个群上的点的元素个数,叫做这个群的阶。
定义在一个有限域上的一个椭圆曲线的元素个数是多少呢?有个快速的算法可以计算: Schoof’s algorithm。可以方便计算椭圆曲线在有限域上的元素个数。

11. 标量乘法和曲线子群

标量乘法是这样的
nP=P+P++Pn times
但在有限域上,我们可以想象出
1P
2P
3P

得出的结果最终会形成一个循环,而且循环中的所有结果都在有限域上,这样,我们根据P生成了一个曲线子群,P就叫做这个子群的生成因子后者基准点。曲线子群就是ECC和其他加密系统的基础。

现在我们梳理一下:

  • 一开始我们有实数群G,
  • 我们取椭圆曲线,得出椭圆曲线上的点,形成一个小一点的群
  • 接着定义有限域,然后将椭圆曲线限制到有限域上,这样框出来的椭圆曲线上的点,形成一个更小一点的群
  • 最后,我们取其中一个点作为基准点,取基准点的向量倍数,生成一个再小一点的子群,这个群,就是我们的ECC要用的群了。

12. 子群的阶

我们想知道,由基准点P生成的子群的阶是多少。现在不能用Schoof’s算法,它是工作在整个椭圆曲线上,而不是其中的一个子群。
要算子群的阶,需要知道:

  1. 子群的阶就是子群中的元素个数,等价于 nP=0,其n是正整数,且n是其中最小的1个,这个n就是子群的阶。
  2. 根据拉格朗日定理,子群P的阶,是父群阶的一个因子,比如一个椭圆曲线有N个元素,它的一个子群有n个元素,n能整除N

接着我们开始算子群P的阶:

  1. Schoof's算法计算椭圆曲线的阶N
  2. 找出N的所有因子
  3. N的每一个因子n,计算nP
  4. 找出使nP=0的最小的n,这个n就是子群的阶.

比如对GP(37)有限域上的椭圆曲线 y2=x3x+3, 它的阶N=42,子群可能有的阶n=1,2,3,6,7,14,21,42, 如果我们取基准点P=(2,3),那么
P!=0,2P!=0,3P!=0,6P!=0,7P=0
那么就说,P的阶是n=7

13. 找一个基准点

对ECC算法来说,我们希望子群拥有更高的阶。
我们先计算椭圆曲线的阶N,找一个比较大的因子n,然后根据n找出一个合适的基准点。
也就是说,我们先找子群的阶,再根据子群的阶找其中的基准点。而不是先找基准点,再算子群的阶。

再加一个信息:根据拉格朗日定理,h=N/n肯定是个整数(因为nN的一个因子)。这个h叫做子群的协因子(cofactor).

对一个椭圆曲线上的任意一点来说, NP=0,因为N总是任何一个n的倍数;
也就是 n(hP)=0
n是素数,点G=hP生成一个阶为n的子群。
这样,我们就根据选择的阶n,算出了一个基准点。

14. 离散对数

在连续的椭圆曲线上,我们如果知道PQ很难算出k,使得Q=kP
那么,
在有限域上的椭圆曲线,这个也是很多难的,叫做椭圆曲线的离散对数问题。

ECC有意思的一点是,这个离散对数问题“更难”,也就是要达到相同的加密强度,k的位数可以更少。这也是有RSA,还有开发ECC的原因。

15. 定义一个ECC的域需要的参数

  1. 有限域的大小是个素数p
  2. 椭圆曲线中的系数a,b
  3. 子群基准点G
  4. 子群的阶n
  5. 子群的协因子h

所以,定义一个我们ECC需要的问题域需要6个因子p,a,b,G,n,h

16. 随机曲线

并不是所有的椭圆曲线上的离散对数都那么难,比如p=hn的椭圆曲线就可以用Smart方法攻击。而且我们也不知道还有没有哪些椭圆曲线的攻击方法我们没发现。
一个更具密码学强度的方法是,我们选一个随机因子S,对S取hash,然后衍生出ab或者G,或者两者都用S生成,那么攻击者就不知道我们用的是什么参数,会更安全些。
但是,NIST规定了一些S,我们也不知道S是不是精心挑选的。。。。。。

17. ECC算法

  1. 私钥就是从[1,n1](n是子群的阶)中随机挑选的一个整数d
  2. 公钥就是点H=dG(G是子群的基准点)

知道dG,算出H很简单,但反过来就很难。
这是个非对称加密算法,基于此,衍生出两个算法ECDH(用于密钥交换),ECDSA(用于签名)

18. ECDH

  1. Alice和Bob各自生成自己的公私钥,Alice的私钥是dA, 公钥是HA=dAG,Bob的是dBHB=dBG。注意Alice和Bob用的是同一个有限域上的同一个椭圆曲线的同一个基准点G
  2. Alice和bob在一个未加密的通道上交换公钥HAHB,
  3. Alice计算S=dAHB, Bob计算S=dBHA, 两个计算出来的S是一样的

这样Alice和Bob就得出了同一个S,就可用于对称加密了。

一个例子

  • p = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f
  • a = 0
  • b = 7
  • xG = 0x79be667e f9dcbbac 55a06295 ce870b07 029bfcdb 2dce28d9 59f2815b 16f81798
  • yG = 0x483ada77 26a3c465 5da4fbfc 0e1108a8 fd17b448 a6855419 9c47d08f fb10d4b8
  • n = 0xffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141
  • h = 1
    1
    2
    3
    4
    5
    6
    Curve: 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使用私钥dA签名消息,Bob使用Alice的公钥HA验签。
ECDSA需要对消息的摘要进行签名,而不是对任意长度的消息签名。消息摘要需要截断到跟子群的阶n一样长度的位数,截断的摘要用作为一个整数z

签名:

  1. [1,n1](n是子群的阶)中随机选择一个整数k
  2. 计算P=kGG是子群的基准点)
  3. 计算r=xP mod n(xPP的x坐标)
  4. 如果r=0,重新选择k
  5. 计算s=k1(z+rdA) mod ndA是Alice的私钥,k1k的乘法倒数 mod n)
  6. 如果s=0,重新选择k

(r,s)组成的对儿就是签名

验签:

  1. 计算u1=s1z mod n
  2. 计算u2=s1r mod n
  3. 计算点P=u1G+u2HA
    如果r=xP mod n, 就说明签名正确

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)

Message: b'Hello!'
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)
Verification: signature matches

Message: b'Hi there!'
Verification: invalid signature

Message: b'Hello!'
Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)
Verification: invalid signature

参考:

  1. https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ : 这个系列非常好,基本是翻译了这篇原文.
  2. RFC8442-Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS) Versions 1.2 and Earlier: 定义了TLS1.2及以前的协议使用的ECC曲线都有哪些,比如X25591,secp256r1等.
  3. RFC7748-Elliptic Curves for Security: 具体定义了X25519,X448曲线算法.
  4. RFC6090-Fundamental Elliptic Curve Cryptography Algorithms: ECC基本定义.
  5. Elliptic Curve Cryptography: openssl对ECC的解释,简单明了,值得一看