文档章节

国密SM2素域椭圆曲线快速约减算法x64编程研究(上)

safedead
 safedead
发布于 2015/02/10 16:27
字数 1437
阅读 171
收藏 2

这是NIST公开资料公布的256位素域椭圆曲线快速约减算法描述:

p256 = (2 ^ 256) − (2 ^ 224) + (2 ^ 192) + (2 ^ 96) − 1
p256 = ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff

Routine 3.2.9 mp_mod_256 (r, a): Set r = a (mod p256 )
1: {Note: the ai are 32–bit quantities.}
2: t  = ( a7 |a6 |a5 |a4 |a3 |a2 |a1 |a0  )
3: s1 = ( a15|a14|a13|a12|a11| 0 | 0 | 0  )
4: s2 = (  0 |a15|a14|a13|a12| 0 | 0 | 0  )
5: s3 = ( a15|a14| 0 | 0 | 0 |a10|a9 |a8  )
6: s4 = ( a8 |a13|a15|a14|a13|a11|a10|a9  )
7: d1 = ( a10|a8 | 0 | 0 | 0 |a13|a12|a11 )
8: d2 = ( a11|a9 | 0 | 0 |a15|a14|a13|a12 )
9: d3 = ( a12| 0 |a10|a9 |a8 |a15|a14|a13 )
10:d4 = ( a13| 0 |a11|a10|a9 | 0 |15 |a14 )
11:d1 = 2p256 − d1
12:d2 = 2p256 − d2
13:d3 = p256 − d3
14:d4 = p256 − d4
15:r  = t + 2s1 + 2s2 + s3 + s4 + d1 + d2 + d3 + d4
16:Reduce r mod p256 by subtraction of up to ten multiples of p256 .

国密算法代号SM2可以认为是NIST素域256位椭圆曲线的变种,最主要区别在于p256和b的取值。国密SM2的公开资料给出的参数为:

(y ^ 2) = (X ^ 3) + (a * x) + b mod p
p  = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
a  = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC

其中a = p - 3,这表明国密SM2和NIST的256v1使用了同样特性的素域椭圆曲线公式:

(y ^2) = (X ^ 3)  - (3 * x) + b mod p256

经过简单推导,得到国密SM2的p256生成公式:

p256 = (2 ^ 256) - (2 ^ 224) - (2 ^ 96) + (2 ^ 64) - 1

公开资料并没有国密SM2的快速约减算法详细描述,但只要有素数p的生成公式,很容易自行推导出来,具体推导方法详见椭圆曲线密码学的基本数学知识,下面是仿NIST风格的算法描述文本:

算法:已知正整数a,数值不大于p256的平方,求模r = a (mod p256)
1 : 注:单元长度位均为32位
2 : t   = ( a7 |a6 |a5 |a4 |a3 |a2 |a1 |a0  )
3 : s1  = ( a8 |a11|a10|a9 |a8 | 0 |a9 |a8  )
4 : s2  = ( a9 |a14|a13|a12|a11| 0 |a10|a9  )
5 : s3  = ( a10|a15|a14|a13|a12| 0 |a11|a10 )
6 : s4  = ( a11| 0 |a15|a14|a13| 0 |a12|a11 )
7 : s5  = ( a12| 0 |a15|a14|a13| 0 |a13|a12 )
8 : s6  = ( a12| 0 | 0 |a15|a14| 0 |a14|a13 )
9 : s7  = ( a13| 0 | 0 | 0 |a15| 0 |a14|a13 )
10: s8  = ( a13| 0 | 0 | 0 | 0 | 0 |a15|a14 )
11: s9  = ( a14| 0 | 0 | 0 | 0 | 0 |a15|a14 )
12: s10 = ( a14| 0 | 0 | 0 | 0 | 0 | 0 |a15 )
13: s11 = ( a15| 0 | 0 | 0 | 0 | 0 | 0 |a15 )
14: s12 = ( a15| 0 | 0 | 0 | 0 | 0 | 0 | 0  )
15: d1  = (  0 | 0 | 0 | 0 | 0 |a8 | 0 | 0  )
16: d2  = (  0 | 0 | 0 | 0 | 0 |a9 | 0 | 0  )
17: d3  = (  0 | 0 | 0 | 0 | 0 |a13| 0 | 0  )
18: d4  = (  0 | 0 | 0 | 0 | 0 |a14| 0 | 0  )
19: r   = t + s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8
          + s9 + s10 + s11 + 2s12 - d1 -d2 -d3 - d4
20: 约减r直到r小于p256,最多减去(12 * p256)

为了方便进行x64编程,将算法描述改为从低到高书写,去除左侧的临时变量名称,并在右侧加上运算符号:

|a00|a01|a02|a03|a04|a05|a06|a07|(=)
|a08|a09| 0 |a08|a09|a10|a11|a08|(+)
|a09|a10| 0 |a11|a12|a13|a14|a09|(+)
|a10|a11| 0 |a12|a13|a14|a15|a10|(+)
|a11|a12| 0 |a13|a14|a15| 0 |a11|(+)
|a12|a13| 0 |a13|a14|a15| 0 |a12|(+)
|a13|a14| 0 |a14|a15| 0 | 0 |a12|(+)
|a13|a14| 0 |a15| 0 | 0 | 0 |a13|(+)
|a14|a15| 0 | 0 | 0 | 0 | 0 |a13|(+)
|a14|a15| 0 | 0 | 0 | 0 | 0 |a14|(+)
|a15| 0 | 0 | 0 | 0 | 0 | 0 |a14|(+)
|a15| 0 | 0 | 0 | 0 | 0 | 0 |a15|(+)
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |a15|(+)
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |a15|(+)
---------------------------------
| 0 | 0 |a08| 0 | 0 | 0 | 0 | 0 |(-)
| 0 | 0 |a09| 0 | 0 | 0 | 0 | 0 |(-)
| 0 | 0 |a13| 0 | 0 | 0 | 0 | 0 |(-)
| 0 | 0 |a14| 0 | 0 | 0 | 0 | 0 |(-)

直觉告诉我,如果就这么直接按行进行加法运算,运算效率不会太高,为此整理如下:

|===|===|===|===|===|===|===|===|
|a08|a08|   |   |   |   |   |a08|
|a09|a09|   |   |   |   |   |a09|
|a10|a10|   |   |   |   |   |a10|
|a11|a11|   |   |   |   |   |a11|
|---|---|---|---|---|---|---|---|
|a12|a12|   |a12|a12|   |   |a12|
|a13|a13|   |a13|a13|   |   |a13|
|a14|a14|   |a14|a14|   |   |a14|
|a15|a15|   |a15|a15|   |   |a15|
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |   |   |a12|
|a13|   |   |   |   |a13|   |a13|
|a14|a14|   |   |   |a14|a14|a14|
|a15|a15|   |   |   |a15|a15|a15|
|---|---|---|---|---|---|---|---|
|   |   |   |a08|a09|a10|   |   |
|---|---|---|---|---|---|---|---|
|   |   |   |a11|   |   |a11|   |
|---|---|---|---|---|---|---|---|
|   |   |   |a13|a14|a15|   |a15|
|===|===|===|===|===|===|===|===|
|   |a08|a08|   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |a09|   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |a13|   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |a14|   |   |   |   |   |
|===|===|===|===|===|===|===|===|

从表中可以看出:

组合数值使用频次:
a08 + a09 + a10 + a11   3次
a12 + a13 + a14 + a15   6次
a13 + a14 + a15         2次
a14 + a15               2次

单独数值使用频次:
a08                     3次
a09                     2次
a10                     1次
a11                     2次
a13                     1次
a14                     1次
a15                     2次

据此制定相应的寄存器规划:

数据输入指针:通用寄存器rsi
 
数据输出指针:通用寄存器rdi
 
通用寄存器备份与恢复:
|---------------|---------------|
|     xmm14     |     xmm15     |
|-------|-------|-------|-------|
|  r12  |  r13  |  r14  |  r15  |
|-------|-------|-------|-------|

原始数据加载:
|---------------|---------------|---------------|---------------|
|     xmm10     |     xmm11     |     xmm12     |     xmm13     |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|a00|a01|a02|a03|a04|a05|a06|a07|a08|a09|a10|a11|a12|a13|a14|a15|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

运算结果缓存:
|---------------|---------------|
|     xmm0      |     xmm1      |
|---|---|---|---|---|---|---|---|
|r00|r01|r02|r03|r04|r05|r06|r07|
|---|---|---|---|---|---|---|---|

下述寄存器用于存放高频数值:
r15 = a15
r14 = a14 + a15
r13 = a13 + a14 + a15
r12 = a12 + a13 + a14 + a15
r11 = a11
r9  = a09
r8  = a08
rsi = a08 + a09 + a10 + a11


按照上述思路实现的完整汇编程序代码见本文的下篇

2015-10-17

最近在做SM2倍点运算函数中发现,前述的思路还可以继续优化,个别寄存器的使用也需要调整,快速约减运算表改进如下:

|===|===|===|===|===|===|===|===|
|a08|a08|   |   |   |   |   |a08|
|a09|a09|   |   |   |   |   |a09|
|a10|a10|   |   |   |   |   |a10|
|a11|a11|   |   |   |   |   |a11|
|a12|a12|   |a12|a12|   |   |a12|
|a13|a13|   |a13|a13|   |   |a13|
|a14|a14|   |a14|a14|   |   |a14|
|a15|a15|   |a15|a15|   |   |a15|
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |   |   |a12|
|a13|a13|   |   |   |a13|   |a13|
|a14|a14|   |   |   |a14|   |a14|
|a15|a15|   |   |   |a15|   |a15|
|---|---|---|---|---|---|---|---|
|   |   |   |a08|a09|a10|a14|   |
|   |   |   |a13|a14|   |a15|   |
|---|---|---|---|---|---|---|---|
|   |   |   |a11|   |   |a11|   |
|---|---|---|---|---|---|---|---|
|   |   |   |   |   |a15|   |a15|
|===|===|===|===|===|===|===|===|
|   |a08|a08|   |   |   |   |   |
|   |a13|a13|   |   |   |   |   |
|---|---|---|---|---|---|---|---|
|   |   |a09|   |   |   |   |   |
|   |   |a14|   |   |   |   |   |
|===|===|===|===|===|===|===|===|

寄存器规划中,用于保存中间数值的寄存器及其数值做了部分调整后如下所示:

r8  = a08 + a13
r9  = a09 + a14
r10 = a10
r11 = a11

rcx = a08 + a09 + a10 + a11 + a12 + a13 + a14 + a15

r12 = a12 + a13 + a14 + a15
r13 = a13 + a14 + a15
r14 = a14 + a15
r15 = a15

并在最终处理上保证了数学正确性,最新完整代码见本人的git项目站点https://github.com/safedead/ecc-x64

© 著作权归作者所有

共有 人打赏支持
safedead
粉丝 2
博文 19
码字总数 16374
作品 0
海淀
256位NIST素域椭圆曲线运算优化细节之一(单个素数p的加减法)

在素域椭圆曲线运算过程中,256位加法和减法运算结果常常位于区间[0,p)之外的情形,需要做+p或是-p的运算 256位NIST素域椭圆曲线参数p的生成公式为: p = 2^256 − 2^224 + 2^192 + 2^96 − ...

safedead
2015/10/10
369
0
支持国密算法和标准的OpenSSL分支--GmSSL

GmSSL (http://gmssl.org) 是支持国密算法和标准的OpenSSL分支,增加了对国密SM2/SM3/SM4算法和ECIES、CPK、ZUC算法的支持,实现了这些算法与EVP API和命令行工具的集成。GmSSL由北京大学信息...

SimonZhao
2016/05/09
7.7K
8
支持国密算法的 Python 加密包 - gmssl-python

GMSSL GmSSL是一个开源的加密包的python实现,支持SM2/SM3/SM4等国密(国家商用密码)算法、项目采用对商业应用友好的类BSD开源许可证,开源且可以用于闭源的商业应用。 安装 pip install gmss...

段洪义
07/30
0
0
密码学-学习资料和网站

我接触密码学有一段时间了,把我收集的资料整理出来,以便后期查阅。另外也给网友一些捷径。 书籍 计算机安全和密码学.Computer.Security.And.Cryptography.pdf 英文版 《深入浅出密码学——...

BjarneCpp
01/09
0
0
行业看点 | 量子计算机时代逼近,互联网上的隐私要被攻克了?

读 9月15日消息,虽然量子计算机将为我们带来史无前例的计算和数据分析能力,但据荷兰埃因霍温理工大学的一项研究称,它也会给现在的网络安全和隐私带来巨大风险。 这项最新研究称,量子计算...

雪花又一年
05/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

20180920 rzsz传输文件、用户和用户组相关配置文件与管理

利用rz、sz实现Linux与Windows互传文件 [root@centos01 ~]# yum install -y lrzsz # 安装工具sz test.txt # 弹出对话框,传递到选择的路径下rz # 回车后,会从对话框中选择对应的文件传递...

野雪球
今天
2
0
OSChina 周四乱弹 —— 毒蛇当辣条

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 达尔文:分享花澤香菜/前野智昭/小野大輔/井上喜久子的单曲《ミッション! 健?康?第?イチ》 《ミッション! 健?康?第?イチ》- 花澤香菜/前野智...

小小编辑
今天
7
3
java -jar运行内存设置

java -Xms64m #JVM启动时的初始堆大小 -Xmx128m #最大堆大小 -Xmn64m #年轻代的大小,其余的空间是老年代 -XX:MaxMetaspaceSize=128m # -XX:CompressedClassSpaceSize=6...

李玉长
今天
4
0
Spring | 手把手教你SSM最优雅的整合方式

HEY 本节主要内容为:基于Spring从0到1搭建一个web工程,适合初学者,Java初级开发者。欢迎与我交流。 MODULE 新建一个Maven工程。 不论你是什么工具,选这个就可以了,然后next,直至finis...

冯文议
今天
2
0
RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部