【密码学】ECC椭圆曲线加密2018年07月13日15:48:10阅读数：41本篇文章介绍密码学中的一个概念：ECC加密算法。接下来我将从以下几个方面介绍一下ECC：•阿贝尔群(AbelianGroup)•什么是椭圆曲线•有限域椭圆曲线计算•椭圆曲线加密(ECC)•ECC参数选取•ECC与比特币椭圆曲线加密，全称EllipseCurveCryptography，简称ECC。与传统的基于大素数因数分解难题的方式不同，ECC通过椭圆曲线的方式产生密钥。在ECC之前，有必要先介绍一下阿贝尔群的基本概念。阿贝尔群(AbelianGroup)给定集合GG和操作如果满足以下性质，则是{G,・}{G,・}群•封闭性▽比bWG’QbWGDa’bwGabwG•结合性▽a，b,cUG,(a•b)•c=a•(b•c)va,b,ceG,(a-b)-c=a•(b-c)•单位元meUG,VaUG,e-a=a-e=ameuG,VawG,e-a=a-e=a•逆元VaUG,日a-iUG,a-a-i=a-i-a=eVauG,3a-1uG,a-a-1=aT-a=e在群的基础上，如果还满足交换性，那么这个群就是一个阿贝尔群了，通常我们也称作交换群。•交换性va,bUG,a-b=b•ava,buG,a-b=b-a我们平时生活中所接触到的加法就是实数域上的阿贝尔群了，单位元是°0,乘法也是阿贝尔群，其单位元为11。什么是椭圆曲线我们来看下椭圆曲线的定义，椭圆曲线是在射影平面上满足维尔斯特方程(Weierstrass)的所有点的集合，这句比较废话，不需要理解。其需要满足两点：•椭圆曲线关于x轴对称•平面中的一条直线和椭圆曲线相交，最多有三个交点满足ECC的椭圆曲线有着如下形式：y2x3+ax+b;4a3+27b2^0y2x3+ax+b4a3+27b2M0一条椭圆曲线大概长这样：▲椭圆曲线案例与计算规则介绍那么椭圆曲线如何去进行运算呢？不妨将椭圆曲线上面的运算定义为“+”运算，以上图为例，给定点A和点B，C'点为AB延长线与曲线的交点，做其对称点C，那么A+B=C。那么如何计算A+A呢，这里用到极限的概念，做点A的切线就可以了，下图中A+A=C。▲椭圆曲线中计算A+A在这个定义之下，那么单位元是什么呢？实际上，单位元是一个理想的“无穷远点”(可以把这个点想象成点(°W)(0严)。这样，在椭圆曲线上面定义的++运算就满足交换群的性质了。我们一步步看是否满足所有的交换群的性质呢？•封闭性：显然满足•结合性：自行理解•单位元：°0,因为°0是无穷远点，因此AA和°0的交点为AA的对称点，根据++操作的计算规则，A+°=AA+O=A•逆元：AA的逆元为AA关于xx轴的对称点•交换性：根据刚刚介绍的计算规则，显然有：A+B=B+AA+B=B+A所以，我们定义在椭圆曲线上的运算实际上是一个交换群。在定义了++运算之后，我们还可以定义椭圆曲线上的乘法运算，按照递归的方式，可以有如下定义2A=A+A2A=A+AkA=A+(k-1)AkA=A+(k-1)A比如给定一条椭圆曲线和A,我们可以按照以下过程求3A3A：▲椭圆曲线的乘法运算在定义了加法操作和乘法操作的基础之上，我们就可以知道为什么椭圆曲线可以用来加密了。我们知道，密码学中用来加密的方案通常都有一定的数学保证，那么椭圆曲线算法的保证是什么呢？椭圆曲线的数学保障：已知椭圆曲线E,给定基点G和点kG,其中k为整数，无法在有效时间内计算出k。上面给出了椭圆曲线的数学保障，如果不是很理解这个保障，那么我们可以对应着RSA的数学保障来理解一下这个问题，在指数运算之中，给定aa和bb,我们可以很快地计算出abab,但是给定aa和abab，却没有很快的计算方法计算出bb(在取模的情况下)。这个说法仅仅助于理解，若想深入了解还需要从理论上给出一定的答复才严谨。有限域椭圆曲线的运算上面所提到的椭圆曲线的计算并不能直接用于密码学之中，因为在实数域上椭圆曲线的计算是有误差的，密码学要求精确。在ECC中，我们还可以定义“阶”的概念，理解阶的概念可以类比于次方操作中阶的概念。对于圆锥曲线上一点PP,其阶为最小整数aa，使得aP=°(modp)aP=0(modp)，其中°0为单位元。细心的读者可能会关心这样一个问题，°0是假想的一个无穷远点，怎么算出这样一个aa呢。这时候就需要用到单位元的概念了。如果我们计算得到了mP=p(modp)mP=p(modp)，那我们就知道a=m—la=m-1。上面所说的运算方法都是从几何角度给出的一个理解，那么如何在代数上进行计算呢？一般来说，给定，以下三步就可以计算：(1)结果x3=k2-xi—X2(modp)x3=k2-x1-x2(modp...
