ECC算法分析--数学背景-自上而下的方式

可以把ecc理解为是曲线域上的rsa，当然只能这么理解，它们即使放到一个域内也是有很大不同的，导致它们分别可以被应用的数学难题就不同。既然可以理解为曲线域上的rsa(或者曲线域上的dh，dsa等)，那么就应该知道rsa，dsa，dh等都是在什么域上的，其实它们都是在素数域上的，所有的素数域都是一样的，所以对于rsa，dsa或者dh来讲，都是可以直接计算的，比如要产生一个大素数，那么就直接产生好了，这一类产生数的问题是现代计算机可以解决的虽然一般机器没有提供现成硬件接口，但是还是可以很容易编程实现的，可是曲线域怎么理解，顾名思义就是定义在一条曲线上的点组成的集合加上一些操作，每一条曲线都拥有一个曲线域，这么说来曲线域并不是唯一的，而是有无穷多个，于是我们在进行计算的时候必须要指明是在哪一条曲线上进行操作，因此必然在实现上要比rsa等素数域上的算法多一个数据结构，这个数据结构就是EC_GROUP，一旦group确定，其余的操作流程就基本和素数域上的一致了，不过也只是流程的一致，具体操作方法并不相同。不同的原因是因为域这个概念对各种操作可以实现重载(建议用OO的观点理解群环域的概念)
域的概念和oo中的类很相似，拥有一个数据集合，拥有加减乘除这些操作，拥有零元素和单位元素，这些对于不同的域来讲可以有不同的实现，群环域就是集合和操作以及零元和单位元的抽象。既然域的加减乘除可以自定义，那么接下来就要定义曲线上的加法，这是一个最基本的操作，因为减法可以理解为加上一个“负”元，乘法又是加法的重复，除法可以理解为乘以一个“倒”元。在叙述曲线域加法法则之前首先看一下射影面的概念。
普通的笛卡尔坐标系中无法用数字表示“无穷”的概念，实际上笛卡尔坐标系就是量化的欧氏几何学，所有欧氏几何中“真理”依然在笛卡尔坐标系中成立，但是这种“有限域”的几何学也许仅仅对工程学比较合适，理论上的几何学应该是包罗万象的，为了将有限和无限全部包容进一个坐标系，就需要用一种方式来记录“无穷”这个概念，对应到几何坐标系就是“无穷远”的点，这个无穷远实际上是不可达的，不要指望一个很远很远的点一下子跳变到无穷远，类似量子跃迁的行为在连续的实数集合是不可能的。另外需要商定的就是无穷远点有且只有一个，因为我们的目的仅仅是在概念上包容无穷远点以便我们定义新的概念，而不是要量化它从而使得计算成为可能，在新的数学理论推出之前，任何量化“无穷”的尝试都是没有意义的。既然不需要量化无穷远点，那么概念上只有一个这样的点就足够了，一个平面上缺了这个点就等于缺了一半内容，加上这个点，一个平面就完整了，起码在概念上就完整了。接下来就要看看如何去定义这个无穷远点了。
定义一个概念有两种方式，一种是描述性的定义，一种是导出式的定义，描述性的定义对于无穷远点实际上没有什么意义， 毕竟我们只是用一下无穷远这个概念，并且想将它归并到已经存在的笛卡尔坐标系，于是就必然需要一个和它相关的概念将之导出来，于是理所当然的首选概念就是平行线的定义，欧氏几何说不相交的两直线平行，别小看了这个定义，就是这个定义抛弃了无穷远点欧几里得的失误在于他将相交和平行定义成了两个概念，它们之间没有互通的桥梁，这就导致了两个概念的二元对立，于是如果是相交线，那么它们肯定在有限伸展长度内相交，如果平行，那么它们根本没有交点，就更不需要在乎交点的概念以及在哪里相交了，如果将平行的概念定义成相交于无穷远的两条直线的话，相交和平行的概念就全部统一于交点这个概念了，如果在有限伸展长度相交，那么两条直线相交，如果在无穷远相交，那么两直线平行。有了这个无穷远点的定义后，接下来就要考虑如何在坐标系表示它了，事实上，由于笛卡尔坐标系完全量化了欧氏几何，所以不可能在这种坐标系中表示无穷远点的，
L1：y=ax+m
L2：y=ax+n
在m和n不等的情况下，上述直线联立得到的方程组是无解的，因此不要指望用这种方式来定义无穷远点，但是要想办法使得上述方程有解，那就是再引入一个自变量z，于是上述直线化为：
L1'：zy=azx+zm
L2'：zy=azx+zn
这样只要z=0，上述明显平行的直线就会相交，相交于无穷远点，坐标(x,y,z)就是新的射影面的坐标，当然也可以变换一下：
x'=zx
y'=zy
z'=z
于是，所有射影面坐标集合中z=0的点就是那个唯一的无穷远点，如果由射影面坐标化到笛卡尔坐标则会出现：x=x'/z,y=y'/z的情况，很显然z是不能为0的，这也是笛卡尔坐标系中无法表示无穷远点的原因。有了无穷远点的概念和坐标，整个平面就和谐了再也不用担心两条曲线没有交点的问题了。
于是曲线上两点的加法被定义成两点连线延长与曲线交于第三点，过第三点作y轴(笛卡尔坐标系)的平行线交曲线于第四点，这个第四点就是最后的和，在曲线域上，其零元就是无穷远点，这个规则看起来很奇怪实际上很一般，我们小学时学的自然数加法就是最简单的曲线加法法则，对应的曲线就是笛卡尔坐标系的x轴，也被简称为数轴，并且我们小学的时候就已经在使用离散点了，自然数就是数轴上的一系列离散点，那个时代我们先从离散的自然数开始学起，最后在初中的时候过渡到了连续的实数，实际上还是在同一条数轴上，但是今天这一次我们刚刚理解了连续曲线域上加法的定义，接下来要返回离散化的定义，这次我们是先学的连续，然后再介绍离散，和小学初中时期对数轴的学习正好相反。
ecc算法中为了使曲线上的点的坐标处于可控范围内，ecc对曲线进行了取模操作，于是重新定义了离散曲线点的加法法则，实际上和连续曲线点的法则相似，这么做是有原因的，毕竟最后实施计算的是机器，而机器并不是都可以做高强度运算的。具体定义就是：
a+b=c(modm);
a*b=c(modm);
这是很容易理解的，a和b的和和c相等的条件是a和b的实数域的加法和与m相除的余数与c/m(实数域除法)的余数相等(同余)，乘法也是一样的，另外这里有个乘法逆元的概念，如果是实数域，一个数的乘法逆元就是其倒数，所谓乘法逆元就是相乘等于单位元的那个数，对于ecc算法的离散曲线域，m的乘法逆元为n，满足m*n=1(modp);称作n是m关于p的乘法逆元。对于ecc算法使用的离散曲线域，单位元就是1，
乘法就是相乘后取模，零元是无穷远，加法就是相加后取模，这很简单。但是如果在离散曲线域碰到一个表达式2/5，可不要把它当成一个数，它是一个除法表达式，这已经不是在实数域了，于是单纯一个2/5没有任何意义，一定要看mod数是多少，如果是10，那么a=2/5的真正值是求5关于10的乘法逆元，然后再乘以2，这里一定要注意。
乘法逆元的求法是通过扩展欧几里德算法进行的，首先看一下扩展的欧几里德算法的描述：
ax+by=gcd(a,b) -------(1)
这里gcd就是欧几里德算法，这个等式1明显是个不定方程，可以通过扩展欧式算法求出所有的x和y，首先如果a和b不互质且有唯一的公约数，那么设它们的最大公约数且唯一的公约数为m于是
a'mx+b'my=m==>a'x+b'y=1 ----(2)
化为了a和b互质的情况；如果a和b存在一个以上的公约数，实际上不定方程1是无解的：
由于1已经化为了2的形式，如果a和b还有公约数n，那么2==>a"nx+b"ny=1==>n(a"x+b"y)=1对于整数而言，除非n=1，否则上述方程不可能有解。如果a和b互质的话，就可以用扩展欧式算法求解x和y了：
扩展欧式算法使用的是递归的思想，根据方程1的形式，我们可以得到很多的形式：
ax1+by1=gcd(a,b)-----A
bx2+(a%b)y2=gcd(b,a%b)-----B
...
总有一天a%b会是0的，于是倒着推过来的话就得到了x和y，将A和B联立求解得到的x和y是一个递推式，也就是可以用xn+1来表示xn，这是最终能求出x和y的基础。这个过程中，我们为了求x和y，借用了n多个方程1形式的方程，目的就是为了利用原始的欧几里德算法将这些看似不相关的方程联系起来，得到一个递推式。最后我们来看一下如何用扩展欧式算法求乘法逆元，乘法逆元可以表示成(a*b)mod p=1，则b是a关于p的逆元，前提是a和p互质，既然互质，并且ab mod p=1，那么可以转换为下面的式子：
a*b+py=1
把b看作x之后上式其实就是可以应用欧几里德算法求解的不定方程。之后的事情就不用多说了。
对于密码学应用的ecc来说，其实质是利用了一个数学难题，该数学难题和rsa以及dh的很相似，只不过是定义在曲线域上面的，要想使用ecc加密，必然要定义一条曲线，然后选择一个点，成为基点，随后计算该基点的阶，所谓的阶就是一个数字，设为p，基点设为B，p*B其实就是连续个B相加，如果pB=无穷远点，那么p就是B的阶，然后随机选择一个小于p的数字k，计算kB的值，将该值设为A，则kB=A，那么A就是公钥，k就是私钥，该数学难题是：由k和B算A容易，由A和B算k困难。加密和解密的过程这里就不再介绍了。
本文简略的介绍了ecc算法的实质以及它的部分实现，在被问到为何ecc在openssl中的实现和rsa之流不同时，你的回答可以是：ecc定义在离散曲线域上，而rsa定义在素数域上。在几何表示上，由于曲线域基于交点定义加法，那么交点是必然要无条件存在的，于是引入了无穷远点作为不能处理的情况的后备处理资源。
最后再说一个很有意思的事情，那就是欧几里德算法的理解，现在很多的教科书都会讲到这个算法，但是如果你去翻一下古老的《几何原本》的话就会对该算法有一种截然不同的理解方式了，欧几里德并没有用除法和余数来描述这个辗转相除法，而是使用测量的概念，如果一个数能除尽另一个数，那么就用“量尽”的表达方式，这种描述方式十分棒，虽然少了严谨性，但是理解起来十分容易，随意找两根不等长的棍子，求它们长度的最大公约数，用短的一根去量长的一根，将长的一根按照短的一根的长度砍断，接着将短的一根作为长棍，原来长棍被砍下的剩余一截作为短棍，依次类推，如果有一次测量中，短棍量尽了长棍，那么以短棍为单位将砍断的小截再次砍断，我们会发现我们拥有一大捆一样长的棍子。这个形象的原理用于将很多不等长的棍子裁成等长的，要求不能浪费，并且达到最终的等长木棍尽可能的长。