idnits 2.17.1 draft-irtf-cfrg-zssbn-01.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 : ---------------------------------------------------------------------------- ** There is 1 instance of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (September 11, 2013) is 3877 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 4492 (Obsoleted by RFC 8422) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). 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: March 15, 2014 September 11, 2013 6 ZSS Short Signature Scheme for BN Curves 7 draft-irtf-cfrg-zssbn-01 9 Abstract 11 This document describes the ZSS Short Signature Scheme for 12 implementation from bilinear pairings on Barreto-Naerhig (BN) 13 ordinary elliptic curves. The ZSS Short Signature Scheme uses general 14 cryptographic hash functions such as SHA-1 or SHA-2 and is efficient 15 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 . . . . . . . . . . . . . . . . . . . . . . . . 7 63 3.3 Representations . . . . . . . . . . . . . . . . . . . . . . 8 64 3.4 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 8 65 4 The ZSS Cryptosystem . . . . . . . . . . . . . . . . . . . . . 9 66 4.1 Parameter Generation . . . . . . . . . . . . . . . . . . . . 9 67 4.2 Key Generation . . . . . . . . . . . . . . . . . . . . . . . 9 68 4.3 Signature Generation . . . . . . . . . . . . . . . . . . . . 9 69 4.4 Signature Verification . . . . . . . . . . . . . . . . . . . 10 70 5 Security Considerations . . . . . . . . . . . . . . . . . . . . 10 71 6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 11 72 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 12 73 7.1 Normative References . . . . . . . . . . . . . . . . . . . 12 74 7.2 Informative References . . . . . . . . . . . . . . . . . . 12 75 Appendix A. BN Elliptic Curves, Twists, Pairings and Supporting 76 Algorithms . . . . . . . . . . . . . . . . . . . . . . . 14 77 A.1. BN Elliptic Curves . . . . . . . . . . . . . . . . . . . . 14 78 A.2. Sextic Twists . . . . . . . . . . . . . . . . . . . . . . . 14 79 A.3. The Ate Pairing . . . . . . . . . . . . . . . . . . . . . 14 80 A.4. Hashing to an Integer Range . . . . . . . . . . . . . . . 16 81 Appendix B. Example Data . . . . . . . . . . . . . . . . . . . . 17 82 B.1 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . 17 83 B.2 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . 19 84 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 21 86 1 Introduction 88 This document describes the ZSS Short Signature Scheme (designed by 89 Zhang, Safavi-Naini, and Susilo) for implementation from bilinear 90 pairings [ZSS]. It does not require any special hash function such 91 as MapToPoint [B-F], which is still probabilistic and generally 92 inefficient, but rather can use cryptographic hash functions such as 93 SHA-1 or SHA-2. 95 This document is restricted to implementation of ZSS on a particular 96 family of Barreto-Naerhig (BN) elliptic curves, though the scheme is 97 valid on other elliptic curve groups. BN curves are a family of non- 98 supersingular (i.e., ordinary) curves that are attractive for 99 pairing-based cryptography for a variety of reasons. These curves 100 are plentiful and easily found and they support a sextic twist, which 101 allows pairing arguments to be defined over relatively small finite 102 fields. Computation of the pairing is the most time consuming 103 procedure in pairing-based cryptography, and BN curves are amenable 104 to twofold or threefold pairing compression and attain high 105 efficiency for all pairing computation algorithms known (e.g., Tate, 106 ate, eil, R-ate, Xate). These curves are also suitable for software 107 and hardware implementations on a wide range of platforms. 109 The specific subclass of BN curves that we choose for this document 110 is discussed in [Pereira], and offers many additional efficiency 111 advantages. The subclass automatically yields the right sextic twist 112 (thus entirely avoiding curve arithmetic for that purpose) and 113 provides simple and obvious generators for the curve and its twist 114 (removing the need for extra processing and storage). It allows for 115 pairing efficiency, uniform finite field arithmetic, choice of 116 suitable field sizes, and enables virtually all optimizations 117 currently proposed in the literature for involved algebraic 118 structures. These advantages are important since short signatures are 119 needed in low-bandwidth communication environments. 121 The scheme is constructed from the Inverse Computational Diffie- 122 Hellman Problem (Inv-CDHP) on bilinear pairings (see Section 1.2 123 below for a discussion of Inv-CDHP). The security of the scheme is 124 based on the assumed hardness of this problem (which is widely 125 accepted), which means there is no polynomial time algorithm to solve 126 it with non-negligible probability. Bilinear pairings have been used 127 to construct Identity (ID)-Based cryptosystems [B-F], so that the 128 identity information of a user functions as his public key. The 129 signing process in a short signature scheme can be regarded as the 130 private key extract process in the ID-based public key setting from 131 bilinear pairings. Therefore, the ZSS signature scheme can be 132 regarded as being derived from Sakai-Kasahara's ID-based encryption 133 scheme with pairing [S-K, RFC6508]. 135 The algorithm is for use in the following context: 137 * where there are two parties, a Signer and a Verifier; 139 * where a message is to be signed and then verified (e.g., for 140 authenticating the initiating party during key establishment); 142 * where a Certificate Authority (CA) or Trusted Third Party (TTP) 143 within a traditional Public Key Infrastructure (PKI) provides a 144 root of trust for both parties. 146 1.1 Bilinear Pairings 148 Let G_1 and G_2 be cyclic additive groups generated by P and P', 149 respectively, both of whose order is a prime q. Let G_3 be a 150 cyclic multiplicative group with the same order q. Let Z_q be the 151 additive group of integers modulo q. 153 Let <,>: G_1 X G_2 --> G_3 be a map with the following properties. 155 1. Bilinearity: =^(ab) for all P, Q elements of G_1 156 and G_2, respectively, and a, b elements of Z_q. 158 2. Non-degeneracy: There exists P, Q elements of G_1 and G_2, 159 respectively, such that != 1. In other words, the map does 160 not send all pairs in G_1 X G_2 to the identity in G_3. 162 3. Computability: There is an efficient algorithm to compute 163 for all P in G_1 and Q in G_2. 165 In our setting of prime order groups, non-degeneracy is equivalent to 166 != 1 for all nontrivial P, Q elements in G_1 and G_2, 167 respectively. So, when P is a generator of G_1 and Q is a generator 168 of G_2, then is a generator of G_3. Such a bilinear map is 169 called a bilinear pairing. 171 1.2 Discrete Logarithm Problem and Diffie-Hellman Problems 173 We consider the following problems in the additive group (G_1;+). 175 Discrete Logarithm Problem (DLP): Given two group elements P and 176 Q, find an integer n in (Z_q)*, such that Q=nP whenever such an 177 integer exists. 179 Decision Diffie-Hellman Problem (DDHP): For a,b,c in (Z_q)*, given 180 P, aP, bP, cP decide whether c is congruent to ab mod q. 182 Computational Diffie-Hellman Problem (CDHP): For a,b in (Z_q)*, 183 given P, aP, bP, compute abP. 185 Inverse Computational Diffie-Hellman Problem (Inv-CDHP): For a in 186 (Z_q)*, given P, aP, compute [a^(-1)]P. 188 Square Computational Diffie-Hellman Problem (Squ-CDHP): For a in 189 (Z_q)*, given P, aP, compute [a^2]P. 191 Bilinear Diffie-Hellman problem (BDHP): Given (P, aP, bP, cP) for 192 some a,b,c in (Z_q)*, compute v in G_3 such that v = ^(abc). 194 The CDHP, Inv-CDHP, and Squ-CDHP are polynomial time equivalent. The 195 DLP, CDHP, Inv-CDHP, Squ-CDHP, and BDHP are assumed to be hard, which 196 means there is no polynomial time algorithm to solve any of them with 197 non-negligible probability. Therefore, the security of pairing based 198 cryptosystems are typically based on these problems. A Gap Diffie- 199 Hellman (GDH) group is a group in which the DDHP can be efficiently 200 solved but the CDHP is intractable. The bilinear pairing gives us 201 such a group, found on elliptic curves or hyperelliptic curves over 202 finite fields. The bilinear pairings can be derived from the Weil or 203 Tate pairing, as in [B-F, Cha-Cheon, Hess]. The ZSS scheme works on 204 any GDH group, but in this document we focus on a particular family 205 of ordinary (i.e., non-supersingular) elliptic curves, known as BN 206 curves, described in Section 3.4 and the pairing described in 207 Appendix A.2. 209 1.3 Terminology 211 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 212 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 213 document are to be interpreted as described in RFC 2119 [RFC2119]. 215 2 Architecture 217 We consider the situation where one entity (the Signer) wishes to 218 sign a message that it is sending to another entity (the Verifier). 220 As in a traditional Public Key Infrastructure (PKI), a Certificate 221 Authority (CA) or Trusted Third Party (TTP) provides assurance of a 222 signer's identity, which is bound to the signer's public key. The CA 223 may generate a public key and private key (a key pair) or the signer 224 may generate their own key pair and register the Signer Public Key 225 (SPK) with a CA. 227 The mechanism by which a secret key is transported MUST be secure, as 228 the security of the authentication provided by ZSS signatures is no 229 stronger than the security of this supply channel. The choice of 230 secret key transport mechanism is outside the scope of this document. 232 During the signing process, once the Signer has formed its message, 233 it signs the message using its Signer Secret Key (SSK). It transmits 234 the Signature with the message. The Verifier MUST then use the 235 message, Signature, and SPK in verification. 237 This document specifies 239 * an algorithm for creating a Signature from a message, using an 240 SSK; 242 * an algorithm for verifying a Signature for a message, using an 243 SPK. 245 This document does not specify (but comments on) 247 * how to choose a valid and secure elliptic curve; 249 * which hash function to use. 251 3 Notation, Definitions and Parameters 253 3.1 Notation 255 n A security parameter; n should be at most half the bit size of 256 q. 258 p A prime, of size at least 2n bits, which is the order of the 259 finite field F_p. In this document, p is always congruent to 3 260 modulo 4. 262 F_p The finite field of order p (i.e., field with p elements). 264 F* The multiplicative group of the non-zero elements in the field 265 F; e.g., (F_p)* is the multiplicative group of the finite field 266 F_p. 268 q The order of E(F_p). In this document, for BN curves, q is 269 always prime. To provide the desired level of security, lg(q) 270 MUST be greater than 2*n. 272 E An elliptic curve defined over F_p, having prime order q. In 273 this document, we use BN elliptic curves with equation y^2 = 274 x^3 + 2 modulo p. 276 E' A sextic twist of the elliptic curve E. In this document, 277 E':y^2 = x^3 + (1-i) over F_p^12. The order of E' over F_{p^2} 278 is q(2p-q). 280 E(F) The additive group of points of affine coordinates (x,y) with 281 x, y in the field F, that satisfy the curve equation for E. 283 P A generator of E(F_p). P has order q. 285 P' A point of E'(F_p^2) that generates the cyclic subgroup of 286 order q. 288 0 The null element of any additive group of points on an elliptic 289 curve, also called the point at infinity. 291 F_p^2 The extension field of degree 2 of the field F_p. In this 292 document, we use a particular instantiation of this field; 293 F_p^2 = F_p[i], where i^2 + 1 = 0. It is for this reason that 294 we choose p congruent to 3 modulo 4. 296 G[q] The q-torsion of a group G. This is the subgroup generated by 297 points of order q in G. 299 < , > The Ate pairing. In this document, this is a bilinear map from 300 E'(F_p^2)[q] X E(F_p)[q] onto the subgroup of order q in 301 (F_p^12)*. A full definition is given in Appendix A.2. 303 g g = . Having this pre-computed value allows the Verifier 304 to only perform one pairing operation to verify a signature. 306 H A cryptographic hash function. [FIPS180-3] contains NIST 307 approved hash functions. 309 lg(x) The base 2 logarithm of the real value x. 311 3.2 Definitions 313 Certificate Authority (CA) - The Certificate Authority is a trusted 314 third party who provides assurance that the SPK 315 belongs to the signer and verified proof of the 316 signer's identity when the signer registered the 317 SPK. 319 Public parameters - The public parameters are a set of parameters 320 that are held by all users of the system. Each 321 application of ZSS MUST define the set of public 322 parameters to be used. The parameters needed are n, 323 p, q, E, P, P', < , >, g, and H. 325 Signer Public Key (SPK) - The Signer's Public key is used to verify 326 the signature of the entity whose SSK corresponds to 327 the SPK. It is a point on the elliptic curve E. 329 Signer Secret Key (SSK) - The Signer's Secret Key is used to generate 330 a signature and must not be revealed to any entity 331 other than the trusted third party and the 332 authorized signer. It is a value between 2 and q-1. 334 3.3 Representations 336 This section provides canonical representations of values that MUST 337 be used to ensure interoperability of implementations. The following 338 representations MUST be used for input into hash functions and for 339 transmission. In this document, concatenation of octet strings s and 340 t is denoted s || t. 342 Integers Integers MUST be represented as an octet string, 343 with bit length a multiple of 8. To achieve this, 344 the integer is represented most significant bit 345 first, and padded with zero bits on the left until 346 an octet string of the necessary length is obtained. 347 This is the octet string representation described in 348 Section 6 of [RFC6090]. 350 F_p elements Elements of F_p MUST be represented as integers in 351 the range 0 to p-1 using the octet string 352 representation defined above. Such octet strings 353 MUST have length L = Ceiling(lg(p)/8). 355 F_p^2 elements The elements of F_p^2 = F_p[i] are represented as 356 x_1 + i * x_2, where x_1 and x_2 are elements of 357 F_p. It is for this reason that we choose p 358 congruent to 3 modulo 4. 360 Points on E, E' Elliptic curve points MUST be represented in 361 uncompressed form as defined in Section 2.2 of 362 [RFC5480]. For an elliptic curve point (x,y) with x 363 and y in F_p, this representation is given by 0x04 364 || x' || y', where x' is the octet string 365 representing x, y' is the octet string representing 366 y, and || denotes concatenation. The representation 367 is 2*L+1 octets in length. 369 3.4 Arithmetic 371 ZSS relies on elliptic curve arithmetic. The coordinates of a point 372 P on the elliptic curve are given by P = (P_x,P_y), where Px and Py 373 are the affine coordinates in F_p satisfying the curve equation. 375 The following conventions are assumed for curve operations: 377 Point addition - If P and Q are two points on a curve E, their sum is 378 denoted as P + Q. 380 Scalar multiplication - If P is a point on a curve, and k an integer, 381 the result of adding P to itself a total of k times 382 is denoted [k]P. 384 In this document, we use BN curves with equation y^2 = x^3 + 2 modulo 385 p. This curve is chosen because of the many efficiency and 386 simplicity advantages it offers, as mentioned in Section 1 and 387 discussed in [Pereira]. For example, one advantage is an easy 388 determination of a generator P of E(F_p), namely P = (-1,1). 390 4 The ZSS Cryptosystem 392 This section describes the ZSS short signature scheme [ZSS]. 394 4.1 Parameter Generation 396 The following static parameters are fixed for each implementation. 397 They are not intended to change frequently, and MUST be specified for 398 each user community. 400 The system parameters to be generated for a given security parameter 401 n are {p, q, E, P, P', <,>, g, H}. These are known by the Sender and 402 the Verifier. 404 4.2 Key Generation 406 To create signatures, each Signer requires an SSK and SPK. The SSK 407 is an integer, and the SPK is an elliptic curve point. The SSK MUST 408 be kept secret (to the Signer and possibly the CA), but the SPK need 409 not be kept secret. 411 The Signer (or CA) MUST randomly select a value in the range 2 to q- 412 1, and assigns this value to x, which is the SSK. 414 The Signer MUST derive its SPK, X, by performing the calculation X 415 =[x]P. 417 If the signer generated the SPK, then it must be registered with a 418 CA. 420 4.3 Signature Generation 422 Given the SSK x, and a message m, the Signer computes the signature S 423 by performing the following steps: 425 1) Compute the hash of the message as a mod q value using the hash 426 algorithm specified in the public parameters. 428 2) Compute (H(m)+x)^-1, where the inversion is performed modulo q. 430 3) Compute S = [(H(m)+x)^-1]P'. The signature is S, and this is a 431 point on the curve E'. 433 The Signer sends m and S. 435 4.4 Signature Verification 437 Given the SPK X, a message m, and a signature S, the Receiver 438 verifies that <[H(m)]P + X, S> = g, to ensure that the Signer is 439 authentic and the message was not altered in transit. This is 440 achieved by the Verifier performing the following steps: 442 1) Check that S is a point on the curve E', otherwise reject the 443 signature. 445 2) Compute the hash of the message as a mod q value using the hash 446 algorithm specified in the public parameters. 448 3) Compute the elliptic curve point [H(m)]P + X. 450 4) Compute the pairing <[H(m)]P + X, S>. 452 5) Verify that <[H(m)]P + X, S> = g; if not, reject the signature. 454 5 Security Considerations 456 This document describes the ZSS Short Signature Scheme. We assume 457 that the security provided by this algorithm depends entirely on the 458 secrecy of the secret keys it uses, and that for an adversary to 459 defeat this security, he will need to perform computationally 460 intensive cryptanalytic attacks to recover a secret key. Note that a 461 security proof exists for ZSS in the Random Oracle Model [ZSS]. 463 When defining public parameters, guidance on parameter sizes from 464 [RFC4492] SHOULD be followed. For lower security levels (e.g., less 465 than 128 bit security), the parameter sizes must be determined based 466 on the elliptic curve discrete logarithm problem over F_p, and for 467 the higher security levels the parameter sizes are based on the 468 finite field size (e.g., 12*lg(p)). Table 1 shows bits of security 469 afforded by various sizes of p. 471 Security (bits) | EC size (lg(p) | finite field size (12*lg(p)) 472 --------------------------------------------------------------- 473 80 | 160 | 1920 474 112 | 224 | 2688 475 128 | 256 | 3072 476 192 | 640 | 7680 477 256 | 1280 | 15360 479 Table 1: Comparable Strengths, taken from [RFC4492] 481 The order of the base point P used in ZSS, and hence the order 482 of E(F_p) for BN curves, MUST be a large prime q. If n bits of 483 security are needed, then lg(q) SHOULD be chosen to be at least 484 2*n. Similarly, if n bits of security are needed, then a hash 485 with output size at least 2*n SHOULD be chosen. 487 Randomizing the messages that are signed is a way to enhance the 488 security of the cryptographic hash function. [SP800-106] 489 provides a technique to randomize messages that are input to a 490 cryptographic hash function during the signature generation 491 step. The intent of this method is to strengthen the collision 492 resistance provided by the hash functions without any changes to 493 the core hash functions and signature algorithms. If the 494 message is randomized with a different random value each time it 495 is signed, it will result in the message having a different 496 digital signature each time. 498 Each user's SSK protects the ZSS communications it receives. 499 This key MUST NOT be revealed to any entity other than the 500 authorized user and possibly the CA (if the CA generated the key 501 pair). 503 In order to ensure that the SSK is received only by an 504 authorized entity, it MUST be transported through a secure 505 channel. The security offered by this signature scheme is no 506 greater than the security provided by this delivery channel. 508 The randomness of values stipulated to be selected at random, as 509 described in this document, is essential to the security 510 provided by ZSS. If the value of x used by a user is 511 predictable, then the value of his SSK could be recovered. This 512 would allow that user's signatures to be forged. Guidance on 513 the generation of random values for security can be found in 514 [RFC4086]. 516 6 IANA Considerations 518 This memo includes no request to IANA. 520 7 References 522 7.1 Normative References 524 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 525 Requirement Levels", BCP 14, RFC 2119, March 1997. 527 [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and 528 B. Moeller, "Elliptic Curve Cryptography (ECC) Cipher 529 Suites for Transport Layer Security (TLS)", RFC 4492, May 530 2006. 532 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 533 "Elliptic Curve Cryptography Subject Public Key 534 Information", RFC 5480, March 2009. 536 [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental 537 Elliptic Curve Cryptography Algorithms", RFC 6090, 538 February 2011. 540 [ZSS] Zhang, F., Safavi-Naini, R., and Susilo, W., "An 541 Efficient Signature Scheme from Bilinear Pairings and Its 542 Applications", PKC 2004, LNCS 2947, Springer-Verlag 543 (2004), pp. 277-290. 545 7.2 Informative References 547 [B-F] Boneh, D., Franklin, M., "Identity-based encryption from 548 the Weil pairing", Advances in Cryptology - Crypto 2001, 549 LNCS 2139, Springer-Verlag (2001), pp. 213-229. 551 [Cha-Cheon] Cha, J.C., Cheon, J.H., "An identity-based signature from 552 gap Diffie-Hellman groups", Public Key Cryptography - PKC 553 2003, LNCS 2139, Springer-Verlag (2003), pp. 18-3. 555 [Devegili] Devegili, A.J., Scott, M., Dahab, R., "Implementing 556 Cryptographic Pairings over Barreto-Naehrig Curves", 557 Pairing 2007, 197-207. 559 [FIPS180-3] Federal Information Processing Standards Publication 560 (FIPS PUB) 180-3, "Secure Hash Standard (SHS)", October 561 2008. 563 [Hess] Hess, F., "Efficient identity based signature schemes 564 based on pairings", SAC 2002, LNCS 2595, Springer-Verlag 565 (2002), pp. 310-324. 567 [Miller] Miller, V., "The Weil pairing, and its efficient 568 calculation", J. Cryptology 17 (2004), 235-261. 570 [P1363] IEEE P1363-2000, "Standard Specifications for Public-Key 571 Cryptography", 2001. 573 [Pereira] Pereira, G. C., et al. "A Family of Implementation- 574 Friendly BN Elliptic Curves", J. Systems and Software, 575 Volume 84, Issue 8, Elsevier (2011), pp 1319-1326. 577 [RFC4086] Eastlake 3rd, D., Schiller, J., and S. Crocker, 578 "Randomness Requirements for Security", BCP 106, 579 RFC 4086, June 2005. 581 [RFC6508] Groves, M., "Sakai-Kasahara Key Encryption (SAKKE)", 582 RFC 6508, February 2012. 584 [S-K] Sakai, R., Ohgishi, K., and M. Kasahara, "ID based 585 cryptosystem based on pairing on elliptic curves", 586 Symposium on Cryptography and Information Security - 587 SCIS, 2001. 589 [SP800-106] Dang, Q., "Randomized Hashing for Digital Signatures", 590 NIST Special Publication 800-106, February 2009. 592 Appendix A. BN Elliptic Curves, Twists, Pairings and Supporting 593 Algorithms 595 A.1. BN Elliptic Curves 596 E is an ordinary elliptic curve, known as a BN curve (of j-invariant 597 0), where E: y^2=x^3+b, defined over a finite prime field F_p. In 598 this document, we let b = 2. We require that p is congruent to 3 599 modulo 4, for efficiency reasons. E has prime order q = #E(F_p), and 600 for BN curves, the primes p and q are given by p = p(u) = 601 36u^4+36u^3+24u^2+6u+1 and q = q(u) = 36u^4+36u^3+18u^2+6u+1, for 602 some integer u. The curve in this document has a generator P = (- 603 1,1). BN curves have embedding degree k = 12 and admit a sextic 604 twist, which allows for an optimal ate pairing on the groups, as we 605 discuss below. 607 Routines for point addition and doubling on E(F_p) can be found in 608 Appendix A.10 of [P1363]. 610 A.2. Sextic Twists Since p is a prime congruent to 3 modulo 4, the 611 finite field F_p^2 can be represented as F_p[i]/(i^2+1). So i^2+1 = 612 0 and elements of F_p^2 are represented as x_1 + i * x_2, where x_1 613 and x_2 are elements of F_p. We may view F_p^12 as F_p^2[x]/(x^6-z), 614 where x^6-z is irreducible over F_p^2. 616 Consider the twisting isomorphism, psi: E'(F_p^2) --> E(F_p), where 617 (x',y') is mapped to (x'z^2),y'z^3) for some z in the multiplicative 618 group of F_p^12. It can be shown that E':y^2 = x^3 +b/z over F_p^2, 619 where z is not a cube nor square in F_p^2. E' is called the sextic 620 twist of E over F_p^2. E'(F_p^2)[q] has a generator P' = [h](-i,1) 621 where h=2p-q. So in the case of E: y^2=x^3+2 over F_p, we have E': 622 y^2=x^3+(1-i) over F_p^2. 624 A.3. The Ate Pairing 626 The Tate, Ate or R-ate pairings can be used with BN curves in ZSS, 627 but we describe the Ate pairing in this document The Ate pairing for 628 BN curves uses roughly half the number of iterations of the Miller 629 loop needed to compute the Tate pairing. 631 In general, the Ate pairing is from G_2 X G1 onto the subgroup of 632 order q in (F_p^12)*, where G_2 = E(F_p^12)[q] and G_1 = E(F_p)[q]. 633 Thus, the Ate pairing takes a point Q in E(F_p^12) and a point 634 R in E(F_p), and evaluates f_Q(R), where f_Q is some polynomial over 635 F_p^12 whose divisor is (q)(Q) - (q)(0). (Note that f_Q is defined 636 only up to scalars of F_p^12.) Miller's algorithm [Miller] provides a 637 method for evaluation of f_Q(R). 639 However, for BN curves, instead of using the full point Q in 640 E(F_p^12), we can use Q' in E'(F_p^2), where E' is the twist under 641 the twisting isomorphism described in the section above, so 642 psi(Q')=Q. This allows us to use a compact representation of the 643 point and to avoid F_p^12 arithmetic when computing the pairing. 645 Thus, let us consider G_1 = E(F_p)[q] and G_2 = E'(F_p^2)[q]. We 646 note that if Q=(Q_x,Q_y) and Q'=(Q_x',Q_y'), then (Q_x,Q_y)= 647 ((z^2)Q_x',(z^3)Q_y'). The version of the Ate pairing used in this 648 document is given by = f_Q'(R)^c in (F_p^12)*, where c=(p^12- 649 1)/q. It satisfies the bilinear relation <[x]Q',R> = = 650 ^x for all Q' in E'(F_p^2)[q] and R in E(F_p)[q], for all 651 integers x. 653 We provide pseudocode for computing with elliptic curve 654 arithmetic expressed in affine coordinates. From this point forward, 655 we will drop the notation of Q' and just use Q, understanding that Q 656 is a point on E'(F_p^2). Note that this section does not fully 657 describe the most efficient way of computing the pairing, as there 658 are further ways of reducing the number and complexity of the 659 operations needed to compute the pairing (e.g., [Devegili]). For 660 example, a common optimization is to factor c = (p^12-1)/q into three 661 parts: (p^6-1), (p^2+1) and (p^4-p^2+1)/q. 663 665 /* Copyright (c) 2012 IETF Trust and the persons identified as 666 authors of the code. All rights reserved. 668 Redistribution and use in source and binary forms, with or without 669 modification, is permitted pursuant to, and subject to the license 670 terms contained in, the Simplified BSD License set forth in Section 671 4.c of the IETF Trust's Legal Provisions Relating to IETF Documents 672 (http://trustee.ietf.org/license-info). */ 674 Routine for computing the pairing : 676 Input Q, a point in E'(F_p^2)[q], and R, a point on 677 E(F_p)[q]. 679 Initialize variables: 680 f = (F_p^12)*; // An element of (F_p^12)* 681 C = Q; // An element of E'(F_p^2)[q] 682 c = (p^12-1)/q; // An integer 684 for bits of q-1, starting with the second most significant 685 bit, ending with the least significant bit, do 687 // gradient of line through C, C, [-2]C. 689 l = 3*( C_x^2 ) / ( 2*C_y ); 691 //accumulate line evaluated at R into f 693 f = f^2 * ( l*( - R_x + C_x ) + ( R_y - C_y ) ); 695 C = [2]C; 697 if bit is 1, then 699 // gradient of line through C, Q, -C-Q. 701 l = ( C_y - Q_y )/( C_x - Q_x ); 703 //accumulate line evaluated at R into f 705 f = f * ( l*( - R_x + C_x ) + ( R_y - C_y ) ); 707 C = C+Q; 709 end if; 711 end for; 713 t = f^c; 715 return representative in (F_p^12)* of t; 717 719 A.4. Hashing to an Integer Range 721 We use the function HashToIntegerRange( s, n, hashfn ) to hash 722 strings to an integer range. Given a string (s), a hash function 723 (hashfn), and an integer (n), this function returns a value between 0 724 and n - 1. 726 Input: 727 * an octet string, s 729 * an integer, n <= (2^hashlen)^hashlen 731 * a hash function, hashfn, with output length hashlen bits 733 Output: 735 * an integer, v, in the range 0 to n-1 737 Method: 739 1) Let A = hashfn( s ) 741 2) Let h_0 = 00...00, a string of null bits of length hashlen 742 bits 744 3) Let l = Ceiling(lg(n)/hashlen) 746 4) For each i in 1 to l, do: 748 a) Let h_i = hashfn(h_(i - 1)) 750 b) Let v_i = hashfn(h_i || A), where || denotes concatenation 752 5) Let v' = v_1 || ... || v_l 754 6) Let v = v' mod n 756 Appendix B. Example Data 758 This appendix provides example data for the ZSS short signature 759 scheme with the public parameters (n, p, q, E, P, P', g, H). 761 We denote elements of Fp_2 by (alpha, beta) for alpha + i*beta, where 762 i in Fp_2 is a root of X^2+1. We denote elements of Fp_12 by 763 ((gamma_0), (gamma_1), (gamma_2), (gamma_3), (gamma_4), (gamma_5)) 764 for gamma_0 + gamma_1*Z + gamma_2*Z^2 + gamma_3*Z^3 + gamma_4*Z^4 + 765 gamma_5*Z^5, where Z in Fp_12 is a root of x^6-z and 766 gamma_j=(alpha_j, beta_j) are elements of Fp_2. 768 B.1 Example 1 770 n = 111 and lg(p) = 222 772 p = p(u) = p(18577485901856771) 773 = 42879554281412312425684491434343070045094087778429904430372487209 774 23 776 q = q(u) = q(18577485901856771) 777 = 42879554281412312425684491434343049337715141757204855580048574422 778 77 780 E: y^2 = x^3 + 2 782 Thus, E': y'^2 = x'^3 + (1, 42879554281412312425684491434343070045 783 09408777842990443037248720922) 785 P = (-1,1) 786 = (4287955428141231242568449143434307004509408777842990443037248720 787 922, 1) 789 P' = [h](-i,1)=(P'x,P'y) where P'x and P'y are elements of Fp_2 and 791 P'x = (4150062559496717098010848775383950942405168339753729033708 792 91183040, 3201547425391805499092396849287316949217764330692173661 793 045966218196) 795 P'y = (2739493618867793153898969775521693478241455091691296751947 796 733115593, 166470767945024234715239288329979167344659708006587338 797 7257740360355) 799 g = is an element of Fp_12 given by 801 ((36699339660626669649427399393560215125019796922092031025948063026 802 15, 247927466780520015848965517635750695647326440402643111951301234 803 2995), 805 (53440222253683237877269791416098727648815280997704796178179123615 806 5, 152660447468210228523508984531632103922262052241800765770764185 807 1816), 809 (49145419234025334524484519757289516582314844784075278041512123443, 810 176265594691520614080041515255534401194732308979032729979138040295 811 4), 813 (23696703075178036967923154124988633199564384190798395748600577760 814 85, 23618404356311472082427998195066752928773113611373491721529464 815 37996), 817 (12762283628400824508803470970369296405340301501303861200304473348 818 06, 13459347095597820798563091367816489138601686487822582178268889 819 4443), 821 (52536691068804792250953154403977106032469644538529906910544187717 822 3, 111049479509897086258622292367384411180467475476136042303440990 823 5476)) 825 SSK = 2121608753564392499593333521375987220574081909435960440370410 826 821656 828 SPK = (120851890594243637869885901573990997912577177623964284017952 829 0609651, 5156510979532175335881708985883359220634082111209944466019 830 22864253) 832 Suppose H(m) = 6104193801232612202724894323091424875875271378342228 833 81137528506355 835 Signature S = (Sx,Sy) where Sx and Sy are elements of Fp_2 and 837 Sx = (4603970358468010885038949506701201323979300401623873254674143 838 95606, 390184854411376879582308121331828716038030146457335118850788 839 9233137) 841 Sy = (2942449282558423549330843008093657343677696839292115922361297 842 49298, 202625687787456997385822667969165094633744989095128763600003 843 736610) 845 For verification of the signature: 846 = g 848 B.2 Example 2 850 n = 127 and lg(p) = 254 852 p = p(u) = p(-4647714815446351873) 853 = 1679810873101583228494080414223173390988918712143906984893371542 854 6072753864723 856 q = q(u) = q(-4647714815446351873) 857 = 16798108731015832284940804142231733909759579603404752749028378864 858 165570215949 860 E: y^2 = x^3 + 2 862 Thus, E': y'^2 = x'^3 + (1, 16798108731015832284940804142231733909 863 889187121439069848933715426072753864722) 865 P = (-1,1) 866 = (1679810873101583228494080414223173390988918712143906984893371542 867 6072753864722, 1) 869 P' = [h](-i,1) = (P'x,P'y), where P'x and P'y are elements of Fp_2 871 P'x = 872 (2759930593230997547690248631365636073479225314645471320757910281 873 674905877291, 230161490788271857374524411062025673221233257170073 874 7603512907075120331574515) 876 P'y = 877 (9480765153516887970576068394945041092622478388406602889697250323 878 02618946458, 6663077446927392079224045631425291036692402823802663 879 947112913140121004068507) 881 g = is an element of Fp_12 given by 882 ((13070690801249658484759892809227642840919015841299984602661540278 883 97835831306, 362837632692008901334341187262873478716707643732273036 884 6913713646023905731503), 886 (352778753845190583740690941014710408681261806065247837729422038997 887 7928485580, 1390842049595369881149037040415050751861458203097739688 888 0797626940316305362787), 890 (148957391318235038979721383575910962973602682276093210989431526351 891 38088456200, 154193402372256829285477206567013233448625527219699948 892 30027125771243100988775), 894 (657015345250965363244058395947686331467494595330600581669861545909 895 8579995196, 9246328720071559688457720607053218330889647295590139338 896 238624175808225962795), 898 (151014665406602395528454680822744016147807484038495196740696804034 899 7117671512, 6964231951063075324378672955330091045708301556113455379 900 316967754148774004530), 902 (132001962407792355737177261139163922637454993559842085107451833663 903 5435672354, 9476335168658772594045570476784073542275866387029189317 904 560203959549876656582)) 906 SSK = 228064033978937665992889984775405287134161793365057496448735949 907 2611 909 SPK = (48893896735870064320433171153400539525040538030176968340812183 910 01282547698392, 15356945755932217528217084848811599775130985825038998 911 692965243198105904624442) 913 Suppose H(m) = 21668398097129279358779433271119370918865051659048528 914 91187078055077 916 Signature S = (Sx,Sy) where Sx and Sy are elements of Fp_2 and 918 Sx = (729051981497750473018989894592657769743437818459774775561224900 919 9723218090232, 683378059974468691645078542720737033649767207447427118 920 6472709797618120651615) 922 Sy = (157432174827386069860812184931399877857826328817373172771264166 923 63269695635786, 93427588866953969700345687463198658107209055412980315 924 33851535785638159753756) 926 For verification of the signature: 927 = g 929 Author's Address 931 Laura Hitt 932 6011 W Courtyard Dr. 933 Building 5, Suite 300 934 Austin, TX 78730 936 EMail: Lhitt@21CT.com