idnits 2.17.1 draft-irtf-cfrg-zss-02.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 10, 2013) is 3789 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: Informational ---------------------------------------------------------------------------- == Missing Reference: 'RFC6808' is mentioned on line 961, but not defined == Missing Reference: 'RFC6809' is mentioned on line 961, but not defined ** Obsolete normative reference: RFC 4492 (Obsoleted by RFC 8422) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT L. Hitt 3 Intended Status: Informational 21CT, Inc. 4 Expires: June 13, 2014 December 10, 2013 6 ZSS Short Signature Scheme for Supersingular and BN Curves 7 draft-irtf-cfrg-zss-02 9 Abstract 11 This document describes the ZSS Short Signature Scheme for 12 implementation from bilinear pairings on supersingular elliptic 13 curves and Barreto-Naerhig (BN) ordinary elliptic curves. The ZSS 14 Short Signature Scheme uses general cryptographic hash functions such 15 as SHA-1 or SHA-2 and is efficient in terms of pairing operations. 17 Status of this Memo 19 This Internet-Draft is submitted to IETF in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF), its areas, and its working groups. Note that 24 other groups may also distribute working documents as 25 Internet-Drafts. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 The list of current Internet-Drafts can be accessed at 33 http://www.ietf.org/1id-abstracts.html 35 The list of Internet-Draft Shadow Directories can be accessed at 36 http://www.ietf.org/shadow.html 38 Copyright and License Notice 40 Copyright (c) 2013 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 56 1.1 Bilinear Pairings . . . . . . . . . . . . . . . . . . . . . 4 57 1.2 Discrete Logarithm Problem and Diffie-Hellman Problems . . . 4 58 1.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 5 59 2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 5 60 3 Notation, Definitions and Parameters . . . . . . . . . . . . . . 6 61 3.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 6 62 3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 8 63 3.3 Representations . . . . . . . . . . . . . . . . . . . . . . 8 64 3.4 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 9 65 4 The ZSS Cryptosystem . . . . . . . . . . . . . . . . . . . . . 10 66 4.1 Parameter Generation . . . . . . . . . . . . . . . . . . . . 10 67 4.2 Key Generation . . . . . . . . . . . . . . . . . . . . . . . 10 68 4.3 Signature Generation . . . . . . . . . . . . . . . . . . . . 11 69 4.4 Signature Verification . . . . . . . . . . . . . . . . . . . 11 70 5 Security Considerations . . . . . . . . . . . . . . . . . . . . 11 71 6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 13 72 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 73 7.1 Normative References . . . . . . . . . . . . . . . . . . . . 13 74 7.2 Informative References . . . . . . . . . . . . . . . . . . . 14 75 Appendix A. Supersingular Elliptic Curves, Pairings and 76 Supporting Algorithms . . . . . . . . . . . . . . . . . . 16 77 A.1 Supersingular Elliptic Curves . . . . . . . . . . . . . . . 16 78 A.2. E(F_p^2) and the Distortion Map for Supersingular Curves . 16 79 A.3. The Tate-Lichtenbaum Pairings for Supersingular Curves . . 16 80 A.4. Hashing to an Integer Range . . . . . . . . . . . . . . . . 18 81 Appendix B. BN Elliptic Curves, Pairings and Supporting 82 Algorithms . . . . . . . . . . . . . . . . . . . . . . . 19 83 B.1. BN Elliptic Curves . . . . . . . . . . . . . . . . . . . . 19 84 B.2. Sextic Twists of BN Curves . . . . . . . . . . . . . . . . 19 85 B.3. The Ate Pairing for BN Curves . . . . . . . . . . . . . . . 19 86 Appendix C. Example Data . . . . . . . . . . . . . . . . . . . . . 21 87 C.1 Example 1 (Supersingular) . . . . . . . . . . . . . . . . . 22 88 C.2 Example 2 (BN) . . . . . . . . . . . . . . . . . . . . . . . 24 89 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 26 91 1 Introduction 93 This document describes the ZSS Short Signature Scheme (designed by 94 Zhang, Safavi-Naini, and Susilo) for implementation from bilinear 95 pairings [ZSS]. It does not require any special hash function such 96 as MapToPoint [B-F], which is still probabilistic and generally 97 inefficient, but rather can use cryptographic hash functions such as 98 SHA-1 or SHA-2. 100 This document is restricted to implementation of ZSS on a particular 101 family of supersingular elliptic curves and a particular family of 102 Barreto-Naerhig (BN) elliptic curves, though the scheme is valid on 103 other elliptic curve groups. The supersingular family offers 104 efficiency and simplicity advantages when computing the pairing, 105 which is the most time consuming procedure in pairing-based 106 cryptography. These advantages are important since short signatures 107 are needed in low-bandwidth communication environments. 109 BN curves are a family of non-supersingular (i.e., ordinary) curves 110 that are attractive for pairing-based cryptography for a variety of 111 other reasons. These curves are plentiful and easily found and they 112 support a sextic twist, which allows pairing arguments to be defined 113 over relatively small finite fields. BN curves are amenable to 114 twofold or threefold pairing compression and attain high efficiency 115 for all pairing computation algorithms known (e.g., Tate, ate, eil, 116 R-ate, Xate). These curves are also suitable for software and 117 hardware implementations on a wide range of platforms. 119 The specific subclass of BN curves that we choose for this document 120 is discussed in [Pereira], and offers many additional efficiency 121 advantages. The subclass automatically yields the right sextic twist 122 (thus entirely avoiding curve arithmetic for that purpose) and 123 provides simple and obvious generators for the curve and its twist 124 (removing the need for extra processing and storage). It allows for 125 pairing efficiency, uniform finite field arithmetic, choice of 126 suitable field sizes, and enables virtually all optimizations 127 currently proposed in the literature for involved algebraic 128 structures. 130 The scheme is constructed from the Inverse Computational Diffie- 131 Hellman Problem (Inv-CDHP) on bilinear pairings (see Section 1.2 132 below for a discussion of Inv-CDHP). The security of the scheme is 133 based on the assumed hardness of this problem (which is widely 134 accepted), which means there is no polynomial time algorithm to solve 135 it with non-negligible probability. Bilinear pairings have been used 136 to construct Identity (ID)-Based cryptosystems [B-F], so that the 137 identity information of a user functions as his public key. The 138 signing process in a short signature scheme can be regarded as the 139 private key extract process in the ID-based public key setting from 140 bilinear pairings. Therefore, the ZSS signature scheme can be 141 regarded as being derived from Sakai-Kasahara's ID-based encryption 142 scheme with pairing [S-K, RFC6508]. 144 The algorithm is for use in the following context: 146 * where there are two parties, a Signer and a Verifier; 148 * where a message is to be signed and then verified (e.g., for 149 authenticating the initiating party during key establishment); 151 * where a Certificate Authority (CA) or Trusted Third Party (TTP) 152 within a traditional Public Key Infrastructure (PKI) provides a 153 root of trust for both parties. 155 1.1 Bilinear Pairings 157 Let G_1 and G_2 be cyclic additive groups generated by P and P', 158 respectively, both of whose order is a prime q. Let G_3 be a 159 cyclic multiplicative group with the same order q. Let Z_q be the 160 additive group of integers modulo q. 162 Let <,>: G_1 X G_2 --> G_3 be a map with the following properties. 164 1. Bilinearity: =^(ab) for all P, Q elements of G_1 165 and G_2, respectively, and a, b elements of Z_q. 167 2. Non-degeneracy: There exists P, Q elements of G_1 and G_2, 168 respectively, such that != 1. In other words, the map does 169 not send all pairs in G_1 X G_2 to the identity in G_3. 171 3. Computability: There is an efficient algorithm to compute 172 for all P in G_1 and Q in G_2. 174 In our setting of prime order groups, non-degeneracy is equivalent to 175 != 1 for all nontrivial P, Q elements in G_1 and G_2, 176 respectively. So, when P is a generator of G_1 and Q is a generator 177 of G_2, then is a generator of G_3. Such a bilinear map is 178 called a bilinear pairing. In the case of supersingular elliptic 179 curves, we let G_1 = G_2, P = P', so is a generator of G_3. 181 1.2 Discrete Logarithm Problem and Diffie-Hellman Problems 183 We consider the following problems in the additive group (G_1;+). 185 Discrete Logarithm Problem (DLP): Given two group elements P and 186 Q, find an integer n in (Z_q)*, such that Q=nP whenever such an 187 integer exists. 189 Decision Diffie-Hellman Problem (DDHP): For a,b,c in (Z_q)*, given 190 P, aP, bP, cP decide whether c is congruent to ab mod q. 192 Computational Diffie-Hellman Problem (CDHP): For a,b in (Z_q)*, 193 given P, aP, bP, compute abP. 195 Inverse Computational Diffie-Hellman Problem (Inv-CDHP): For a in 196 (Z_q)*, given P, aP, compute [a^(-1)]P. 198 Square Computational Diffie-Hellman Problem (Squ-CDHP): For a in 199 (Z_q)*, given P, aP, compute [a^2]P. 201 Bilinear Diffie-Hellman problem (BDHP): Given (P, aP, bP, cP) for 202 some a,b,c in (Z_q)*, compute v in G_3 such that v = ^(abc). 204 The CDHP, Inv-CDHP, and Squ-CDHP are polynomial time equivalent. The 205 DLP, CDHP, Inv-CDHP, Squ-CDHP, and BDHP are assumed to be hard, which 206 means there is no polynomial time algorithm to solve any of them with 207 non-negligible probability. Therefore, the security of pairing based 208 cryptosystems are typically based on these problems. A Gap Diffie- 209 Hellman (GDH) group is a group in which the DDHP can be efficiently 210 solved but the CDHP is intractable. The bilinear pairing gives us 211 such a group, found on elliptic curves or hyperelliptic curves over 212 finite fields. The bilinear pairings can be derived from the Weil or 213 Tate pairing, as in [B-F, Cha-Cheon, Hess]. The ZSS scheme works on 214 any GDH group, but in this document we focus on particular families 215 of elliptic curves, which are described in Section 3.4 and the 216 pairing described in Appendix A.2. 218 1.3 Terminology 220 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 221 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 222 document are to be interpreted as described in RFC 2119 [RFC2119]. 224 2 Architecture 226 We consider the situation where one entity (the Signer) wishes to 227 sign a message that it is sending to another entity (the Verifier). 229 As in a traditional Public Key Infrastructure (PKI), a Certificate 230 Authority (CA) or Trusted Third Party (TTP) provides assurance of a 231 signer's identity, which is bound to the signer's public key. The CA 232 may generate a public key and private key (a key pair) or the signer 233 may generate their own key pair and register the Signer Public Key 234 (SPK) with a CA. 236 The mechanism by which a secret key is transported MUST be secure, as 237 the security of the authentication provided by ZSS signatures is no 238 stronger than the security of this supply channel. The choice of 239 secret key transport mechanism is outside the scope of this document. 241 During the signing process, once the Signer has formed its message, 242 it signs the message using its Signer Secret Key (SSK). It transmits 243 the Signature with the message. The Verifier MUST then use the 244 message, Signature, and SPK in verification. 246 This document specifies 248 * an algorithm for creating a Signature from a message, using an 249 SSK; 251 * an algorithm for verifying a Signature for a message, using an 252 SPK. 254 This document does not specify (but comments on) 256 * how to choose a valid and secure elliptic curve; 258 * which hash function to use. 260 3 Notation, Definitions and Parameters 262 3.1 Notation 264 n A security parameter; n should be at most half the bit size of 265 q. 267 p A prime, of size at least 2n bits, which is the order of the 268 finite field F_p. In this document, p is always congruent to 3 269 modulo 4. 271 F_p The finite field of order p (i.e., field with p elements). 273 F* The multiplicative group of the non-zero elements in the field 274 F; e.g., (F_p)* is the multiplicative group of the finite field 275 F_p. 277 q An odd prime. In the case of supersingular curves, q divides 278 p+1 and is the order of a subgroup of E(F_p). For BN curves, q 279 is the order of E(F_p). To provide the desired level of 280 security, lg(q) MUST be greater than 2*n. 282 E An elliptic curve defined over F_p. In this document, for the 283 case of supersingular curves, E(F_p) has a subgroup of prime 284 order q, and for the case of BN curves, E(F_p) has prime order 285 q. In this document, we use supersingular curves with equation 286 y^2 = x^3 - 3 * x modulo p and BN elliptic curves with equation 287 y^2 = x^3 + 2 modulo p. 289 E' A sextic twist of the elliptic curve E. For the family of BN 290 curves in this document, E':y^2 = x^3 + (1-i) over F_p^12, and 291 the order of E' over F_{p^2} is q(2p-q). 293 E(F) The additive group of points of affine coordinates (x,y) with 294 x, y in the field F, that satisfy the curve equation for E. 296 P A point of E(F_p) that generates the cyclic (sub)group of order 297 q. In the case of supersingular curves, P generates a subgroup 298 of order q and in the case of BN curves, P is a generator of 299 the full group E(F_p) and has order q. 301 P' A point of E'(F_p^2) that generates the cyclic subgroup of 302 order q. 304 0 The null element of any additive group of points on an elliptic 305 curve, also called the point at infinity. 307 F_p^2 The extension field of degree 2 of the field F_p. In this 308 document, we use a particular instantiation of this field; 309 F_p^2 = F_p[i], where i^2 + 1 = 0. It is for this reason that 310 we choose p congruent to 3 modulo 4. 312 PF_p The projectivization of F_p. We define this to be 313 (F_p^2)*/(F_p)*. Note that PF_p is cyclic and has order p + 1, 314 which is divisible by q. 316 G[q] The q-torsion of a group G. This is the subgroup generated by 317 points of order q in G. 319 < , > A bilinear pairing. We use < , > to represent a version of the 320 Tate-Lichtenbaum pairing for supersingular curves and the ate 321 pairing for BN curves. In this document, the Tate-Lichtenbaum 322 pairing is a bilinear map from E(F_p)[q] x E(F_p)[q] onto the 323 subgroup of order q in PF_p, and the ate pairing is a bilinear 324 map from E'(F_p^2)[q] X E(F_p)[q] onto the subgroup of order q 325 in (F_p^12)*. A full definition for each of these is given in 326 Appendix A.3 and Appendix B.3. 328 g g = . In the supersingular case, P = P', so we have g = 329 . Having this pre-computed value allows the Verifier to 330 only perform one pairing operation to verify a signature. 332 H A cryptographic hash function. [FIPS180-3] contains NIST 333 approved hash functions. 335 lg(x) The base 2 logarithm of the real value x. 337 3.2 Definitions 339 Certificate Authority (CA) - The Certificate Authority is a trusted 340 third party who provides assurance that the SPK 341 belongs to the signer and verified proof of the 342 signer's identity when the signer registered the 343 SPK. 345 Public parameters - The public parameters are a set of parameters 346 that are held by all users of the system. Each 347 application of ZSS MUST define the set of public 348 parameters to be used. The parameters needed are n, 349 p, q, E, P, P', < , >, g, and H. In the 350 supersingular case, P' = P. 352 Signer Public Key (SPK) - The Signer's Public key is used to verify 353 the signature of the entity whose SSK corresponds to 354 the SPK. It is a point on the elliptic curve E. 356 Signer Secret Key (SSK) - The Signer's Secret Key is used to generate 357 a signature and must not be revealed to any entity 358 other than the trusted third party and the 359 authorized signer. It is a value between 2 and q-1. 361 3.3 Representations 363 This section provides canonical representations of values that MUST 364 be used to ensure interoperability of implementations. The following 365 representations MUST be used for input into hash functions and for 366 transmission. In this document, concatenation of octet strings s and 367 t is denoted s || t. 369 Integers Integers MUST be represented as an octet string, 370 with bit length a multiple of 8. To achieve this, 371 the integer is represented most significant bit 372 first, and padded with zero bits on the left until 373 an octet string of the necessary length is obtained. 374 This is the octet string representation described in 375 Section 6 of [RFC6090]. 377 F_p elements Elements of F_p MUST be represented as integers in 378 the range 0 to p-1 using the octet string 379 representation defined above. Such octet strings 380 MUST have length L = Ceiling(lg(p)/8). 382 F_p^2 elements The elements of F_p^2 = F_p[i] are represented as 383 x_1 + i * x_2, where x_1 and x_2 are elements of 384 F_p. It is for this reason that we choose p 385 congruent to 3 modulo 4. 387 PF_p elements Elements of PF_p are cosets of (F_p)* in (F_p^2)*. 388 Every element of F_p^2 can be written unambiguously 389 in the form x_1 + i * x_2, where x_1 and x_2 are 390 elements of F_p. Thus, elements of PF_p (except the 391 unique element of order 2) can be represented 392 unambiguously by x_2/x_1 in F_p. Since q is odd, 393 every element of PF_p[q] can be represented by an 394 element of F_p in this manner. 396 Elements of PF_p MUST be represented as an element 397 of F_p using the algorithm in Appendix A.2. They 398 are therefore represented as octet strings as 399 defined above and are L octets in length. 400 Representation of the unique element of order 2 in 401 PF_p will not be required. 403 This representation of elements in PF_p[q] allows 404 efficient implementation of PF_p[q] group 405 operations, as these can be defined using arithmetic 406 in F_p. If a and b are elements of F_p representing 407 elements A and B of PF_p[q], respectively, then A * 408 B in PF_p[q] is represented by (a + b)/(1 - a * b) 409 in F_p. 411 Points on E, E' Elliptic curve points MUST be represented in 412 uncompressed form as defined in Section 2.2 of 413 [RFC5480]. For an elliptic curve point (x,y) with x 414 and y in F_p, this representation is given by 0x04 415 || x' || y', where x' is the octet string 416 representing x, y' is the octet string representing 417 y, and || denotes concatenation. The representation 418 is 2*L+1 octets in length. 420 3.4 Arithmetic 422 ZSS relies on elliptic curve arithmetic. The coordinates of a point 423 P on the elliptic curve are given by P = (P_x,P_y), where Px and Py 424 are the affine coordinates in F_p satisfying the curve equation. 426 The following conventions are assumed for curve operations: 428 Point addition - If P and Q are two points on a curve E, their sum is 429 denoted as P + Q. 431 Scalar multiplication - If P is a point on a curve, and k an integer, 432 the result of adding P to itself a total of k times 433 is denoted [k]P. 435 In this document, we use either supersingular curves with equation 436 y^2 = x^3 - 3 * x modulo p, or BN curves with equation y^2 = x^3 + 2 437 modulo p. These curves are chosen because of the efficiency and 438 simplicity advantages they offer. The choice of -3 for the 439 coefficient of x in the supersingular curve provides advantages for 440 elliptic curve arithmetic that are explained in [P1363]. Barreto's 441 trick [Barreto] of eliminating the computation of the denominators 442 when calculating the pairing also applies to these supersingular 443 curves. Advantages for the BN curves are discussed in Section 1 and 444 in [Pereira]. For example, one advantage is an easy determination of 445 a generator P of E(F_p), namely P = (-1,1). 447 4 The ZSS Cryptosystem 449 This section describes the ZSS short signature scheme [ZSS]. 451 4.1 Parameter Generation 453 The following static parameters are fixed for each implementation. 454 They are not intended to change frequently, and MUST be specified for 455 each user community. 457 The system parameters to be generated for a given security parameter 458 n are {p, q, E, P, P', <,>, g, H}. These are known by the Sender and 459 the Verifier. In the supersingular case, P' = P. 461 4.2 Key Generation 463 To create signatures, each Signer requires an SSK and SPK. The SSK 464 is an integer, and the SPK is an elliptic curve point. The SSK MUST 465 be kept secret (to the Signer and possibly the CA), but the SPK need 466 not be kept secret. 468 The Signer (or CA) MUST randomly select a value in the range 2 to q- 469 1, and assigns this value to x, which is the SSK. 471 The Signer MUST derive its SPK, X, by performing the calculation X 472 =[x]P. 474 If the signer generated the SPK, then it must be registered with a 475 CA. 477 4.3 Signature Generation 479 Given the SSK x, and a message m, the Signer computes the signature S 480 by performing the following steps: 482 1) Compute the hash of the message as a mod q value using the hash 483 algorithm specified in the public parameters. 485 2) Compute (H(m)+x)^-1, where the inversion is performed modulo q. 487 3) Compute S = [(H(m)+x)^-1]P'. (Recall that in the supersingular 488 case, P' = P.) The signature is S, and this is a point on the 489 curve E in the supersingular case, and E' in the BN case. 491 The Signer sends m and S. 493 4.4 Signature Verification 495 Given the SPK X, a message m, and a signature S, the Receiver 496 verifies that <[H(m)]P + X, S> = g, to ensure that the Signer is 497 authentic and the message was not altered in transit. This is 498 achieved by the Verifier performing the following steps: 500 1) Check that S is a point on the curve E in the supersingular 501 case and E' in the BN case, otherwise reject the signature. 503 2) Compute the hash of the message as a mod q value using the hash 504 algorithm specified in the public parameters. 506 3) Compute the elliptic curve point [H(m)]P + X. 508 4) Compute the pairing <[H(m)]P + X, S>. 510 5) Verify that <[H(m)]P + X, S> = g; if not, reject the signature. 512 5 Security Considerations 514 This document describes the ZSS Short Signature Scheme. We assume 515 that the security provided by this algorithm depends entirely on the 516 secrecy of the secret keys it uses, and that for an adversary to 517 defeat this security, he will need to perform computationally 518 intensive cryptanalytic attacks to recover a secret key. Note that a 519 security proof exists for ZSS in the Random Oracle Model [ZSS]. 520 Security rests on the (k+1)-Exponent Problem, which is to compute 521 y^(k+1)P when given k+1 values . There are 522 certain cases when the Cheon attack [Cheon] can be applied to this 523 problem, though still at exponential cost, and choosing p such that 524 both of p+1 and p-1 have no small divisor greater than (log p)^2 can 525 prevent the possibility of this attack. 527 When defining public parameters, guidance on parameter sizes from 528 [RFC4492] SHOULD be followed. For lower security levels (e.g., less 529 than 128 bit security), the parameter sizes must be determined based 530 on the elliptic curve discrete logarithm problem over F_p, and for 531 the higher security levels the parameter sizes are based on the 532 finite field size (e.g., 2*lg(p) for the supersingular curve family, 533 12*lg(p) for the BN curve family). 535 Table 1 and Table 2 show bits of security afforded by various sizes 536 of p for the case of supersingular curves and BN curves, 537 respectively. 539 Security (bits) | EC size (lg(p) | finite field size (2*lg(p)) 540 --------------------------------------------------------------- 541 80 | 512 | 1024 542 112 | 1024 | 2048 543 128 | 1536 | 3072 544 192 | 3840 | 7680 545 256 | 7680 | 15360 547 Table 1: For supersingular curves, comparable strengths, taken from 548 [RFC4492] 550 Security (bits) | EC size (lg(p) | finite field size (12*lg(p)) 551 --------------------------------------------------------------- 552 80 | 160 | 1920 553 112 | 224 | 2688 554 128 | 256 | 3072 555 192 | 640 | 7680 556 256 | 1280 | 15360 558 Table 2: For BN curves, comparable strengths, taken from [RFC4492] 560 The order of the base point P used in ZSS (and hence the order of 561 E(F_p) for BN curves), MUST be a large prime q. If n bits of security 562 are needed, then lg(q) SHOULD be chosen to be at least 2*n. 563 Similarly, if n bits of security are needed, then a hash with output 564 size at least 2*n SHOULD be chosen. 566 Randomizing the messages that are signed is a way to enhance the 567 security of the cryptographic hash function. [SP800-106] provides a 568 technique to randomize messages that are input to a cryptographic 569 hash function during the signature generation step. The intent of 570 this method is to strengthen the collision resistance provided by the 571 hash functions without any changes to the core hash functions and 572 signature algorithms. If the message is randomized with a different 573 random value each time it is signed, it will result in the message 574 having a different digital signature each time. 576 Each user's SSK protects the ZSS communications it receives. This 577 key MUST NOT be revealed to any entity other than the authorized user 578 and possibly the CA (if the CA generated the key pair). 580 In order to ensure that the SSK is received only by an authorized 581 entity, it MUST be transported through a secure channel. The 582 security offered by this signature scheme is no greater than the 583 security provided by this delivery channel. 585 The randomness of values stipulated to be selected at random, as 586 described in this document, is essential to the security provided by 587 ZSS. If the value of x used by a user is predictable, then the value 588 of his SSK could be recovered. This would allow that user's 589 signatures to be forged. Guidance on the generation of random values 590 for security can be found in [RFC4086]. 592 6 IANA Considerations 594 This memo includes no request to IANA. 596 7 References 598 7.1 Normative References 600 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 601 Requirement Levels", BCP 14, RFC 2119, March 1997. 603 [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and 604 B. Moeller, "Elliptic Curve Cryptography (ECC) Cipher 605 Suites for Transport Layer Security (TLS)", RFC 4492, May 606 2006. 608 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 609 "Elliptic Curve Cryptography Subject Public Key 610 Information", RFC 5480, March 2009. 612 [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental 613 Elliptic Curve Cryptography Algorithms", RFC 6090, 614 February 2011. 616 [ZSS] Zhang, F., Safavi-Naini, R., and Susilo, W., "An 617 Efficient Signature Scheme from Bilinear Pairings and Its 618 Applications", PKC 2004, LNCS 2947, Springer-Verlag 619 (2004), pp. 277-290. 621 7.2 Informative References 623 [Barreto] Barreto, P., Kim, H., Lynn, B., and Scott, M., "Efficient 624 Algorithms for Pairing-Based Cryptosystems", Advances in 625 Cryptology - Crypto 2002, LNCS 2442, Springer-Verlag 626 (2002), pp. 354-369. 628 [B-F] Boneh, D., Franklin, M., "Identity-based encryption from 629 the Weil pairing", Advances in Cryptology - Crypto 2001, 630 LNCS 2139, Springer-Verlag (2001), pp. 213-229. 632 [Cha-Cheon] Cha, J.C., Cheon, J.H., "An identity-based signature from 633 gap Diffie-Hellman groups", Public Key Cryptography - PKC 634 2003, LNCS 2139, Springer-Verlag (2003), pp. 18-3. 636 [Cheon] Cheon, J.H., "Discrete Logarithm Problems with Auxiliary 637 Inputs", J. Cryptology 23 (2010), pp. 457-476. 639 [Devegili] Devegili, A.J., Scott, M., Dahab, R., "Implementing 640 Cryptographic Pairings over Barreto-Naehrig Curves", 641 Pairing 2007, pp. 197-207. 643 [FIPS180-3] Federal Information Processing Standards Publication 644 (FIPS PUB) 180-3, "Secure Hash Standard (SHS)", October 645 2008. 647 [Hess] Hess, F., "Efficient identity based signature schemes 648 based on pairings", SAC 2002, LNCS 2595, Springer-Verlag 649 (2002), pp. 310-324. 651 [Miller] Miller, V., "The Weil pairing, and its efficient 652 calculation", J. Cryptology 17 (2004), pp. 235-261. 654 [P1363] IEEE P1363-2000, "Standard Specifications for Public-Key 655 Cryptography", 2001. 657 [Pereira] Pereira, G. C., et al. "A Family of Implementation- 658 Friendly BN Elliptic Curves", J. Systems and Software, 659 Volume 84, Issue 8, Elsevier (2011), pp. 1319-1326. 661 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 662 "Randomness Requirements for Security", BCP 106, 663 RFC 4086, June 2005. 665 [RFC6508] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)", 666 RFC 6508, February 2012. 668 [S-K] Sakai, R., Ohgishi, K., and M. Kasahara, "ID based 669 cryptosystem based on pairing on elliptic curves", 670 Symposium on Cryptography and Information Security - 671 SCIS, 2001. 673 [SP800-106] Dang, Q., "Randomized Hashing for Digital Signatures", 674 NIST Special Publication 800-106, February 2009. 676 Appendix A. Supersingular Elliptic Curves, Pairings and Supporting 677 Algorithms 679 A.1 Supersingular Elliptic Curves 680 When E is a supersingular elliptic curve (of j-invariant 1728), we 681 consider the family such that E: y^2 = x^3 - 3 * x modulo p. E(F_p) 682 contains a cyclic subgroup of order q, denoted E(F_p)[q], whereas the 683 larger object E(F_p^2) contains the direct product of two cyclic 684 subgroups of order q, denoted E(F_p^2)[q]. 686 P is a generator of E(F_p)[q]. It is specified by the (affine) 687 coordinates (P_x,P_y) in F_p, satisfying the curve equation. 689 Routines for point addition and doubling on E(F_p) can be found in 690 Appendix A.10 of [P1363]. 692 A.2. E(F_p^2) and the Distortion Map for Supersingular Curves 694 If (Q_x,Q_y) are (affine) coordinates in F_p for some point (denoted 695 Q) in E(F_p)[q], then (-Q_x,iQ_y) are (affine) coordinates in F_p^2 696 for some point in E(F_p^2)[q]. This latter point is denoted [i]Q, by 697 analogy with the definition for scalar multiplication. The two 698 points P and [i]P together generate E(F_p^2)[q]. The map [i]: 699 E(F_p)-> E(F_p^2) is sometimes termed the distortion map. This map is 700 used to ensure the pairing is applied to independent points so that 701 the pairing is not equal to 1. 703 A.3. The Tate-Lichtenbaum Pairings for Supersingular Curves 705 As in [RFC6508], we describe the pairing < , > to be used in ZSS for 706 supersingular elliptic curves. We will need to evaluate polynomials 707 f_R that depend on points on E(F_p)[q]. Miller's algorithm [Miller] 708 provides a method for evaluation of f_R(X), where X is some element 709 of E(F_p^2)[q] and R is some element of E(F_p)[q] and f_R is some 710 polynomial over F_p whose divisor is (q)(R) - (q)(0). Note that f_R 711 is defined only up to scalars of F_p. 713 The version of the Tate-Lichtenbaum pairing used in this document is 714 given by = f_R([i]Q)^c / (F_p)*. It satisfies the bilinear 715 relation <[x]R,Q> = = ^x for all Q, R in E(F_p)[q], for 716 all integers x. Note that the domain of definition is restricted to 717 E(F_p)[q] x E(F_p)[q] so that certain optimizations are natural. 719 We provide pseudocode for computing with elliptic curve 720 arithmetic expressed in affine coordinates. We make use of Barreto's 721 trick [Barreto] for avoiding the calculation of denominators. Note 722 that this section does not fully describe the most efficient way of 723 computing the pairing; it is possible to compute the pairing without 724 any explicit reference to the extension field F_p^2. This reduces 725 the number and complexity of the operations needed to compute the 726 pairing. 728 730 /* Copyright (c) 2012 IETF Trust and the persons identified as 731 authors of the code. All rights reserved. 733 Redistribution and use in source and binary forms, with or without 734 modification, is permitted pursuant to, and subject to the license 735 terms contained in, the Simplified BSD License set forth in Section 736 4.c of the IETF Trust's Legal Provisions Relating to IETF Documents 737 (http://trustee.ietf.org/license-info). */ 739 Routine for computing the pairing : 741 Input R, Q points on E(F_p)[q]; 743 Initialize variables: 744 v = (F_p)*; // An element of PF_p[q] 745 C = R; // An element of E(F_p)[q] 746 c = (p+1)/q; // An integer 748 for bits of q-1, starting with the second most significant 749 bit, ending with the least significant bit, do 751 // gradient of line through C, C, [-2]C. 753 l = 3*( C_x^2 - 1 ) / ( 2*C_y ); 755 //accumulate line evaluated at [i]Q into v 757 v = v^2 * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) ); 759 C = [2]C; 761 if bit is 1, then 763 // gradient of line through C, R, -C-R. 765 l = ( C_y - R_y )/( C_x - R_x ); 767 //accumulate line evaluated at [i]Q into v 769 v = v * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) ); 771 C = C+R; 773 end if; 775 end for; 777 t = v^c; 779 return representative in F_p of t; 781 End of routine; 783 Routine for computing representative in F_p of elements of 784 PF_p: 786 Input t, in F_p^2, representing an element of PF_p; 788 Represent t as a + i*b, with a,b in F_p; return b/a; 790 End of routine; 792 794 A.4. Hashing to an Integer Range 796 We use the function HashToIntegerRange( s, n, hashfn ) to hash 797 strings to an integer range. Given a string (s), a hash function 798 (hashfn), and an integer (n), this function returns a value between 0 799 and n - 1. 801 Input: 802 * an octet string, s 804 * an integer, n <= (2^hashlen)^hashlen 806 * a hash function, hashfn, with output length hashlen bits 808 Output: 810 * an integer, v, in the range 0 to n-1 812 Method: 814 1) Let A = hashfn( s ) 816 2) Let h_0 = 00...00, a string of null bits of length hashlen 817 bits 819 3) Let l = Ceiling(lg(n)/hashlen) 820 4) For each i in 1 to l, do: 822 a) Let h_i = hashfn(h_(i - 1)) 824 b) Let v_i = hashfn(h_i || A), where || denotes concatenation 826 5) Let v' = v_1 || ... || v_l 828 6) Let v = v' mod n 830 Appendix B. BN Elliptic Curves, Pairings and Supporting Algorithms 832 B.1. BN Elliptic Curves 833 When E is an ordinary elliptic curve known as a BN curve (of j- 834 invariant 0), we consider the family such that E: y^2=x^3+b, defined 835 over a finite prime field F_p. In this document, we let b = 2. We 836 require that p is congruent to 3 modulo 4, for efficiency reasons. E 837 has prime order q = #E(F_p), and for BN curves, the primes p and q 838 are given by p = p(u) = 36u^4+36u^3+24u^2+6u+1 and q = q(u) = 839 36u^4+36u^3+18u^2+6u+1, for some integer u. The BN curve in this 840 document has a generator P = (-1,1). BN curves have embedding degree 841 k = 12 and admit a sextic twist, which allows for an optimal ate 842 pairing on the groups, as we discuss below. 844 Routines for point addition and doubling on E(F_p) can be found in 845 Appendix A.10 of [P1363]. 847 B.2. Sextic Twists of BN Curves 848 Since p is a prime congruent to 3 modulo 4, the finite field F_p^2 849 can be represented as F_p[i]/(i^2+1). So i^2+1 = 0 and elements of 850 F_p^2 are represented as x_1 + i * x_2, where x_1 and x_2 are 851 elements of F_p. We may view F_p^12 as F_p^2[x]/(x^6-z), where x^6-z 852 is irreducible over F_p^2. 854 Consider the twisting isomorphism, psi: E'(F_p^2) --> E(F_p), where 855 (x',y') is mapped to (x'z^2),y'z^3) for some z in the multiplicative 856 group of F_p^12. It can be shown that E':y^2 = x^3 +b/z over F_p^2, 857 where z is not a cube nor square in F_p^2. E' is called the sextic 858 twist of E over F_p^2. E'(F_p^2)[q] has a generator P' = [h](-i,1) 859 where h=2p-q. So in the case of E: y^2=x^3+2 over F_p, we have E': 860 y^2=x^3+(1-i) over F_p^2. 862 B.3. The Ate Pairing for BN Curves 864 The Tate, Ate or R-ate pairings can be used with BN curves in ZSS, 865 but we describe the Ate pairing in this document The Ate pairing for 866 BN curves uses roughly half the number of iterations of the Miller 867 loop needed to compute the Tate pairing. 869 In general, the Ate pairing is from G_2 X G1 onto the subgroup of 870 order q in (F_p^12)*, where G_2 = E(F_p^12)[q] and G_1 = E(F_p)[q]. 871 Thus, the Ate pairing takes a point Q in E(F_p^12) and a point 872 R in E(F_p), and evaluates f_Q(R), where f_Q is some polynomial over 873 F_p^12 whose divisor is (q)(Q) - (q)(0). (Note that f_Q is defined 874 only up to scalars of F_p^12.) Miller's algorithm [Miller] provides a 875 method for evaluation of f_Q(R). 877 However, for BN curves, instead of using the full point Q in 878 E(F_p^12), we can use Q' in E'(F_p^2), where E' is the twist under 879 the twisting isomorphism described in the section above, so 880 psi(Q')=Q. This allows us to use a compact representation of the 881 point and to avoid F_p^12 arithmetic when computing the pairing. 883 Thus, let us consider G_1 = E(F_p)[q] and G_2 = E'(F_p^2)[q]. We 884 note that if Q=(Q_x,Q_y) and Q'=(Q_x',Q_y'), then (Q_x,Q_y)= 885 ((z^2)Q_x',(z^3)Q_y'). The version of the Ate pairing used in this 886 document is given by = f_Q'(R)^c in (F_p^12)*, where c=(p^12- 887 1)/q. It satisfies the bilinear relation <[x]Q',R> = = 888 ^x for all Q' in E'(F_p^2)[q] and R in E(F_p)[q], for all 889 integers x. 891 We provide pseudocode for computing with elliptic curve 892 arithmetic expressed in affine coordinates. From this point forward, 893 we will drop the notation of Q' and just use Q, understanding that Q 894 is a point on E'(F_p^2). Note that this section does not fully 895 describe the most efficient way of computing the pairing, as there 896 are further ways of reducing the number and complexity of the 897 operations needed to compute the pairing (e.g., [Devegili]). For 898 example, a common optimization is to factor c = (p^12-1)/q into three 899 parts: (p^6-1), (p^2+1) and (p^4-p^2+1)/q. 901 903 /* Copyright (c) 2012 IETF Trust and the persons identified as 904 authors of the code. All rights reserved. 906 Redistribution and use in source and binary forms, with or without 907 modification, is permitted pursuant to, and subject to the license 908 terms contained in, the Simplified BSD License set forth in Section 909 4.c of the IETF Trust's Legal Provisions Relating to IETF Documents 910 (http://trustee.ietf.org/license-info). */ 912 Routine for computing the pairing : 914 Input Q, a point in E'(F_p^2)[q], and R, a point on 915 E(F_p)[q]. 917 Initialize variables: 918 f = (F_p^12)*; // An element of (F_p^12)* 919 C = Q; // An element of E'(F_p^2)[q] 920 c = (p^12-1)/q; // An integer 922 for bits of q-1, starting with the second most significant 923 bit, ending with the least significant bit, do 925 // gradient of line through C, C, [-2]C. 927 l = 3*( C_x^2 ) / ( 2*C_y ); 929 //accumulate line evaluated at R into f 931 f = f^2 * ( l*( - R_x + C_x ) + ( R_y - C_y ) ); 933 C = [2]C; 935 if bit is 1, then 937 // gradient of line through C, Q, -C-Q. 939 l = ( C_y - Q_y )/( C_x - Q_x ); 941 //accumulate line evaluated at R into f 943 f = f * ( l*( - R_x + C_x ) + ( R_y - C_y ) ); 945 C = C+Q; 947 end if; 949 end for; 951 t = f^c; 953 return representative in (F_p^12)* of t; 955 957 Appendix C. Example Data 959 This appendix provides example data for the ZSS short signature 960 scheme with the public parameters (n, p, q, E, P, P', g, H). The 961 supersingular curve parameters are also found in [RFC6808,RFC6809]. 963 We denote elements of Fp_2 by (alpha, beta) for alpha + i*beta, where 964 i in Fp_2 is a root of X^2+1. We denote elements of Fp_12 by 965 ((gamma_0), (gamma_1), (gamma_2), (gamma_3), (gamma_4), (gamma_5)) 966 for gamma_0 + gamma_1*Z + gamma_2*Z^2 + gamma_3*Z^3 + gamma_4*Z^4 + 967 gamma_5*Z^5, where Z in Fp_12 is a root of x^6-z and 968 gamma_j=(alpha_j, beta_j) are elements of Fp_2. 970 C.1 Example 1 (Supersingular) 972 n = 128 974 p = 997ABB1F 0A563FDA 65C61198 DAD0657A 975 416C0CE1 9CB48261 BE9AE358 B3E01A2E 976 F40AAB27 E2FC0F1B 228730D5 31A59CB0 977 E791B39F F7C88A19 356D27F4 A666A6D0 978 E26C6487 326B4CD4 512AC5CD 65681CE1 979 B6AFF4A8 31852A82 A7CF3C52 1C3C09AA 980 9F94D6AF 56971F1F FCE3E823 89857DB0 981 80C5DF10 AC7ACE87 666D807A FEA85FEB 983 q = 265EAEC7 C2958FF6 99718466 36B4195E 984 905B0338 672D2098 6FA6B8D6 2CF8068B 985 BD02AAC9 F8BF03C6 C8A1CC35 4C69672C 986 39E46CE7 FDF22286 4D5B49FD 2999A9B4 987 389B1921 CC9AD335 144AB173 595A0738 988 6DABFD2A 0C614AA0 A9F3CF14 870F026A 989 A7E535AB D5A5C7C7 FF38FA08 E2615F6C 990 203177C4 2B1EB3A1 D99B601E BFAA17FB 992 E: y^2 = x^3 -3x 994 P = P' = (Px,Py) where 996 Px = 53FC09EE 332C29AD 0A799005 3ED9B52A 997 2B1A2FD6 0AEC69C6 98B2F204 B6FF7CBF 998 B5EDB6C0 F6CE2308 AB10DB90 30B09E10 999 43D5F22C DB9DFA55 718BD9E7 406CE890 1000 9760AF76 5DD5BCCB 337C8654 8B72F2E1 1001 A702C339 7A60DE74 A7C1514D BA66910D 1002 D5CFB4CC 80728D87 EE9163A5 B63F73EC 1003 80EC46C4 967E0979 880DC8AB EAE63895 1005 Py = 0A824906 3F6009F1 F9F1F053 3634A135 1006 D3E82016 02990696 3D778D82 1E141178 1007 F5EA69F4 654EC2B9 E7F7F5E5 F0DE55F6 1008 6B598CCF 9A140B2E 416CFF0C A9E032B9 1009 70DAE117 AD547C6C CAD696B5 B7652FE0 1010 AC6F1E80 164AA989 492D979F C5A4D5F2 1011 13515AD7 E9CB99A9 80BDAD5A D5BB4636 1012 ADB9B570 6A67DCDE 75573FD7 1BEF16D7 1014 g = 66FC2A43 2B6EA392 148F1586 7D623068 1015 C6A87BD1 FB94C41E 27FABE65 8E015A87 1016 371E9474 4C96FEDA 449AE956 3F8BC446 1017 CBFDA85D 5D00EF57 7072DA8F 541721BE 1018 EE0FAED1 828EAB90 B99DFB01 38C78433 1019 55DF0460 B4A9FD74 B4F1A32B CAFA1FFA 1020 D682C033 A7942BCC E3720F20 B9B7B040 1021 3C8CAE87 B7A0042A CDE0FAB3 6461EA46 1023 H = SHA-256 (defined in [FIPS180-3]). 1025 The SSK is: 1026 x = AFF429D3 5F84B110 D094803B 3595A6E2 998BC99F 1028 The SPK is: 1029 X = (Xx,Xy) where 1031 Xx = 5958EF1B 1679BF09 9B3A030D F255AA6A 1032 23C1D8F1 43D4D23F 753E69BD 27A832F3 1033 8CB4AD53 DDEF4260 B0FE8BB4 5C4C1FF5 1034 10EFFE30 0367A37B 61F701D9 14AEF097 1035 24825FA0 707D61A6 DFF4FBD7 273566CD 1036 DE352A0B 04B7C16A 78309BE6 40697DE7 1037 47613A5F C195E8B9 F328852A 579DB8F9 1038 9B1D0034 479EA9C5 595F47C4 B2F54FF2 1040 Xy = 1508D375 14DCF7A8 E143A605 8C09A6BF 1041 2C9858CA 37C25806 5AE6BF75 32BC8B5B 1042 63383866 E0753C5A C0E72709 F8445F2E 1043 6178E065 857E0EDA 10F68206 B63505ED 1044 87E534FB 2831FF95 7FB7DC61 9DAE6130 1045 1EEACC2F DA3680EA 4999258A 833CEA8F 1046 C67C6D19 487FB449 059F26CC 8AAB655A 1047 B58B7CC7 96E24E9A 39409575 4F5F8BAE 1049 Suppose H(m) = 3230 31312D30 32007465 6C3A2B34 1050 34373730 30393030 31323300 1052 Signature S = (Sx,Sy) where 1053 Sx = 93AF67E5 007BA6E6 A80DA793 DA300FA4 1054 B52D0A74 E25E6E7B 2B3D6EE9 D18A9B5C 1055 5023597B D82D8062 D3401956 3BA1D25C 1056 0DC56B7B 979D74AA 50F29FBF 11CC2C93 1057 F5DFCA61 5E609279 F6175CEA DB00B58C 1058 6BEE1E7A 2A47C4F0 C456F052 59A6FA94 1059 A634A40D AE1DF593 D4FECF68 8D5FC678 1060 BE7EFC6D F3D68353 25B83B2C 6E69036B 1062 Sy = 155F0A27 241094B0 4BFB0BDF AC6C670A 1063 65C325D3 9A069F03 659D44CA 27D3BE8D 1064 F311172B 55416018 1CBE94A2 A783320C 1065 ED590BC4 2644702C F371271E 496BF20F 1066 588B78A1 BC01ECBB 6559934B DD2FB65D 1067 2884318A 33D1A42A DF5E33CC 5800280B 1068 28356497 F87135BA B9612A17 26042440 1069 9AC15FEE 996B744C 33215123 5DECB0F5 1071 For verification of the signature: 1072 = g 1074 C.2 Example 2 (BN) 1076 n = 127 and lg(p) = 254 1078 p = p(u) = p(-4647714815446351873) 1079 = 1679810873101583228494080414223173390988918712143906984893371542 1080 6072753864723 1082 q = q(u) = q(-4647714815446351873) 1083 = 16798108731015832284940804142231733909759579603404752749028378864 1084 165570215949 1086 E: y^2 = x^3 + 2 1088 Thus, E': y'^2 = x'^3 + (1, 16798108731015832284940804142231733909 1089 889187121439069848933715426072753864722) 1091 P = (-1,1) 1092 = (1679810873101583228494080414223173390988918712143906984893371542 1093 6072753864722, 1) 1095 P' = [h](-i,1) = (P'x,P'y), where P'x and P'y are elements of Fp_2 1097 P'x = 1098 (2759930593230997547690248631365636073479225314645471320757910281 1099 674905877291, 230161490788271857374524411062025673221233257170073 1100 7603512907075120331574515) 1102 P'y = 1103 (9480765153516887970576068394945041092622478388406602889697250323 1104 02618946458, 6663077446927392079224045631425291036692402823802663 1105 947112913140121004068507) 1107 g = is an element of Fp_12 given by 1108 ((13070690801249658484759892809227642840919015841299984602661540278 1109 97835831306, 362837632692008901334341187262873478716707643732273036 1110 6913713646023905731503), 1112 (352778753845190583740690941014710408681261806065247837729422038997 1113 7928485580, 1390842049595369881149037040415050751861458203097739688 1114 0797626940316305362787), 1116 (148957391318235038979721383575910962973602682276093210989431526351 1117 38088456200, 154193402372256829285477206567013233448625527219699948 1118 30027125771243100988775), 1120 (657015345250965363244058395947686331467494595330600581669861545909 1121 8579995196, 9246328720071559688457720607053218330889647295590139338 1122 238624175808225962795), 1124 (151014665406602395528454680822744016147807484038495196740696804034 1125 7117671512, 6964231951063075324378672955330091045708301556113455379 1126 316967754148774004530), 1128 (132001962407792355737177261139163922637454993559842085107451833663 1129 5435672354, 9476335168658772594045570476784073542275866387029189317 1130 560203959549876656582)) 1132 SSK = 228064033978937665992889984775405287134161793365057496448735949 1133 2611 1135 SPK = (48893896735870064320433171153400539525040538030176968340812183 1136 01282547698392, 15356945755932217528217084848811599775130985825038998 1137 692965243198105904624442) 1139 Suppose H(m) = 21668398097129279358779433271119370918865051659048528 1140 91187078055077 1142 Signature S = (Sx,Sy) where Sx and Sy are elements of Fp_2 and 1144 Sx = (729051981497750473018989894592657769743437818459774775561224900 1145 9723218090232, 683378059974468691645078542720737033649767207447427118 1146 6472709797618120651615) 1148 Sy = (157432174827386069860812184931399877857826328817373172771264166 1149 63269695635786, 93427588866953969700345687463198658107209055412980315 1150 33851535785638159753756) 1152 For verification of the signature: 1154 = g 1156 Author's Address 1158 Laura Hitt 1159 6011 W Courtyard Dr. 1160 Building 5, Suite 300 1161 Austin, TX 78730 1163 EMail: LHitt@21CT.com