加载中…
个人资料
区块链的作坊
区块链的作坊
  • 博客等级:
  • 博客积分:0
  • 博客访问:31,052
  • 关注人气:9
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

椭圆曲线算法(二)

(2017-05-18 19:01:32)
标签:

ecc

密码技术

椭圆曲线

离散对数

打台球

 一、单向函数

        单向函数是密码学应用中的一个重要数学问题,可以说没有单向函数,就没有公钥密码体制。所谓单向函数就是这样一种计算规则:从A计算B容易,但是从B推导A是极困难的,因为认为它的计算方向只能是一个方向,所以称为单向函数。大质数的模运算就是一种非常有效的单向函数,比如给定大数a,p,计算a mod p=b,这很容易,但是反过来,知道b,p,要想计算a是极困难的。

二、离散对数问题

        给定一个质数p,和有限域Zp上的一个本原元a,对Zp上整数b,寻找唯一的整数c,使得a^c≡b(mod p),计算c就是所谓离散对数问题。一般的,如果仔细选择p(p很大,比如2的256次方长度的数),则认为该问题是难解的,且目前还没有找到计算离散对数问题的多项式时间算法(可理解为有效降低时间复杂度的计算方法)。所以离散对数问题是更为复杂的单向函数。这使得离散对数问题成为密码学应用的一个重要数学理论基础。下面问题就是如何选择这个有限域Zp,使得离散对数问题计算复杂度最大。引入椭圆曲线离散对数,就是为了构造这样的有限域Zp。

三、椭圆曲线离散对数问题

        椭圆曲线方程的所有解(x,y)再加上自定义的一个无穷远的点构成了方程的解集,由椭圆曲线的定义知道,曲线是连续的,故解集中解有无穷多个,密码学应用需要的是有限域,所以需要建立计算规则,从解集来构建一个有限元素的域,作为离散对数问题的域。所以现在有了初始的元素域,我们来构造计算规则,计算出一个符合离散对数问题的有限域Zp。

        (1)加法规则

        椭圆曲线上的两点(不同)P、Q,P+Q=R,R的值是这样得到的:过P、Q两点的直线与椭圆曲线相交第三点R',然后找到R'以x轴对称的点即为R;如果P、Q点相同,则过点是切线,其相交于曲线的另一点R',同样找到以x轴对称的点即为R。

        事实证明,采用这种方法计算得到的点的集合满足群的大多数条件:闭合性、结合性、存在单位元和逆元。这里对具体计算坐标的公式就不做讨论了,需要了解可以查相关参考文献。

        还有一个问题需要定义,就是单位元即一个点θ,对任意点P,满足P+ θ=P,事实证明,这个点是不存在的,为此我们自定义一个无穷远的虚点为单位元,根据群的定义,对任意一个群元素P,其存在一个逆元-P,满足P+(-P)=θ,那么如何找到-P呢?

        利用前面的加法规则,可以找到-P是P关于x轴对称的点,如果点P坐标(xp,yp),则逆元-P坐标为(xp,-xp),这对于素数域上的椭圆曲线而言,实现起来非常容易, -yp=p-yp mod p

      到目前为止,我们找到了构造椭圆曲线的域、群、群属性的所有内容。

      (2)椭圆曲线离散对数问题的密码学应用

        在某些条件下,椭圆曲线上所有点构成一个循环群,并且一定存在一个本原元,它的幂值生成了整个群(这就是离散对数问题)。为此,我们给定一个椭圆曲线E,确定本原元p和一个元素T,那么离散对数问题就是找到整数d,满足P+P+......+P=dP=T。在密码体制中,d通常为整数,也是私钥,曲线上的点T是公钥,坐标为(xT,yT),前面我们已经介绍了如何计算dP。

        如果回到实数上的椭圆曲线就会发现,椭圆曲线离散对数问题的几何解释也非常简单:给定一个起点P ( 公开参数) ,可以通过在椭圆曲线上来回跳跃,有效地计算2 P,3 P ,…,dP = T ( 公钥) ;然后发布起点P 和终点T。为了破译密码体制,攻击者必须弄清楚在椭圆曲线上“跳跃”的频率;而这个跳跃的次数就是密码d ,即私钥。

       有一个非常形象的比喻:椭圆曲线离散对数问题犹如一个人打台球,从一个点出发,经过n次击打,把球打到指定的位置是容易的,但是告诉你球的起点和终点,让你计算击打的次数却非常困难,因为击打的方案有很多。

 

[参考文献]

1、可汗学院

2、百度百科

3、一个关于椭圆曲线密码学的初级读本。http://8btc.com/thread-1240-1-1.html

      

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有