密码学基础 -- ECC

目录

1.ECC概述

1.1 汽车行业倾向使用ECC

1.2 ECC的难以理解

2.ECC原理

2.1 椭圆曲线真的不是一个椭圆

2.2 从图形了解ECC

2.3 ECC用法

3.ECC曲线汇总

1.ECC概述

1.1 汽车行业倾向使用ECC

当前公认安全有效的三大类公钥密钥体制分别为基于大数因子分解难题(RSA)、离散对数难题(DSA)和椭圆曲线离散对数（ECC）难题的密码体制。

最初RSA由于其容易理解被广泛运用，但随着计算机性能的提升，要保证RSA的安全性，则必须要增加密钥长度，所以我们可以看到RSA密钥从1024bit慢慢来到了4096比特。

由于汽车网络安全近几年才兴起，专为密钥存储设计的硬件资源有限，如果用RSA算法，密钥存储数量有限，而ECC(Elliptic Curve Cryptography)的出现有效弥补了这方面的缺憾，实现了密钥效率上的突破，根据NIST.SP.800-57pt1r5描述，对称算法和非对称算法的安全强度如下图所示：

可以看到，160bits的ECC密钥长度实现的安全强度等同于RSA 密钥长度1024bits。

所以现目前，汽车行业越来越倾向使用ECC来实现验签、会话密钥协商等。

1.2 ECC的难以理解

但是，ECC这个算法的原理确实难以理解。

要真正搞懂ECC，我们需要先了解椭圆曲线的概念和分类。

一般来讲，椭圆曲线是一个具体两个变量x、y的三次方程，满足

的所有点(x,y)的集合，以及一个无穷远点O(y趋于无穷)。

在不同域上，椭圆曲线的方程也有不同，所以还需要掌握实数域、有限域上的椭圆曲线方程。

讲到这里，我估计部分朋友已经劝退了，所以我今天就从以容易理解的简化版方式进行描述，旨在了解概念。

2.ECC原理

2.1 椭圆曲线真的不是一个椭圆

以实数域上的椭圆曲线为例，它是一条由方程  给定的曲线，a和b是常数，并满足，如下图：

这与椭圆的方程差别很大，如下图：

那么为什么要叫椭圆曲线呢？

这是数学家在研究椭圆周长时，发现椭圆周长公式变换后可以得到 ，因此椭圆曲线一直沿用至今。

椭圆曲线因为a、b的取值不同，在坐标系上有不同的形态，具体如下：

注意观察上面曲线，可以发现它们有两个明显共同点：

• 曲线关于X轴对称
• 任何非垂直X轴的直线与曲线至多三个交点

 基于以上特性，我们来进行几何作图操作。

2.2 从图形了解ECC

1. 过曲线上的A和B作直线，得到与曲线相交的第三个点C，
2. 过C做X轴的垂线得到C’’，这里我们定义A⊕B = C’’，读作A点加 B；
3. 过A与C’’与曲线相较于D点D点有一个基于水平对称的点D’’，这里我们定义A ⊕C’’ = D’’，如下图

如果我们继续用A去做点运算，可以轻易得到，A⊕D’’=E’’，依次类推。 

那么假设我们已知起点A终点Z，请问这期间一共做了多少次点运算才能得到Z？

这就好像你在室内足球场踢球，朋友在外面等待，比赛结束后，你让朋友猜你一共踢了多少次皮球才得到1分，这显然是非常困难的。

有了这个思路，我们继续往下。

假设A点与曲线相切，这时候因为A和B是同一个点，所以公式 A⊕B = C’’，就变为了A⊕A = C’’，简写为C’’ = 2A：

注意这里的2A，不是简单的把坐标轴的值乘以2，而是计算曲线上的点，具体可以看下图我在Desmos上的公式推导，这里不多赘述以免迷糊。

 现在A与C’’再次连线，我们可以得到A⊕C’’ = A⊕2A = D’’，那么D’’ = 3A。

 以此类推，我们可以得到最常见的标量运算公式：

P = kG

通过G点进行k次运算可以得出P，但反过来，如果只知道G和P，就很难求出k是多少。

因为P和Q都是椭圆曲线上的一个点，是坐标，k是整数；假设P = (-2,3)，Q= (2，-6)，要求出k是多少，这被公认是非常难的。

因此，我们可以把k作为私钥，G和P作为公钥。

PS：个人认为，作为使用者，ECC基本原理了解到这个程度即可，如果真要刨根问底，那得先从数学复习，建议从群论到有限域再到曲线推导。

2.3 ECC用法

ECC一般用于签名或者密钥协商。我们看看如何实现会话密钥协商：

1.  Bob使用私钥b和公钥G生成结果B，并发给Alice；
2. Alice拿到公钥后，用私钥a和G生成结果A = aG，并发给Bob；
3. Bob拿到计算结果A，并用自己的私钥b与A生成新的密钥，bA = baG；
4. Alice拿到计算结果B，并用自己的私钥a与B生成新的密钥，aB = abG；

 由于公式P = kG，k是整数，因此上述ba = ab。所以上述过程生成了只有Alice和Bob才知道的密钥，该密钥可用于会话的数据对称加解密。

即使攻击者拿到了G和B这些数据，由于私钥b\a的难以攻破(已知椭圆曲线上的起点和终点，求运算了多少次是非常难的)，因此该方式也是比较安全。

3.ECC曲线汇总

从上面的原理我们知道，要使用ECC进行数据加解密，最难得是建立起ECC曲线方程，所以现目前车规行业常用标准中推荐的椭圆曲线。

根据英飞凌公开材料显示，目前TC3xx所支持的曲线包括：

• NIST curves P-192, P-224, P-256, K-163, B-163, K-233, B-233
• BrainpoolP160r1, brainpoolP192r1, brainpoolP224r1, brainpoolP256r1
• Bernstein Curve 25519

国内来说国密局担心NIST有后门，推出了自主算法SM2， 如下：