鸿蒙源码分析（三十六）

客官°小女子只卖身不卖艺 2022-09-07 04:00 219阅读 0赞

# Ecc算法简单介绍 #

因为安全加密模块使用到很多椭圆曲线加密方法，今天主要为大家介绍一下ecc的加密原理和简单流程。具体详细过程这里不做过赘述，只介绍加密和签名的验证。因为算法代码中主要涉及这部分的知识。详细的知识原理可以参考csdn有相关优秀文章，本篇博客借助博主 **Leo挺** 文章链接在后面。  
ECC（Elliptic Curves Cryptography）加密算法是一种公钥加密算法，与主流的RSA算法相比，ECC算法可以使用较短的密钥达到相同的安全程度。近年来，人们对ECC的认识已经不再处于研究阶段，开始逐步进入实际应用，如国家密码管理局颁布的SM2算法就是基于ECC算法的。下面我们来认识一下ECC的工作原理。

## 代码部分传送门 ##

[hks\_mbedtls\_ecc.c文件代码分析][hks_mbedtls_ecc.c]

## 一、椭圆曲线 ##

**定义**  
在引入椭圆曲线之前，不得不提到一种新的坐标系-------射影平面坐标系，它是对笛卡尔直角坐标系的扩展，增加了无穷远点的概念。在此坐标系下，两条平行的直线是有交点的，而交点就是无穷远点。两者的变换关系为：  
笛卡尔坐标系中的点a（x,y），令x=X/Z，y=Y/Z，则射影平面坐标系下的点a的坐标为（X,Y,Z)，如点（2,3）就转换为（2Z,3Z,Z）。  
椭圆曲线定义：一条椭圆曲线在射影平面上满足方程： Y 2 Z + a 1 X Y Z + a 3 Y Z 2 = X 3 + a 2 X 2 Z + a 4 X Z 2 + a 6 Z 3 \\mathrm\{Y\}^\{2\} \\mathrm\{Z\}+\\mathrm\{a\}\_\{1\} \\mathrm\{XYZ\}+\\mathrm\{a\}\_\{3\} \\mathrm\{YZ\}^\{2\}=\\mathrm\{X\}^\{3\}+\\mathrm\{a\}\_\{2\} \\mathrm\{X\}^\{2\} \\mathrm\{Z\}+\\mathrm\{a\}\_\{4\} \\mathrm\{XZ\}^\{2\}+\\mathrm\{a\}\_\{6\} Z^\{3\} Y2Z\+a1XYZ\+a3YZ2=X3\+a2X2Z\+a4XZ2\+a6Z3的所有点的集合，且曲线上每个点都是非奇异的。

该方程有名维尔维斯特拉斯方程，椭圆曲线的形状不是椭圆，只是因为其描述的方程类似于计算一个椭圆周长的方程。转换到笛卡尔坐标系下的方程为：  
 y 2 + a 1 x y + a 3 y = x 3 + a 2 x 2 + a 4 x + a 6 y^\{2\}+a\_\{1\} x y+a\_\{3\} y=x^\{3\}+a\_\{2\} x^\{2\}+a\_\{4\} x+a\_\{6\} y2\+a1xy\+a3y=x3\+a2x2\+a4x\+a6  
**加法法则**  
运算法则：任意取椭圆曲线上两点P、Q （若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R。我们规定P+Q=R。（如图） ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2OTc2MjUy_size_16_color_FFFFFF_t_70]

*  此处+不是简单的实数相加，是抽象出来的
 *  O∞+P=P，O∞为零元
 *  曲线上三个点A,B,C处于一条直线上，则A+B+C=O∞

下面，我们利用P、Q点的坐标(x1,y1)，(x2,y2)，求出R=P+Q的坐标(x4,y4)。  
P,Q,R’共线， 设为  y = k x + b y=k x+b y=kx\+b,  
若  P ≠ Q , k = ( y 1 − y 2 ) / ( x 1 − x 2 ) P \\neq Q, \\quad k=\\left(y\_\{1\}-y\_\{2\}\\right) /\\left(x\_\{1\}-x\_\{2\}\\right) P=Q,k=(y1−y2)/(x1−x2)  
若  P = Q , k = ( 3 x 2 + 2 a 2 x + a 4 − a 1 y ) / ( 2 y + a 1 x + a 3 ) P=Q, k=\\left(3 x\_\{2\}+2 a\_\{2\} x+a\_\{4\}-a\_\{1\} y\\right) /\\left(2 y+a\_\{1\} x+a\_\{3\}\\right) P=Q,k=(3x2\+2a2x\+a4−a1y)/(2y\+a1x\+a3)  
解方程组得到：  
 x 4 = k 2 + k a 1 − a 2 − x 1 − x 2 x\_\{4\}=k^\{2\}+k a\_\{1\}-a\_\{2\}-x\_\{1\}-x\_\{2\} x4=k2\+ka1−a2−x1−x2  
 y 4 = k ( x 1 − x 4 ) − y 1 − a 1 x 4 − a 3 ; y\_\{4\}=k\\left(x\_\{1\}-x\_\{4\}\\right)-y\_\{1\}-a\_\{1\} x\_\{4\}-a\_\{3\} ; y4=k(x1−x4)−y1−a1x4−a3;$

## 二、密码学中的椭圆曲线 ##

**定义**  
在有限域Fp中定义一个椭圆曲线，常用 y 2 = x 3 + a x + b y^2 = x^3+ax+b y2=x3\+ax\+b

1.  Fp中只有p个元素，p为素数
2.  Fp中，a+b≡c (mod p)，a×b≡c (mod p)，a/b≡c (mod p)
3.  4a3+27b2≠0　(mod p) a，b是小于p的非负整数
4.  x，y属于0到p-1间的证书，曲线标记为Ep（a，b）

阶：椭圆曲线上一点P，存在正整数n，使得nP=O∞，则n为P的阶，若n不存在，则P是无限阶的，有限域上定义的椭圆曲线上所有点的阶都存在。  
**加密过程**

1.  A选定一条椭圆曲线Ep（a,b），并取曲线上一点作为基点G
2.  A选择一个私钥k，并生成公钥K=kG
3.  A将Ep（a,b）和k，G发送给B
4.  B收到后将明文编码到Ep（a,b）上一点M，并产生一个随机数r
5.  B计算点C1=M+rK，C2=rG
6.  B将C1，C2传给A
7.  A计算C1-kC2=M+rkG-krG=M
8.  A对M解码得到明文

攻击者只能得到Ep（a,b），G，K，C1，C2，没有k就无法得到M。

**签名验证过程**

1.  A选定一条椭圆曲线Ep（a，b），并取曲线上一点作为基点G
2.  A选择一个私钥k，并生成公钥K=kG
3.  A产生一个随机数r，计算R(x,y)=rG
4.  A计算Hash=SHA(M)，M‘=M(modp)
5.  A计算S=（Hash+M’k）/ r(modp)
6.  B获得S和M’，Ep(a,b)，K，R(x,y)
7.  B计算Hash=SHA(M)，M’=M(mod p)
8.  B计算R’=（Hash\*G+M’*K）/S=(Hash*G+M’\*kG)\*r/(Hash+M’k)=rG=R（x,y），若R’=R，则验签成功。

**综上所述，代码主要基于加密和验签原理实现。感谢阅读和点赞（摘自leo挺的博客）**

文章参考链接：[ecc算法介绍][ecc]

[hks_mbedtls_ecc.c]: https://blog.csdn.net/m0_46976252/article/details/119786865
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2OTc2MjUy_size_16_color_FFFFFF_t_70]: /images/20220829/7a3fc2b5c8e14273aed29308615b67aa.png
[ecc]: https://blog.csdn.net/leo_wonty/article/details/7366418?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162959601916780261954866%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=162959601916780261954866&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v29-2-7366418.pc_search_result_cache&utm_term=ecc%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187