在阮一峰的博客上发现一篇有意思的推荐文章,讲述了椭圆曲线加密算法(Elliptic Curve Cryptography)的实现原理,原作者友好的将文章使用的源代码放在了Github供读者使用,我也成功在Ubuntu搭建起了实验环境。此文的原意并不是深究ECC算法是如何实现安全地加密,而是让感兴趣的读者可以易于理解ECC算法的基本逻辑,我也不是密码学方面的专家,所以文章不严谨的地方烦请斧正。

We also don’t want to dig too deep into the mathematical rabbit hole

首先,我们有一个二元三次方程组。

$$
y^2=x^3+ax+b
$$
在假设a=-1,b=5的情况下,我们可以得到如下图的曲线:

然后,我们随机选取两个X的值,那么我们就可以通过计算Y值得出蓝色的A和蓝色的B两个坐标。下一步,我们把蓝色的A和B两点连接,他们的连接线将会与曲线在一点相交,我们把这个相交点的Y值反转,即可得到如下图所示的橙色A+B点。这里留一个疑问,蓝色A点+蓝色B点的值会等于橙色A+B点吗?

紧接着,我们把A+B点连接到曲线上的某一点C。同样的,只要这一条线不是垂直的,我们就可以在A+B点和C点之间的连接线中找到一个与曲线相交的点,我们一样把这个相交点的Y值反转,即可得到如下图所示的橙色A+B+C点。

如此类推,我们就可以不断的通过这样的方法,从一点出发得到另外一个新的点。为了便于更直观的理解,我们希望用相同的点P来表示每一个新的点,所以我们利用当前位置的切线来得到点P,用同样的办法得出P+P点(或称2P点),得到如下图:

接下来,我们再一次从P+P点回到原始的P点,得到的结果,我们称之为P+2P+3P(或称3P点)

类似的,我们可以利用这个方法一直持续下去N次,得到NP。那么当我只告诉你如下图的NP的坐标(意味你已知NP)时,你可以不可以推算出N的次数呢?

这里N=13,因为图是作者画的,所以她肯定知道呀。但如果排除这种情况以外(已得知N值),你将很难通过推算找到答案。听到这里,大概密码学的味道开始出现了,N代表的就是私钥,而NP代表的就是公钥。换句话说就是,当我们知道NP和P的值的时候,推算出N的值是困难的

有人就会问了,当我已经知道NP和P的值,那么我可以从P+P开始,再到P+2P+3P的一直尝试下去,不就可以得到NP了吗?那我们接下去看。首先我们看到下面的加法交换律,

$$
a+(b+c)=(a+b)+c
$$

我们可以借助作者提供的源码,在 jupyter notebook 中计算出坐标点A,点B和点C不同顺序相加的结果:

1.jpg

两者的结果是非常接近的,造成误差是由于算法的浮点类型设置,另外原文也已经解释了关于数学有限域的问题,但这不是本文着重点。这里我们认为加法交换律是成立,得出结论一:坐标点可以无序的相加而不影响结果

刚刚“加法交换“的例子我们已经讲到(已知)P+2P=3P,那么下面式子是不是成立呢?

$$
P+3P=4P=2P+2P
$$
同样在电脑上使用 jupyter notebook 计算一次,我们得出下面的两个图:

等式两边的结果都是在同一个点上,即上面的式子是成立的,得出结论二:将坐标点化作成倍关系的累加是不影响结果的。有了上面两个结论,我们就可以开外挂来“加速运算”了,所以回到刚刚的问题:

我可以从P+P开始,再到P+2P+3P的一直尝试下去,不就可以得到NP了吗?

举个例子,已知N=227,尝试分解227P的运算过程。首先将227分解成用二进制的方式表达:
$$
11100011
$$
接着代入P点的坐标,且将二进制运算转换为对应的幂运算,式子如下:

$$
2^7P+2^6P+2^5P+2^1P+2^0P
$$
等同于:
$$
128P+64P+32P+2P+P
$$
相比于逐次累加227次运算得出227P的结果,上面的式子可以化简为8次运算就可以得出结果,也比较符合计算机的运算方式。因此,对于猜解N值,幂运算的方法比逐次累加的方法快太多了。接下来就是熟悉的同底数幂相加和求对数的问题,例如:

$$
a^x+a^y=a^{x+y}
$$

$$
3^4 = 3\times 3\times 3\times 3=81
$$

$$
4=log_381
$$

所以求解N的值就可以转换成对数的求解。那为什么已知NP求解N是困难的?因为椭圆曲线密码体制就是建立在对椭圆曲线离散对数问题(ECDLP)求解困难性假设基础上 ,如开头所说的,本文不深究数学问题。只需要知道当N值变成更大的数字,例如 2256 或者 1082 的时候,攻击者逐次累计的方式就变得无效,且保证了攻击者在已知NP和P的情况下,无法计算出N值。

Namely, find out what’s the N value from NP and P point given if N is big enough. This is called Elliptic Curve Discrete Logarithm Problem.

文章最后举例Alice和Bob是如何交换密钥以及实现加密通信的。

第一步,约定使用ECC算法作为加密协议;

第二步,Alice发送公钥P和NP值给Bob,N为Alice的私钥。当N值足够大的时候,已知NP来求解N是困难的,因此N值只有Alice知道;

第三步,Bob同意使用公钥P,并且回复MP给Alice,M为Bob的私钥。当M值足够大的时候,已知MP来求解M是困难的,因此M值只有Bob知道;

第四步,协商一个对称加密算法,如AES256。Alice和Bob使用共享的密钥SK来加密和解密信息;

$$
SK=NP\times M=MP \times N
$$
这里又有一个新的安全问题,那就是Alice如何校验MP这个值就是来自Bob的呢?因此需要引入公钥基础设施(Public key infrastructure)的概念来防止中间人攻击(MITM attack),例如HTTPS绿锁头的原理。

参考资料:

Elliptic Curve Cryptography Explained

How To Set Up Jupyter Notebook with Python 3 on Ubuntu 18.04 | DigitalOcean