GB-T 32918.4-2016 信息安全技术 SM2椭圆曲线公钥密码算法 第4部分：公钥加密算法.pdf

1、I C S3 5.0 4 0L8 0中 华 人 民 共 和 国 国 家 标 准G B/T3 2 9 1 8.42 0 1 6信息安全技术 S M 2椭圆曲线公钥密码算法 第4部分:公钥加密算法I n f o r m a t i o ns e c u r i t y t e c h n o l o g yP u b l i ck e yc r y p t o g r a p h i ca l g o r i t h mS M 2b a s e do ne l l i p t i cc u r v e sP a r t 4:P u b l i ck e ye n c r y p t i o na

2、l g o r i t h m2 0 1 6-0 8-2 9发布2 0 1 7-0 3-0 1实施中华人民共和国国家质量监督检验检疫总局中 国 国 家 标 准 化 管 理 委 员 会发 布目 次前言引言1 范围12 规范性引用文件13 术语和定义14 符号缩略语15 算法参数与辅助函数2 5.1 综述2 5.2 椭圆曲线系统参数2 5.3 用户密钥对2 5.4 辅助函数2 5.4.1 概述2 5.4.2 密码杂凑算法2 5.4.3 密钥派生函数2 5.4.4 随机数发生器36 加密算法及流程3 6.1 加密算法3 6.2 加密算法流程37 解密算法及流程4 7.1 解密算法4 7.2 解密算法

3、流程5附录A(资料性附录)消息加解密示例7 A.1 综述7 A.2 Fp上椭圆曲线消息加解密7 A.3 F2m上椭圆曲线消息加解密9参考文献1 2G B/T3 2 9 1 8.42 0 1 6前 言 G B/T3 2 9 1 8 信息安全技术 S M 2椭圆曲线公钥密码算法 分为5个部分:第1部分:总则;第2部分:数字签名算法;第3部分:密钥交换协议;第4部分:公钥加密算法;第5部分:参数定义。本部分为G B/T3 2 9 1 8的第4部分。本部分按照G B/T1.12 0 0 9给出的规则起草。本部分由国家密码管理局提出。本部分由全国信息安全标准化技术委员会(S A C/T C2 6 0)归

4、口。本部分起草单位:北京华大信安科技有限公司、中国人民解放军信息工程大学、中国科学院数据与通信保护研究教育中心。本部分主要起草人:陈建华、祝跃飞、叶顶峰、胡磊、裴定一、彭国华、张亚娟、张振峰。G B/T3 2 9 1 8.42 0 1 6引 言 N.K o b l i t z和V.M i l l e r在1 9 8 5年各自独立地提出将椭圆曲线应用于公钥密码系统。椭圆曲线公钥密码所基于的曲线性质如下:有限域上椭圆曲线在点加运算下构成有限交换群,且其阶与基域规模相近;类似于有限域乘法群中的乘幂运算,椭圆曲线多倍点运算构成一个单向函数。在多倍点运算中,已知多倍点与基点,求解倍数的问题称为椭圆曲线离

5、散对数问题。对于一般椭圆曲线的离散对数问题,目前只存在指数级计算复杂度的求解方法。与大数分解问题及有限域上离散对数问题相比,椭圆曲线离散对数问题的求解难度要大得多。因此,在相同安全程度要求下,椭圆曲线密码较其他公钥密码所需的密钥规模要小得多。S M 2是国家密码管理局组织制定并提出的椭圆曲线密码算法标准。G B/T3 2 9 1 8的主要目标如下:G B/T3 2 9 1 8.1定义和描述了S M 2椭圆曲线密码算法的相关概念及数学基础知识,并概述了该部分同其他部分的关系。G B/T3 2 9 1 8.2描述了一种基于椭圆曲线的签名算法,即S M 2签名算法。G B/T3 2 9 1 8.3描

6、述了一种基于椭圆曲线的密钥交换协议,即S M 2密钥交换协议。G B/T3 2 9 1 8.4描述了一种基于椭圆曲线的公钥加密算法,即S M 2加密算法,该算法需使用G B/T3 2 9 0 52 0 1 6定义的S M 3密码杂凑算法。G B/T3 2 9 1 8.5给出了S M 2算法使用的椭圆曲线参数,以及使用椭圆曲线参数进行S M 2运算的示例结果。本部分为G B/T3 2 9 1 8的第4部分,规定了S M 2椭圆曲线密码系统的加密解密过程。G B/T3 2 9 1 8.42 0 1 6信息安全技术 S M 2椭圆曲线公钥密码算法 第4部分:公钥加密算法1 范围G B/T3 2 9

7、1 8的本部分规定了S M 2椭圆曲线公钥密码算法的公钥加密算法,并给出了消息加解密示例和相应的流程。本部分适用于商用密码应用中的消息加解密,消息发送者可以利用接收者的公钥对消息进行加密,接收者用对应的私钥进行解密,获取消息。2 规范性引用文件下列文件对于本文件的应用是必不可少的。凡是注日期的引用文件,仅注日期的版本适用于本文件。凡是不注日期的引用文件,其最新版本(包括所有的修改单)适用于本文件。G B/T3 2 9 1 8.12 0 1 6 信息安全技术 S M 2椭圆曲线公钥密码算法 第1部分:总则G B/T3 2 9 0 52 0 1 6 信息安全技术 S M 3密码杂凑算法3 术语和定

8、义下列术语和定义适用于本文件。3.1秘密密钥 s e c r e tk e y在密码体制中收发双方共同拥有的、而第三方不知道的一种密钥。3.2消息 m e s s a g e任意有限长度的比特串。3.3密钥派生函数 k e yd e r i v a t i o nf u n c t i o n通过作用于共享秘密和双方都知道的其他参数,产生一个或多个共享秘密密钥的函数。4 符号缩略语下列符号和缩略语适用于本文件。A,B 使用公钥密码系统的两个用户。dB 用户B的私钥。E(Fq)Fq上椭圆曲线E的所有有理点(包括无穷远点O)组成的集合。Fq 包含q个元素的有限域。G 椭圆曲线的一个基点,其阶为素数

9、。H a s h()密码杂凑算法。Hv()消息摘要长度为v比特的密码杂凑算法。1G B/T3 2 9 1 8.42 0 1 6KD F()密钥派生函数。h 余因子,h=#E(Fq)/n,其中n是基点G的阶。M 待加密的消息。M 解密得到的消息。n 基点G的阶(n是#E(Fq)的素因子)。O 椭圆曲线上的一个特殊点,称为无穷远点或零点,是椭圆曲线加法群的单位元。PB 用户B的公钥。q 有限域Fq中元素的数目。a,b Fq中的元素,它们定义Fq上的一条椭圆曲线E。x|y x与y的拼接,x、y是比特串或字节串。kP 椭圆曲线上点P的k倍点,即,kP=P+P+P k个,k是正整数。x,y 大于或等于x

10、且小于或等于y的整数的集合。x 顶函数,大于或等于x的最小整数。例如,7=7,8.3=9。y 底函数,小于或等于x的最大整数。例如,7=7,8.3=8。#E(Fq)E(Fq)上点的数目,称为椭圆曲线E(Fq)的阶。5 算法参数与辅助函数5.1 综述公钥加密算法规定发送者用接收者的公钥将消息加密成密文,接收者用自己的私钥对收到的密文进行解密还原成原始消息。5.2 椭圆曲线系统参数椭圆曲线系统参数包括有限域Fq的规模q(当q=2m时,还包括元素表示法的标识和约化多项式);定义椭圆曲线E(Fq)的方程的两个元素a、bFq;E(Fq)上的基点G=(xG,yG)(GO),其中xG和yG是Fq中的两个元素

11、;G的阶n及其他可选项(如n的余因子h等)。椭圆曲线系统参数及其验证应符合G B/T3 2 9 1 8.12 0 1 6第5章的规定。5.3 用户密钥对用户B的密钥对包括其私钥dB和公钥PB=dBG。用户密钥对的生成算法与公钥验证算法应符合G B/T3 2 9 1 8.12 0 1 6第6章的规定。5.4 辅助函数5.4.1 概述本部分规定的椭圆曲线公钥加密算法涉及三类辅助函数:密码杂凑算法、密钥派生函数和随机数发生器。这三类辅助函数的强弱直接影响加密算法的安全性。5.4.2 密码杂凑算法本部分规定使用国家密码管理局批准的密码杂凑算法,如S M 3密码杂凑算法。2G B/T3 2 9 1 8.

12、42 0 1 65.4.3 密钥派生函数密钥派生函数的作用是从一个共享的秘密比特串中派生出密钥数据。在密钥协商过程中,密钥派生函数作用在密钥交换所获共享的秘密比特串上,从中产生所需的会话密钥或进一步加密所需的密钥数据。密钥派生函数需要调用密码杂凑算法。设密码杂凑算法为Hv(),其输出是长度恰为v比特的杂凑值。密钥派生函数KD F(Z,k l e n):输入:比特串Z,整数k l e n 表示要获得的密钥数据的比特长度,要求该值小于(23 2-1)v。输出:长度为k l e n的密钥数据比特串K。a)初始化一个3 2比特构成的计数器c t=0 x 0 0 0 0 0 0 0 1;b)对i从1到k

13、 l e n/v执行:1)计算H ai=Hv(Z|c t);2)c t+;c)若k l e n/v是整数,令H a!k l e n/v=H ak l e n/v,否则令H a!k l e n/v为H ak l e n/v最左边的(k l e n-(vk l e n/v)比特;d)令K=H a1|H a2|H ak l e n/v-1|H a!k l e n/v。5.4.4 随机数发生器本部分规定使用国家密码管理局批准的随机数发生器。6 加密算法及流程6.1 加密算法设需要发送的消息为比特串M,k l e n为M的比特长度。为了对明文M进行加密,作为加密者的用户A应实现以下运算步骤:A1:用随机

14、数发生器产生随机数k1,n-1;A2:计算椭圆曲线点C1=kG=(x1,y1),按G B/T3 2 9 1 8.12 0 1 6中4.2.9和4.2.5给出的方法,将C1的数据类型转换为比特串;A3:计算椭圆曲线点S=hPB,若S是无穷远点,则报错并退出;A4:计算椭圆曲线点kPB=(x2,y2),按G B/T3 2 9 1 8.12 0 1 6中4.2.6和4.2.5给出的方法,将坐标x2、y2的数据类型转换为比特串;A5:计算t=KD F(x2|y2,k l e n),若t为全0比特串,则返回A1;A6:计算C2=Mt;A7:计算C3=H a s h(x2|M|y2);A8:输出密文C=C

15、1|C3|C2。注:加密过程的示例参见附录A。6.2 加密算法流程加密算法流程见图1。3G B/T3 2 9 1 8.42 0 1 6图1 加密算法流程7 解密算法及流程7.1 解密算法设k l e n为密文中C2的比特长度。为了对密文C=C1|C3|C2进行解密,作为解密者的用户B应实现以下运算步骤:4G B/T3 2 9 1 8.42 0 1 6B 1:从C中取出比特串C1,按G B/T3 2 9 1 8.12 0 1 6中4.2.4和4.2.1 0给出的方法,将C1的数据类型转换为椭圆曲线上的点,验证C1是否满足椭圆曲线方程,若不满足则报错并退出;B 2:计算椭圆曲线点S=hC1,若S是

16、无穷远点,则报错并退出;B 3:计算dBC1=(x2,y2),按G B/T3 2 9 1 8.12 0 1 6中4.2.6和4.2.5给出的方法,将坐标x2、y2的数据类型转换为比特串;B 4:计算t=KD F(x2|y2,k l e n),若t为全0比特串,则报错并退出;B 5:从C中取出比特串C2,计算M=C2t;B 6:计算u=H a s h(x2|M|y2),从C中取出比特串C3,若uC3,则报错并退出;B 7:输出明文M。注:解密过程的示例参见附录A。7.2 解密算法流程解密算法流程见图2。5G B/T3 2 9 1 8.42 0 1 6图2 解密算法流程6G B/T3 2 9 1

17、8.42 0 1 6附 录 A(资料性附录)消息加解密示例A.1 综述本附录选用G B/T3 2 9 0 52 0 1 6给出的密码杂凑算法,其输入是长度小于26 4的消息比特串,输出是长度为2 5 6比特的杂凑值,记为H2 5 6()。本附录中,所有用1 6进制表示的数,左边为高位,右边为低位。本附录中,明文采用G B/T1 9 8 8编码。A.2 Fp上椭圆曲线消息加解密椭圆曲线方程为:y2=x3+a x+b示例1:Fp-1 9 2素数p:B D B 6 F 4 F E 3 E 8 B 1 D 9 E 0 D A 8 C 0 D 4 6 F 4 C 3 1 8 C E F E 4 A F

18、E 3 B 6 B 8 5 5 1 F系数a:B B 8 E 5 E 8 F B C 1 1 5 E 1 3 9 F E 6 A 8 1 4 F E 4 8 AAA 6 F 0 A D A 1 AA 5 D F 9 1 9 8 5系数b:1 8 5 4 B E B D C 3 1 B 2 1 B 7 A E F C 8 0 A B 0 E C D 1 0 D 5 B 1 B 3 3 0 8 E 6 D B F 1 1 C 1基点G=(xG,yG),其阶记为n。坐标xG:4 A D 5 F 7 0 4 8 D E 7 0 9 A D 5 1 2 3 6 D E 6 5 E 4 D 4 B 4 8

19、 2 C 8 3 6 D C 6 E 4 1 0 6 6 4 0坐标yG:0 2 B B 3 A 0 2 D 4 AAA D A C A E 2 4 8 1 7 A 4 C A 3 A 1 B 0 1 4 B 5 2 7 0 4 3 2 D B 2 7 D 2阶n:B D B 6 F 4 F E 3 E 8 B 1 D 9 E 0 D A 8 C 0 D 4 0 F C 9 6 2 1 9 5 D F A E 7 6 F 5 6 5 6 4 6 7 7待加密的消息M:e n c r y p t i o n s t a n d a r d消息M的1 6进制表示:6 5 6 E 6 3 7 2 7

20、 9 7 0 7 4 6 9 6 F 6 E 2 0 7 3 7 4 6 1 6 E 6 4 6 1 7 2 6 4私钥dB:5 8 8 9 2 B 8 0 7 0 7 4 F 5 3 F B F 6 7 2 8 8 A 1 D F AA 1 A C 3 1 3 4 5 5 F E 6 0 3 5 5 A F D公钥PB=(xB,yB)为:坐标xB:7 9 F 0 A 9 5 4 7 A C 6 D 1 0 0 5 3 1 5 0 8 B 3 0 D 3 0 A 5 6 5 3 6 B C F C 8 1 4 9 F 4 A F 4 A坐标yB:A E 3 8 F 2 D 8 8 9 0 8

21、3 8 D F 9 C 1 9 9 3 5 A 6 5 A 8 B C C 8 9 9 4 B C 7 9 2 4 6 7 2 F 9 1 2加密各步骤中的有关值:产生随机数k:3 8 4 F 3 0 3 5 3 0 7 3 A E E C E 7 A 1 6 5 4 3 3 0 A 9 6 2 0 4 D 3 7 9 8 2 A 3 E 1 5 B 2 C B 5计算椭圆曲线点C1=kG=(x1,y1):坐标x1:2 3 F C 6 8 0 B 1 2 4 2 9 4 D F D F 3 4 D B E 7 6 E 0 C 3 8 D 8 8 3 D E 4 D 4 1 F A 0 D 4

22、C F 5坐标y1:7 0 C F 1 4 F 2 0 D A F 0 C 4 D 7 7 7 F 7 3 8 D 1 6 B 1 6 8 2 4 D 3 1 E E F B 9 D E 3 1 E E 1 F在此C1选用未压缩的表示形式,点转换成字节串的形式为P C|x1|y1,其中P C为单一字节且P C=0 4,仍记为C1。计算椭圆曲线点kPB=(x2,y2):坐标x2:5 7 E 7 B 6 3 6 2 3 F A E 5 F 0 8 C D A 4 6 8 E 8 7 2 A 2 0 A F A 0 3 D E D 4 1 B F 1 4 0 3 7 7坐标y2:0 E 0 4 0

23、D C 8 3 A F 3 1 A 6 7 9 9 1 F 2 B 0 1 E B F 9 E F D 8 8 8 1 F 0 A 0 4 9 3 0 0 0 6 0 3消息M的比特长度k l e n=1 5 2计算t=KD F(x2|y2,k l e n):0 4 6 B 0 4 A 9 A D F 5 3 B 3 8 9 B 9 E 2 A A F B 4 7 D 9 0 F 4 D 0 8 9 7 8计算C2=Mt:6 1 0 5 6 7 D B D 4 8 5 4 F 5 1 F 4 F 0 0 A D C C 0 1 C F E 9 0 B 1 F B 1 C计算C3=H a s h

24、(x2|M|y2):x2|M|y2:5 7 E 7 B 6 3 6 2 3 F A E 5 F 0 8 C D A 4 6 8 E 8 7 2 A 2 0 A F A 0 3 D E D 4 1 B F 1 4 0 3 7 7 6 5 6 E 6 3 7 2 7 9 7 0 7 4 6 97G B/T3 2 9 1 8.42 0 1 66 F 6 E 2 0 7 3 7 4 6 1 6 E 6 4 6 1 7 2 6 4 0 E 0 4 0 D C 8 3 A F 3 1 A 6 7 9 9 1 F 2 B 0 1 E B F 9 E F D 8 8 8 1 F 0 A 0 4 9 30 0

25、0 6 0 3C3:6 A F B 3 B C E B D 7 6 F 8 2 B 2 5 2 C E 5 E B 2 5 B 5 7 9 9 6 8 6 9 0 2 B 8 C F 2 F D 8 7 5 3 6 E 5 5 E F 7 6 0 3 B 0 9 E 7 C输出密文M=C1|C3|C2:0 4 2 3 F C 6 8 0 B 1 2 4 2 9 4 D F D F 3 4 D B E 7 6 E 0 C 3 8 D 8 8 3 D E 4 D 4 1 F A 0 D 4 C F 5 7 0 C F 1 4 F 2 0 D A F 0 C 4 D 7 7 7 F 7 3 8 D

26、1 6 B 1 6 8 2 4 D 3 1 E E F B 9 D E 3 1 E E 1 F 6 A F B 3 B C E B D 7 6 F 8 2 B 2 5 2 C E 5 E B 2 5 B 5 7 9 9 68 6 9 0 2 B 8 C F 2 F D 8 7 5 3 6 E 5 5 E F 7 6 0 3 B 0 9 E 7 C 6 1 0 5 6 7 D B D 4 8 5 4 F 5 1 F 4 F 0 0 A D C C 0 1 C F E 9 0 B 1 F B 1 C解密各步骤中的有关值:计算椭圆曲线点dBC1=(x2,y2):坐标x2:5 7 E 7 B 6 3

27、6 2 3 F A E 5 F 0 8 C D A 4 6 8 E 8 7 2 A 2 0 A F A 0 3 D E D 4 1 B F 1 4 0 3 7 7坐标y2:0 E 0 4 0 D C 8 3 A F 3 1 A 6 7 9 9 1 F 2 B 0 1 E B F 9 E F D 8 8 8 1 F 0 A 0 4 9 3 0 0 0 6 0 3计算t=KD F(x2|y2,k l e n):0 4 6 B 0 4 A 9 A D F 5 3 B 3 8 9 B 9 E 2 A A F B 4 7 D 9 0 F 4 D 0 8 9 7 8计算M=C2t:6 5 6 E 6 3

28、7 2 7 9 7 0 7 4 6 9 6 F 6 E 2 0 7 3 7 4 6 1 6 E 6 4 6 1 7 2 6 4计算u=H a s h(x2|M|y2):6 A F B 3 B C E B D 7 6 F 8 2 B 2 5 2 C E 5 E B 2 5 B 5 7 9 9 6 8 6 9 0 2 B 8 C F 2 F D 8 7 5 3 6 E 5 5 E F 7 6 0 3 B 0 9 E 7 C明文M:6 5 6 E 6 3 7 2 7 9 7 0 7 4 6 9 6 F 6 E 2 0 7 3 7 4 6 1 6 E 6 4 6 1 7 2 6 4,即为:e n c

29、r y p t i o n s t a n d a r d示例2:Fp-2 5 6素数p:8 5 4 2 D 6 9 E 4 C 0 4 4 F 1 8 E 8 B 9 2 4 3 5 B F 6 F F 7 D E 4 5 7 2 8 3 9 1 5 C 4 5 5 1 7 D 7 2 2 E D B 8 B 0 8 F 1 D F C 3系数a:7 8 7 9 6 8 B 4 F A 3 2 C 3 F D 2 4 1 7 8 4 2 E 7 3 B B F E F F 2 F 3 C 8 4 8 B 6 8 3 1 D 7 E 0 E C 6 5 2 2 8 B 3 9 3 7 E 4

30、9 8系数b:6 3 E 4 C 6 D 3 B 2 3 B 0 C 8 4 9 C F 8 4 2 4 1 4 8 4 B F E 4 8 F 6 1 D 5 9 A 5 B 1 6 B A 0 6 E 6 E 1 2 D 1 D A 2 7 C 5 2 4 9 A基点G=(xG,yG),其阶记为n。坐标xG:4 2 1 D E B D 6 1 B 6 2 E A B 6 7 4 6 4 3 4 E B C 3 C C 3 1 5 E 3 2 2 2 0 B 3 B A D D 5 0 B D C 4 C 4 E 6 C 1 4 7 F E D D 4 3 D坐标yG:0 6 8 0 5 1

31、 2 B C B B 4 2 C 0 7 D 4 7 3 4 9 D 2 1 5 3 B 7 0 C 4 E 5 D 7 F D F C B F A 3 6 E A 1 A 8 5 8 4 1 B 9 E 4 6 E 0 9 A 2阶n:8 5 4 2 D 6 9 E 4 C 0 4 4 F 1 8 E 8 B 9 2 4 3 5 B F 6 F F 7 D D 2 9 7 7 2 0 6 3 0 4 8 5 6 2 8 D 5 A E 7 4 E E 7 C 3 2 E 7 9 B 7待加密的消息M:e n c r y p t i o n s t a n d a r d消息M的1 6进制表示

32、:6 5 6 E 6 3 7 2 7 9 7 0 7 4 6 9 6 F 6 E 2 0 7 3 7 4 6 1 6 E 6 4 6 1 7 2 6 4私钥dB:1 6 4 9 A B 7 7 A 0 0 6 3 7 B D 5 E 2 E F E 2 8 3 F B F 3 5 3 5 3 4 AA 7 F 7 C B 8 9 4 6 3 F 2 0 8 D D B C 2 9 2 0 B B 0 D A 0公钥PB=(xB,yB):坐标xB:4 3 5 B 3 9 C C A 8 F 3 B 5 0 8 C 1 4 8 8 A F C 6 7 B E 4 9 1 A 0 F 7 B A 0

33、 7 E 5 8 1 A 0 E 4 8 4 9 A 5 C F 7 0 6 2 8 A 7 E 0 A坐标yB:7 5 D D B A 7 8 F 1 5 F E E C B 4 C 7 8 9 5 E 2 C 1 C D F 5 F E 0 1 D E B B 2 C D B A D F 4 5 3 9 9 C C F 7 7 B B A 0 7 6 A 4 2加密各步骤中的有关值:产生随机数k:4 C 6 2 E E F D 6 E C F C 2 B 9 5 B 9 2 F D 6 C 3 D 9 5 7 5 1 4 8 A F A 1 7 4 2 5 5 4 6 D 4 9 0 1 8 E 5 3 8 8 D 4 9 D D 7 B 4 F计算椭圆曲线点C1=kG=(x1,y1):坐标x1:2 4 5 C 2 6 F B 6 8 B 1 D D D D B 1 2 C 4 B 6