读书频道 > 安全 > 深入浅出密码学——常用加密技术原理与应用
9.1.2 椭圆曲线上的群操作
2012-09-26 16:20:23     我来说两句 
收藏    我要投稿   
本书拥有的诸多特征使得它成为密码学从业者和学生独一无二的资源—本书介绍了绝大多数实际应用中使用的加密算法,并重点突出了它们的实用性。对于每种加密模式,我们都给出了最新的安全评估和推荐使用的密钥长度...  立即去当当网订购

假设用加法符号2“+ ”表示群操作。“加”意味着给定两个点及其对应的坐标,比如p
我们需要计算第三个点R 的坐标,使得:


 

下面将看到,事实证明加法操作看上去是非常随意。幸运的是,如果考虑定义在实数上的曲线,对应的物理位置可以很好地说明加法操作。而使用地理位置进行说明时,必须区分两种情况:两个不同点的加法( 即相异点相加) 和同一点与自身的加法( 即相同点相加) 。

相异点相加P+ Q 这个主要是针对计算R = P + Q ,且P  ≠  Q 的情况。构建的方法为:画一条经过P 和Q 的线,该线与椭圆曲线的交点就是第三个点。根据定义,将第三个点关于x 轴映射,得到的映射点就是点 R 。图9-4 显示了实数上椭圆曲线的相异点相加。


 

相同点相加P + P 这主要针对的是P + Q 但P = Q 的情况。因此,可以写作R = P + P  =2P。这里的构建方式有点不同。画一条经过P 点的切线,即可得到此切线与椭圆曲线的第二个交点;将此交点关于x 轴映射,得到的对称点就是相同点相加的结果R 。图9-5 显示了实数上椭圆曲线的相同点相加。


 

你也许想知道为什么群操作的形式看上去很随意。因为某些历史原因,如果已知两个点,在仅使用加、减、乘和除四种算术运算的情况下,常用这种tangent-and-chord 方法来构建第三个点。事实证明,如果椭圆曲线上的点采用这种方式进行相加,则点的集合也满足群所需的大多数条件,即闭合性、结合性、存在单位元和逆元。

当然,密码体制不可能使用这种几何构建方式;但使用这种简单的坐标几何就可以把上面的两种几何构建表示为分析表达式,即公式。正如上文所述,这些公式仅涉及四个基本的算术运算;并且这四个算术运算可以在任何域中进行,而非仅限于实数域内( 比照第4.2 节)。现在以上面使用的曲线方程为例,考虑它在素数域 GF(p)而不是实数域上的特性,就可得到群操作的如下分析表达式:
 
椭圆曲线上的相同点相加与相异点相加


 

其中


 

注意:在相异点加法中,参数s 指的是经过P 和Q 的直线的斜率;而在相同点加法中,参数s 指的是经过点P 的切线的斜率。

尽管我们已经在有限群的构建方面取得极大进步,但最终还是没有成功。我们一直忽略的一个问题就是椭圆曲线上所有的点都满足


 

的单位元( 或中性元)  。事实证明,满足这个条件的点 (x ,  y )是不存在的。所以,我们将一个无穷的抽象点定义为单位元  。这个无穷点可以看作是位于 y 轴正半轴的无穷远处,或y 轴负半轴的无穷远处。

根据群的定义,现在可将任何群元素P 的逆元- P 定义为:


 

现在的问题是,我们如何找到-P ?如果使用上面提到的tangent-and-chord 方法,则点的逆元为点,即其逆元是该点关于x 轴对称的点。图9-6 显示了点P 与其对应的逆元。从这里可以看出,找到点的逆元非常简单,只需得到其y 坐标的负数即可。对素数域 GF(p ) 上的椭圆曲线( 这是密码学中最有趣的情况) 而言,实现起来非常容易,因为,因此可以得到:



 

到目前为止,我们已经定义了椭圆曲线的所有群属性。下面来看一个群操作的示例。
 
示例9.4   考虑小型域Z17上的曲线:


 

点P =(5, 1) 的相同点加法为:


 

为便于说明,我们可将坐标插入到曲线方程中,检查结果2 P = (6, 3) 是否真的是曲线上的一个点:
 


 

_____________________________________________________________
2. 将操作选择命名为“加法”完全是随意的,我们也可以将其称为乘法。

点击复制链接 与好友分享!回本站首页
分享到: 更多
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:9.1.1 椭圆曲线的定义
下一篇:9.2 使用椭圆曲线构建离散对数问题
相关文章
图文推荐
排行
热门
文章
下载
读书

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站