Cryptography_ECC椭圆曲线加密算法

算法介绍

椭圆加密算法（ECC）是一种公钥加密体系，最初由Koblitz和Miller于1985年提出，其数学基础是利用椭圆曲线上的有理点构成阿贝尔加法群上椭圆离散对数的计算难度。 公钥密码系统根据其所基于的问题一般分为三类：大质因数分解问题、离散对数问题和椭圆曲线问题。 有时椭圆曲线类也归为离散对数类。 与RSA相比，ECC的优势在于可以使用更短的密钥来达到与RSA相当或更高的安全性。 RSA加密算法也是一种非对称加密算法。 RSA广泛用于公钥加密和电子商务。 . 常用于通信加密、数字签名等。据研究，160位ECC加密的安全性等同于1024位RSA加密，210位ECC加密的安全性等同于2048位RSA加密。 比特币和美丽的国家政府都在使用。 挺好的，但是由于后门问题等一些原因，一直没有被广泛使用。

知识概念

椭圆曲线

公式如下图

a、b的取值满足

下图是曲线某a、b值对应的坐标图

当我们随机选取曲线上的A点和B点时，连接线的延长线与曲线上的另一点相交，交点按X轴镜像对称，得到C点，而C点与A相连，且与曲线A交点关系相同，然后将此交点镜像到X轴上得到D点，重复k次得到最后一个点Q，问题用这个算法就是知道起点A和终点Q，但是不知道中间经历了多少次运算，也就是向前计算Q点很简单，但反向计算k的值（即运算次数）比较困难。

上面是两点AB，可以表示为A+B=C（这里不是简单的加法运算，而是数学运算，比如求斜率，求交点等）

那么如果AB两点无限接近，那么就等于A点相切再镜像，可以表示为A+A=2A（这不是简单的加法运算，而是数学运算，比如如寻找坡度、寻找交点等）

点乘：Q=kP 点Q是最后一个点，点P是起点A。

DH（Diffie-Hellman 密钥协商算法）

Diffie-Hellman 密钥协商算法是一种保证共享密钥KEY 安全穿越不安全网络的方法。 它是OAKLEY的一个组件，由Whitefield和Martin Hellman于1976年提出。这种机制的巧妙之处在于需要安全通信的两方可以使用这种方法来确定对称密钥。 然后可以使用此密钥进行加密和解密。 但是需要注意的是，这个密钥交换协议/算法只能用于密钥的交换，不能用于消息的加解密。 在双方决定使用的密钥之后，使用其他对称密钥操作加密算法对消息进行实际加密和解密。

ECDH

将椭圆曲线的特性加入到DH算法的思想中后，称为ECDH。 大致流程如下

这就是ECDH的密钥交换算法。 ECDHE 是指临时使用。

ECC加解密过程

r：代表一个随机数

M：表示明文

Q：表示公钥（端点）

P：表示起点

k：私钥

Q=kP：即起点P经过k次操作得到Q点

加密：从消息M中选择一个随机数r生成密文C，C=(rP,M+rQ)

2. 选择一个

解密：M+rQ-k(rP) = M+r(kP)-k(rP) = M

由于椭圆曲线是连续的，因此不适用于密码学。 所以需要将其转化为离散的有限域。

在密码学中，有限域GF(p)是一个非常重要的域，其中p是质数（因为当p是质数时，可以保证集合中的所有元素都有加法和乘法逆元（0除外）） . 简单来说，GF(p)就是mod p，因为一个数对p取模后，结果在[0, p -1]之间比特币曲线，即域中有p个元素。 对于元素a和b，则(a+b) mod p和(a*b) mod p，结果都是域中的元素。 GF(p)中的加法和乘法就是通常的加法和乘法。 GF(p)的加法和乘法单位分别为0和1。 元素的加法和乘法的逆元很容易理解和得到，这里就不多说了。 在《密码学与网络安全》一书中有详细介绍。 说。

限制椭圆曲线公式的取值，比如x,y,x,y的取值范围为整数，运算结果向上取整，设置p的值后，p取模后限制曲线在等式两边的一个区域中，如下图，四舍五入后，就会变成一个离散的有限域（因为画图工具的缘故，好像有连续的，其实都是一个一个点). 该域中点的总数 n 称为曲线的阶数。

最后还有一个问题，就是公钥Q（端点）是一个坐标点，如何将其转化为序列值，即把y值作为奇偶校验放在x值前面。 由于我们主要是了解原理，所以关于乘法逆、阿贝尔群、椭圆曲线计算公式等方面的知识这里就不做说明了，有兴趣的可以单独研究。

画图不易比特币曲线，如有转载请说明，学无止境，如有错误还望大家不吝赐教。