背景图

关于椭圆曲线的理解

概述

一直觉得加密算法比较神奇,但是比特币中使用的椭圆双曲线算法一直让我感觉很神奇,之前看的时候没有看懂,这次认真看了两篇文档之后,终于理解了这种算法的奇妙之处,看来数学这个东西其实没有大家想像的那么难,也许就是很简单的东西堆砌成一个庞然大物,以至于你不再看得清楚了。

椭圆曲线的形状,并不是椭圆.是因为椭圆曲线的描述方程,类似于计算一个椭圆的周长的方程得名。

从阿贝尔群开始

群的定义是定义了二元操作“运算”并且用符号+表示的一个集合。假定我们要操作的群用 𝔾表示,那么我们在这个群上面要定义的“运算”必须符合以下几个属性:

  • 闭包。如果a和b都是𝔾的成员,那么a+b也是𝔾的成员。
  • 组合性。(a+b)+c=a+(b+c)
  • 单位元。存在确切的一个值,称之为单位元,0可以保证该等式成立 a+0=0+a=a
  • 逆元。每个成员都有一个相反数:对于任意值a必定存在b使得a+b=0

如果加上第五条这要求:

  • 交换性a+b=b+a

这样的群我们称之为 阿贝尔群。

椭圆曲线

椭圆曲线是一个对数函数,曲线上的每个点都必须是非奇异的,所谓的”非奇异”或”光滑”的,在数学中是指曲线上任意一点都存在切线。椭圆曲线对于X轴是对称的,记住这点很重要。关于这个函数的更多说明,还是参照引用的文章吧,里面提到的比我说的详细多了。

椭圆曲线的阿贝尔群

其实关于阿贝尔群,大家一定认为加法就是指数学中的那个加法,而对于椭圆曲线,这个加法还不一定非要是数学数字中的加法,这里的加法是指线相交,而加法中的元素也不是数字,而是一个点。举例来说,P+Q=R是指P与Q的连线与曲线相较于点Q,那么对于这个公式P-R=-Q又该如何解释呢?其实减号意味着点对于X轴对称的另一个点,另外公式变换一个P+(-R)=-Q,你再想想对称性,这个公式是不是成立的?这就是这个曲线的妙处所在。至于结合律就更好理解了,3点一线,不管你取那两个点,第三个点都能算出来不是么?至于0就是无穷远处的点就是0,这个适用于,直线平行于X轴或者y轴的时候使用。

关于乘法

1
mP = P + P + ...... + P = Q

注意这里的乘法就是,一次一次加法算出来的,如果m越大,那么计算的量也就越大。我们学的椭圆曲线密码体制就是利用以上的这个困难问题来设计的。

素数域Fp

如果椭圆曲线上一点P,存在最小的正整数n,使得数乘 nP=0∞,则将n称为P的阶,若n 不存在,我们说P是无限阶的。

事实上,在有限域上定义的椭圆曲线上所有的点的阶n都是存在的。

加解密过程

终于到了学习,这个算法是如何进行加解密的过程的原理了,其实就是利用了上面提到的乘法和素数域的知识,另外也有了几个参数,这几个参数对应我们之前在bitcoin中使用的各种参数调节的问题,这里就应该是调节的本质了吧.。好了下面我们来分析》》》

描述一条Fp上的椭圆曲线,常用到六个参量:T=(p,a,b,n,x,y)。

  • (p 、a 、b) 用来确定一条椭圆曲线,p为素数域内点的个数,a和b是其内的两个大数;(这个p就是最后y mod p 的那个值,应该说p的取值决定了n的个数)
  • x,y为G基点的坐标,也是两个大数;
  • n为点G基点的阶;

以上六个量就可以描述一条椭圆曲线,有时候我们还会用到h(椭圆曲线上所有点的个数p与n相除的整数部分)。

现在我们描述一个利用椭圆曲线进行加密通信的过程

  1. A机器选定一条椭圆曲线 Ep(a,b) 并取椭圆曲线上一点,作为基点G。
  2. A机器选择一个私有密钥k,并生成公开密钥 K=kG。
  3. A机器将 Ep(a,b) 和点K,G传给用户B。
  4. B机器接到信息后 ,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r。
  5. B机器计算。C1 = M + rK; C2=rG.
  6. B机器将点C1、C2传给A机器。
  7. A接到信息后,计算C1-kC2,结果就是点M。因为C1-kC2=M+rK-k(rG)=M+rk-r(kG)=M, 再对点M进行解码就可以得到明文。这样值就通过0运算神奇地还原了,注意这里的计算一是设计椭圆计算,椭圆计算是基于数学计算的过程的。

在这个加密通信中,如果有一个偷窥者H ,他只能看到Ep(a,b)、K、G、C1、C2,而通过K、G 求k 或通过C2、G求r 都是相对困难的,因此,H无法得到A、B间传送的明文信息。

ECDH

是基于ECC(Elliptic Curve Cryptosystems,椭圆曲线密码体制,参看ECC)的DH( Diffie-Hellman)密钥交换算法。其实就是双方互相传送公钥,然后通过双方的公钥计算出双方都知道的加密密钥S(注意这里面没有随机数传送,所以整个过程是安全的。)。

该算法可以用来解决如下问题:两端(Alice 和 Bob)想要安全的交换信息并且第三方不能获取到该信息。当然这是TLS协议中的目的之一,我们给出一个例子。
(其实下面的描述其实是ECDHE,而不是ECDH)

  1. Alice 和 Bob 生成他们自己的私钥和公钥,即Alice 有 da、Ha = daG;Bob有db、Hb = db G
  2. Alice把Ha发给Bob,Bob把Hb发给Alice。这样Alice 有da,Ha,Hb,Bob有db,Ha,Hb。
  3. Alice计算S = daHb(即自己的私钥乘上Bob的公钥),同样的,Bob计算S = dbGa(自己的私钥乘上Alice的公钥)。两边计算的S是相同的。

ECDSA签名算法

现在有一个场景:Alice想要用私钥签名一个数据,Bob想要使用Alice的公钥验证这个签名;只有Alice能够进行计算签名然后得到签名,每个人都能验证签名值。

首先Alice和Bob拥有相同的椭圆曲线参数,算法被签名称之为ECDSA,是DSA算法的一个变体。

ECDSA签名算法的输入 是 数据的哈希值,而不是数据的本身,至于哈希算法选用哪一个就取决于自己了。为了使得ECDSA的输入值的比特数和子群的阶n的比特数一样,哈希值可能会被截断。我们把ECDSA输入称之为Z。
算法工作流程如下:

  1. 取一个范围在[1, n - 1]的随机数k
  2. 计算点P=kG (就是计算出公钥)
  3. 计算r = xP mod n (算出r的值,n是基点的阶)
  4. 如果 r == 0,执行第一步
  5. 计算s = k-1 (z + r*dA) mod n (dA是Alice的公钥,k-1 是 k 对n的逆元, k是上面的随机数)
  6. 如果s==0,执行第一步
  7. 二元组(r, s)就是签名值

上图中,Alice使用私钥da对z进行签名,生成二元组(r, s)。
Bob使用Alice的公钥对(r, s)和Z进行验证。

现在我们来看看Bob如何验证的:

  1. 计算u1 = s-1 * z mod n
  2. 计算u2 = s-1 * r mod n
  3. 计算P = u1*G + u2*HA
  4. 如果r == xP mod n,则验证正确

过程证明请查看相应的引用。

椭圆算法总结

通过最后的示例我们可以看出,椭圆算法的公私钥其实是一样的,其实说白了就双方都不需要知晓别人给定的那个k和r的值,因为kr相乘之后,大家的值都是一致的,但是不能在网上随便传输k和r的值吧,这样还有什么安全性,这里很巧妙地利用了归的技术,隐藏了这种特性的原始值。这种特性就是椭圆曲线的对称性而衍生的阿贝尔群的特性。

鉴于np=0,所以一个私钥理论上是可以对应多个公钥的,一个公钥也可以对应多个私钥。

参考和引用

椭圆曲线算法:入门(1)
椭圆曲线算法(ECC)学习(一)
钱包和地址
Elliptic Curve Cryptography: a gentle introduction
Elliptic Curve Cryptography: finite fields and discrete logarithms
有限域和离散对数问题(ECC椭圆曲线算法2)
ECDH and ECDSA(ECC椭圆曲线算法3)

0%