简单理解椭圆曲线的非对称加密应用

红太狼 2023-07-09 06:29 12阅读 0赞

椭圆曲线的确很复杂，涉及理论知识较多，尤其是数学知识太多太多，无法一窥全貌，经过理解，我觉得最需要理解的就是，那条经典的椭圆曲线有什么神秘之处，优势如何实现非对称密码加密的，如果觉得有用，请给个简短评论，我心欢喜。

# 椭圆曲线 #

椭圆曲线就是下图那样的一个对称曲线，一点都不像椭圆啊！这个主要源于名称来自于椭圆曲线积分，而这个积分主要是因为通过积分计算椭圆边长而得名。所以通过代数（可理解为多项式）定义的椭圆曲线积分函数就是椭圆曲线。我们来看动图理解椭圆曲线：  
![椭圆曲线的计算][20200228104735327.gif]  
(图片来源[链接][Link 1])

上图就是漂亮的椭圆曲线，基于X轴对称，在曲线上面有A，B两点，可以任意取，做一条直线，一定会与曲线相交于另外一点，做Y轴平行的垂线到另一边，得到点C。这个运算过程就是基于椭圆曲线定义的加法运算，而且在数学上可以保证A+B=C一定成立（如何确保需要不少数学知识）。咱们拓展一下，如果A，B相同，那么一个点就没法画线了，那么聪明的数学家把该点的切线（光滑曲线一定有切线）定义为P点，如果A，B等于P，那么A+B=2P=C，这样就定义了在曲线上的乘法，还包括其他…定义，就构建了一个高大上的名字—群（高阶数学啊）。有了2P的定义，就可以定义3P,4P…nP了，这样就在曲线上形成了无数个离散的点，如下图一样。  
![A+B运算的离散点][A_B]  
上图看起来这些点压根就不像曲线啊，的确不像，那是因为对曲线上的点进行模运算（%运算符），这样在这个空间中，都是曲线上的点取模后绘制的，他们同样满足曲线上定义的规律。  
如同在曲线上做的那样，这些点通过绘制直线，仍然可以依然找到A+B=C的点（注意经过边缘后，会对折到下边（模运算），到了最右边会对折到最左边），而且这些点分布完全没有规律（除了基于X轴对称）。如果把A，B看作是2P，那么给定P点，和数字2，可以很容易找到C点，反过来，知道P点和C点，需要找到C=2P是很难的，可以通过穷举法暴力破解的。这就是加密的核心了，给定一个秘密，验证很容易，破解很复杂。给定一个数字n（这个需要在椭圆曲线中有定义），计算nP=C，就是加密过程了。

未来后续理解椭圆曲线，数学家们是定义的椭圆曲线：E(p,a,b,G,n,h), 这是一个多元组，这里的p就是定义这个曲线的大小，p越大，这个曲线覆盖面积就越大，穷举难度也越大，a,b定义了椭圆曲线的多项式系数，这个在算法选定的时候就确定下来了。G表示生产元（复杂的概念），简单理解就是曲线上的一个点G，例如（3,10）通过这个点G定义1G, 2G, 3P…nP的一个序列构成的集合，n越大，点集合越大。h是协因子，一般等于1，确保生成元G的点远远少于椭圆曲线定义的所有点数，这样穷举法成功的概率就接近于零了。另外，椭圆曲线有着比RSA算法在同样位数加密下具有更好的加密性能。

# 椭圆曲线的加密 #

从上节我们知道椭圆曲线定义一个算法P = nG, 通过n可以很容易计算P，知道G，P很难猜测n，这样就构成了加密基础。本节我们看看如何通过这样一个特性，科学家们如何定义非对称加密的。  
首先大家基于同样的椭圆曲线参数进行加密通讯，双方都知道：E(p,a,b,G,n,h)。Alice随机选择一个数ra, 要求小于n, 计算Pa = ra \* G，发送给Bob.  
Bob同样随机选择一个数rb, 要求小于n，计算Pb = rb \* G，发送给Alice.  
这样Alice和Bob的随机数ra, rb相当于私钥，公开给对方的Pa, Pb相当于公钥。此时，Alice如果需要给Bob发送加密信息，就可以用Bob的公钥加密，Bob可以用自己的私钥进行解密，计算过程如下：  
Alice选择另一个随机数k, 把需要加密的内容Pm(就是需要把原文编码到椭圆曲线定义的空间中)，计算出秘文Cm = \{k\*G, Pm + k \* Pb\}，这里Pb是Bob的公钥，秘文由2个点构成。Bob收到秘文后进行如下计算：  
Pm + k \* Pb - rb \* (k \* G) = Pm + k \* rb \* G - rb \* k \* G = Pm  
这个公式稍微解释一下：Bob从网络中接受到Pm + k \* Pb的结果，k \* G的结果，并有着自己的私钥rb， 因此计算出Pm.  
从而得到原文点Pm.

另外一个用处就是实现密钥协商，比如https的ECDHE算法密钥协商：  
Alice通过计算得出协商秘钥：Ka = ra \* Pb  
Bob通过计算得出协商密钥：Kb = rb \* Pa  
可以通过简单计算得到Ka = Kb:  
Ka = ra \* Pb = ra \* (rb \* G) = rb \* (ra \* G) = rb \* Pa = Kb

神奇吧！非对称密钥是基于数学规律构建的方法。希望通过本文，可以让你对椭圆曲线加密有一个简单的理解。

[20200228104735327.gif]: https://img-blog.csdnimg.cn/20200228104735327.gif
[Link 1]: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
[A_B]: https://img-blog.csdnimg.cn/20200228105807117.gif