基于蒙哥马利域的ECC算法的优化

◆陈曼

基于蒙哥马利域的ECC算法的优化

◆陈曼

（山东大学数学学院 山东 250013）

由于现代社会通讯技术的发展，使得消息的传递更加方便，但同时伴随着消息被窃听，泄露，篡改的危险。为了安全的传递消息，许多加密算法随即被提出。本文主要讨论基于离散对数问题的椭圆曲线加密方案，通过结合几何与代数的思想来讨论椭圆曲线的运算规律，提出基于蒙哥马利域设计运行椭圆曲线加密解密程序，其相对于一般数域程序结果大概快了10倍。

椭圆曲线；蒙哥马利算法；加密算法

1 引言

为了解决上述难题，Neal Koblitz 和Victor Miller 两人在1985年分别独立地提出了椭圆曲线加密算法。椭圆曲线加密方案相比于RSA加密算法，它运用了较高深的数学知识——椭圆曲线离散对数问题，这能够减少对密钥长度的要求，即椭圆曲线安全传输消息允许使用较短长度的密钥。椭圆曲线密码由于使用更短长度的密钥，具有更小存储容量，更慢带宽的优势，能够广泛应用在线上支付，手机智能卡，无线传递信息。经过几十年的发展，椭圆曲线加密算法被各大国际组织机构广泛的使用，许多国际组织如ANSI、IEEE、ISO将椭圆曲线标准化。到目前为止，椭圆曲线数字签名机制ECDSA已成为经济贸易传输信息的加密标准。因此，针对椭圆曲线密码研究有效的优化算法，具有重要的实际用处和发展前景。

2 椭圆曲线密码储备知识

2.1 基本概念

称为点乘运算，或为标量积。

2.2 椭圆曲线

设椭圆曲线是如下方程

可以推出椭圆曲线是齐次方程，且满足

图1 椭圆曲线运算法则

并且

2.4 椭圆曲线加密系统

（1）例如Alice选择一条椭圆曲线，选择椭圆曲线上p（3.10）作为椭圆曲线上的基点，且基点的阶数是28。

（4）Bob需要计算

（5）Bob再将消息传递给Alice，因此Alice根据

人活着，并不会一切顺利如意，但如果我们都有小草那种顽强拼搏，无私奉献的精神，那我们的祖国必将充满无限的生机与活力。

能够得到M的值。

3 基于蒙哥马利域上ECC算法的实现

椭圆曲线加密系统主要在于倍点运算。蒙哥马利算法[4]利用完全剩余系的性质，在计时避免了的除法运算，能够有效地提高模乘运算的速度。Montgomery算法的基本思想是：计算；设，，；，通常取；是r模n的逆，即；。因为，所以mod r、都可以通过简单的移位操作实现，从而消去了最复杂的除法运算。

图3 流程图

计算

算法：

Step 1

具备烘干功能的洗烘一体机，已经在大众消费者当中形成一部分固定需求，并引领出一种新兴的生活方式，在线上线下均呈现出高速增长。中怡康监测数据显示，2018年1-9月，洗烘一体机线上零售额同比增长41.5%，线下同比增长49.2%。

Step 2

Step 3 if then

return

else return

基于网络爬虫的调查数据一般都会存在不可避免的“硬伤”。网络信息繁多而杂乱，有效信息占比过少而导致调查数据存在较大偏误，本次探索性调查存在以下几个缺陷：(1)有效招聘信息比例较低。大量招聘信息由于不规范或不完整，而被视为无效信息剔除。本文通过网络爬虫共采集了招聘信息17 346条，经过数据清理后的有效招聘只有6 826条，有效率不到四成。(2)无法获取珠三角企业通过其他途径发布的招聘信息。如企业委托猎头公司引进高端人才或者在国外网站发布的招聘信息，都无法获取。(3) “隐形”招聘需求无法获取。由于国内外籍人才数量太少，大多特定领域的外籍人才几乎不可能在国内找到，从而没有发布招聘信息。

艺术家每次创作出的女性题材的画面，应该充满视觉的动力、极强手感性的大笔触与大色域，创造出很有视觉的“摩擦力”，发出个性化的特殊艺术语言。当创作画面时可用不多的书写性线条或色块创作出“近似形象”，而不需要达到很细微。这样可使色块或线条成为产生特定效果的刺激物，成为耐人寻味的主体，也即转化成为画中事、画中物，这些色彩和线条组合即为“视觉力”的强有力场。

大数bitmap的实现：在C语言中，我们通过本来利用一般的思想的是一个数组位存一位数，存储1024bit的大数需要初始化数组，但是可以利用更节省空间的方法。C语言unsigned int 的范围是，一个数组位就可以存32bit（1个int = 4Byte.s = 4*8bit = 32 bit），1024比特用初始化数组可以储存。在本程序中，我用a[0]代表实际数组的长度，因此1024比特位的大数需要用数组存储。

椭圆曲线参数的方程：

q：B640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D

椭圆曲线上的点

：93DE051D62BF718FF5ED0704487D01D6E1E4086909DC3280E8C4E4817C66DDDD

：21FE8DDA4F21E607631065125C395BBC1C1C00CBFA6024350C464CD70A3EA616

：02E65B0762D042F51F0D23542B13ED8CFA2E9A0E7206361E013A283905E31F

计算所得。

比较直接用除法做运算以及选择蒙哥马利域的运算结果（图4、图5）。

图4 所用时间

图5 实验结果比较图

实验结果表明基于蒙哥马利域的椭圆曲线算法比一般数域下的速度快了10倍左右，其主要原因是一般除法太耗时间，而蒙哥马利算法通过位移就可以实现除法。

4 结束语

椭圆曲线是具有深厚历史，结合代数与几何知识的加密方案。本文简单介绍椭圆曲线的方程，运算性质，加密算法以及数字签名。本文利用数组bitmap思想实现大数存储，实现基于蒙哥马利域下的椭圆曲线算法。

参考文献：

[1]张方国.椭圆曲线在密码中的应用：过去，现在，将来…[J].山东大学学报（理学版），2013，48（05）：1-3.

[2]陈恭亮.信息安全数学基础[M].北京：清华大学出版社，2004：109-204.

[3]Andres.Elliptic curves and their application to crytography.Germany：University Augsburg，2001：11.

[4]贺令亚.蒙哥马利算法在RSA中的应用研究[J].现代计算机（专业版），2014（29）：7-9.