文档章节

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

safedead
 safedead
发布于 2015/02/10 16:27
字数 1437
阅读 205
收藏 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
博文 20
码字总数 16937
作品 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
基于python的国密算法gmssl-python版本发布[3.2.1]

关于 项目起源于一个银行合作项目,银行接口中涉及了大量的国密算法,但是目前大多数类库都是java或者c/c++,于是本人东拼西凑了一个类库,希望能给大家带来方便。 GMSSL GmSSL是一个开源的加...

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

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

BjarneCpp
01/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

1个开发如何撑起一个过亿用户的小程序

本文由云+社区发表 2018年12月,腾讯相册累计用户量突破1亿,月活1200万,阿拉丁指数排行 Top 30,已经成为小程序生态的重量级玩家。 三个多月来,腾讯相册围绕【在微信分享相册照片】这一核...

腾讯云加社区
4分钟前
0
0
golang ssh包使用方法介绍

在使用gexpect包发现很多问题之外,这里又尝试使用ssh user@127.0.0.1的思路进行用户切换。这里记录下具体的使用方法,遇到的ssh: must specify HostKeyCallback 问题的解法方法及最终使用过...

linuxprobe16
9分钟前
0
0
layer

Layui Layer在open弹出层中异步加载数据和form表单radio、checkbox、select不渲染,不可点击的解决办法 layer 实现弹窗提交信息 function confirmUpdateAward(i) { layer.open({ ...

mickelfeng
58分钟前
0
0
Spring boot中如何获取profiles环境

  实现ApplicationContextAware @Componentpublic class QiNiuPropertiesConfig implements ApplicationContextAware { /// 获取当前环境public String getActiveProfile() { ret......

writeademo
今天
3
0
机器学习中的End-to-End到底是怎么回事?

简单讲就是,Input--->系统(这里指神经网络)--->Output(直接给出输入,NN神经网络就给出结果,一气喝成!!!) 借用一段对话:(http://dy.163.com/v2/article/detail/C3J6F2NJ0511AQHO....

火力全開
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部