椭圆曲线密码算法

椭圆曲线密码算法

椭圆曲线密码算法（Elliptic Curve Cryptography,ECC）是基于椭圆曲线数学的一种公钥密码算法，其安全性依赖于椭圆曲线离散对数问题的困难性。

下面这3篇文章详细讲述了椭圆曲线密码算法的数学原理，不过是英文版的，但是讲述的非常详细，需要掌握的相关数学概念也讲述的很清楚。 http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ http://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/ http://andrea.corbellini.name/2015/05/30/elliptic-curve-cryptography-ecdh-and-ecdsa/ 下面这2篇是上面文章的翻译： http://blog.csdn.net/mrpre/article/details/72850598 http://blog.csdn.net/mrpre/article/details/72850644

椭圆曲线密码算法优点

短的密钥长度，意味着小的带宽和存储要求。所有的用户可以选择同一基域上的不同的椭圆曲线，可使所有的用户使用同样的操作完成域运算。

椭圆曲线定义

设$p$是一个大于3的素数，在有限域$F_p$上的椭圆曲线$y^2=x^3+ax+b$由一个基于同余式$y^2=x^3+ax+bmodp$的解集$(x,y)\in F_p\times F_p$和一个无穷远点的特定点$O$组成，这里$a,b\in F_p$是满足$4a^3+27b^2̸=0modp$的常数。

下图是显示了其中一种实际的椭圆曲线：

对椭圆曲线上的点，我们可以定义一种形式的加法：如果椭圆曲线上的三个点位于同一直线上，那么它们的和为$O$（无穷远点）。

根据上面的定义导出椭圆曲线上的加法运算法则如下： 当$P̸=Q$时：

当$P=Q$时：

下面的动画解释了为什么是切线： 随着两个点越来越接近，过这两点的直线最终变成了曲线的切线

上面用几何的形式解释了椭圆曲线上的加法法则，下面是数学表达式。设$P_1=(x_1,y_1)$与$P_2=(x_2,y_2)$为椭圆曲线上的两个点，加减法运算如下： 1） $-O=O$ 2） $-P_1=(x_1,-y_1)$ 3） $O+P_1=P_1$ 4） 若$P_2=-P_1$，则$P_1+P_2=O$ 5） 若$P_2̸=-P_1$，则$P_1+P_2=(x_3,y_3)$，其中$x_3=m^2-x_1-x_2$，$-y_3=m(x_3-x_1)+y_1$，

椭圆曲线上点群的离散对数问题

给定椭圆曲线上的点$P$和点$Q$，寻找数$k$，使得$kP=Q$，其中$k$称为$Q$的基于$P$的离散对数。

在等式$kP=P+P+\cdots +P=Q$中，已知$k$和点$P$，求点$Q$比较容易，反之已知点$Q$和点$P$，求$k$却是相当苦难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计的。在实际应用中，$k$作为私钥，而$Q$作为公钥。

如何计算$kP=P+P+\cdots +P=Q$

用这种形式表示时，计算$kP$似乎需要$k$次加法运算。如果$k$有$n$个二进制位，那么算法的时间复杂度将为$O(2^n)$，这真不是很好。存在一些更快的算法。其中一种是“加倍（double)与相加（add)”算法。计算的原理可以用一个例子来更好地解释。取$n=151$。它的二进制表示形式为$10010111_2$ 。这一二进制表示形式可以转换为一系列$2$的幂之和。

(取$k$的 每个二进制位上的数字，并用它乘以一个$2$的幂.) 用这种方法，我们可以将$k$这样写:

“加倍（double)与相加（add)”算法需要这样做: • 取$P$. • 加倍，得到$2P$. • $2P$与$P$相加(为了得到 $2^{1}P+2^{0}P$). • 加倍 $2P$，得到$2^{2}P$. • 与前一结果相加 (得到 $2^{2}P+2^{1}P+2^{0}P$). • 加倍 $2^{2}P$，得到$2^{3}P$. • 对$2^{3}P$不做任何操作. • 加倍$2^{3}P$，得到$2^{4}P$. • 与前一结果相加 (得到 $2^{4}P+2^{2}P+2^{1}P+2^{0}P$). • … 最后，我们可以计算$151•P$，只需7次“加倍”运算和4次“相加”运算。

secp256k1椭圆曲线

比特币系统的区块链实现中使用的椭圆曲线为secp256k1。所以这里需要学习一下。 secp256k1曲线形如$y^2=x^3+ax+b$，由六元组$D=(p,a,b,G,n,h)$定义，其中： $p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F=2^{2}56-2^{3}2-2^9-2^8-2^7-2^6-2^4-1$ $a=0000000000000000000000000000000000000000000000000000000000000000$ $b=0000000000000000000000000000000000000000000000000000000000000007$ The base point G in compressed form is（压缩形式表示的基点G定义）: $G=0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798$ and in uncompressed form is（非压缩形式表示）: $G=0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8$ Finally the order n of G and the cofactor are（G的阶、协因子）:

G的阶：$n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141$ 协因子：$h=01$ secp256k1椭圆曲线形状如下： This is a graph of secp256k1’s elliptic curve $y^2=x^3+7$ over the real numbers. Note that because secp256k1 is actually defined over the field $Z_p$, its graph will in reality look like random scattered points, not anything like this. 详细参考：https://en.bitcoin.it/wiki/Secp256k1

椭圆曲线参数 六元组解释： 我们的椭圆曲线算法是工作在循环子群上的。几个参数含义如下： （1）素数$p$，这个值定义了有限域的大小 （2）椭圆曲线的系数$a$、$b$ （3）基点$G$（子群的生成元） （4）子群的阶$n$ （5）协因子$h$ ($h=N/n$)

补充数学概念

这里所用到的密码学其数学基础主要是《数论》、《代数》。如果想要弄清其原理，这两部分数学基础是需要研读的。

同余式

数学上，同余（congruence modulo，符号：≡）是数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。

两个整数$a,b,$若它们除以正整数$m$所得到的余数相等，则称$a,b$对于模$m$同余，记作$a\equiv b$ $(modm)$。读作$a$与$b$关于模$m$同余。（例 $26\equiv 14(mod12)$）。同余式的其他详细参考：https://zh.wikipedia.org/wiki/同餘

密码学与有限循环群

现代密码学算法和协议中，消息是作为有限空间中的数字或元素来处理的。加密和解密的各种操作必须在消息之间进行变换，以使变换服从有限消息空间内部的封闭性。然而，数的一般运算诸如加减乘除并不满足有限空间内部的封闭性。所以密码算法通常运行于具有某些保持封闭性的代数结构的空间中，这种代数结构就是有限循环群。在数学中，群是一种代数结构，由一个集合以及一个二元运算组成。群必须满足以下四个条件：封闭性，结合律，存在单位元和存在逆元。

群(Group)的定义： 设$G$是一个非空集合，对于$G$中的任意两个元素$a,b$，乘法运算满足以下条件，那么$G$称为一个群： (1). 对于$G$中任意元素$a,b,c$，有$a(bc)=(ab)c$. (2). 在$G$中存在一个元素$e$，它对$G$中任意元素$a$有$ea=a$.（有单位元） (3). 对于$G$中任意元素$a$，都存在$G$中一个元素$b$使的$ba=e$.（有逆）

最常见的群之一是整数集$Z$以及加法操作。

有限循环群在群的基础上满足两个额外条件：群元素个数有限以及交换律。循环群由单个元素（产生元）的叠加操作生成，最常见的有限循环群为模拟时钟。

椭圆曲线群定义

在数学上，椭圆曲线群的元素为椭圆曲线上的点，群操作为”+”,”+”的定义为，给定曲线两点$P$，$Q$，$P+Q$等于$P$和$Q$两点的连线与曲线交点沿$X$轴的对称点，如果$P=Q$，则$P+P$等于$P$在曲线上的切线与曲线交点沿$X$轴的对称点。该群的单位元为无穷远零点记作$O=(0,0)$，有$P+O=P$，点$P$的逆元为其沿$X$轴的对称点，记作$-P$。

椭圆曲线有限循环群

前面介绍的椭圆曲线都是基于有理数的，但是计算机运算浮点数(小数)的速度较慢，更重要的是四舍五入浮点数会产生误差，导致多次加密解密操作后原始消息不能被还原。故考虑到加密算法的可实现性，密码学上使用基于整数的模加运算产生椭圆曲线有限循环群。 基于整数的模加运算的特点：

运算速度快精确的运算结果产生有限循环

下面举例说明，如何产生ECC有限循环群： 例如考虑$y^2=x^3-7x+10(mod19)$的集合，该集合中所有的元素如下图所示。模运算把发散的椭圆曲线映射到19*19的正方形空间中，并且保持了原有曲线的上下对称特性。 下图展示了$y^2=x^3-7x+10(mod19)$集合中的元素和椭圆曲线的关系。 点$Q’$映射到点$Q$，点$P$的对称点也由点$-P’$映射到点$-P$。 如果取一个更大的质数$p$进行模运算，集合中的元素点也会相应地增多。下图展示了利用同一个曲线方程进行不同模运算的结果。在实际的椭圆曲线加密算法中，使用长度为192-256位的质数$p$进行模运算。

现在我们基于$y^2=x^3-7x+10(mod19)$，利用产生元$P=(2,2)$来生成ECC有限循环群。如下图所示。 $G=\{nP|P=(2,2)\}$完整的集合为$ { p=(2,2),2P=(13,8),3P=(1,2),4P=(16,17),5P=(10,3),6P=(18,15),7P=(3,15),8P=(12,1),9P=(9,12),10P=(5,10),11P=(17,15),12P=(7,0),13P=(17,4),14P=(5,9),15P=(9,7),16P=(12,18),17P=(3,4),18P=(18,4),19P=(10,16),20P=(16,2),21P=(1,17),22P=(13,11),23P=(2,17),24P=O=(0,0)}$。如下图所示，随着$n$的连续增加，元素点的分布没有任何特征，这正是密码学需要的特性。 可参考：http://mp.weixin.qq.com/s/jOcVk7olBDgBgoy56m5cxQ

椭圆曲线的阶

椭圆曲线定义在有限域上，这也意味着，椭圆曲线上的点也是有限的。所以引出了一个问题：一个椭圆曲线到底有多少个点？定义“椭圆曲线上点的个数”为 椭圆曲线的 阶 (order)。至于怎么计算阶参考这篇文章吧： https://en.wikipedia.org/wiki/Schoof's_algorithm

椭圆曲线的数乘和循环子群

在实数域，数乘（标量乘法）被定义如下： 如何计算及算法复杂度，上面有讲过，这里讲述它的一个性质。举例说明： 椭圆曲线$y^2\equiv x^3+2x+3(mod97)$，点$P=(3,6)$。现在计算$P$的数乘。 上图可以化为下图的表示形式： 结果显示点$P$的倍数的结果只有出现5个点，其他的点从未出现；其次他们是周期出现的。 显然，上面的5个点的集合，运算是封闭的。 当然，不仅仅$P$有这样的性质，其他点也有类似的性质。 即，$P$的加法构成了一个群$S$，由于$S$属于$G$，故$S$是$G$的子群。 循环子群是ECC的基础。

子群的阶

首先，我们已经定义了阶就是群中点的个数。在子群中也是这样的，但是我们可以换一种表达方式：子群的阶是最小能够使得$nP=0$的$n$。子群的阶和群的阶是有关系的。拉格朗日定理说明了，子群的阶是群的阶的因子。即如果$N$是群的阶，则其子群的阶$n$，则$n$是$N$的因子（$n$ is a diviser of $N$）。

找到子群的阶的方法（根据上面讲述的定义和性质就能得出下面的方法）： （1）计算群的阶$N$ （2）找出所有$N$的因子 （3）每个$N$的因子$n$，然后乘以$P$ （4）在3中，找出最小的$n$，使得满足$nP=0$。则$n$是子群的阶。

如何找一个基点

在ECC算法种，我们希望找到一个阶数较大的子群。 通常我们会选择一个椭圆曲线，然后计算它的阶$N$，选择一个较大的因子$n$，然后找一个合适的基点。也就是说，我们不是首先找一个基点，然后计算它的阶，而是相反，我们先找到一个合适的阶，然后找以这个数为阶的子群的生成元。

首先，拉格朗日揭示，$h=N/n$是一个整数（当然，$n$是$N$的因子），$h$有一个自己的名字：cofactor of the subgroup（协因子）。

其次，每个椭圆曲线上的点$P$，$NP=0$，因为$N$是$P$的阶$n$的倍数。 我们可以写成这样 $n(hP)=0$。 假设$n$是一个素数，我们令$G=hP$，则$G$就是子群的生成元。 $n$必须是素数，若非如此，则$nP=0$不一定表示$n$是$P$的阶，因为$P$的阶可能是$n$的一个因子。 总结如下：

计算椭圆曲线的阶$N$。选择一个数$n$当成子群的阶。$n$应该是$N$的素因数计算$h=N/n$随机选择一个点$P$计算$G=hP$如果$G$是$0$，到第4步。否则，我们找到了这个基点。