idnits 2.17.1 draft-shen-sm2-ecdsa-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 35 instances of too long lines in the document, the longest one being 21 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 138 has weird spacing: '...enation of x ...' == Line 167 has weird spacing: '...enation of x ...' == The document doesn't use any RFC 2119 keywords, yet has text resembling RFC 2119 boilerplate text. -- The document date (October 24, 2011) is 4569 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC2119' is mentioned on line 96, but not defined == Unused Reference: 'RFC1341' is defined on line 461, but no explicit reference was found in the text == Unused Reference: 'RFC2049' is defined on line 468, but no explicit reference was found in the text ** Obsolete normative reference: RFC 1341 (Obsoleted by RFC 1521) Summary: 4 errors (**), 0 flaws (~~), 7 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force S. Shen, Ed. 3 Internet-Draft X. Lee, Ed. 4 Intended status: Standards Track Chinese Academy of Science 5 Expires: April 26, 2012 October 24, 2011 7 SM2 Digital Signature Algorithm 8 draft-shen-sm2-ecdsa-00 10 Abstract 12 This document discribles an Digital Signature Algorithm based on 13 elliptic curves which is invented by Xiaoyun Wang et al. This 14 digital signature algorithm is published by Chinese Commercial 15 Cryptography Administration Office for the use of electronic 16 authentication service system. 18 The document *** published by Chinese Commercial Cryptography 19 Administration Office includes four parts: general introdocution, 20 Digital Signature Algorithm, Key Exchange Protocol and Public Key 21 Encryption Algorithm. This document only gives the general 22 introduction and digital signature algorithm. 24 Status of This Memo 26 This Internet-Draft is submitted to IETF in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on April 26, 2012. 41 Copyright Notice 43 Copyright (c) 2011 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 2. Conventions Used in this Document . . . . . . . . . . . . . . 3 60 3. Symbols and Terms . . . . . . . . . . . . . . . . . . . . . . 3 61 3.1. Symbols . . . . . . . . . . . . . . . . . . . . . . . . . 3 62 3.2. Terms . . . . . . . . . . . . . . . . . . . . . . . . . . 5 63 4. General Introdoction to ECC . . . . . . . . . . . . . . . . . 5 64 5. Digital Signature Algorithm . . . . . . . . . . . . . . . . . 5 65 5.1. Digital Signature System . . . . . . . . . . . . . . . . . 5 66 5.1.1. General Rules . . . . . . . . . . . . . . . . . . . . 5 67 5.1.2. Parameters of Elliptic Curve System . . . . . . . . . 5 68 5.1.3. Key pairs . . . . . . . . . . . . . . . . . . . . . . 6 69 5.1.4. Auxilary Functions . . . . . . . . . . . . . . . . . . 6 70 5.2. Generation of Signature . . . . . . . . . . . . . . . . . 6 71 5.2.1. Digital Signature Generation Algorithm . . . . . . . . 6 72 5.2.2. Flow Chart of Digital Signature Generation . . . . . . 7 73 5.3. Verification of Signature . . . . . . . . . . . . . . . . 8 74 5.3.1. Digital Signagure Vefification Algorithm . . . . . . . 8 75 5.3.2. Flow Chart of Digital Signature Verification . . . . . 9 76 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 77 6.1. Normative References . . . . . . . . . . . . . . . . . . . 11 78 6.2. Informative References . . . . . . . . . . . . . . . . . . 11 79 Appendix A. Example . . . . . . . . . . . . . . . . . . . . . . . 11 80 A.1. General Introduction . . . . . . . . . . . . . . . . . . . 11 81 A.2. Digital Signature of over E(Fp) . . . . . . . . . . . . . 12 82 A.3. Digital Signature of over E(F2^m) . . . . . . . . . . . . 13 84 1. Introduction 86 This document is mainly the tranlation of the algorithm published by 87 Chinese Commercial Cryptography Administration Office for the 88 convenience of IETF and IRTF community. The credit of inventing this 89 algorithm goes to the authors of the algorithm. 91 2. Conventions Used in this Document 93 The key words "MUST", "MUST NOT", "SHOULD", "SHOULD NOT", and "MAY" 94 in this document are to be interpreted as defined in "Key words for 95 use in RFCs to Indicate Requirement Levels" [RFC2119]. 97 3. Symbols and Terms 99 3.1. Symbols 101 a, b Elements in finite field Fq and they defines a Elliptic 102 Curve E over Fq 103 B The MOV threshold. This is a positive integer B such that 104 taking discrete logarithms over GF (q^B) is judged to be at 105 least as difficult as taking elliptic discrete logarithms over 106 GF (q). 107 deg(f) The degree of a polynomial f(x) 108 E The elliptic curve defined by a and b over a finite field Fq 109 E(Fq) The set of all the rational points of E 110 #E(Fq) The number of elements in E(Fq), the degree of elliptic curve E(Fq) 111 ECDLP Elliptic Curve Discrete Logarithm Problem 112 Fp A prime field with p elements 113 Fq A prime field with q elements 114 F*q The multiplicative group composed of all non-zero elememnts in Fq 115 F2^m The binary field extension with 2^m elements 116 G A base point on the elliptic curve E, with prime order 117 gcd(x;y) The greatest common devisor of x and y 118 h The cofactor h= #E(Fp)/n, where n is the degree of a base point G 119 LeftRotate( ) The operation of Rotation to left 120 lmax The upper limit of the largest prime factor of the cofactor h 121 m The extention degree of the field F2^m over the binary field F2 122 modf(x) The operation module the polynomial f(x). All the coefficients 123 mod 2 when f(x) is a polynomial over F2. 124 modn The operation of modulo n, for example, 23 mod7 = 2 126 n The degree of a base point G (n is a prime factor of #E(Fq) 127 O The point of infinity (or zero) on the elliptic curre E. 128 P A point P on the elliptic curre E which is not O. The coordinates 129 xP and yP satisfies the elliptic curve equation 130 P1+P2 The summation of the two points P1 and P2 on elliptic curve E 131 p A prime number greater than 3 132 q The number of elements in the finite field Fq 133 rmin The lower limit of the degree n of a base point G 134 Tr( ) The trace function 135 xP The x-coordinate of the point P 136 yP The y-coordinate of the point P 137 x^(-1) The only y such that x*y=1 (modn), 1 < = y < = n, gcd(x, n)=1 138 x||y The concatenation of x and y, where x and y are bit string or byte string 139 x == y (modn) x modn = y modn 140 ** y~P The point compression expression of yP 141 Zp The ring of integers modulo p 142 < G > The cyclic group generated by base point G 143 [k]P The k multiple of a point P over elliptic curve, where k is a positive integer 144 [x;y] The set of integers which greater than or equal to x and less than or equal to y 145 /x\ The smallest integer greater than or equal to x, for example GBP[not]/7\=7, /8.3\=9 146 \x/ The largest integer less than or equal to x, for example GBP[not]\7/=7, \8.3/=8 147 XOR The exclusive-or operation of two bit strings or byte strings of same length 148 *********** 149 A,B The two users using the public key system 150 a, b Elements in finite field Fq and they defines a Elliptic 151 Curve E over Fq 152 dA The private key of the user A 153 E(Fq) The set of all the rational points of E 154 e The hash of message M 155 e' The hash of message M' 156 Fq A prime field with q elements 157 G A base point on the elliptic curve E, with prime order 158 Hv( ) The hash function with output of legnth v bits 159 IDA The identifier of user A 160 M The message for signature 161 M!ae The message for verification 162 modn The operation of modulo n, for example, 23 mod7 = 2 163 n The degree of base point G (n is a prime factor of #E(Fq)) 164 O The point of infinity (or zero) on the elliptic curre E 165 PA The public key of user A 166 q The number of elements in the finite field Fq 167 x||y The concatenation of x and y, where x and y are bit string or byte string 168 ZA The identifier of user A, part of parameters of elliptic curve and hash value of PA 169 (r,s) The sent signature 170 (r',s') The received signature 171 [k]P The k multiple of a point P over elliptic curve, where k is a positive integer 172 [x;y] The set of integers which greater than or equal to x and less than or equal to y 173 /x\ The smallest integer greater than or equal to x, for example GBP[not]/7\=7, /8.3\=9 174 \x/ The largest integer less than or equal to x, for example GBP[not]\7/=7, \8.3/=8 175 #E(Fq) The number of elements in E(Fq), the degree of elliptic curve E(Fq) 176 ********** 177 3.2. Terms 179 The following terms are used in this document. 181 digital signature 182 The metadata over some data. It should provide authentication, 183 integrity protection and non repudiation. 184 [ANSI X9.63-2001] 186 message 187 The bits string of arbitary length. 188 [ISO/IEC 15946-4 3.7] 190 signed message 191 The data composed of a message and its digital signature. 192 [ISO/IEC 15946-4 3.14] 194 key 195 A parameter for cryptographic calculation. It was used for encryption 196 or decryption, shared sectet and verification of digital signature. 197 [ANSI X9.63-2001] 199 4. General Introdoction to ECC 201 TBD 203 5. Digital Signature Algorithm 205 5.1. Digital Signature System 207 5.1.1. General Rules 209 In the digital signtature algorithm, one signer generate digital 210 signature over given data and one verifier verifies the validation of 211 the signature. Each signer ownes one public key and one private key. 212 The private key was used for signing and verifier verfifies the 213 signature using the public key. Before generation of the digital 214 signature, the message M and ZA need to be compressed via a hash 215 function; before the verification of the digital signature, the 216 message M' and ZA need to be compressed via a hash function. 218 5.1.2. Parameters of Elliptic Curve System 220 The parameters of an elliptic curve systme include the size q of a 221 finite field Fq (when q=2^m, also include basis representation and 222 irreducible polynomial); the two elements a and b (in Fq) which 223 defines the elliptic curve equation; the base point G=(xG, yG) (G not 224 euqals O), where xG and yG are ellements in Fq; the degree n of G and 225 other optional parameter such as cofactor h. 227 5.1.3. Key pairs 229 The user A's key pair include his private key dA and public key 230 PA=[dA]G=(xA, yA). 232 5.1.4. Auxilary Functions 234 5.1.4.1. Introduction 236 The auxilary functions in the elliptic curve digital signature 237 algorithm in this document include hash algorithm and random number 238 generator. 240 5.1.4.2. Hash Functions 242 The sm2 digital signature algorithm requires the hash functions 243 approved by Chinese Commercial Cryptography Administration Office, 244 such as sm3. 246 5.1.4.3. Random Number Generator 248 The sm2 digital signature algorithm requires random number generators 249 approved by by Chinese Commercial Cryptography Administration Office. 251 5.1.4.4. Other User Information 253 As teh signer, User A has the identifier IDA of length entlenA bits, 254 denote ENTLA as the two bytes transformed from the integer entlenA. 255 In the digital signature algorithms in this document, both signer and 256 verifier need to obtain ZA by calculating the hash value of ZA. 258 ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) 260 5.2. Generation of Signature 262 5.2.1. Digital Signature Generation Algorithm 264 Let M be the message for signing, in order to obtain the signature 265 (r, s), the signer A need to perform the following: 267 A1: set M~=ZA || M 268 A2: calculate e=Hv(M~) 269 A3: pick a random number k in [1, n-1] via a random number generator 270 A4: calculate the elliptic curve point (x1, y1)=[k]G 271 A5: calculate r=(e+x1) modn, return to A3 if r=0 or r+k=n 272 A6: calculate s=((1+dA)^(-1)*(k-r*dA)) modn, return to A3 if s=0 273 A7: the digital signature of M is (r, s) 275 5.2.2. Flow Chart of Digital Signature Generation 277 +-------------------------------------------+ 278 | the original data of user A | 279 | (parameters of elliptic curve | 280 | system, ZA, M, PA, dA) | | 281 +-------------------------------------------+ 282 | 283 | 284 v 285 +-------------------------------------------+ 286 | +------------------------+ | 287 | | A1: set M~=ZA || M | | 288 | +------------------------+ | 289 | | | 290 | v | 291 | +------------------------+ | 292 | | A2: calculate e=Hv(M~)| | 293 | +------------------------+ | 294 | | | 295 | v | 296 | +------------------------+ | 297 | | A3: set M~=ZA || M | < ----+ | 298 | +------------------------+ | | 299 | | | | 300 | v | | 301 | +--------------------------+ | | 302 | | A4: pick a random number | | | 303 | | k in [1, n-1] | | | 304 | +--------------------------+ | | 305 | | | | 306 | +--------------------------+ | | 307 | | A5: calculate the point | | | 308 | | (x1, y1)=[k]G | | | 309 | +--------------------------+ | | 310 | | | | 311 | v | | 312 | /---------------------\ YES | | 313 | | r=0 or r+k=n ? | ----->| | 314 | \---------------------/ | | 315 | | | | 316 | | NO | | 317 | v | | 318 | +---------------------------------+ | | 319 | | A6: calculate | | | 320 | | s=((1+dA)^(-1)*(k-r*dA)) modn | | | 321 | +---------------------------------+ | | 322 | | | | 323 | v | | 324 | /---------------------\ YES | | 325 | | r=0 ? | ------+ | 326 | \---------------------/ | 327 | | | 328 | | NO | 329 | v | 330 | +----------------------------+ | 331 | | A6: the digital signature | | 332 | | of M is (r, s) | | 333 | +----------------------------+ | 334 +-------------------------------------------+ 335 | 336 | 337 v 338 +-------------------------------------------+ 339 | Output the message M | 340 | and its digital signature (r,s) | 341 +-------------------------------------------+ 343 Figure 1: Flow Chart of Digital Signature Generation 345 5.3. Verification of Signature 347 5.3.1. Digital Signagure Vefification Algorithm 349 To verfify the received message M' and it's digital signature, the 350 verifier need to perform the following: 352 B1: verify whether r' in [1,n-1], verification failed if not 353 B2: vefify whether s' in [1,n-1], verification failed if not 354 B3: set M'~=ZA || M' 355 B4: calculate e'=Hv(M'~) 356 B5: calculate t = (r' + s') modn, verification failed if t=0 357 B6: calculate the point (x1', y1')=[s']G + [t]PA 358 B7: calculate R=(e'+x1') modn, verfication pass if yes, otherwise failed 360 Note: The verification will certainly fail if ZA does not correspond to 361 teh hash value of A. 363 5.3.2. Flow Chart of Digital Signature Verification 365 +-------------------------------------------+ 366 | the original data of user B | 367 | (parameters of elliptic curve | 368 | system, ZA, M', PA, (r', s')) | | 369 +-------------------------------------------+ 370 | 371 | 372 v 373 +-------------------------------------------+ 374 | +---------------------------+ | 375 | | B1: verify r' in [1,n-1] | | 376 | +---------------------------+ | 377 | | | 378 | v | 379 | /---------------------\ NO | 380 | | r' in [1,n-1] ? | ------+ | 381 | \---------------------/ | 382 | | | 383 | | YES | 384 | v | 385 | +---------------------------+ | 386 | | B2: verify s' in [1,n-1] | | 387 | +---------------------------+ | 388 | | | 389 | v | 390 | /---------------------\ NO | 391 | | s' in [1,n-1] ? | ------+ | 392 | \---------------------/ | 393 | | | 394 | | YES | 395 | v | 396 | +------------------------+ | 397 | | B3: set M'~=ZA || M' | < ----+ | 398 | +------------------------+ | | 399 | | | | 400 | v | | 401 | +--------------------------+ | | 402 | | B4: calculate e'=Hv(M'~) | | | 403 | +--------------------------+ | | 404 | | | | 405 | v | | 406 | +--------------------------+ | | 407 | | B5: calculate | | | 408 | | t = (r' + s') modn | | | 409 | +--------------------------+ | | 410 | | | | 411 | v | | 412 | /---------------------\ YES | | 413 | | t=0 ? | ----->| | 414 | \---------------------/ | | 415 | | | | 416 | | NO | | 417 | v | | 418 | +---------------------------------+ | | 419 | | B6: calculate | | | 420 | | s=((1+dA)^(-1)*(k-r*dA)) modn | | | 421 | +---------------------------------+ | | 422 | | | | 423 | v | | 424 | /---------------------\ YES | | 425 | | r=0 ? | ------+ | 426 | \---------------------/ | | 427 | | | | 428 | | NO | | 429 | v | | 430 | +----------------------------+ | | 431 | | B6: calculate | | | 432 | | (x1', y1')=[s']G + [t]PA | | | 433 | +----------------------------+ | | 434 | | | | 435 | v | | 436 | +----------------------------+ | | 437 | | B7: calculate | | | 438 | | R=(e'+x1') modn | | | 439 | +----------------------------+ | | 440 | | | | 441 | v | | 442 | /---------------------\ NO | | 443 | | R=r' ? | ------+ | 444 | \---------------------/ | | 445 | | | | 446 | | YES | | 447 | | | | 448 +-------------------------------------------+ 449 | | 450 v v 451 +-------------------+ +-------------------+ 452 | Verification Pass | | Verification Fail | 453 +-------------------+ +-------------------+ 455 Figure 2: Flow Chart of Digital Signature Verification 457 6. References 459 6.1. Normative References 461 [RFC1341] Borenstein, N. and N. Freed, "MIME (Multipurpose Internet 462 Mail Extensions): Mechanisms for Specifying and Describing 463 the Format of Internet Message Bodies", RFC 1341, 464 June 1992. 466 6.2. Informative References 468 [RFC2049] Freed, N. and N. Borenstein, "Multipurpose Internet Mail 469 Extensions (MIME) Part Five: Conformance Criteria and 470 Examples", RFC 2049, November 1996. 472 Appendix A. Example 474 A.1. General Introduction 476 This appendix uses the hash algorithm described in 477 draft-shen-sm3-hash-00, which applies on a bit string of length less 478 than 2^54 and output a hash value of size 256, denotes as H256( ). 480 In this appendix, all the hexadecimal number has high digits on the 481 left and low digits on teh right. 483 In this appendix, all the messages are in ASCII code. 485 Let the user A's identity be: ALICE123@YAHOO.COM. Denoted in ASCII 486 code IDA: 488 414C 49434531 32334059 41484F4F 2E434F4 490 ENTLA=0090. 492 A.2. Digital Signature of over E(Fp) 494 The elliptic curve equationi is: 496 y^2 = x^3 + ax + b 498 Example 1: Fp-256 499 A Prime p: 500 8542D69E 4C044F18 E8B92435 BF6FF7DE 45728391 5C45517D 722EDB8B 08F1DFC3 502 The coefficient a: 503 787968B4 FA32C3FD 2417842E 73BBFEFF 2F3C848B 6831D7E0 EC65228B 3937E498 505 The coefficient b: 506 63E4C6D3 B23B0C84 9CF84241 484BFE48 F61D59A5 B16BA06E 6E12D1DA 27C5249A 508 The base point G=(xG,yG)GBP[not]whose degree is n: 509 x-coordinate xG: 510 421DEBD6 1B62EAB6 746434EB C3CC315E 32220B3B ADD50BDC 4C4E6C14 7FEDD43D 511 y-coordinate yG: 512 0680512B CBB42C07 D47349D2 153B70C4 E5D7FDFC BFA36EA1 A85841B9 E46E09A2 513 degree n: 514 8542D69E 4C044F18 E8B92435 BF6FF7DD 29772063 0485628D 5AE74EE7 C32E79B7 516 The message M to be signed:message digest 518 The private key dA: 519 128B2FA8 BD433C6C 068C8D80 3DFF7979 2A519A55 171B1B65 0C23661D 15897263 521 The public key PA=(xA,yA): 522 x-coordinate xA: 523 0AE4C779 8AA0F119 471BEE11 825BE462 02BB79E2 A5844495 E97C04FF 4DF2548A 524 y-coordinate yA: 525 7C0240F8 8F1CD4E1 6352A73C 17B7F16F 07353E53 A176D684 A9FE0C6B B798E857 527 Hash value ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) 529 ZA: 530 F4A38489 E32B45B6 F876E3AC 2168CA39 2362DC8F 23459C1D 1146FC3D BFB7BC9A 532 The intermediate value during signing processing: 533 M~=ZA || M: 534 F4A38489 E32B45B6 F876E3AC 2168CA39 2362DC8F 23459C1D 1146FC3D BFB7BC9A 535 6D657373 61676520 64696765 7374 536 hash value e=H256(M): 537 B524F552 CD82B8B0 28476E00 5C377FB1 9A87E6FC 682D48BB 5D42E3D9 B9EFFE76 538 random number k: 539 6CB28D99 385C175C 94F94E93 4817663F C176D925 DD72B727 260DBAAE 1FB2F96F 540 point (x1,y1)=[k]G: 541 x-coordinate x1: 542 110FCDA5 7615705D 5E7B9324 AC4B856D 23E6D918 8B2AE477 59514657 CE25D112 543 y-coordinate y1: 544 1C65D68A 4A08601D F24B431E 0CAB4EBE 084772B3 817E8581 1A8510B2 DF7ECA1A 545 r=(e+x1) modn: 546 40F1EC59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 547 (1 + dA)^(-1) 548 79BFCF30 52C80DA7 B939E0C6 914A18CB B2D96D85 55256E83 122743A7 D4F5F956 549 s = ((1 + dA)^(-1)1 * (k - r * dA)) modn: 550 6FC6DAC3 2C5D5CF1 0C77DFB2 0F7C2EB6 67A45787 2FB09EC5 6327A67E C7DEEBE7 552 Digital Signature of the message M: (r,s) 553 r: 554 40F1EC59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 555 s: 556 6FC6DAC3 2C5D5CF1 0C77DFB2 0F7C2EB6 67A45787 2FB09EC5 6327A67E C7DEEBE7 558 The intermediate value during verification processing: 559 hash value e' = H256(M'~): 560 B524F552 CD82B8B0 28476E00 5C377FB1 9A87E6FC 682D48BB 5D42E3D9 B9EFFE76 561 t=(r!ae+s!ae) modn: 562 2B75F07E D7ECE7CC C1C8986B 991F441A D324D6D6 19FE06DD 63ED32E0 C997C801 563 point (x0!ae, y0')=[s']G: 564 x-coordinate x0': 565 7DEACE5F D121BC38 5A3C6317 249F413D 28C17291 A60DFD83 B835A453 92D22B0A 566 y-coordinate y0': 567 2E49D5E5 279E5FA9 1E71FD8F 693A64A3 C4A94611 15A4FC9D 79F34EDC 8BDDEBD0 568 point (x00', y00')=[t]PA: 569 x-coordinate x00': 570 1657FA75 BF2ADCDC 3C1F6CF0 5AB7B45E 04D3ACBE 8E4085CF A669CB25 64F17A9F 571 y-coordinate y00': 572 19F0115F 21E16D2F 5C3A485F 8575A128 BBCDDF80 296A62F6 AC2EB842 DD058E50 573 point (x1', y1')=[s']G + [t]PA: 574 x-coordinate x1': 575 110FCDA5 7615705D 5E7B9324 AC4B856D 23E6D918 8B2AE477 59514657 CE25D112 576 y-coordinate y1': 577 1C65D68A 4A08601D F24B431E 0CAB4EBE 084772B3 817E8581 1A8510B2 DF7ECA1A 578 R = (e' + x1') modn: 579 40F1EC59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 581 A.3. Digital Signature of over E(F2^m) 583 The elliptic curve equationi is: 585 y^2 + xy = x^3 + ax + b 587 Example 1: F2^m -257 588 The polynomial to generate base field is: x^257 + x^12 + 1 590 The coefficient a: 591 0 593 The coefficient b: 594 00 E78BCD09 746C2023 78A7E72B 12BCE002 66B9627E CB0B5A25 367AD1AD 4CC6242B 596 The base point G=(xG,yG)GBP[not]whose degree is n: 597 x-coordinate xG: 598 00 CDB9CA7F 1E6B0441 F658343F 4B10297C 0EF9B649 1082400A 62E7A748 5735FADD 600 y-coordinate yG: 601 01 3DE74DA6 5951C4D7 6DC89220 D5F7777A 611B1C38 BAE260B1 75951DC8 060C2B3E 603 degree n: 604 7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF BC972CF7 E6B6F900 945B3C6A 0CF6161D 606 The message M to be signed:message digest 608 The private key dA: 609 771EF3DB FF5F1CDC 32B9C572 93047619 1998B2BF 7CB981D7 F5B39202 645F0931 611 The public key PA=(xA,yA): 612 x-coordinate xA: 613 01 65961645 281A8626 607B917F 657D7E93 82F1EA5C D931F40F 6627F357 542653B2 614 y-coordinate yA: 615 01 68652213 0D590FB8 DE635D8F CA715CC6 BF3D05BE F3F75DA5 D5434544 48166612 617 Hash value ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) 618 ZA: 619 26352AF8 2EC19F20 7BBC6F94 74E11E90 CE0F7DDA CE03B27F 801817E8 97A81FD5 621 The intermediate value during signing processing: 622 M~=ZA || M: 623 26352AF8 2EC19F20 7BBC6F94 74E11E90 CE0F7DDA CE03B27F 801817E8 97A81FD5 624 6D657373 61676520 64696765 7374 626 hash value e=H256(M~): 627 AD673CBD A3114171 29A9EAA5 F9AB1AA1 633AD477 18A84DFD 46C17C6F A0AA3B12 628 random number k: 629 36CD79FC 8E24B735 7A8A7B4A 46D454C3 97703D64 98158C60 5399B341 ADA186D6 630 point (x1,y1)=[k]G: 631 x-coordinate x1: 633 00 3FD87D69 47A15F94 25B32EDD 39381ADF D5E71CD4 BB357E3C 6A6E0397 EEA7CD66 634 y-coordinate y1: 635 00 80771114 6D73951E 9EB373A6 58214054 B7B56D1D 50B4CD6E B32ED387 A65AA6A2 636 r=(e+x1) modn: 637 6D3FBA26 EAB2A105 4F5D1983 32E33581 7C8AC453 ED26D339 1CD4439D 825BF25B 638 (1 + dA)^(-1) 639 73AF2954 F951A9DF F5B4C8F7 119DAA1C 230C9BAD E60568D0 5BC3F432 1E1F4260 640 s = ((1 + dA)^(-1)1 * (k - r * dA)) modn: 641 3124C568 8D95F0A1 0252A9BE D033BEC8 4439DA38 4621B6D6 FAD77F94 B74A9556 643 Digital Signature of the message M: (r,s) 644 r: 645 6D3FBA26 EAB2A105 4F5D1983 32E33581 7C8AC453 ED26D339 1CD4439D 825BF25B 646 s: 647 3124C568 8D95F0A1 0252A9BE D033BEC8 4439DA38 4621B6D6 FAD77F94 B74A9556 649 The intermediate value during verification processing: 650 hash value e' = H256(M'~): 651 AD673CBD A3114171 29A9EAA5 F9AB1AA1 633AD477 18A84DFD 46C17C6F A0AA3B12 652 t=(r!ae+s!ae) modn: 653 1E647F8F 784891A6 51AFC342 0316F44A 042D7194 4C91910F 835086C8 2CB07194 654 point (x0!ae, y0')=[s']G: 655 x-coordinate x0': 656 00 252CF6B6 3A044FCE 553EAA77 3E1E9264 44E0DAA1 0E4B8873 89D11552 EA6418F7 657 y-coordinate y0': 658 00 776F3C5D B3A0D312 9EAE44E0 21C28667 92E4264B E1BEEBCA 3B8159DC A382653A 659 point (x00', y00')=[t]PA: 660 x-coordinate x00': 661 00 07DA3F04 0EFB9C28 1BE107EC C389F56F E76A680B B5FDEE1D D554DC11 EB477C88 662 y-coordinate y00': 663 01 7BA2845D C65945C3 D48926C7 0C953A1A F29CE2E1 9A7EEE6B E0269FB4 803CA68B 664 point (x1', y1')=[s']G + [t]PA: 665 x-coordinate x1': 666 00 3FD87D69 47A15F94 25B32EDD 39381ADF D5E71CD4 BB357E3C 6A6E0397 EEA7CD66 667 y-coordinate y1': 668 00 80771114 6D73951E 9EB373A6 58214054 B7B56D1D 50B4CD6E B32ED387 A65AA6A2 669 R = (e' + x1') modn: 670 6D3FBA26 EAB2A105 4F5D1983 32E33581 7C8AC453 ED26D339 1CD4439D 825BF25B 671 Authors' Addresses 673 Sean Shen (editor) 674 Chinese Academy of Science 675 No.4 South 4th Zhongguancun Street 676 Beijing, 100190 677 China 679 Phone: +86 10-58813038 680 EMail: shenshuo@cnnic.cn 682 Xiaodong Lee (editor) 683 Chinese Academy of Science 684 No.4 South 4th Zhongguancun Street 685 Beijing, 100190 686 China 688 Phone: +86 10-58813038 689 EMail: shenshuo@cnnic.cn