区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

Koblitz和Miller独立地提出了椭圆曲线公钥密码体制(ECC),安全性基于椭圆曲线群上的离散对数问题的难解性,该问题目前最好的解法是指数级时间的算法。

导语:本课堂用通俗易懂的系列内容为大家呈现区块链与密码学领域相关知识。这里有知识也有故事,从感兴趣到有乐趣,全民课堂等你来学。这个系列中的课程内容首先从比特币着手进行入门介绍,再延伸至区块链的相关技术原理与发展趋势,然后深入浅出地依次介绍在区块链中应用的各类密码学技术。欢迎大家订阅本公众号,持续进行学习。

6.4 椭圆曲线简介

– 椭圆曲线的定义 –

1985年,Koblitz和Miller独立地提出了椭圆曲线公钥密码体制(ECC),安全性基于椭圆曲线群上的离散对数问题的难解性,该问题目前最好的解法是指数级时间的算法。

一般认为,RSA和DH密钥交换协议需用1024比特以上的模数才安全,但对ECC,只要160比特的模数就可达到同样级别的安全性。

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

椭圆曲线指的是由Weierstrass方程

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

所确定的曲线

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线图形

有限域Fp上的椭圆曲线是由满足Fp上的方程  

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

的所有点和无穷远点O构成的集合

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

有时也记作E

– 椭圆曲线上的加法运算 –

PQ是E上的任意两点,连接PQER’,则称R’关于x轴的对称点RPQ的和,记为:

Q = R

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线加法运算示意图

PQ重合时

R = P+Q = P+P = 2P

此时称之为点倍运算

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线点倍运算示意图

PQ关于x轴对称时,

定义PQ的和为O,即:

Q = O

并称O为无穷远点

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线无穷远点示意图

可以证明,有限域上的椭圆曲线在我们定义的加法运算下构成群。

既然构成群,就必然有零元和负元,这里的零元就为无穷远点OP的负元就是它关于x轴的对称点,记为–P

显然有

P+=O+P=P

P=(xy),则 –P=(x, –y) 且 P+(–P)=O

– 加法运算的代数表示 –

已知E(F)上两点P=(x1, y1), Q=(x2, y2) , 求P+Q

解:设P+Q=R =(x3, y3),

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

解得

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线点加运算代数表示

P≠Q时,

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

P=Q时,

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线点加运算代数表示

k(k>2)个相同的点P相加为

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

此时称之为点乘运算

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法
椭圆曲线点乘运算示意图

– 椭圆曲线离散对数问题 –

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

称n为点P的阶,记为n=ord(P)

由阶为n的点P在上述加法定义下生成的循环群<P>是椭圆曲线群(E(F), +)的一个n阶子群。

设E是有限域F上的椭圆曲线,GE的一个循环子群,点PG的一个生成元,即G={kP: k≥1},在已知PQ的条件下,求解整数n,使得nP=Q的问题,称为椭圆曲线E上的离散对数问题。

今天的课程就到这里啦,下一堂课我们将学习基于椭圆曲线的数字签名算法中的SM2算法,带大家继续了解数字签名,敬请期待!

区块链与密码学全民课堂第6-4讲:椭圆曲线的数字签名算法

同学们可以关注PlatON World,持续学习哦。我们下节课见啦。

本文转载自https://mp.weixin.qq.com/s?__biz=MzUzNTg2ODg5MQ==&mid=2247492121&idx=1&sn=74c8fbd681f9f15cac6f21ec0db5cb43&chksm=fafc46adcd8bcfbb1fdb8f2c604f3f8e06833d65186ee92023ae404f5f6c078fc8d15ab81a66&scene=178&cur_album_id=1411898566347735044#rd

(0)
上一篇 3月 7, 2021 08:37
下一篇 3月 8, 2021 20:51

相关推荐

发表评论

登录后才能评论