文档章节

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

safedead
 safedead
发布于 2015/02/10 16:27
字数 1437
阅读 143
收藏 2
点赞 0
评论 0

这是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
密码学-学习资料和网站

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

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

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

雪花又一年
05/04
0
0
微软开发出量子电脑也破解不了的 TLS 加密算法

我们访问的 HTTPS 网站使用了 TLS 协议加密连接。TLS 协议一般是使用 RSA 公钥算法。RSA 算法是使用大素数相乘生成一对密钥,其中一个公开称之为公钥,另一个则是私钥。你可以通过因式分解利...

oschina
2015/08/05
7K
53
量子计算强“矛”将至 网络空间铸“盾”在即

随着量子计算的不断突破,其计算机能力的大幅跃升将为网络安全带来新挑战——许多加密算法将会变得相当脆弱。未来,如何应对量子计算对数据的“暴力解密”?当前移动互联网、云计算、大数据、...

雪花又一年
05/02
0
0
国密算法SM2/3/4实现

相关信息 国家密码管理局发布的标准 SM2:http://www.oscca.gov.cn/News/201012/News_1197.htm SM3:http://www.oscca.gov.cn/News/201012/News_1199.htm SM4的没找到 开源实现 Github上找到......

realm520
2016/11/24
410
0
椭圆曲线加解密及签名算法的技术原理及其Go语言实现

  椭圆曲线加密算法,即:Elliptic Curve Cryptography,简称ECC,是基于椭圆曲线数学理论实现的一种非对称加密算法。相比RSA,ECC优势是可以使用更短的密钥,来实现与RSA相当或更高的安全...

莫名2013
06/26
0
0
纽约时报:软件性能突飞猛进推翻摩尔定律

根据《纽约时报》网络版周一刊载的文章,软件开发的突飞猛进推翻了“摩尔定律”。 摩尔定律是指IC上可容纳的晶体管数目,约每隔18个月便会增加一倍,性能也将提升一倍。摩尔定律是由英特尔(...

老枪
2011/03/09
1K
12
“再得抗量子密术,30000亦不在话下”的hsr会如何抵抗量子攻击?

HSR一直热炒的一个点在于他们宣称自己能够抵抗量子计算机算力暴增带来的51%攻击,比比特币更加安全。 那我们首先需要明确:量子计算机的算力真的会对比特币构成51%攻击的威胁吗? 先抛结论,...

雪花又一年
05/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JupyterLab安装地图插件

JupyterLab安装地图插件 (本文所述软件还在发展之中,欢迎加入开源项目,提供建议、测试和开发。) 在Jupyter中进行数据分析时,往往需要将数据叠加到地图上。简单的可以利用matplotlib/ec...

openthings
2分钟前
0
0
Coding and Paper Letter(八)

资源整理 1 Coding: 1.Python项目,由Allen Downey撰写的Think Python第二版的LaTeX源代码和支持代码。 ThinkPython2 2.R语言包h3jsr,h3jsr使用V8的神奇力量通过其javascript绑定提供对Ube...

胖胖雕
11分钟前
0
0
skiplist跳跃表

插入删除log(N) TODO

梦想游戏人
12分钟前
1
0
利用世界杯,读懂 Python 装饰器

Python 装饰器是在面试过程高频被问到的问题,装饰器也是一个非常好用的特性, 熟练掌握装饰器会让你的编程思路更加宽广,程序也更加 pythonic。 今天就结合最近的世界杯带大家理解下装饰器。...

p柯西
26分钟前
0
0
Xshell登录阿里云服务器ECS

Xshell登录阿里云服务器ECS 1. 参考资料: 1). 《阿里云服务器怎么用?阿里云服务器使用教程》 链接:http://www.cr173.com/html/50758_1.html 2). eagle-zhang的CSDN博客《Xshell连接不上阿...

SuShine
35分钟前
1
0
IDEA中的HTTP Client Editor测试API

在前后端分离项目,前后端通过api进行通信。如果用postman免费版进行api测试的话,由于无法保存测试脚本到文件,不方便前端查看。 你可以选择付费版。也可以利用IDEA自带的HTTP Client Edito...

hutaishi
38分钟前
0
0
解决“只能通过Chrome网上应用商店安装该程序”的方法

摘要 : 最近有些用户反映某个Chrome插件在安装的时候,提示“只能通过Chrome网上应用商店安装该程序”,为了解决这一问题,Chrome插件网带来了相关的解决方法。 某些用户在Chrome插件网下载了...

沧海一刀
39分钟前
0
0
通过UNIX域套接字传递文件描述符

  传送文件描述符是高并发网络服务编程的一种常见实现方式。Nebula 高性能通用网络框架即采用了UNIX域套接字传递文件描述符设计和实现。本文详细说明一下传送文件描述符的应用。 1. TCP服务...

Bwar
42分钟前
0
0
python操作Excle

# -*- coding: utf-8 -*-from openpyxl import load_workbook, Workbook#index:第几个sheet页,第一个sheet页的index为0def readExcle(filename,index): # 加载excle文件 wb = l......

淺陌离殇
44分钟前
0
0
Apache爆日志文件漏洞

全球使用最广泛的Web服务器Apache近日被爆出了一个安全漏洞,该漏洞可能导致攻击者控制服务器。 该漏洞包含在mod_rewrite 模块中的do_rewritelog()日志函数中。由于该函数还无法完全过滤写入...

问题终结者
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部