ecc算法

[复制链接]
510|7
手机看帖
扫描二维码
随时随地手机跟帖
keer_zu|  楼主 | 2022-5-13 08:17 | 显示全部楼层 |阅读模式
ECC算法介绍
        ECC(Elliptic Curves Cryptography)加密算法是⼀种公钥加密算法,与主流的RSA算法相⽐,ECC算法可以使⽤较短的密钥达到
相同的安全程度。近年来,⼈们对ECC的认识已经不再处于研究阶段,开始逐步进⼊实际应⽤,如国家密码管理局颁布的SM2算法就是基
于ECC算法的。下⾯我们来认识⼀下ECC的⼯作原理。
椭圆曲线
定义
        在引⼊椭圆曲线之前,不得不提到⼀种新的坐标系-------射影平⾯坐标系,它是对笛卡尔直⾓坐标系的扩展,增加了⽆穷远点的概念。
在此坐标系下,两条平⾏的直线是有交点的,⽽交点就是⽆穷远点。两者的变换关系为:
笛卡尔坐标系中的点a(x,y),令x=X/Z,y=Y/Z,则射影平⾯坐标系下的点a的坐标为(X,Y,Z),如点(2,3)就转换为(2Z,3Z,Z)。

椭圆曲线定义:⼀条椭圆曲线在射影平⾯上满⾜⽅程:

54296627da2e3692a1.png

的所有点的集合,且曲线上每个点都是⾮奇异的。
该⽅程有名维尔维斯特拉斯⽅程,椭圆曲线的形状不是椭圆,只是因为其描述的⽅程类似于计算⼀个椭圆周长的⽅程。转换到笛卡尔坐标系
下的⽅程为:
316627da3780e3a5.png


使用特权

评论回复
keer_zu|  楼主 | 2022-5-13 08:21 | 显示全部楼层
加法法则
运算法则:任意取椭圆曲线上两点P、Q (若P、Q两点重合,则做P点的切线)做直线交于椭圆曲线的另⼀点R’,过R’做y轴的平⾏线交
于R。我们规定P+Q=R。(如图)
38349627da44dddb23.png


83465627da3f7912ff.png

使用特权

评论回复
keer_zu|  楼主 | 2022-5-13 08:28 | 显示全部楼层
密码学中的椭圆曲线
定义

在有限域Fp中定义⼀个椭圆曲线,常⽤ 53447627da4d83b497.png

  • Fp中只有p个元素,p为素数
  • Fp中,a+b≡c (mod p),a×b≡c (mod p),a/b≡c (mod p)
  • 13665627da54bb1efc.png (mod p)  a,b是⼩于p的⾮负整数
  • x,y属于0到p-1间的证书,曲线标记为Ep(a,b)

阶:椭圆曲线上⼀点P,存在正整数n,使得nP=O∞,则n为P的阶,若n不存在,则P是⽆限阶的,有限域上定义的椭圆曲线上所有点的阶
都存在。
椭圆曲线难题
K=kG,其中K,G为Ep(a,b)上的点,k为⼩于n的整数,n是点G的阶,给定k和G,计算K容易,但是给定K和G,求k就很难了!
因此,设K为公钥,k为私钥,G为基点。


使用特权

评论回复
keer_zu|  楼主 | 2022-5-13 08:28 | 显示全部楼层
加密过程
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。


使用特权

评论回复
keer_zu|  楼主 | 2022-5-13 08:29 | 显示全部楼层
签名验签流程
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(modp)
8. B计算R'=(Hash*G+M'*K)/S=(Hash*G+M'*kG)*r/(Hash+M'k)=rG=R(x,y),若R'=R,则验签成功。
以上加解密和签名验签流程只是⼀个例⼦,具体应⽤时可以利⽤K=kG这⼀特性变幻出多种加解密⽅式。


使用特权

评论回复
keer_zu|  楼主 | 2022-5-13 09:52 | 显示全部楼层
keer_zu|  楼主 | 2022-5-13 09:52 | 显示全部楼层
keer_zu|  楼主 | 2022-5-13 09:54 | 显示全部楼层
ecc.pdf (780.67 KB)

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

个人签名:qq群:49734243 Email:zukeqiang@gmail.com

1288

主题

12164

帖子

53

粉丝