ECC(椭圆曲线加密算法)公私钥生成方法

曲线方程为:

( )

mod p(modulo prime number p)表示该曲线位于素数阶p的有限域上，那么曲线形状可以近似为下图：

Elliptic-curve cryptography ( ECC ) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields ECC requires smaller keys compared to non-ECC cryptography (based on plain Galois fields ) to provide equivalent security

参考文章

[TOC]

数学上，椭圆曲线为一代数曲线，形如

$$y^2 = x^3 + ax + b$$

并且该曲线无奇点(尖点或自相交)，判别式$\Delta = -16(4a 3+27b 2)$不为0

在椭圆曲线中添加无穷远点 O ,由于曲线关于y轴对称，假设P为曲线上一点，则P关于y轴的对称点定义为-P。无穷远点的对称点为其自身，因此 O = -O

定义 + 运算，假设P，Q，-R在曲线上，则 P + Q = -R -> P + Q + R = O 其中-R与P，Q共线。

定义数乘

$$

nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}

$$

$$y^2 = x^3 + ax+ b \bmod{p}$$

下图是曲线$y^2 = x^3 -7x+10\bmod{p}$，其中p为19，97，127，487时的点集。可看到点集关于y = p/2对称。

定义直线$ax+bx+c \equiv 0 \bmod{p}$，既等间距的直线族。

若点集中P,Q,-R三点在同一直线上，则 P+Q+R = O

$(9 9^{-1})\ mod\ 23 = 1 = (9 18)mod\ 23$

$P = (x_p,y_p)$

$Q = (x_q,y_q)$

$R = (x_r,y_r)$

$$P+Q = -R$$

公式

$$

x_r = (m^2-x_p-x_q) \bmod{p}

$$

$$

y_r = [y_p+m(x_r-x_p)]\bmod{p}

$$

若$P \neq Q $则$m = (y_p - y_q)(x_p-x_q)^{-1}\bmod{p}$

若$P = Q$则$m = (3x_p 2+a)(2y_p) {-1}\bmod{p}$

点集中点的数量称为椭圆曲线的阶数，有快速算法 Schoof's algorithm

$$nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}}$$

例如曲线$y^2 \equiv x^3 + 2x + 3 \bmod{97}$的点$P = (3,6)$

通过上边例子可以看出P与数乘，最终只有有限的循环出现的几个结果$kP = (k\bmod{5})P$,这五点在加法运算下封闭。这五点构成了 循环子群 ，其中P称为 generator or base point of the cyclic subgroup

Cyclic subgroups are the foundations of ECC and other cryptosystems

the order of is the smallest positive integer $n$ such that $nP = 0$ In fact, if you look at the previous example, our subgroup contained five points, and we had $5P = 0$

The order of $P$ is linked to the order of the elliptic curve by Lagrange's theorem , which states that the order of a subgroup is a divisor of the order of the parent group

In other words, if an elliptic curve contains $N$ points and one of its subgroups contains $n$ points, then $n$ is a divisor of $N$, so $N\ mod\ n \equiv 0$

For example, the curve $y^2 = x^3-x+3$ over the field $F_{37}$ has order $N = 42$ Its subgroups may have order 1,2,3,6,7,14,21 and 42 If we try $P = (2,3)$ can see that $1P\neq0,2P\neq0,3P\neq0,6P\neq0,7P=0,$ so the order of is 7

对于ECC算法，我们希望子群阶数足够高。所以通常我们选择一条椭圆曲线，计算其阶数，并选择一个较大的因子作为子群的阶数，最终找到一个基点。

在Lagrange's theorem中令$h =N/n$,称$h$为 cofactor of the subgroup 余因子

由于$nP = 0$所以$h(nP) = 0 = n(hP)$

现在考虑$n$是素数,令$G =hP$,则生成一个以$G$为基点的n阶子群

现已知点PQ在椭圆曲线上，如何确定整数$k$使得$Q =kP$ 这个问题被称为椭圆曲线的离散对数问题，这个问题被认为是一个困难的问题，目前还没有多项式时间解决方法。

在密码学中Digital Signature Algorithm (DSA), the Diffie-Hellman key exchange (D-H) and the ElGamal algorithm都与该问题有关。

ECC问题相比其它几个问题更难以解决。

Our elliptic curve algorithms will work in a cyclic subgroup of an elliptic curve over a finite field

得到算法六元组$(p,a,b,G,n,h)$

在前面提到离散对数问题非常困难，但也不是所有的都困难，有些类型的椭圆曲线就非常脆弱，有非常快速的方法解决，例如$p = hn$时就有多项式时间解决的方法。

怎样保证曲线是安全的呢？

为了解决这个问题，我们需要再附加一个参数 seed $S$，这是一个随机数涌来生成参数a和b，或者基点G再或者所有的参数。这些参数通过hash函数生成，hash容易计算但是难以逆推。

椭圆曲线的生成通过随机数生成，这使得曲线足够的随机。

如果我们知道$d$和$G$,计算$H$非常容易。但是如果我们仅知道$H$和$G$,计算$d$将非常困难，因为这是离散对数问题。

ECDH是 Diffie-Hellman algorithm 的一种变体，更像密钥交换协商而不是加密。应用场景：双方需要安全的交换信息，即使第三方拦截到也无法破译。这是TSL背后的一个原则。

$$S=d_AH_B=d_A(d_BG)=d_B(d_AG)=d_BH_A$$

Alice使用私钥$d_A$签名文件，Bob使用Alice的共钥$H_A$来确认。

ECDSA作用在消息的hash上，而不是直接作用在消息上。Hash函数可以选择密码学安全的。hash需要被截断为和子群阶数$n$所占bit一样的长度，例如前边n是256bit，那么hash也需要是256bit，截断后的hash定义为整数$z$

$(r,s)$ 就是签名。

Alice对hash $z$ 使用私钥 $d_A$ 和随机数 $j$签名。Bob使用Alice的共钥 $H_A$验证。

验证签名，验证签名需要Alice的共钥 $H_A$ 截断的hash $z$，以及签名 $(r,s)$

如果 $r=x_P\bmod{n}$则是合法的

$$

\begin{array}{rl}

P & = u_1 G + u_2 H_A \

& = u_1 G + u_2 d_A G \

& = (u_1 + u_2 d_A) G

\end{array}

$$

再带入 $u_1,u_2$的定义

$$

\begin{array}{rl}

P & = (u_1 + u_2 d_A) G \

& = (s^{-1} z + s^{-1} r d_A) G \

& = s^{-1} (z + r d_A) G

\end{array}

$$

这里省略了$mod\ n$，因为在子群阶数为$n$,所以相当于自动对n取模。由$s = k^{-1} (z + rd_A) \bmod{n}$推出$k = s^{-1} (z + rd_A)\bmod{n}$

$$

\begin{array}{rl}

P & = s^{-1} (z + r d_A) G \

& = k G

\end{array}

$$

这与签名算法第二步生成的是同一个点P，接下来验证是否满足生成算法第三步即可验证签名。

当使用ECDSA进行数字签名时，k要相当饱满。如果每次签名都使用相同的k，或者k是可预测的，那么就被找出私钥。 This is the kind of mistake made by Sony a few years ago ，PS3只能运行Sony使用ECDSA签名过的程序，但问题是Sony使用了固定的k

这样可以轻松的找出Sony的私钥$d_S$，只要买两份签名的游戏，取出他们的hash ($z_1 z_2$),和两份签名$(r_1,s_1),(r_2,s_2)$,以及椭圆参数。

$$

s = k^{-1}(z+rd_S)\bmod{n}\Rightarrow d_S = r^{-1}(sk-z)\bmod{n}

$$

我们认为离散对数问题是非常困难的，但是并没有数学上的证明。目前解决离散对数问题由三种方法，假设$Q=xP$，求x

随意假定$x=am+b$

$$

\begin{array}{rl}

Q & = xP \

Q & = (am + b) P \

Q & = am P + b P \

Q - am P & = b P

\end{array}

$$

选择一条标准曲线 prime192v1 ,$n$=0xffffffff ffffffff ffffffff 99def836 146bc9b1 b4d22831,$\sqrt{n} \approx 79\cdot10 {28}$，每个点需要32Byte存储，大概总共需要$25\cdot10 {30}$byte，这比全世界存储还多。而且 prime192v1 还是一个低阶曲线。

使用量子算法可让复杂度降低$O((\log{n})^3)$

$y 2+xy=x 3+ax^2+1$ a为0或1，拥有$2^m$点，其中m为素数

$x 2+xy=x 3+x^2+b$ b是随机生成的整数

这两条曲线计算较快。

1背景简介

随着通讯网络特别是Internet的高速发展，利用网络作为信息交流和信息处理变得越来越普遍，社会的传统事务和业务运作模式受到前所未有的冲击。目前，无论是国家政府还是企业都正融入这场网络革命中，从其原来的传统经营模式向网络模式演化。未来的电子政务、电子商务、电子业务将成为不可逆转的发展趋势。在与日俱增的网络活动中，人们越来越关心信息安全这个问题。这集中体现在：

（1）网络的身份认证——确认网络客户的真实身份

（2）信息和数据的保密性——个人或系统机密信息和数据保护

（3）信息和数据完整性——防止不合法的数据修改

（4）不可抵赖性——网络环境下行为的事后的不可抵赖（数字签名）

信息安全中最核心的技术是密码技术，基本上可分为序列密码、对称密码（又称分组密码）、非对称密码（又称公钥密码）三种。

非对称密码算法是支撑解决以上所涉的四个关键方面的问题的核心。目前越来越流行的是基于PKI体系模型的解决方案。在PKI体系模型中，客户端需要一较好的个人信息安全载体，智能卡或智能密码钥匙将是一较理想的方式，都必须支持公钥算法，而ECC是最适合使用在这一资源受限制的客户端产品中。

2 椭圆曲线密码算法ECC

自公钥密码问世以来，学者们提出了许多种公钥加密方法，它们的安全性都是基于复杂的数学难题。根据所基于的数学难题来分类，有以下三类系统目前被认为是安全和有效的：

（1）大整数因子分解系统(代表性的有RSA)，

（2）有限域（数学中的一种代数结构）离散对数系统(代表性的有DSA)，

（3）有限域椭园曲线离散对数系统(ECC)。

当前最著名、应用最广泛的公钥系统RSA是由Rivet、Shamir、Adelman提出 的(简称为RSA系统)，它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA方法的优点主要在于原理简单，易于使用。但是，随着分解大整数方法的进步及完善、计算机速度的提高以及计算机网络的发展（可以使用成千上万台机器同时进行大整数分解），作为RSA加解密安全保障的大整数要求越来越大。为了保证RSA使用的安全性，其密钥的位数一直在增加，比如，目前一般认为RSA需要1024位以上的字长才有安全保障。

但是，密钥长度的增加导致了其加解密的速度大为降低，硬件实现也变得越来越难以忍受，这对使用RSA的应用带来了很重的负担，对进行大量安全交易的电子商务更是如此，从而使得其应用范围越来越受到制约。DSA（Data Signature Algorithm）是基于有限域离散对数问题的数字签名标准，它仅提供数字签名，不提供数据加密功能。安全性更高、算法实现性能更好的公钥系统椭圆曲线加密算法ECC（Elliptic Curve Cryptography）基于有限域上椭圆曲线的离散对数计算困难性。人类研究椭圆曲线已有百年以上的历史，但真正把其应用到密码学中是1985年由Koblitz(美国华盛顿大学)和Miller(IBM公司) 两人提出。定义在有限域（Fp 或F(2m)）的椭圆曲线(y2=x3+ax+b)上的点（x,y），再加上无穷点O，如按一定的规则运算（估且称为乘法）将组成一个群（数学中的一种代数结构）。有限域上椭圆曲线乘法群也有相对应的离散对数计算困难性问题。因此，许多公开密码系统都是基于此问题发展出来的，如类似ELGamal,DSA等密码系统的ECES，ECDSA。

3 椭圆曲线加密算法ECC的优点

椭圆曲线加密算法ECC与RSA方法相比有着很多技术优点：

●安全性能更高

加密算法的安全性能一般通过该算法的抗攻击强度来反映。ECC和其他几种公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数计算困难性（ECDLP）在计算复杂度上目前是完全指数级，而RSA 亚指数级的。这体现ECC比RSA的每bit安全性能更高。

●计算量小和处理速度快

在一定的相同的计算资源条件下，虽然在RSA中可以通过选取较小的公钥（可以小到3）的方法提高公钥处理速度，即提高加密和签名验证的速度，使其在加密和签名验证速度上与ECC有可比性，但在私钥的处理速度上（解密和签名），ECC远比RSA、DSA快得多。因此ECC总的速度比RSA、DSA要快得多。同时ECC系统的密钥生成速度比RSA快百倍以上。因此在相同条件下，ECC则有更高的加密性能。

●存储空间占用小

ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多。160位 ECC与1024位 RSA、DSA有相同的安全强度。而210位 ECC则与2048bit RSA、DSA具有相同的安全强度。意味着它所占的存贮空间要小得多。这对于加密算法在资源受限环境上（如智能卡等）的应用具有特别重要的意义。

●带宽要求低

当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时ECC带宽要求却低得多。而公钥加密系统多用于短消息，例如用于数字签名和用于对对称系统的会话密钥传递。带宽要求低使ECC在无线网络领域具有广泛的应用前景。

4椭圆曲线加密算法ECC的相关标准

ECC的这些特点使它在某些领域（如PDA、手机、智能卡）的应用将取代RSA，并成为通用的公钥加密算法。许多国际标准化组织(政府、工业界、金融界、商业界等)已将各种椭圆曲线密码体制作为其标准化文件向全球颁布。ECC标准大体可以分为两种形式：一类是技术标准，即描述以技术支撑为主的ECC体制，主要有IEEEP1363、ANSI X962、ANSI X963、SEC1、SEC2、FIP 186-2、ISO/IEC 14888-3。规范了ECC的各种参数的选择，并给出了各级安全强度下的一组ECC参数。另一类是应用标准，即在具体的应用环境中建议使用ECC技术，主要有ISO/IEC 15946、IETF PKIX、IETF TLS、WAP WTLS等。在标准化的同时，一些基于标准（或草案）的各种椭圆曲线加密、签名、密钥交换的软、硬件也相继问世。美国RSA数据安全公司在1997年公布了包含ECC的密码引擎工具包BSAFE 40; 以加拿大Certicom为首的安全公司和工业界联合也研制、生产了以椭圆曲线密码算法为核心的密码产品，还提出了各种安全条件下对椭圆曲线离散对数攻击的悬赏挑战。可以相信，ECC技术在信息安全领域中的应用会越来越广。

椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为 ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。

椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。

椭圆曲线密码学：

椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射。

基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。其缺点是同长度密钥下加密和解密操作的实现比其他机制花费的时间长。

但由于可以使用更短的密钥达到同级的安全程度，所以同级安全程度下速度相对更快。一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。

公钥加密算法有两种，RSA 和 ECC，RSA 简单易懂但效率低，ECC 效率高，用 256 位秘钥抵得过 RSA 3072 位秘钥，但 ECC 数学原理复杂，实现也比 RSA 难。

要理解 ECC 椭圆曲线加密算法，就得顺藤摸瓜，一路搞定下面这些原理。

于是得到了这样的曲线：

这个方程式用来加解密的过程，就不解释了，网上资料不少，密码学的书中也有。

其原理基于，射影平面上的加法算法，其正向过程是简单容易的，而加法的逆向过程，则是困难的。我们可以用打台球来比喻，确定一个球的初始位置为 p1，对 p1 进行 n 次击球（假设 n 次击球的力度和方向一致），最终获得位置为 p2。已知 p1 和 n，则获得 p2 非常容易，进行 n 次击球便可。但若已知 p1 和 p2，要倒推出 n 来，则很难。这个道理，人人皆知。 椭圆曲线在射影平面上的加法之不可逆，和上面的台球游戏类似。

用来加解密和签名的 ECC 曲线，由如下几个参数确定：(p,a,b,G,n,h)。 p 便是有限域的整数范围， a，b 则是确定曲线的形状， G 是曲线上选择的初始点，n 则是用来进行加法的次数， h 是协因子，不知道干嘛用的，一般取 1。

比特币所用 Secp256k1 曲线的参数如下：

p = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 = 2^256 – 2^32 – 977

a = 0

b = 7

这就是中本聪挑选的曲线，并非一条流行通用的曲线。去掉模运算，用 x y 方程简单表示为 y^2 = x^3 + 7。

Secp256k1 中 “sec” 的意思是 Standards for Efficient Cryptography，"p" 则代表有限域参数 p，256 代表 p 的位数，而 “k” 则大有深意。

“k” 代表 Koblitz，这是椭圆曲线加密算法发明人 Koblitz 的名字，在这里指的一类曲线，这一类曲线的参数是刻意挑选出来的。比如上面的 a 和 b，一个 0，一个 7，一看就知道是刻意挑选出来的。

k 后面的 1 代表序号。

与 “k” 对应的叫 “r”，所谓 r 指代 Random，就是随机数的意思。大家就明白了，曲线所用参数是随机挑选出来的。比如 Secp256r1 的参数如下：

p = 2^224(2^32 − 1) + 2^192 + 2^96 − 1

a = 115792089210356248762697446949407573530086143415290314195533631308867097853948

b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

这个 Secp256r1 还有一个名字，叫 NIST P256，NIST 是 National Institute of Standards and Technology，也就是美国国家标准技术委员会，隶属商务部，专门为政府机构制定技术标准。所以，Secp256r1 那算是闪耀着官方光环的技术。这个标准是 1999 年 NIST 发布的。

既然 p，a，b这些参数都是随机挑选出来的，那么自然应该更安全了。理论上是这样的，但“随机” 这两个字可不是那么容易的，不是上嘴唇一碰下嘴唇就能出来一个随机数。 计算机里的随机数一直是个难题。 

Secp256r1 的随机数生成是用哈希算法 SHA1 实现的，用SHA1算法对某个字符串进行哈希，每次都能生成非常随即的数字。 而 Secp256r1 的 p，a，b 做 SHA1 的字符串是：c49d360886e704936a6678e1139d26b7819f7e90。

密码学界以及加密学应用技术行业的疑心由此而起：NIST 为何挑选了这个字符串？

哈希运算的特点，大家都清楚，NIST 无法根据一条既定曲线，返过去计算出 SHA1 的种子字符串。

所以大家就怀疑，NIST 很可能测试了无数的种子字符串，最终选择了一条较弱的曲线。这是一种暴力的挑选方法，据传 NIST 测试了 10 亿条曲线。2014 年密码学者 Daniel J Bernstein1 和 Tung Chou 便发表过文章 “How to manipulate curve standards: a white paper for the black hat” 介绍了如何操控 ECC 曲线标准的制定。

大家的担心虽然并无实证，但 NIST 在椭圆曲线上做手脚，并非第一次，而且之前那次是有实锤证据的。2007 年 NIST 发布了 130 页的技术标准文书： NIST Special Publication 800-90，其中介绍了 “Deterministic Random Bit Generators”，也就是随机数生成的技术，和上面所说用 SHA1 生成随机数类似。 介绍的技术中，有一种叫 Dual_EC_DRBG，也就是用双椭圆曲线生成随机数的技术。 技术原理和用椭圆曲线做加法进行加密类似。

还用台球做比，为了生成随机数，在巨大巨大的 “有限域” 台球桌上摆放两个台球在 p1 和 p2 位置。对在 p1 的第一个台球进行 n 次击打，n是一个秘密数字，获得位置 p1‘，这就是生成的随机数。完事后 p2 也进行 n 次击打，获得位置 p2’，将 p2‘ 替代 n，作为下一次生成随机数的秘密数字。最后，将 p1 和 p2 摆回最初的位置 p1 和 p2，等待下次。

从原理上来说，这种算法生成随机数是没问题的。就是比起其它随机数生成算法，效率要慢一些，有些密码学家就提出这个问题，这种算法的效率比该标准中的其他算法要慢三个数量级。

诡异的是，Dual_EC_DRBG 是 NSA 推荐到 NIST，并强力支持的。 NSA 是谁？大名鼎鼎的美国国家安全局，与美国民间密码学界斗争多年的强力部门。

2007 年，牛逼的 CRYPTO 大会上，密码学者 Dan Shumow 和 Niels Ferguson 指出，Dual_EC_DRBG 不仅是慢的问题，它有后门啊，NIST 指定的算法也许没问题，但 P1 和 P2 这两个初始位置有问题：这两个参数之间是有关系的，可以推算的。

这真是打了 NIST 和 NSA 的脸。当然，密码学者们并没有实锤证据，到底这个是 NIST 和 NSA 恶意设计，还是一个为他们工作的科研人员私下作恶。

直到 2013 年棱镜门爆发，斯诺登披露的政府文件显示，NSA 刻意在加密算法中植入后门。之后，路透社披露，NSA 收买了 RSA 公司，在其软件中植入 Dual_EC_DRBG，以利于破解加密技术，对互联网信息进行窃听。一切水落石出真相大白，就是 NSA 协同 NIST 捣的鬼。

比特币中对 Secp256r1 弃而不用，选择了 Secp256k1，而中本聪开发比特币软件，是在 2008 年之前。所以应当是在 2007 年 CRYPTO 大会上对 Dual_EC_DRBG 的责难，引起了中本聪的警觉。那时候棱镜门还没爆发，对于 NSA 的恶意操纵，还并没有证据。

机构作恶，人们无可奈何，无人脸红，也无人为其负责。放个后门，放了就放了吧，大家躲着走就是。

网上对于椭圆曲线加密过程的介绍过于繁琐，对于只想了解加密如何进行的人来说浪费时间，所以我这里只对关键计算步骤进行介绍，略去椭圆曲线的相关原理（百度一搜一大把）。

最最关键且基本只用到的是 Ep(a,b)的加法

对与椭圆曲线y^2 = x^3+ax+b(mod p) ：

两点P(x1,y1) Q(x2,y2),P≠-Q,则P+Q=(x3,y3)由以下算法定义：

实际通信流程如下：

再对点M进行解码就可以得到明文。上述流程中的加法即为Ep(a,b)的加法。

这个算法实际是基于已知kG难解k实现的，简单清晰。