ECC算法学习（一）算法公式

news/2024/5/20 2:48:10/文章来源:https://blog.csdn.net/guoxulieying/article/details/131166912

ECC

一、ECC简介
- - 优缺点
  - 运用
二、算法理论基础
- - 1. 椭圆曲线的加法
  - 2. 椭圆曲线的二倍运算
  - 3. 同余运算
  - 4. 有限域
  - 5. 乘法逆元
三、算法公式
- - 1、有限域的负元
  - 2、有限域的加法， $P + Q$
  - 3. 斜率计算（P=Q即要计算P点切线，需要求导）
  - 4. 椭圆曲线加解密算法原理
  - 5. 椭圆曲线签名算法原理
  - 6. 签名过程
  - 7. 验证过程

一、ECC简介

ECC全称为“Ellipse Curve Ctyptography”，是一种基于椭圆曲线数学的公开密钥加密算法。与传统的基于大质数分解难题的加密算法不同，该加密方式基于 “离散对数” 这种数学难题。
椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。

优缺点

优点：
性能提升，同样的密钥长度，基于ECC加密要比基于RSA安全很多。而且计算量较小，处理速度更快，存储空间和传输带宽占用较少。

缺点：

曲线的选择很复杂。
ECC是基于椭圆曲线的离散对数问题，这并不是一个很好理解的问题，这里的椭圆曲线实际上并不是一个真正意义的椭圆，它的运算和椭圆类似，实际上是一个随着参数变化而不断变化的曲线，不同参数的选取会出现不同的曲线，不同的曲线就会形成不用的ECC标准，不同标准的ECC产生的加解密效果也是千差万别的。
有可能这条复杂的曲线被人植入了后门，别人就可以通过这个后门轻松的破解。
现行的一套很流行的ECC标准是由美国郭建安全局NAS发布的，这个标准就被很多人质疑是有被植入了后门的。
专利问题。
关于ECC的使用，很多人申请了很多的专利，现在关于ECC使用的专利大多数都掌握在一家公司的手中，这家公司就是黑莓。所以，当你想要构建自己的一套ECC标准的时候，可能不知道哪里就触及了它们的专利，卷入专利之争。

运用

目前我国居民二代身份证正在使用 256 位的椭圆曲线密码，虚拟货币比特币也选择ECC作为加密算法。

二、算法理论基础

椭圆曲线算法可以看作是定义在特殊集合下数的运算，满足一定的规则。椭圆曲线因为用二元三次方程y^2= x^3+ ax + b来表示,类似椭圆周长计算方程而得名。

1. 椭圆曲线的加法

过曲线上的两点A、B画一条直线，找到直线与椭圆曲线的交点，交点关于X轴对称位置的点，定义为A+B，即为加法。如下图A+B=C

请添加图片描述

2. 椭圆曲线的二倍运算

上述方法无法解释A+A，即两点重合的情况，因此在这种情况下，将椭圆曲线在A点的切线，与椭圆曲线的交点，交点关于X轴对称的位置的点，定义为A+A，即2A，即为二倍运算。

请添加图片描述

3. 同余运算

同余就是有相同的余数，两个整数 a、 b，若它们除以正整数 m所得的余数相等，则称 a， b对于模m同余。

$\equiv b(mod \quad m)$

4. 有限域

椭圆曲线是连续的，并不适合用于加密；所以必须把椭圆曲线变成离散的点，要把椭圆曲线定义在有限域上。而椭圆曲线密码所使用的椭圆曲线是定义在有限域内，有限域最常见的例子是有限域GF§，指给定某质数p，由0,1,2…p-1共p个元素组成的整数集合中加法、二倍运算。例如GF(233)就是
$y^2 = (x^3 + 7)(mod \quad 223)$

5. 乘法逆元

在模7乘法中：

1的逆元为 $1 (1 * 1)$
2的逆元为 $4 (2 * 4)$
3的逆元为 $5 (3 * 5)$
4的逆元为 $2 (4 * 2)$
5的逆元为 $3 (5 * 3)$
6的逆元为 $6 (6 * 6)$

三、算法公式

并不是所有的椭圆曲线都适合加密， $y^2 = x^3 + ax + b$ 类可以用来加密的椭圆曲线，也是最为简单的一类。

针对曲线Ep(a,b)表示为 $y^2 = x^3 + ax + b(mod \quad p), x,y \in [0,p], p为质数$

该曲线关于x轴对称。选择两个满足下列条件的小于p(p为素数)的非负整数a、b，要求满足以下条件
$3a^3 + 27b^2 \neq 0$

1、有限域的负元

$P (x, y)$ 的负元是 $\quad mod \quad p) = (x, p - y)$

2、有限域的加法， $P + Q$

$P(x_1, y_1)$ ， $Q(x_2, y_2)$ 和 $R(x_3, y_3)$ 三点(其中R是PQ直线与曲线的交点的关于x轴的对称点，即 $R = P + Q$ )有如下关系：
$x_3 \equiv k^2 - x_1 - x_2(mod \quad p)$
$x_3 \equiv k^2 - x_1 - x_2(mod \quad p)$

3. 斜率计算（P=Q即要计算P点切线，需要求导）

若 $P = Q$ ，则 $k = (2x_2 + a)/2y_1$
若 $\neq Q$ ，则 $k = (y_2 - y_1)/(x_2 - x_1)$

为了方便理解，可以套用以上公式，解决以下例题。

例：已知 $E_{23}(1,1)$ 上两点 $P (2, 10)$ , $Q (9, 7)$ ，求1) $- P$ , 2) $P + Q$ , 3) $2 P$

解：1) $P (3, 10)$ 的负元是 $\quad mod \quad 23) = (3, 23 - 10) = (3, 13)$
2) $\neq Q, k = (7 - 10)/(9 - 3) = -1/2$ ，因为 $\quad 23)$ ，
所以2的乘法逆元为12，
$\equiv -1 * 2^{-1}(mod \quad 23) \equiv -1 * 12(mod \quad 23)$ ，故k=11.
$x_3 \equiv k^2 - x_1 - x_2(mod \quad p) \equiv 11^2 -3 - 9(mod \quad 23) = 109(mod \quad 23) \equiv 17$
$y_3 \equiv k(x1. - x3) - y_1(mod \quad p) \equiv 11[3-(-6)] - 10(mod \quad 23) = 89(mod \quad 23) \equiv 20$ ，故 $P + Q$ 的坐标为 $(17, 20)$
3) $P = Q$ ，
$\equiv [3 * (3^2) + 1)] / (2 + 10)(mod \quad 23) = 7 + 5^{-1}(mod \quad 23)$ ，
因为 $\equiv 1(mod \quad 23)$ ，5的乘法逆元为14，
故k=6。
$x_3 \equiv k^2 - x_1 - x_2(mod \quad p) = 6^2 - 3 - 3(mod \quad 23) = 30(mod \quad 23) \equiv 7$
$y^3 \equiv k(x_1 - x_3) - y_1(mod \quad p) = 6 * (3 - 7) - 10(mod \quad 23) = -34(mod \quad 23) \equiv 12$ ，故 $x P$ 的坐标为 $(7, 12)$

4. 椭圆曲线加解密算法原理

设私钥、公钥分别为d、Q，即 $Q = d G$ ，其中G为基点，椭圆曲线上的已知G和dG，求d是非常困难的，也就是说已知公钥和基点，想要算出私钥是非常困难的。
公钥加密：选择随机数r，将消息M生成密文C，该密文是一个点对， $C = {rG, M+rQ}$ ，其中Q为公钥。
私钥解密： $M + r Q - d (r G) = M + r (d G) - d (r G) = M$ ，其中d、Q分别为私钥、公钥。

5. 椭圆曲线签名算法原理

椭圆曲线签名算法(ECDSA)。设私钥、公钥分别为d、Q，即 $Q = d G$ ，其中G为基点。

私钥签名：

选择随机数r，计算点 $r G (x, y)$ 。
根据随机数r、消息M的哈希h、私钥d，计算 $s = (h + d x) / r$ 。
将消息M、和签名 ${rG, s}$ 发给接收方。

公钥验证签名:

接收方收到消息M、以及签名 ${rG=(x,y), s}$ 。
根据消息求哈希h。
使用发送方公钥Q计算： $h G / s + x Q / s$ ，并与rG比较，如相等即验签成功。
原理： $h G / s + x Q / s = h G / s + x (d G) / s = (h + x d) G / s = r (h + x d) G / (h + d x) = r G$