Internet Engineering Task Force S. Shen, Ed. Internet-Draft X. Lee, Ed. Intended status: Standards Track Chinese Academy of Science Expires: April 26, 2012 October 24, 2011 SM2 Digital Signature Algorithm draft-shen-sm2-ecdsa-00 Abstract This document discribles an Digital Signature Algorithm based on elliptic curves which is invented by Xiaoyun Wang et al. This digital signature algorithm is published by Chinese Commercial Cryptography Administration Office for the use of electronic authentication service system. The document *** published by Chinese Commercial Cryptography Administration Office includes four parts: general introdocution, Digital Signature Algorithm, Key Exchange Protocol and Public Key Encryption Algorithm. This document only gives the general introduction and digital signature algorithm. Status of This Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on April 26, 2012. Copyright Notice Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of Shen & Lee Expires April 26, 2012 [Page 1] Internet-Draft SM2 Digital Signature Algorithm October 2011 publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions Used in this Document . . . . . . . . . . . . . . 3 3. Symbols and Terms . . . . . . . . . . . . . . . . . . . . . . 3 3.1. Symbols . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2. Terms . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. General Introdoction to ECC . . . . . . . . . . . . . . . . . 5 5. Digital Signature Algorithm . . . . . . . . . . . . . . . . . 5 5.1. Digital Signature System . . . . . . . . . . . . . . . . . 5 5.1.1. General Rules . . . . . . . . . . . . . . . . . . . . 5 5.1.2. Parameters of Elliptic Curve System . . . . . . . . . 5 5.1.3. Key pairs . . . . . . . . . . . . . . . . . . . . . . 6 5.1.4. Auxilary Functions . . . . . . . . . . . . . . . . . . 6 5.2. Generation of Signature . . . . . . . . . . . . . . . . . 6 5.2.1. Digital Signature Generation Algorithm . . . . . . . . 6 5.2.2. Flow Chart of Digital Signature Generation . . . . . . 7 5.3. Verification of Signature . . . . . . . . . . . . . . . . 8 5.3.1. Digital Signagure Vefification Algorithm . . . . . . . 8 5.3.2. Flow Chart of Digital Signature Verification . . . . . 9 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.1. Normative References . . . . . . . . . . . . . . . . . . . 11 6.2. Informative References . . . . . . . . . . . . . . . . . . 11 Appendix A. Example . . . . . . . . . . . . . . . . . . . . . . . 11 A.1. General Introduction . . . . . . . . . . . . . . . . . . . 11 A.2. Digital Signature of over E(Fp) . . . . . . . . . . . . . 12 A.3. Digital Signature of over E(F2^m) . . . . . . . . . . . . 13 Shen & Lee Expires April 26, 2012 [Page 2] Internet-Draft SM2 Digital Signature Algorithm October 2011 1. Introduction This document is mainly the tranlation of the algorithm published by Chinese Commercial Cryptography Administration Office for the convenience of IETF and IRTF community. The credit of inventing this algorithm goes to the authors of the algorithm. 2. Conventions Used in this Document The key words "MUST", "MUST NOT", "SHOULD", "SHOULD NOT", and "MAY" in this document are to be interpreted as defined in "Key words for use in RFCs to Indicate Requirement Levels" [RFC2119]. 3. Symbols and Terms 3.1. Symbols a, b Elements in finite field Fq and they defines a Elliptic Curve E over Fq B The MOV threshold. This is a positive integer B such that taking discrete logarithms over GF (q^B) is judged to be at least as difficult as taking elliptic discrete logarithms over GF (q). deg(f) The degree of a polynomial f(x) E The elliptic curve defined by a and b over a finite field Fq E(Fq) The set of all the rational points of E #E(Fq) The number of elements in E(Fq), the degree of elliptic curve E(Fq) ECDLP Elliptic Curve Discrete Logarithm Problem Fp A prime field with p elements Fq A prime field with q elements F*q The multiplicative group composed of all non-zero elememnts in Fq F2^m The binary field extension with 2^m elements G A base point on the elliptic curve E, with prime order gcd(x;y) The greatest common devisor of x and y h The cofactor h= #E(Fp)/n, where n is the degree of a base point G LeftRotate( ) The operation of Rotation to left lmax The upper limit of the largest prime factor of the cofactor h m The extention degree of the field F2^m over the binary field F2 modf(x) The operation module the polynomial f(x). All the coefficients mod 2 when f(x) is a polynomial over F2. modn The operation of modulo n, for example, 23 mod7 = 2 n The degree of a base point G (n is a prime factor of #E(Fq) O The point of infinity (or zero) on the elliptic curre E. P A point P on the elliptic curre E which is not O. The coordinates xP and yP satisfies the elliptic curve equation P1+P2 The summation of the two points P1 and P2 on elliptic curve E Shen & Lee Expires April 26, 2012 [Page 3] Internet-Draft SM2 Digital Signature Algorithm October 2011 p A prime number greater than 3 q The number of elements in the finite field Fq rmin The lower limit of the degree n of a base point G Tr( ) The trace function xP The x-coordinate of the point P yP The y-coordinate of the point P x^(-1) The only y such that x*y=1 (modn), 1 < = y < = n, gcd(x, n)=1 x||y The concatenation of x and y, where x and y are bit string or byte string x == y (modn) x modn = y modn ** y~P The point compression expression of yP Zp The ring of integers modulo p < G > The cyclic group generated by base point G [k]P The k multiple of a point P over elliptic curve, where k is a positive integer [x;y] The set of integers which greater than or equal to x and less than or equal to y /x\ The smallest integer greater than or equal to x, for example GBP[not]/7\=7, /8.3\=9 \x/ The largest integer less than or equal to x, for example GBP[not]\7/=7, \8.3/=8 XOR The exclusive-or operation of two bit strings or byte strings of same length *********** A,B The two users using the public key system a, b Elements in finite field Fq and they defines a Elliptic Curve E over Fq dA The private key of the user A E(Fq) The set of all the rational points of E e The hash of message M e' The hash of message M' Fq A prime field with q elements G A base point on the elliptic curve E, with prime order Hv( ) The hash function with output of legnth v bits IDA The identifier of user A M The message for signature M!ae The message for verification modn The operation of modulo n, for example, 23 mod7 = 2 n The degree of base point G (n is a prime factor of #E(Fq)) O The point of infinity (or zero) on the elliptic curre E PA The public key of user A q The number of elements in the finite field Fq x||y The concatenation of x and y, where x and y are bit string or byte string ZA The identifier of user A, part of parameters of elliptic curve and hash value of PA (r,s) The sent signature (r',s') The received signature [k]P The k multiple of a point P over elliptic curve, where k is a positive integer [x;y] The set of integers which greater than or equal to x and less than or equal to y /x\ The smallest integer greater than or equal to x, for example GBP[not]/7\=7, /8.3\=9 \x/ The largest integer less than or equal to x, for example GBP[not]\7/=7, \8.3/=8 #E(Fq) The number of elements in E(Fq), the degree of elliptic curve E(Fq) ********** Shen & Lee Expires April 26, 2012 [Page 4] Internet-Draft SM2 Digital Signature Algorithm October 2011 3.2. Terms The following terms are used in this document. digital signature The metadata over some data. It should provide authentication, integrity protection and non repudiation. [ANSI X9.63-2001] message The bits string of arbitary length. [ISO/IEC 15946-4 3.7] signed message The data composed of a message and its digital signature. [ISO/IEC 15946-4 3.14] key A parameter for cryptographic calculation. It was used for encryption or decryption, shared sectet and verification of digital signature. [ANSI X9.63-2001] 4. General Introdoction to ECC TBD 5. Digital Signature Algorithm 5.1. Digital Signature System 5.1.1. General Rules In the digital signtature algorithm, one signer generate digital signature over given data and one verifier verifies the validation of the signature. Each signer ownes one public key and one private key. The private key was used for signing and verifier verfifies the signature using the public key. Before generation of the digital signature, the message M and ZA need to be compressed via a hash function; before the verification of the digital signature, the message M' and ZA need to be compressed via a hash function. 5.1.2. Parameters of Elliptic Curve System The parameters of an elliptic curve systme include the size q of a finite field Fq (when q=2^m, also include basis representation and irreducible polynomial); the two elements a and b (in Fq) which defines the elliptic curve equation; the base point G=(xG, yG) (G not Shen & Lee Expires April 26, 2012 [Page 5] Internet-Draft SM2 Digital Signature Algorithm October 2011 euqals O), where xG and yG are ellements in Fq; the degree n of G and other optional parameter such as cofactor h. 5.1.3. Key pairs The user A's key pair include his private key dA and public key PA=[dA]G=(xA, yA). 5.1.4. Auxilary Functions 5.1.4.1. Introduction The auxilary functions in the elliptic curve digital signature algorithm in this document include hash algorithm and random number generator. 5.1.4.2. Hash Functions The sm2 digital signature algorithm requires the hash functions approved by Chinese Commercial Cryptography Administration Office, such as sm3. 5.1.4.3. Random Number Generator The sm2 digital signature algorithm requires random number generators approved by by Chinese Commercial Cryptography Administration Office. 5.1.4.4. Other User Information As teh signer, User A has the identifier IDA of length entlenA bits, denote ENTLA as the two bytes transformed from the integer entlenA. In the digital signature algorithms in this document, both signer and verifier need to obtain ZA by calculating the hash value of ZA. ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) 5.2. Generation of Signature 5.2.1. Digital Signature Generation Algorithm Let M be the message for signing, in order to obtain the signature (r, s), the signer A need to perform the following: Shen & Lee Expires April 26, 2012 [Page 6] Internet-Draft SM2 Digital Signature Algorithm October 2011 A1: set M~=ZA || M A2: calculate e=Hv(M~) A3: pick a random number k in [1, n-1] via a random number generator A4: calculate the elliptic curve point (x1, y1)=[k]G A5: calculate r=(e+x1) modn, return to A3 if r=0 or r+k=n A6: calculate s=((1+dA)^(-1)*(k-r*dA)) modn, return to A3 if s=0 A7: the digital signature of M is (r, s) 5.2.2. Flow Chart of Digital Signature Generation +-------------------------------------------+ | the original data of user A | | (parameters of elliptic curve | | system, ZA, M, PA, dA) | | +-------------------------------------------+ | | v +-------------------------------------------+ | +------------------------+ | | | A1: set M~=ZA || M | | | +------------------------+ | | | | | v | | +------------------------+ | | | A2: calculate e=Hv(M~)| | | +------------------------+ | | | | | v | | +------------------------+ | | | A3: set M~=ZA || M | < ----+ | | +------------------------+ | | | | | | | v | | | +--------------------------+ | | | | A4: pick a random number | | | | | k in [1, n-1] | | | | +--------------------------+ | | | | | | | +--------------------------+ | | | | A5: calculate the point | | | | | (x1, y1)=[k]G | | | | +--------------------------+ | | | | | | | v | | Shen & Lee Expires April 26, 2012 [Page 7] Internet-Draft SM2 Digital Signature Algorithm October 2011 | /---------------------\ YES | | | | r=0 or r+k=n ? | ----->| | | \---------------------/ | | | | | | | | NO | | | v | | | +---------------------------------+ | | | | A6: calculate | | | | | s=((1+dA)^(-1)*(k-r*dA)) modn | | | | +---------------------------------+ | | | | | | | v | | | /---------------------\ YES | | | | r=0 ? | ------+ | | \---------------------/ | | | | | | NO | | v | | +----------------------------+ | | | A6: the digital signature | | | | of M is (r, s) | | | +----------------------------+ | +-------------------------------------------+ | | v +-------------------------------------------+ | Output the message M | | and its digital signature (r,s) | +-------------------------------------------+ Figure 1: Flow Chart of Digital Signature Generation 5.3. Verification of Signature 5.3.1. Digital Signagure Vefification Algorithm To verfify the received message M' and it's digital signature, the verifier need to perform the following: Shen & Lee Expires April 26, 2012 [Page 8] Internet-Draft SM2 Digital Signature Algorithm October 2011 B1: verify whether r' in [1,n-1], verification failed if not B2: vefify whether s' in [1,n-1], verification failed if not B3: set M'~=ZA || M' B4: calculate e'=Hv(M'~) B5: calculate t = (r' + s') modn, verification failed if t=0 B6: calculate the point (x1', y1')=[s']G + [t]PA B7: calculate R=(e'+x1') modn, verfication pass if yes, otherwise failed Note: The verification will certainly fail if ZA does not correspond to teh hash value of A. 5.3.2. Flow Chart of Digital Signature Verification +-------------------------------------------+ | the original data of user B | | (parameters of elliptic curve | | system, ZA, M', PA, (r', s')) | | +-------------------------------------------+ | | v +-------------------------------------------+ | +---------------------------+ | | | B1: verify r' in [1,n-1] | | | +---------------------------+ | | | | | v | | /---------------------\ NO | | | r' in [1,n-1] ? | ------+ | | \---------------------/ | | | | | | YES | | v | | +---------------------------+ | | | B2: verify s' in [1,n-1] | | | +---------------------------+ | | | | | v | | /---------------------\ NO | | | s' in [1,n-1] ? | ------+ | | \---------------------/ | | | | | | YES | | v | | +------------------------+ | Shen & Lee Expires April 26, 2012 [Page 9] Internet-Draft SM2 Digital Signature Algorithm October 2011 | | B3: set M'~=ZA || M' | < ----+ | | +------------------------+ | | | | | | | v | | | +--------------------------+ | | | | B4: calculate e'=Hv(M'~) | | | | +--------------------------+ | | | | | | | v | | | +--------------------------+ | | | | B5: calculate | | | | | t = (r' + s') modn | | | | +--------------------------+ | | | | | | | v | | | /---------------------\ YES | | | | t=0 ? | ----->| | | \---------------------/ | | | | | | | | NO | | | v | | | +---------------------------------+ | | | | B6: calculate | | | | | s=((1+dA)^(-1)*(k-r*dA)) modn | | | | +---------------------------------+ | | | | | | | v | | | /---------------------\ YES | | | | r=0 ? | ------+ | | \---------------------/ | | | | | | | | NO | | | v | | | +----------------------------+ | | | | B6: calculate | | | | | (x1', y1')=[s']G + [t]PA | | | | +----------------------------+ | | | | | | | v | | | +----------------------------+ | | | | B7: calculate | | | | | R=(e'+x1') modn | | | | +----------------------------+ | | | | | | | v | | | /---------------------\ NO | | | | R=r' ? | ------+ | | \---------------------/ | | Shen & Lee Expires April 26, 2012 [Page 10] Internet-Draft SM2 Digital Signature Algorithm October 2011 | | | | | | YES | | | | | | +-------------------------------------------+ | | v v +-------------------+ +-------------------+ | Verification Pass | | Verification Fail | +-------------------+ +-------------------+ Figure 2: Flow Chart of Digital Signature Verification 6. References 6.1. Normative References [RFC1341] Borenstein, N. and N. Freed, "MIME (Multipurpose Internet Mail Extensions): Mechanisms for Specifying and Describing the Format of Internet Message Bodies", RFC 1341, June 1992. 6.2. Informative References [RFC2049] Freed, N. and N. Borenstein, "Multipurpose Internet Mail Extensions (MIME) Part Five: Conformance Criteria and Examples", RFC 2049, November 1996. Appendix A. Example A.1. General Introduction This appendix uses the hash algorithm described in draft-shen-sm3-hash-00, which applies on a bit string of length less than 2^54 and output a hash value of size 256, denotes as H256( ). In this appendix, all the hexadecimal number has high digits on the left and low digits on teh right. In this appendix, all the messages are in ASCII code. Let the user A's identity be: ALICE123@YAHOO.COM. Denoted in ASCII code IDA: 414C 49434531 32334059 41484F4F 2E434F4 ENTLA=0090. Shen & Lee Expires April 26, 2012 [Page 11] Internet-Draft SM2 Digital Signature Algorithm October 2011 A.2. Digital Signature of over E(Fp) The elliptic curve equationi is: y^2 = x^3 + ax + b Example 1: Fp-256 A Prime p: 8542D69E 4C044F18 E8B92435 BF6FF7DE 45728391 5C45517D 722EDB8B 08F1DFC3 The coefficient a: 787968B4 FA32C3FD 2417842E 73BBFEFF 2F3C848B 6831D7E0 EC65228B 3937E498 The coefficient b: 63E4C6D3 B23B0C84 9CF84241 484BFE48 F61D59A5 B16BA06E 6E12D1DA 27C5249A The base point G=(xG,yG)GBP[not]whose degree is n: x-coordinate xG: 421DEBD6 1B62EAB6 746434EB C3CC315E 32220B3B ADD50BDC 4C4E6C14 7FEDD43D y-coordinate yG: 0680512B CBB42C07 D47349D2 153B70C4 E5D7FDFC BFA36EA1 A85841B9 E46E09A2 degree n: 8542D69E 4C044F18 E8B92435 BF6FF7DD 29772063 0485628D 5AE74EE7 C32E79B7 The message M to be signed:message digest The private key dA: 128B2FA8 BD433C6C 068C8D80 3DFF7979 2A519A55 171B1B65 0C23661D 15897263 The public key PA=(xA,yA): x-coordinate xA: 0AE4C779 8AA0F119 471BEE11 825BE462 02BB79E2 A5844495 E97C04FF 4DF2548A y-coordinate yA: 7C0240F8 8F1CD4E1 6352A73C 17B7F16F 07353E53 A176D684 A9FE0C6B B798E857 Hash value ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) ZA: F4A38489 E32B45B6 F876E3AC 2168CA39 2362DC8F 23459C1D 1146FC3D BFB7BC9A The intermediate value during signing processing: M~=ZA || M: F4A38489 E32B45B6 F876E3AC 2168CA39 2362DC8F 23459C1D 1146FC3D BFB7BC9A 6D657373 61676520 64696765 7374 hash value e=H256(M): B524F552 CD82B8B0 28476E00 5C377FB1 9A87E6FC 682D48BB 5D42E3D9 B9EFFE76 Shen & Lee Expires April 26, 2012 [Page 12] Internet-Draft SM2 Digital Signature Algorithm October 2011 random number k: 6CB28D99 385C175C 94F94E93 4817663F C176D925 DD72B727 260DBAAE 1FB2F96F point (x1,y1)=[k]G: x-coordinate x1: 110FCDA5 7615705D 5E7B9324 AC4B856D 23E6D918 8B2AE477 59514657 CE25D112 y-coordinate y1: 1C65D68A 4A08601D F24B431E 0CAB4EBE 084772B3 817E8581 1A8510B2 DF7ECA1A r=(e+x1) modn: 40F1EC59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 (1 + dA)^(-1) 79BFCF30 52C80DA7 B939E0C6 914A18CB B2D96D85 55256E83 122743A7 D4F5F956 s = ((1 + dA)^(-1)1 * (k - r * dA)) modn: 6FC6DAC3 2C5D5CF1 0C77DFB2 0F7C2EB6 67A45787 2FB09EC5 6327A67E C7DEEBE7 Digital Signature of the message M: (r,s) r: 40F1EC59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 s: 6FC6DAC3 2C5D5CF1 0C77DFB2 0F7C2EB6 67A45787 2FB09EC5 6327A67E C7DEEBE7 The intermediate value during verification processing: hash value e' = H256(M'~): B524F552 CD82B8B0 28476E00 5C377FB1 9A87E6FC 682D48BB 5D42E3D9 B9EFFE76 t=(r!ae+s!ae) modn: 2B75F07E D7ECE7CC C1C8986B 991F441A D324D6D6 19FE06DD 63ED32E0 C997C801 point (x0!ae, y0')=[s']G: x-coordinate x0': 7DEACE5F D121BC38 5A3C6317 249F413D 28C17291 A60DFD83 B835A453 92D22B0A y-coordinate y0': 2E49D5E5 279E5FA9 1E71FD8F 693A64A3 C4A94611 15A4FC9D 79F34EDC 8BDDEBD0 point (x00', y00')=[t]PA: x-coordinate x00': 1657FA75 BF2ADCDC 3C1F6CF0 5AB7B45E 04D3ACBE 8E4085CF A669CB25 64F17A9F y-coordinate y00': 19F0115F 21E16D2F 5C3A485F 8575A128 BBCDDF80 296A62F6 AC2EB842 DD058E50 point (x1', y1')=[s']G + [t]PA: x-coordinate x1': 110FCDA5 7615705D 5E7B9324 AC4B856D 23E6D918 8B2AE477 59514657 CE25D112 y-coordinate y1': 1C65D68A 4A08601D F24B431E 0CAB4EBE 084772B3 817E8581 1A8510B2 DF7ECA1A R = (e' + x1') modn: 40F1EC59 F793D9F4 9E09DCEF 49130D41 94F79FB1 EED2CAA5 5BACDB49 C4E755D1 A.3. Digital Signature of over E(F2^m) The elliptic curve equationi is: Shen & Lee Expires April 26, 2012 [Page 13] Internet-Draft SM2 Digital Signature Algorithm October 2011 y^2 + xy = x^3 + ax + b Example 1: F2^m -257 The polynomial to generate base field is: x^257 + x^12 + 1 The coefficient a: 0 The coefficient b: 00 E78BCD09 746C2023 78A7E72B 12BCE002 66B9627E CB0B5A25 367AD1AD 4CC6242B The base point G=(xG,yG)GBP[not]whose degree is n: x-coordinate xG: 00 CDB9CA7F 1E6B0441 F658343F 4B10297C 0EF9B649 1082400A 62E7A748 5735FADD y-coordinate yG: 01 3DE74DA6 5951C4D7 6DC89220 D5F7777A 611B1C38 BAE260B1 75951DC8 060C2B3E degree n: 7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF BC972CF7 E6B6F900 945B3C6A 0CF6161D The message M to be signed:message digest The private key dA: 771EF3DB FF5F1CDC 32B9C572 93047619 1998B2BF 7CB981D7 F5B39202 645F0931 The public key PA=(xA,yA): x-coordinate xA: 01 65961645 281A8626 607B917F 657D7E93 82F1EA5C D931F40F 6627F357 542653B2 y-coordinate yA: 01 68652213 0D590FB8 DE635D8F CA715CC6 BF3D05BE F3F75DA5 D5434544 48166612 Hash value ZA=H256(ENTLA || IDA || a || b || xG || yG || xA || yA) ZA: 26352AF8 2EC19F20 7BBC6F94 74E11E90 CE0F7DDA CE03B27F 801817E8 97A81FD5 The intermediate value during signing processing: M~=ZA || M: 26352AF8 2EC19F20 7BBC6F94 74E11E90 CE0F7DDA CE03B27F 801817E8 97A81FD5 6D657373 61676520 64696765 7374 hash value e=H256(M~): AD673CBD A3114171 29A9EAA5 F9AB1AA1 633AD477 18A84DFD 46C17C6F A0AA3B12 random number k: 36CD79FC 8E24B735 7A8A7B4A 46D454C3 97703D64 98158C60 5399B341 ADA186D6 point (x1,y1)=[k]G: x-coordinate x1: Shen & Lee Expires April 26, 2012 [Page 14] Internet-Draft SM2 Digital Signature Algorithm October 2011 00 3FD87D69 47A15F94 25B32EDD 39381ADF D5E71CD4 BB357E3C 6A6E0397 EEA7CD66 y-coordinate y1: 00 80771114 6D73951E 9EB373A6 58214054 B7B56D1D 50B4CD6E B32ED387 A65AA6A2 r=(e+x1) modn: 6D3FBA26 EAB2A105 4F5D1983 32E33581 7C8AC453 ED26D339 1CD4439D 825BF25B (1 + dA)^(-1) 73AF2954 F951A9DF F5B4C8F7 119DAA1C 230C9BAD E60568D0 5BC3F432 1E1F4260 s = ((1 + dA)^(-1)1 * (k - r * dA)) modn: 3124C568 8D95F0A1 0252A9BE D033BEC8 4439DA38 4621B6D6 FAD77F94 B74A9556 Digital Signature of the message M: (r,s) r: 6D3FBA26 EAB2A105 4F5D1983 32E33581 7C8AC453 ED26D339 1CD4439D 825BF25B s: 3124C568 8D95F0A1 0252A9BE D033BEC8 4439DA38 4621B6D6 FAD77F94 B74A9556 The intermediate value during verification processing: hash value e' = H256(M'~): AD673CBD A3114171 29A9EAA5 F9AB1AA1 633AD477 18A84DFD 46C17C6F A0AA3B12 t=(r!ae+s!ae) modn: 1E647F8F 784891A6 51AFC342 0316F44A 042D7194 4C91910F 835086C8 2CB07194 point (x0!ae, y0')=[s']G: x-coordinate x0': 00 252CF6B6 3A044FCE 553EAA77 3E1E9264 44E0DAA1 0E4B8873 89D11552 EA6418F7 y-coordinate y0': 00 776F3C5D B3A0D312 9EAE44E0 21C28667 92E4264B E1BEEBCA 3B8159DC A382653A point (x00', y00')=[t]PA: x-coordinate x00': 00 07DA3F04 0EFB9C28 1BE107EC C389F56F E76A680B B5FDEE1D D554DC11 EB477C88 y-coordinate y00': 01 7BA2845D C65945C3 D48926C7 0C953A1A F29CE2E1 9A7EEE6B E0269FB4 803CA68B point (x1', y1')=[s']G + [t]PA: x-coordinate x1': 00 3FD87D69 47A15F94 25B32EDD 39381ADF D5E71CD4 BB357E3C 6A6E0397 EEA7CD66 y-coordinate y1': 00 80771114 6D73951E 9EB373A6 58214054 B7B56D1D 50B4CD6E B32ED387 A65AA6A2 R = (e' + x1') modn: 6D3FBA26 EAB2A105 4F5D1983 32E33581 7C8AC453 ED26D339 1CD4439D 825BF25B Shen & Lee Expires April 26, 2012 [Page 15] Internet-Draft SM2 Digital Signature Algorithm October 2011 Authors' Addresses Sean Shen (editor) Chinese Academy of Science No.4 South 4th Zhongguancun Street Beijing, 100190 China Phone: +86 10-58813038 EMail: shenshuo@cnnic.cn Xiaodong Lee (editor) Chinese Academy of Science No.4 South 4th Zhongguancun Street Beijing, 100190 China Phone: +86 10-58813038 EMail: shenshuo@cnnic.cn Shen & Lee Expires April 26, 2012 [Page 16]