Microsoft Word - SM2椭圆曲线公钥密码算法第2部分数字签名算法.doc

Size: px

Start display at page:

Download "Microsoft Word - SM2椭圆曲线公钥密码算法第2部分数字签名算法.doc"

叹旭米
5 years ago
Views:

1 SM2 椭圆曲线公钥密码算法第 2 部分 : 数字签名算法 Public key cryptographic algorithm SM2 based on elliptic curves-- Part 2: Digital signature algorithm

2 目次 1 术语和定义符号和缩略语数字签名算法综述椭圆曲线系统参数用户密钥对辅助函数用户其它信息数字签名的生成算法及流程数字签名的生成算法数字签名生成算法流程数字签名的验证算法及流程数字签名的验证算法数字签名验证算法流程... 6 附录 A 数字签名与验证示例... 7 A.1 综述... 7 A.2 F p 上的椭圆曲线数字签名... 7 A.3 F m 上的椭圆曲线数字签名

3 SM2 椭圆曲线公钥密码算法第 2 部分 : 数字签名算法 1 术语和定义下列术语和定义适用于本部分消息 message 任意有限长度的比特串签名消息 signed message 由消息以及该消息的签名部分所组成的一组数据项签名密钥 signature key 在数字签名生成过程中由签名者专用的秘密数据项, 即签名者的私钥签名生成过程 signature generation process 输入消息签名密钥和椭圆曲线系统参数, 并输出数字签名的过程可辨别标识 distinguishing identifier 可以无歧义辨别某一实体身份的信息 2 符号和缩略语下列符号和缩略语适用于本文件 A, B 使用公钥密码系统的两个用户 d A E(F q ) e 用户 A 的私钥 F q 上椭圆曲线 E 的所有有理点 ( 包括无穷远点 O) 组成的集合密码杂凑算法作用于消息 M 的输出值 e 密码杂凑算法作用于消息 M 的输出值包含 q 个元素的有限域 F q G 椭圆曲线的一个基点, 其阶为素数 H v ( ) 消息摘要长度为 v 比特的密码杂凑算法 ID A 用户 A 的可辨别标识 M 待签名消息 M 待验证消息 modn 模 n 运算例如,23 mod 7=2 n 基点 G 的阶 (n #E(F q ) 的素因子 ) O 椭圆曲线上的一个特殊点, 称为无穷远点或零点, 椭圆曲线加法群的单位元 1

4 P A q 用户 A 的公钥有限域 F q 中元素的数目 a, b F q 中的元素, 它们定义 F q 上的一条椭圆曲线 E x y x 与 y 的拼接, 其中 x y 可以比特串或字节串 Z A (r, s) (r, s ) 关于用户 A 的可辨别标识部分椭圆曲线系统参数和用户 A 公钥的杂凑值发送的签名收到的签名 [k]p 椭圆曲线上点 P 的 k 倍点, 即,[ k ] P = $ P +!! P#! !" P,k 正整数 [x, y] 大于或等于 x 且小于或等于 y 的整数的集合 k 个 3 数字签名算法 3.1 综述数字签名算法由一个签名者对数据产生数字签名, 并由一个验证者验证签名的可靠性每个签名者有一个公钥和一个私钥, 其中私钥用于产生签名, 验证者用签名者的公钥验证签名在签名的生成过程之前, 要用密码杂凑算法对 M ( 包含 Z A 和待签消息 M) 进行压缩 ; 在验证过程之前, 要用密码杂凑算法对 M ( 包含 Z A 和待验证消息 M ) 进行压缩 3.2 椭圆曲线系统参数椭圆曲线系统参数包括有限域 F q 的规模 q ( 当 q = 2 m 时, 还包括元素表示法的标识和约化多项式 ); 定义椭圆曲线 E(F q ) 的方程的两个元素 a b F q ;E(F q ) 上的基点 G = (x G, y G ) (G O), 其中 x G 和 y G F q 中的两个元素 ;G 的阶 n 及其它可选项 ( 如 n 的余因子 h 等 ) 椭圆曲线系统参数及其验证应符合 SM2 椭圆曲线公钥密码算法第 1 部分第 4 章的规定 3.3 用户密钥对用户 A 的密钥对包括其私钥 d A 和公钥 P A =[d A ]G = (x A, y A ) 用户密钥对的生成算法与公钥验证算法应符合 SM2 椭圆曲线公钥密码算法第 1 部分第 5 章的规定 3.4 辅助函数概述在本部分规定的椭圆曲线数字签名算法中, 涉及到两类辅助函数 : 密码杂凑算法与随机数发生器密码杂凑算法本部分规定使用国家密码管理局批准的密码杂凑算法, 如 SM3 密码杂凑算法随机数发生器本部分规定使用国家密码管理局批准的随机数发生器 3.5 用户其它信息作为签名者的用户 A 具有长度为 entlen A 比特的可辨别标识 ID A, 记 ENTL A 由整数 entlen A 转换而成的两个字节, 在本部分规定的椭圆曲线数字签名算法中, 签名者和验证者都需要用密码杂凑算法求得用户 A 的杂凑值 Z A 按 SM2 椭圆曲线公钥密码算法第 1 部分和给出的方法, 将椭圆曲线方程参数 a b G 的坐标 x G y G 和 P A 的坐标 x A y A 的数据类型转换为比特串, Z A =H 256 (ENTL A ID A a b x G y G x A y A ) 4 数字签名的生成算法及流程 4.1 数字签名的生成算法设待签名的消息为 M, 为了获取消息 M 的数字签名 (r, s), 作为签名者的用户 A 应实现以下运算步 2

5 骤 : A1: 置 M = Z A M; A2: 计算 e =H v ( M ), 按 SM2 椭圆曲线公钥密码算法第 1 部分和给出的方法将 e 的数据类型转换为整数 ; A3: 用随机数发生器产生随机数 k [1, n-1]; A4: 计算椭圆曲线点 (x 1, y 1 )=[k]g, 按 SM2 椭圆曲线公钥密码算法第 1 部分给出的方法将 x 1 的数据类型转换为整数 ; A5: 计算 r = (e+x 1 ) modn, 若 r = 0 或 r +k = n 则返回 A3; A6: 计算 s= ((1+d A ) -1 (k-r d A )) mod n, 若 s=0 则返回 A3; A7: 按 SM2 椭圆曲线公钥密码算法第 1 部分给出的细节将 r s 的数据类型转换为字节串, 消息 M 的签名为 (r, s) 注 : 数字签名生成过程的示例参见附录 A 4.2 数字签名生成算法流程数字签名生成算法流程见图 1 3

6 用户 A 的原始数据 ( 椭圆曲线系统参数 Z A M P A d A ) 第 1 步 : 置 M =Z A M 第 2 步 : 计算 e=h v ( M ) 第 3 步 : 产生随机数 k [1, n-1] 第 4 步 : 计算椭圆曲线点 (x 1, y 1 )=[k]g 第 5 步 : 计算 r= (e+x 1 ) modn r=0 或 r+k=n? 第 6 步 : 计算 s=((1+d A ) -1 (k-r d A )) modn s=0? 第 7 步 : 确定数字签名 (r, s) 输出消息 M 及其数字签名 (r, s) 图 1 数字签名生成算法流程 5 数字签名的验证算法及流程 5.1 数字签名的验证算法为了检验收到的消息 M 及其数字签名 (r, s ), 作为验证者的用户 B 应实现以下运算步骤 : B1: 检验 r [1, n-1] 成立, 若不成立则验证不通过 ; B2: 检验 s [1, n-1] 成立, 若不成立则验证不通过 ; B3: 置 M =Z A M ; B4: 计算 e =H v ( M ), 按 SM2 椭圆曲线公钥密码算法第 1 部分和给出的方法将 e 的 4

7 数据类型转换为整数 ; B5: 按本 SM2 椭圆曲线公钥密码算法第 1 部分给出的方法将 r s 的数据类型转换为整数, 计算 t = (r + s ) modn, 若 t = 0, 则验证不通过 ; B6: 计算椭圆曲线点 (x 1, y 1 ) = [ s ]G + [ t ]P A ; B7: 按 SM2 椭圆曲线公钥密码算法第 1 部分给出的方法将 x 1 的数据类型转换为整数, 计算 R = (e +x 1 ) modn, 检验 R = r 成立, 若成立则验证通过 ; 则验证不通过注 : 如果 Z A 不用户 A 所对应的杂凑值, 验证自然通不过数字签名验证过程的示例参见附录 A 5

8 5.2 数字签名验证算法流程数字签名验证算法流程见图 2 用户 B 的原始数据 ( 椭圆曲线系统参数 Z A P A M (r, s )) 第 1 步 : 检验 r [1, n-1] 成立 r [1,n-1]? 第 2 步 : 检验 s [1, n-1] 成立 s [1, n-1]? 第 3 步 : 置 M =Z A M 第 4 步 : 计算 e =H v ( M ) 第 5: 计算 t = (r +s ) modn t = 0? 第 6 步 : 计算椭圆曲线点 (x 1, y 1 ) = [ s ]G + [ t ]P A 第 7 步 : 计算 R = (e + x 1 ) mod n R=r? 验证通过验证不通过图 2 数字签名验证算法流程 6

9 附录 A 数字签名与验证示例 A.1 综述本附录选用 SM3 密码杂凑算法给出的密码杂凑算法, 其输入长度小于 2 64 的消息比特串, 输出长度为 256 比特的杂凑值, 记为 H 256 ( ) 本附录中, 所有用 16 进制表示的数, 左边为高位, 右边为低位本附录中, 消息采用 GB/T1988 给出的编码设用户 A 的身份 :ALICE123@YAHOO.COM 用 GB/T1988 给出的编码 ID A :414C F4F 2E434F4D ENTL A =0090 A.2 F p 上的椭圆曲线数字签名椭圆曲线方程为 :y 2 = x 3 + ax + b 示例 1:F p -256 素数 p:8542d69e 4C044F18 E8B92435 BF6FF7DE C45517D 722EDB8B 08F1DFC3 系数 a:787968b4 FA32C3FD E 73BBFEFF 2F3C848B 6831D7E0 EC65228B 3937E498 系数 b:63e4c6d3 B23B0C84 9CF BFE48 F61D59A5 B16BA06E 6E12D1DA 27C5249A 基点 G = (x G, y G ), 其阶记为 n 坐标 x G :421DEBD6 1B62EAB EB C3CC315E 32220B3B ADD50BDC 4C4E6C14 7FEDD43D 坐标 y G : B CBB42C07 D47349D2 153B70C4 E5D7FDFC BFA36EA1 A85841B9 E46E09A2 阶 n: 8542D69E 4C044F18 E8B92435 BF6FF7DD D 5AE74EE7 C32E79B7 待签名的消息 M:message digest 私钥 d A :128B2FA8 BD433C6C 068C8D80 3DFF7979 2A519A55 171B1B65 0C23661D 公钥 P A = (x A, y A ): 坐标 x A :0AE4C779 8AA0F BEE11 825BE462 02BB79E2 A E97C04FF 4DF2548A 坐标 y A :7C0240F8 8F1CD4E1 6352A73C 17B7F16F 07353E53 A176D684 A9FE0C6B B798E857 杂凑值 Z A = H 256 (ENTL A ID A a b x G y G x A y A ) Z A :F4A38489 E32B45B6 F876E3AC 2168CA DC8F 23459C1D 1146FC3D BFB7BC9A 签名各步骤中的有关值 : M =Z A M: F4A38489 E32B45B6 F876E3AC 2168CA DC8F 23459C1D 1146FC3D BFB7BC9A 6D 密码杂凑函数值 e = H 256 ( M ):B524F552 CD82B8B E00 5C377FB1 9A87E6FC 682D48BB 5D42E3D9 B9EFFE76 产生随机数 k:6cb28d99 385C175C 94F94E F C176D925 DD72B DBAAE 1FB2F96F 计算椭圆曲线点 (x 1, y 1 ) = [k]g: 坐标 x 1 :110FCDA D 5E7B9324 AC4B856D 23E6D918 8B2AE CE25D112 坐标 y 1 :1C65D68A 4A08601D F24B431E 0CAB4EBE B3 817E8581 1A8510B2 DF7ECA1A 计算 r = (e+x 1 ) modn:40f1ec59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 7

10 5BACDB49 C4E755D1 (1+d A ) -1 :79BFCF30 52C80DA7 B939E0C6 914A18CB B2D96D E A7 D4F5F956 计算 s = ((1+d A ) -1 (k - r d A )) modn: 6FC6DAC3 2C5D5CF1 0C77DFB2 0F7C2EB6 67A FB09EC5 6327A67E C7DEEBE7 消息 M 的签名为 (r, s): 值 r:40f1ec59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 值 s:6fc6dac3 2C5D5CF1 0C77DFB2 0F7C2EB6 67A FB09EC5 6327A67E C7DEEBE7 验证各步骤中的有关值 : 密码杂凑算法值 e =H 256 ( M ):B524F552 CD82B8B E00 5C377FB1 9A87E6FC 682D48BB 5D42E3D9 B9EFFE76 计算 t = (r + s ) mod n:2b75f07e D7ECE7CC C1C8986B 991F441A D324D6D6 19FE06DD 63ED32E0 C997C801 计算椭圆曲线点 (x 0, y 0 ) = [s ]G: 坐标 x 0 : 7DEACE5F D121BC38 5A3C F413D 28C17291 A60DFD83 B835A453 92D22B0A 坐标 y 0 : 2E49D5E5 279E5FA9 1E71FD8F 693A64A3 C4A A4FC9D 79F34EDC 8BDDEBD0 计算椭圆曲线点 (x 0 0, y 0 0 ) = [t]p A : 坐标 x 0 0 :1657FA75 BF2ADCDC 3C1F6CF0 5AB7B45E 04D3ACBE 8E4085CF A669CB25 64F17A9F 坐标 y 0 0 :19F0115F 21E16D2F 5C3A485F 8575A128 BBCDDF80 296A62F6 AC2EB842 DD058E50 计算椭圆曲线点 (x 1, y 1 ) = [s ]G +[t]p A : 坐标 x 1 : 110FCDA D 5E7B9324 AC4B856D 23E6D918 8B2AE CE25D112 坐标 y 1 : 1C65D68A 4A08601D F24B431E 0CAB4EBE B3 817E8581 1A8510B2 DF7ECA1A 计算 R = (e + x 1 ) modn:40f1ec59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 A.3 F m 2 上的椭圆曲线数字签名椭圆曲线方程为 :y 2 + xy= x 3 + ax 2 + b 示例 2:F 2 m-257 基域生成多项式 :x 257 +x 系数 a:0 系数 b:00 E78BCD09 746C A7E72B 12BCE002 66B9627E CB0B5A25 367AD1AD 4CC6242B 基点 G= (x G, y G ), 其阶记为 n 坐标 x G : 00 CDB9CA7F 1E6B0441 F658343F 4B10297C 0EF9B A 62E7A FADD 坐标 y G : 01 3DE74DA6 5951C4D7 6DC89220 D5F7777A 611B1C38 BAE260B DC8 060C2B3E 阶 n: 7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF BC972CF7 E6B6F B3C6A 0CF6161D 待签名的消息 M:message digest 私钥 d A : 771EF3DB FF5F1CDC 32B9C B2BF 7CB981D7 F5B F0931 公钥 P A = (x A, y A ): 坐标 x A : A B917F 657D7E93 82F1EA5C D931F40F 6627F B2 坐标 y A : D590FB8 DE635D8F CA715CC6 BF3D05BE F3F75DA5 D 杂凑值 Z A = H 256 (ENTL A ID A a b x G y G x A y A ) Z A :26352AF8 2EC19F20 7BBC6F94 74E11E90 CE0F7DDA CE03B27F E8 97A81FD5 签名各步骤中的有关值 : 8

11 M = Z A M: 26352AF8 2EC19F20 7BBC6F94 74E11E90 CE0F7DDA CE03B27F E8 97A81FD5 6D 密码杂凑算法值 e = H 256 ( M ):AD673CBD A A9EAA5 F9AB1AA1 633AD477 18A84DFD 46C17C6F A0AA3B12 产生随机数 k:36cd79fc 8E24B735 7A8A7B4A 46D454C D C B341 ADA186D6 计算椭圆曲线点 (x 1, y 1 ) = [k]g: 坐标 x 1 :00 3FD87D69 47A15F94 25B32EDD 39381ADF D5E71CD4 BB357E3C 6A6E0397 EEA7CD66 坐标 y 1 : D73951E 9EB373A B7B56D1D 50B4CD6E B32ED387 A65AA6A2 计算 r = ( e+x 1 ) mod n:6d3fba26 EAB2A105 4F5D E C8AC453 ED26D339 1CD4439D 825BF25B (1+d A ) -1 :73AF2954 F951A9DF F5B4C8F7 119DAA1C 230C9BAD E60568D0 5BC3F432 1E1F4260 计算 s = ((1+d A ) -1 (k - r d A )) modn:3124c568 8D95F0A1 0252A9BE D033BEC8 4439DA B6D6 FAD77F94 B74A9556 消息 M 的签名为 (r, s): 值 r:6d3fba26 EAB2A105 4F5D E C8AC453 ED26D339 1CD4439D 825BF25B 值 s:3124c568 8D95F0A1 0252A9BE D033BEC8 4439DA B6D6 FAD77F94 B74A9556 验证各步骤中的有关值 : 密码杂凑算法值 e =H 256 ( M ):AD673CBD A A9EAA5 F9AB1AA1 633AD477 18A84DFD 46C17C6F A0AA3B12 计算 t = (r + s ) modn: 1E647F8F A6 51AFC F44A 042D7194 4C91910F C8 2CB07194 计算椭圆曲线点 (x 0, y 0 ) = [s ]G: 坐标 x 0 : CF6B6 3A044FCE 553EAA77 3E1E E0DAA1 0E4B D11552 EA6418F7 坐标 y 0 : F3C5D B3A0D312 9EAE44E0 21C E4264B E1BEEBCA 3B8159DC A382653A 计算椭圆曲线点 (x 0 0, y 0 0 ) = [t]p A : 坐标 x 0 0 :00 07DA3F04 0EFB9C28 1BE107EC C389F56F E76A680B B5FDEE1D D554DC11 EB477C88 坐标 y 0 0 :01 7BA2845D C65945C3 D48926C7 0C953A1A F29CE2E1 9A7EEE6B E0269FB4 803CA68B 计算椭圆曲线点 (x 1, y 1 ) = [s ]G +[t]p A : 坐标 x 1 : 00 3FD87D69 47A15F94 25B32EDD 39381ADF D5E71CD4 BB357E3C 6A6E0397 EEA7CD66 坐标 y 1 : D73951E 9EB373A B7B56D1D 50B4CD6E B32ED387 A65AA6A2 计算 R = (e + x 1 ) mod n: 6D3FBA26 EAB2A105 4F5D E C8AC453 ED26D339 1CD4439D 825BF25B 9

Visualize CMap

Visualize CMap 0001 0020 0002 0021 0003 0022 0004 0023 0005 0024 0006 0025 0007 0026 0008 0027 0009 0028 000A 0029 000B 002A 000C 002B 000D 002C 000E 002D 000F 002E 0010 002F 0011 0030 0012 0031 0013 0032 0014 0033 0015

Microsoft Word - SM2椭圆曲线公钥密码算法第2部分 数字签名算法.doc

Microsoft Word - SM2椭圆曲线公钥密码算法第2部分数字签名算法.doc