【密码学】数学基础-椭圆曲线

简介: 本文来里聊一聊密码学当中另一个用的比较广泛的数学知识,椭圆曲线,至于为什么叫椭圆曲线,在参考资料[1]当中, 给出了一个解释。

数学基础之椭圆曲线


ZPG}WSS](XR1FK6I1[){RLA.jpg椭圆曲线

本文来里聊一聊密码学当中另一个用的比较广泛的数学知识,椭圆曲线,至于为什么叫椭圆曲线,在参考资料[1]当中, 给出了一个解释。

当初人们享用微积分计算椭圆曲线的周长,通过一定的积分技巧,最终要求出以下类型的积分:

image.png

其中分母的函数项是, 如果平方以下,就得到了, 这个恰好是椭圆曲线的方程的一种形式,这种形式被称为Weierstrass型。本文也主要讨论这一种类型,当然其他类型的曲线在密码学中也有使用,由于个人水平有限,就先只讲一下Weierstrass型。

友情提示: 本文后面会用到之前聊过的有限域的相关知识,如果不熟悉的读者可以自行回顾一下我之前写的文章。


实数域上的椭圆曲线

先来看一下实数域上的椭圆曲线,这里推荐一个工具,cocalc, 具体链接可以再参考资料里面找,这个工具可以在线使用saga等工具,本文当中大部分图都是用这个工具绘制的,同样我也会给出绘制的代码,各位读者大佬们可以自己玩玩。

先来看几个例子:

E = EllipticCurve([-1, 0])
Ep = plot(E,-3,4,thickness=1)
show(Ep)

H83EF7_2TDH~`FO46FN0D$4.png

image.gif曲线一

上图表示的是, 这一条曲线的图。

E = EllipticCurve([-1, 1])
Ep = plot(E,-3,4,thickness=1)
show(Ep)

25EK[4QE])M]W(OUBW[}_50.png曲线二

上图表示的是, 这一条曲线。

其余对于a和b的改变曲线的形状,读者可以自行构建环境运行看看,这里我就不过多去截图了。

直观的看完椭圆曲线的形状,那么接下来我们来看一下有关椭圆曲线的运算,本文只是简单介绍一下运算的规则和性质,有关证明,我其实也不太熟悉,所以就不讲了,这次不给自己挖坑,证明这东西看着头大,哈哈。

考虑一个集合,满足椭圆曲线(这里的曲线目前指的是Weierstrass, 后文不做特殊说明,均为这种形式)表达式所有的点(x, y)构成的集合, 这里要加上一个无穷远点的概念,记做O, 我们记做集合E(a, b), 如果a和b不同,所对应的集合也就不同。

比如上面的图当中我绘制的两条曲线,实际体现在代码当中就是EllipticCurve([-1, 0])EllipticCurve([-1, 1]), 分别对应a和b的值。

有了集合,自然而然的要考虑在这个集合上可以定义什么运算,我们在这个集合上定义一个加法运算"+", 可以证明,如果a和b满足如下条件:

image.png

的话,在这个加法运算和E(a, b)下,构成一个群,具体证明我也不太清楚,本文的重点还是一些结论,对于证明什么的先放到一边去吧。

首先,给出无穷远点,也就是上文提到的O是怎么来的,从几何的角度来说,如果椭圆曲线上的三个点共线,则他们的和为O, 基于这个无穷远点的定义,我们给出椭圆曲线上面具体的加法运算:

  • O是加法的单位元,对于单位元的性质,具体参考有限域的的知识,这里不啰嗦了,下面假设椭圆曲线上有两个点P和Q, 其中, 并且 。
  • 点P的负元是和点P当中x相同y坐标相反的点,根据椭圆曲线关于y轴对称,很容易验证,这个负元是在椭圆曲线上的,举个例子,比如P = (x, y),那么 -P = (x, -y)。
  • 如果要计算P和Q两个点的和,这肯定是不能简单的相加的,不相信的可以自己试试,如果直接横纵坐标相加,这个点大概率的不在这条曲线上了,所以定义如下规则的加法运算,连接P, Q, 显然可以得到一条直线和椭圆曲线相交于另一点R, 这个焦点是存在且唯一的,为了构成一个群,定义如下加法运算: P + Q = -R
  • 考虑Q=-P的情况,这里定义 P + (-P) = O, 两点由一条垂线连接,可以假设他们相交于无穷远点O
  • 最后一种情况,也就是倍点运算,也就是Q+Q的情况,这里可以画一条切线,相交曲线与S, 这里 Q + Q = 2Q = -S

通过上面的定义,可以证明在上述的加法运算下构成一个交换群。

对,作为灵魂画手的我又来手绘了,下图演示了在椭圆曲线上的加法运算,依然不接收绘图的吐槽,哈哈。

~PV~ATS)([9(ON]{DC8U5(S.png

image.gif加法运算

上面是通过几何的方面对椭圆曲线上的加法运算进行了描述,但是这个几何看起来直观,但是要进行运算,还是需要给出代数描述,这里直接给出结论,对于推导过程,想了解的可以读者自行查阅相关资料。

假设P = (, ), Q = (, ), 连接它们曲线的斜率为, 这个实际上也就是两点间的斜率公式,假设P和Q的连线l与椭圆曲线相交于点R, 经过计算可得R = P + Q,即:

image.png

除此之外,P和Q重合的情况,也就是倍点运算,具体公式如下:

image.png

到这里,实数域上面的椭圆曲线就介绍完了,本文只是做了一个简单的介绍,涉及到详细的数学推导这里都没有展开,有兴趣的读者可以自行查阅相关资料,不过作为了解这个东西,只是了解一些结论方面的东西个人感觉也够用了,当然如果想在椭圆曲线上面做深入研究的话,这个还是需要更深一层的了解的。


有限域()上的椭圆曲线

对于密码学而言,定义在实数域上面的东西大概率是没法直接来用的,因为在计算机里面存在的大多不会是连续的值,都是离散的值,所以考虑一下在有限域上的椭圆曲线,这里本文只讨论下的有限域,对于GF()这个其实也相似,不过计算起来要麻烦点,毕竟多项式的运算没有数字运算简单,所以先不讨论了。

来看一下在下面的椭圆曲线的表现形式,其实也就是x和y都取整数,并且模p, 表达式如下:

image.png

同样的,这里面也是有无穷远点O的,和实数域上的椭圆曲线不同的是,这里多了一个参数p, 所以这个群记做, 同样的,要想构成一个群,也是需要满足一定条件的, 具体条件如下:

image.png

这里和实数域上的也类似,只不过多了取模的运算。

同样的,我们来看一个例子,依然用cocalc来进行绘图,假设曲线, 具体绘图代码如下:

E = EllipticCurve(GF(23),[1,1])
print(E)
graphics_array([plot(E.change_ring(GF(23)))])

_`A~Q}DAUVW4OW13`HN55L0.png

image.gifE_23(1, 1)

这里,实际上他就不是连续的了,而是一个个离散的点,并且是没有什么规律的,具体的加法运算和实数域上类似,只不过要注意的是这里是在下的运算。

不过这个就没有几何方面的直观显示了,直接给出代数定义吧, 对于曲线的两个点P和Q:

image.png

其中:

image.png

这里实际上和实数域上面也是类似的,公式来源于密码编码学域网络安全一书。


小结

本文主要是介绍了一些椭圆曲线的一些运算方法和结论,并没有涉及实质性的证明,对于椭圆曲线来说,这里面用到的数学知识实际上比Elgamal和RSA多了不少,本文公式和文字比较多,也比较枯燥,希望读者见谅。

相关文章
|
存储 JavaScript 网络架构
【开源图床】使用Typora+PicGo+Github+CDN搭建个人博客图床
【开源图床】使用Typora+PicGo+Github+CDN搭建个人博客图床
476 3
|
消息中间件 存储 监控
消息队列:分布式系统中的重要组件
消息队列:分布式系统中的重要组件
|
监控
idea插件报错导致不能启动的处理技巧
在安装IDEA的插件时,难免会遇到插件不合理导致的IDEA启动时报错,没有办法从IDEA的plugins管理面板卸载插件,那怎么办呢? 答:手动删除。查找IDEA的日志C:\Users\{username}\.IntelliJIdea2016.1\system\log\idea.log,启动IDEA并监控该日志行为及报错信息;然后在电脑上安装Everything (该工具可
6318 1
|
安全 开发工具 git
CTF工具隐写分离神器Binwalk安装和详细使用方法
CTF工具隐写分离神器Binwalk安装和详细使用方法
3868 0
|
关系型数据库 PostgreSQL
|
2月前
|
存储 自然语言处理 安全
PHP-Casbin:现代化 PHP 应用的权限管理引擎
PHP-Casbin 是基于 PERM 模型的轻量级权限框架,支持 ACL、RBAC、ABAC 等多种访问控制模型,适用于 API 安全控制、企业权限管理等场景。其灵活配置、多语言协同与分布式支持,使其成为现代化 PHP 应用权限管理的首选工具。
124 0
|
人工智能 供应链 安全
|
算法 安全 网络安全
支付系统,网络安全06----支付安全---,机密性,加密算法,目前最流行的加密算法,AES加密算法,目前最流行的非对称加密算法RSA,对称加密和非对称加密的优缺点,非对称加密是基于非常复杂的数学算法
支付系统,网络安全06----支付安全---,机密性,加密算法,目前最流行的加密算法,AES加密算法,目前最流行的非对称加密算法RSA,对称加密和非对称加密的优缺点,非对称加密是基于非常复杂的数学算法
|
搜索推荐 算法 UED
探讨CSDN等级制度:博客等级、原力等级、创作者等级
探讨CSDN等级制度:博客等级、原力等级、创作者等级
797 0
|
存储 机器学习/深度学习 算法
【数据结构入门精讲 | 第二篇】考研408、企业面试基础概念习题
【数据结构入门精讲 | 第二篇】考研408、企业面试基础概念习题
666 0