文档章节

256位NIST素域椭圆曲线运算优化细节之一(单个素数p的加减法)

safedead
 safedead
发布于 2015/10/10 19:17
字数 1041
阅读 520
收藏 3
点赞 0
评论 0

在素域椭圆曲线运算过程中,256位加法和减法运算结果常常位于区间[0,p)之外的情形,需要做+p或是-p的运算

256位NIST素域椭圆曲线参数p的生成公式为:

p = 2^256 − 2^224 + 2^192 + 2^96 − 1

按照符号将此式分解得:

p = (2^256 + 2^192 + 2^96) - (2^224 + 1)

转化为16进制并按64位分节,变成下面的形式:

+: 0000000000000001 0000000000000000 0000000100000000 0000000000000000
-: 0000000100000000 0000000000000000 0000000000000000 0000000000000001
=: ffffffff00000001 0000000000000000 00000000ffffffff ffffffffffffffff

仔细观察可以发现,所涉及64位加法和减法中,只出现一个64位立即数:

0000000100000000

假设某次256位减法最终发生借位,其低256位数值保存于寄存器r8:r11中,现在需要+p运算以修正之,若是用构成p的4个立即数直接运算的话,其代码如下:

#   --------------
#   r8:r11 += p256
#   --------------
    addq    $0xffffffffffffffff, %r8
    adcq    $0xffffffff, %r9
    adcq    $0, %r10
    adcq    $0xffffffff00000001, %r11

由x64指令特性可知,这么书写是不允许的,大于32位的立即数会使编译通不过,通过前面的分析可知,可以将4个加法转化为3个加法和4个减法来实现,其代码如下:

    movq    $0x100000000, %rax
    addq    %rax, %r9
    adcq    $0x0, %r10
    adcq    $0x1, %r11
#   ----
    subq    $0x1, %r8
    sbbq    $0, %r9
    sbbq    $0, %r10
    sbbq    %rax, %r11

有没有其它方法呢?当然有,比如可以预先将素数p的4个64位数值保存于寄存器r12:r15中,其代码如下:

#   --------------
#   r12:r15 = p256
#   r8:r11 += p256
#   --------------
    addq    %r12, %r8
    adcq    %r13, %r9
    adcq    %r14, %r10
    adcq    %r15, %r11

为了一个256位常数牺牲4个通用寄存器是万不得已的选择,除非此运算占据整体运算的大部分,才值得这么做,比如对素数p求乘法逆时,超过80%的运算都是+/-p,此时有必要将素数p直接保存在通用寄存器中以便随时使用。

利用x64立即数书写规则,使用两个寄存器RAX:RDX生成素数p的内容,其代码如下:

#   ------------------------
#   rax = 0x00000000ffffffff
#   rdx = 0xffffffff00000001
#   ------------------------
    movq    $0xffffffff, %rax
    movq    %rax, %rdx
    negq    %rdx
#   --------------
#   r8:r11 += p256
#   --------------
    addq    $-1, %r8
    adcq    %rax, %r9
    adcq    $0, %r10
    adcq    %rdx, %r11

这里特别要注意立即数-1的实际数值,在x86汇编里相当于0xffffffff,即32个连续的二进制1,在x64汇编则是64个连续的二进制1,相当于0xffffffffffffffff,其它立即数的书写规则和x86一致,都是32位有符号立即数,只有movq指令对rax操作时,才支持64位立即数,千万要小心。

在编写256位NIST素域椭圆曲线倍点函数时,最终采用的方案是使用两个通用寄存器分别保存素数p的最高64位和最低64位,同时利用x64汇编的立即数书写规则,其数值的生成代码如下:

#   ------------------------
#   rbx = 0x00000000ffffffff
#   rbp = 0xffffffff00000001
#   ------------------------
    xorq    %rbp, %rbp
    movq    $0xffffffff, %rax
    movq    %rax, %rbx
    subq    %rax, %rbp

倍点函数内计算+p的代码如下:

#   ---------------
#   r12:r15 += p256
#   ---------------
    addq    $-1, %r12
    adcq    %rbx, %r13
    adcq    $0, %r14
    adcq    %rbp, %r15

倍点函数内计算-p的代码如下:

#   ---------------
#   r12:r15 -= p256
#   ---------------
    subq    $-1, %r12
    sbbq    %rbx, %r13
    sbbq    $0, %r14
    sbbq    %rbp, %r15

国密素域椭圆曲线SM2从公式上来讲和NIST素域椭圆曲线有相似之处,同样可以优化+/-素数p的汇编代码,首先我们回顾一下国密SM2的素数p取值:

p256 = FFFFFFFEFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFF00000000 FFFFFFFFFFFFFFFF

现仍旧使用2个通用寄存器缓存素数p的部分数值,其数值生成代码如下:

#   ------------------------
#   rbx = 0xFFFFFFFF00000000
#   rbp = 0xFFFFFFFEFFFFFFFF
#   ------------------------
    movq    $-0x100000000, %rbx
    movq    $-0x100000001, %rbp

SM2倍点函数内计算+p的代码如下:

#   --------------
#   r8:r11 += p256
#   --------------
    addq    $-1, %r8
    adcq    %rbx, %r9
    adcq    $-1, %r10
    adcq    %rbp, %r11

SM2倍点函数内计算-p的代码如下:

#   --------------
#   r8:r11 -= p256
#   --------------
    subq    $-1, %r8
    sbbq    %rbx, %r9
    sbbq    $-1, %r10
    sbbq    %rbp, %r11


© 著作权归作者所有

共有 人打赏支持
safedead
粉丝 2
博文 19
码字总数 16374
作品 0
海淀
国密SM2素域椭圆曲线快速约减算法x64编程研究(上)

这是NIST公开资料公布的256位素域椭圆曲线快速约减算法描述: p256 = (2 ^ 256) − (2 ^ 224) + (2 ^ 192) + (2 ^ 96) − 1p256 = ffffffff 00000001 00000000 00000000 00000000 ffffffff ......

safedead ⋅ 2015/02/10 ⋅ 0

ECC非对称加密算法

椭圆曲线 椭圆曲线在代数上的表示是下面这个方程: y2 = x3 + ax + b 其中,a = 0, b = 7 (比特币系统所使用的版本),它的图形如下: 椭圆曲线有一些很有用的特征 一条非垂直的直线与椭圆曲线...

14142135623731 ⋅ 01/17 ⋅ 0

[以太坊源代码分析] IV. 椭圆曲线密码学和以太坊中的椭圆曲线数字签名算法应用

数字签名算法在Ethereum中的应用不少,目前已知至少有两处:一是在生成每个交易(Transaction, tx)对象时,对整个tx对象进行数字签名;二是在共识算法的Clique算法实现中,在针对新区块进行授...

teaspring ⋅ 2017/09/04 ⋅ 0

椭圆曲线加解密及签名算法的技术原理及其Go语言实现

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

莫名2013 ⋅ 01/05 ⋅ 0

支持国密算法和标准的OpenSSL分支--GmSSL

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

SimonZhao ⋅ 2016/05/09 ⋅ 8

网站HTTPS 实践(一): HTTPS协议和原理

1、前言 百度已经于近日上线了全站 HTTPS 的安全搜索,默认会将 HTTP 请求跳转成 HTTPS。本文重点介绍 HTTPS 协议, 并简单介绍部署全站 HTTPS 的意义。 2、HTTPS 协议概述 HTTPS 可以认为是 ...

linuxprobe16 ⋅ 2016/11/03 ⋅ 0

使用SSH---最新加密算法ecsda密钥认证登陆

原理与安全性RSA 与 DSA 都是非对称加密算法。其中RSA的安全性是基于极其困难的大整数的分解(两个素数的乘积);DSA 的安全性是基于整数有限域离散对数难题。基本上可以认为相同密钥长度的 ...

qd轻描淡写 ⋅ 2017/12/21 ⋅ 0

独立的 Python 加密库--PyCryptodome

PyCryptodome 是一个低级密码学原语的独立 Python 包,它支持 Python 2.4 及以上,全部 Python 3 版本以及 PyPy。 PyCryptodome 是 PyCrypto 分叉出来的一个项目。它对 PyCrypto (2.6.1) 的最...

匿名 ⋅ 2017/09/04 ⋅ 0

揭秘比特币和区块链(三):比特币的私钥、公钥与地址

地址、交易、区块、网络是区块链数据里面最基本最重要的概念。地址用来标示一笔交易的支出方和接收方。所有的交易最终需要被记到统一的账本——区块链上,而这个账本是通过区块确认并完成的。...

雪花又一年 ⋅ 04/19 ⋅ 0

实现高性能纠删码引擎 | 纠删码技术详解(下)

作者介绍: 徐祥曦,七牛云工程师,独立开发了多套高性能纠删码/再生码编码引擎。 柳青,华中科技大学博士,研究方向为基于纠删码的分布式存储系统。 前言: 在上篇《如何选择纠删码编码引擎...

七仙女很忙 ⋅ 2017/05/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

tcp/ip详解-链路层

简介 设计链路层的目的: 为IP模块发送和接收IP数据报 为ARP模块发送ARP请求和接收ARP应答 为RARP模块发送RARP请求和接收RARP应答 TCP/IP支持多种链路层协议,如以太网、令牌环往、FDDI、RS-...

loda0128 ⋅ 今天 ⋅ 0

spring.net aop代码例子

https://www.cnblogs.com/haogj/archive/2011/10/12/2207916.html

whoisliang ⋅ 今天 ⋅ 0

发送短信如何限制1小时内最多发送11条短信

发送短信如何限制1小时内最多发送11条短信 场景: 发送短信属于付费业务,有时为了防止短信攻击,需要限制发送短信的频率,例如在1个小时之内最多发送11条短信. 如何实现呢? 思路有两个 截至到当...

黄威 ⋅ 昨天 ⋅ 0

mysql5.7系列修改root默认密码

操作系统为centos7 64 1、修改 /etc/my.cnf,在 [mysqld] 小节下添加一行:skip-grant-tables=1 这一行配置让 mysqld 启动时不对密码进行验证 2、重启 mysqld 服务:systemctl restart mysql...

sskill ⋅ 昨天 ⋅ 0

Intellij IDEA神器常用技巧六-Debug详解

在调试代码的时候,你的项目得debug模式启动,也就是点那个绿色的甲虫启动服务器,然后,就可以在代码里面断点调试啦。下面不要在意,这个快捷键具体是啥,因为,这个keymap是可以自己配置的...

Mkeeper ⋅ 昨天 ⋅ 0

zip压缩工具、tar打包、打包并压缩

zip 支持压缩目录 1.在/tmp/目录下创建目录(study_zip)及文件 root@yolks1 study_zip]# !treetree 11└── 2 └── 3 └── test_zip.txt2 directories, 1 file 2.yum...

蛋黄Yolks ⋅ 昨天 ⋅ 0

聊聊HystrixThreadPool

序 本文主要研究一下HystrixThreadPool HystrixThreadPool hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java /** * ThreadPool used to executed {@link Hys......

go4it ⋅ 昨天 ⋅ 0

容器之上传镜像到Docker hub

Docker hub在国内可以访问,首先要创建一个账号,这个后面会用到,我是用126邮箱注册的。 1. docker login List-1 Username不能使用你注册的邮箱,要用使用注册时用的username;要输入密码 ...

汉斯-冯-拉特 ⋅ 昨天 ⋅ 0

SpringBoot简单使用ehcache

1,SpringBoot版本 2.0.3.RELEASE ①,pom.xml <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.0.3.RELE......

暗中观察 ⋅ 昨天 ⋅ 0

Spring源码解析(八)——实例创建(下)

前言 来到实例创建的最后一节,前面已经将一个实例通过不同方式(工厂方法、构造器注入、默认构造器)给创建出来了,下面我们要对创建出来的实例进行一些“加工”处理。 源码解读 回顾下之前...

MarvelCode ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部