一、概述

如今，许多加密算法和安全标准都使用公钥算法加解密和数字签名。其中RSA算法应用最广泛。RSA基于离散对数的算法，密钥长度越长，安全性越高。近年来，出于安全需要，RSA密钥长度越来越长，计算时间越来越慢。如今，交易任务量巨大，长期的密码学操作给系统带来了巨大的负担。因此，密钥长度较小的椭圆曲线算法正发挥着越来越重要的作用。研究表明，在相同的安全条件下，使用256位椭圆曲线密钥和3072位RSA密钥的安全性相当。

二、原理

2.1 椭圆曲线

椭圆曲线不同于我们高中的椭圆曲线。它是有限域上的平面曲线，曲线上的点符合方程 y 2 = x 3 a x b y^2=x^3 ax b y2=x3 ax b 椭圆曲线域和曲线上的操作符合阿贝尔群的定义，阿贝尔群可以参考我之前的博客

密码学速检查笔记(1)-- 对称加密加密

椭圆曲线与阿贝尔群的对应关系如下：

首先是计算对象，一般在椭圆曲线上。
然后是阿贝尔群中的运算符号椭圆曲线的定义如下 R Q P ′ = 0 R Q P' = 0 R Q P′=0 R Q = ? P ′ = P R Q = -P' = P R+Q=−P′=P 简单来说就是R点加Q点，等于RQ所在直线与椭圆曲线的交点，对x轴作对称的点
最后是运算的幺元为无穷远点 O O O ，因为其满足 O = − O O = -O O=−O 且 P + O = P = O + P P+O = P = O+P P+O=P=O+P

当R和Q重合时，RQ所在的直线为椭圆曲线的切线，此时，我们可以用数字点乘的形式代表 Q + Q = 2 Q Q+Q=2Q Q+Q=2Q 对于数字乘点这个运算，符合乘法交换律，如下例： 2 ( 3 Q ) = 3 ( 2 Q ) = 6 Q 2(3Q)=3(2Q)=6Q 2(3Q)=3(2Q)=6Q

对于一个数字乘点操作，已知点 Q Q Q 和数字 k k k ，我们可以很轻松算出点 P = k Q P=kQ P=kQ ，但是已知 P P P 和 Q Q Q 的情况下，算出 k k k 往往是很复杂的，就像在一个四面都是镜面，封闭的房间中，有一束激光光源和反射点，我们无法推测该光源究竟经过了多少次反射才能映射到反射点。这就是椭圆曲线加密中使用到的最核心的特性。在公钥加密算法中， Q Q Q点常作为一个公开的基点， k k k点为私钥，通常为随机数， P = k Q P=kQ P=kQ 则常被用作公钥。

下面贴一份蛋老师的讲解视频，讲得很清楚，可以作为博客的补充。

bilibili–公钥加密技术ECC椭圆曲线加密算法原理

2.2 Elliptic Curve Diffie-Hellman算法（ECDH）

Diffie-Hellman是一种密钥交换算法，可以在一个非安全的通信渠道中形成一个共享、不会被窃取的密文。刚刚分享的视频里也举了个例子，假设Alice的私钥是蓝色，Bob的私钥是红色，公钥是黄色，他们想生成一个共享的颜色，但是又不想其他人知道这个颜色，于是他们首先用自己的私钥颜色和公钥颜色混合，然后将该混合颜色发送给对方，如Alice将蓝色和黄色混合得到绿色，Bob将黄色和红色混合得到褐色，然后Alice把绿色发给Bob，Bob将褐色发给Alice，然后他们再使用这个颜色和自己的颜色混合，得到相同的黄褐色。蓝 + 黄 + 红 = 红 + 黄 + 蓝蓝+黄+红 = 红+黄+蓝蓝+黄+红=红+黄+蓝在ECDH算法中，相同的场景，Alice和Bob想生成一个共同的密文，Alice拥有密钥对 ( d A , Q A ) (d_A,Q_A) (dA,QA)，Bob拥有密钥对 ( d B , Q B ) (d_B,Q_B) (dB,QB)。Alice和Bob相互知道对方的 Q Q Q。下一步，Alice会计算 ( x k , y k ) = d A Q B (x_k,y_k)=d_A Q_B (xk,yk)=dAQB，Bob会计算 ( x k , y k ) = d B Q A (x_k,y_k)=d_B Q_A (xk,yk)=dBQA ，共享的密文为 x k x_k xk。因为 d A Q B = d A ( d B G ) = d B ( d A G ) = d B Q A d_AQ_B=d_A(d_BG)=d_B(d_AG)=d_BQ_A dAQB=dA(dBG)=dB(dAG)=dBQA

在ECDH中，Alice和Bob对外界都只展示公钥 Q Q Q ，没有人能够从公钥算出私钥，所以攻击者也无法得到共享密文 x k = d Q x_k=dQ xk=dQ 了。而且为了进一步保护信息，通常共享密文会经过hash处理，去除密文中的weak bits使得攻击更加困难。

2.3 Elliptic Curve Digital Signature Algorithm算法（ECDSA）

椭圆曲线的特性同样能被利用在数字签名算法中，它是DSA算法中的一个变种。这里列出具体的符号定义

Parameter
Ep(a,b)	椭圆曲线，方程为 y 2 = x 3 + a x + b y^2=x^3+ax+b y2=x3+ax+b
G G G	基点，一个曲线上的大素数阶n子群的点
n n n	G的阶，满足 n G = O nG=O nG=O， O O O是幺元
d A d_A dA	私钥，一个随机数
Q A Q_A QA	公钥， d A G d_AG dAG
m m m	发送出去的消息
H H H	哈希处理后的消息 H a s h ( m ) Hash(m) Hash(m)

数字签名具体流程如下，首先Alice和Bob回协商好通信的参数： Alice：

选择一个椭圆曲线 E p ( a , b ) E_p(a,b) Ep(a,b)，选择曲线上的一点 G G G作为基点。
生成公私钥对 ( Q A , d A ) (Q_A,d_A) (QA,dA)，并将 n n n， E p E_p Ep， G G G， Q A Q_A QA发送给Bob。 Bob：
检查 Q A Q_A QA 是否不等于幺元 O O O。若等于，签名一定不合法
检查 Q A Q_A QA 是否在曲线 E p ( a , b ) E_p(a,b) Ep(a,b) 上
检查 n Q A nQ_A nQA 是否等于幺元 O O O

每次发送消息时： Alice准备对消息 m m m 签名发送给Bob:

Alice对消息作哈希 H = H a s h ( m ) H=Hash(m) H=Hash(m) ，哈希函数有SHA-2，SHA-3等，会把消息转换为一个整数

取 H H H最左的 n n n 个数字，得到消息摘要 z z z

选择一个介于 [ 1 , n − 1 ] [1,n-1] [1,n−1] 的随机数字 k k k

计算曲线上的点 R = ( x 1 , y 1 ) = k G R=(x_1,y_1)=kG R=(x1,y1)=kG

计算 r 1 = x 1 m o d n r_1=x_1 \mod n r1=x1modn，如果 r 1 = 0 r_1=0 r1=0，返回第3步