idnits 2.17.1 draft-martin-ibcs-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 2951. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2926. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2933. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2939. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (September 2007) is 6061 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 4346 (ref. 'TLS') (Obsoleted by RFC 5246) -- Obsolete informational reference (is this intentional?): RFC 3852 (ref. 'CMS') (Obsoleted by RFC 5652) == Outdated reference: A later version (-09) exists of draft-ietf-smime-ibearch-05 == Outdated reference: A later version (-10) exists of draft-ietf-smime-bfibecms-06 Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 X. Boyen 3 L. Martin 4 Internet Draft Voltage Security 5 Expires: March 2008 September 2007 7 Identity-Based Cryptography Standard (IBCS) #1: Supersingular 8 Curve Implementations of the BF and BB1 Cryptosystems 10 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents 15 that any applicable patent or other IPR claims of which he 16 or she is aware have been or will be disclosed, and any of 17 which he or she becomes aware will be disclosed, in 18 accordance with Section 6 of BCP 79. 20 Internet-Drafts are working documents of the Internet 21 Engineering Task Force (IETF), its areas, and its working 22 groups. Note that other groups may also distribute working 23 documents as Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of 26 six months and may be updated, replaced, or obsoleted by 27 other documents at any time. It is inappropriate to use 28 Internet-Drafts as reference material or to cite them other 29 than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/ietf/1id-abstracts.txt 34 The list of Internet-Draft Shadow Directories can be 35 accessed at 36 http://www.ietf.org/shadow.html 38 Abstract 40 This document describes the algorithms that implement Boneh- 41 Franklin and Boneh-Boyen Identity-based Encryption. This 42 document is in part based on IBCS #1 v2 of Voltage Security's 43 Identity-based Cryptography Standards (IBCS) documents, from 44 which some irrelevant sections have been removed to create the 45 content of this document. 47 Table of Contents 49 1. Introduction..............................................5 50 1.1. Sending a Message that is Encrypted Using IBE........6 51 1.1.1. Sender Obtains Recipient's Public Parameters....7 52 1.1.2. Construct and Send IBE-encrypted Message........8 53 1.2. Receiving and Viewing an IBE-encrypted Message.......8 54 1.2.1. Recipient Obtains Public Parameters from PPS....9 55 1.2.2. Recipient Obtains IBE Private Key from PKG.....10 56 1.2.3. Recipient Decrypts IBE-encrypted Message.......10 57 2. Notation and definitions.................................11 58 2.1. Notation............................................11 59 2.2. Definitions.........................................13 60 3. Basic elliptic curve algorithms..........................14 61 3.1. The group action in affine coordinates..............14 62 3.1.1. Implementation for type-1 curves...............14 63 3.2. Point multiplication................................16 64 3.3. Operations in Jacobian projective coordinates.......18 65 3.3.1. Implementation for type-1 curves...............18 66 3.4. Divisors on elliptic curves.........................20 67 3.4.1. Implementation in F_p^2 for type-1 curves......20 68 3.5. The Tate pairing....................................23 69 3.5.1. Tate pairing calculation.......................23 70 3.5.2. The Miller algorithm for type-1 curves.........23 71 4. Supporting algorithms....................................26 72 4.1. Integer range hashing...............................26 73 4.1.1. Hashing to an integer range....................26 74 4.2. Pseudo-random byte generation by hashing............27 75 4.2.1. Keyed pseudo-random bytes generator............27 76 4.3. Canonical encodings of extension field elements.....28 77 4.3.1. Encoding an extension element as a string......28 78 4.3.2. Type-1 curve implementation....................29 79 4.4. Hashing onto a subgroup of an elliptic curve........30 80 4.4.1. Hashing a string onto a subgroup of an elliptic 81 curve.................................................30 82 4.4.2. Type-1 curve implementation....................30 83 4.5. Bilinear mapping....................................31 84 4.5.1. Regular or modified Tate pairing...............31 85 4.5.2. Type-1 curve implementation....................32 86 4.6. Ratio of bilinear pairings..........................33 87 4.6.1. Ratio of regular or modified Tate pairings.....33 88 4.6.2. Type-1 curve implementation....................34 89 5. The Boneh-Franklin BF cryptosystem.......................34 90 5.1. Setup...............................................34 91 5.1.1. Master secret and public parameter generation..34 92 5.1.2. Type-1 curve implementation....................35 93 5.2. Public key derivation...............................37 94 5.2.1. Public key derivation from an identity and public 95 parameters............................................37 96 5.3. Private key extraction..............................37 97 5.3.1. Private key extraction from an identity, a set of 98 public parameters and a master secret.................37 99 5.4. Encryption..........................................38 100 5.4.1. Encrypt a session key using an identity and 101 public parameters.....................................38 102 5.5. Decryption..........................................40 103 5.5.1. Decrypt an encrypted session key using public 104 parameters, a private key.............................40 105 6. The Boneh-Boyen BB1 cryptosystem.........................41 106 6.1. Setup...............................................41 107 6.1.1. Generate a master secret and public parameters.41 108 6.1.2. Type-1 curve implementation....................42 109 6.2. Public key derivation...............................43 110 6.2.1. Derive a public key from an identity and public 111 parameters............................................43 112 6.3. Private key extraction..............................44 113 6.3.1. Extract a private key from an identity, public 114 parameters and a master secret........................44 115 6.4. Encryption..........................................45 116 6.4.1. Encrypt a session key using an identity and 117 public parameters.....................................45 118 6.5. Decryption..........................................47 119 6.5.1. Decrypt using public parameters and private key47 120 7. Test data................................................50 121 7.1. Algorithm 3.2.2 (PointMultiply).....................50 122 7.2. Algorithm 4.1.1 (HashToRange).......................50 123 7.3. Algorithm 4.5.1 (Pairing)...........................51 124 7.4. Algorithm 5.2.1 (BFderivePubl)......................51 125 7.5. Algorithm 5.3.1 (BFextractPriv).....................52 126 7.6. Algorithm 5.4.1 (BFencrypt).........................52 127 7.7. Algorithm 6.3.1 (BBextractPriv).....................53 128 7.8. Algorithm 6.4.1 (BBencrypt).........................54 129 8. ASN.1 module.............................................55 130 9. Security considerations..................................60 131 10. IANA considerations.....................................63 132 11. Acknowledgments.........................................63 133 12. References..............................................64 134 12.1. Normative references...............................64 135 12.2. Informative references.............................64 136 Authors' Addresses..........................................65 137 Intellectual Property Statement.............................65 138 Disclaimer of Validity......................................66 139 Copyright Statement.........................................66 140 Acknowledgment..............................................66 142 1. Introduction 144 This document provides a set of specifications for 145 implementing identity-based encryption (IBE) systems based on 146 bilinear pairings. Two cryptosystems are described: the IBE 147 system proposed by Boneh and Franklin (BF) [BF], and the IBE 148 system proposed by Boneh and Boyen (BB1) [BB1]. Fully secure 149 and practical implementations are described for each system, 150 comprising the core IBE algorithms as well as ancillary hybrid 151 components used to achieve security against active attacks. 152 These specifications are restricted to a family of 153 supersingular elliptic curves over finite fields of large 154 prime characteristic, referred to as "type-1" curves (see 155 Section 2.1). Implementations based on other types of curves 156 currently fall outside the scope of this document. 158 IBE is a public-key technology, but one which varies from 159 other public-key technologies is a slight yet significant way. 160 In particular, IBE keys are calculated instead of being 161 generated randomly, which leads to a different architecture 162 for a system using IBE than for a system using other public- 163 key technologies. An overview of these differences and how a 164 system using IBE works are given in [IBEARCH]. 166 Identity-based encryption (IBE) is a public-key encryption 167 technology that allows a public key to be calculated from an 168 identity and the corresponding private key to be calculated 169 from the public key. Calculation of both the public and 170 private keys in an IBE-based system can occur as needed, 171 resulting in just-in-time key material. This contrasts with 172 other public-key systems [P1363], in which keys are generated 173 randomly and distributed prior to secure communication 174 commencing. The ability to calculate a recipient's public key, 175 in particular, eliminates the need for the sender and receiver 176 in an IBE-based messaging system to interact with each other, 177 either directly or through a proxy such as a directory server, 178 before sending secure messages. 180 This document describes an IBE-based messaging system and how 181 the components of the system work together. The components 182 required for a complete IBE messaging system are the 183 following: 185 o A Private-key Generator (PKG). The PKG contains the 186 cryptographic material, known as a master secret, for 187 generating an individual's IBE private key. A PKG 188 accepts an IBE user's private key request and after 189 successfully authenticating them in some way returns 190 the IBE private key. 192 o A Public Parameter Server (PPS). IBE System 193 Parameters include publicly sharable cryptographic 194 material, known as IBE public parameters, and policy 195 information for the PKG. A PPS provides a well-known 196 location for secure distribution of IBE public 197 parameters and policy information for the IBE PKG. 199 A logical architecture would be to have a PKG/PPS per a name 200 space, such as a DNS zone. The organization that controls the 201 DNS zone would also control the PKG/PPS and thus the 202 determination of which PKG/PSS to use when creating public and 203 private keys for the organization's members. In this case the 204 PPS URI can be uniquely created by the form of the identity 205 that it supports. This architecture would make it clear which 206 set of public parameters to use and where to retrieve them for 207 a given identity. 209 IBE encrypted messages can use standard message formats, such 210 as the Cryptographic Message Syntax [CMS]. How to use IBE with 211 CMS is defined in [IBECMS]. 213 Note that IBE algorithms are used only for encryption, so if 214 digital signatures are required they will need to be provided 215 by an additional mechanism. 217 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL 218 NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 219 "OPTIONAL" in this document are to be interpreted as described 220 in [KEYWORDS]. 222 1.1. Sending a Message that is Encrypted Using IBE 224 In order to send an encrypted message, an IBE user must 225 perform the following steps: 227 1. Obtain the recipient's public parameters 229 The recipient's IBE public parameters allow the creation 230 of unique public and private keys. A user of an IBE 231 system is capable of calculating the public key of a 232 recipient after he obtains the public parameters for 233 their IBE system. Once the public parameters are 234 obtained, IBE-encrypted messages can be sent. 236 2. Construct and Send IBE-encrypted Message 238 All that is needed, in addition to the IBE public 239 parameters, is the recipient's identity in order to 240 generate their public key for use in encrypting messages 241 to them. When this identity is the same as the identity 242 that a message would be addressed to, then no more 243 information is needed from a user to send someone a 244 secure message then is needed to send them an unsecured 245 message. This is one of the major benefits of an IBE- 246 based secure messaging system. Examples of identities 247 can be an individual, group, or role identifiers. 249 1.1.1. Sender Obtains Recipient's Public Parameters 251 The sender of a message obtains the IBE public parameters that 252 he needs for calculating the IBE public key of the recipient 253 from a PPS that is hosted at a well-known URI. The IBE public 254 parameters contain all of the information that the sender 255 needs to create an IBE-encrypted message except for the 256 identity of the recipient. [IBEARCH] describes the URI where a 257 PPS is located, the format of IBE public parameters, and how 258 to obtain them. The URI from which users obtain IBE public 259 parameters MUST be authenticated in some way; PPS servers MUST 260 support TLS 1.1 [TLS] to satisfy this requirement and MUST 261 verify that the subject name in the server certificate matches 262 the URI of the PPS. [IBEARCH] also describes the way in which 263 identity formats are defined and a minimum interoperable 264 format that all PPSs and PKGs MUST support. This step is shown 265 below in Figure 1. 267 IBE Public Parameter Request 268 -----------------------------> 269 Sender PPS 270 <----------------------------- 271 IBE Public Parameters 273 Figure 1 Requesting IBE Public Parameters 275 The sender of an IBE-encrypted message selects the PPS and 276 corresponding PKG based on his local security policy. 277 Different PPSs may provide public parameters that specify 278 different IBE algorithms or different key strengths, for 279 example, or require the use of PKGs that require different 280 levels of authentication before granting IBE private keys. 282 1.1.2. Construct and Send IBE-encrypted Message 284 To IBE-encrypt a message, the sender chooses a content 285 encryption key (CEK) and uses it to encrypt his message and 286 then encrypts the CEK with the recipient's IBE public key (for 287 example, as described in [CMS]). This operation is shown below 288 in Figure 2. This document describes the algorithms needed to 289 implement two forms of IBE. [IBECMS] describes how to use the 290 Cryptographic Message Syntax (CMS) to encapsulate the 291 encrypted message along with the IBE information that the 292 recipient needs to decrypt the message. 294 CEK ----> Sender ----> IBE-encrypted CEK 296 ^ 297 | 298 | 300 Recipient's Identity 301 and IBE Public Parameters 303 Figure 2 Using an IBE Public-key Algorithm to Encrypt 305 1.2. Receiving and Viewing an IBE-encrypted Message 307 In order to read an encrypted message, a recipient of an IBE- 308 encrypted message parses the message (for example, as 309 described in [IBECMS]). This gives him the URI he needs to 310 obtain the IBE public parameters required to perform IBE 311 calculations as well as the identity that was used to encrypt 312 the message. Next the recipient must carry out the following 313 steps: 315 1. Obtain the recipient's public parameters 317 An IBE system's public parameters allow it to uniquely 318 create public and private keys. The recipient of an IBE- 319 encrypted message can decrypt an IBE-encrypted message 320 if he has both the IBE public parameters and the 321 necessary IBE private key. The PPS can also provide the 322 URI of the PKG where the recipient of an IBE-encrypted 323 message can obtain the IBE private keys. 325 2. Obtain the IBE private key from the PKG 327 To decrypt an IBE-encrypted message, in addition to the 328 IBE public parameters the recipient needs to obtain the 329 private key that corresponds to the public key that the 330 sender used. The IBE private key is obtained after 331 successfully authenticating to a private key generator 332 (PKG), a trusted third party that calculates private 333 keys for users. The recipient receives the IBE private 334 key over an HTTPS connection. The URI of a PKG MUST be 335 authenticated in some way; PKG servers MUST support TLS 336 1.1 [TLS] to satisfy this requirement. 338 3. Decrypt IBE-encrypted message 340 The IBE private key decrypts the CEK, which is then used 341 to decrypt encrypted message. 343 The PKG may allow users other than the intended recipient to 344 receive some IBE private keys. Giving a mail filtering 345 appliance permission to obtain IBE private keys on behalf of 346 users, for example, can allow the appliance to decrypt and 347 scan encrypted messages for viruses or other malicious 348 features. 350 1.2.1. Recipient Obtains Public Parameters from PPS 352 Before he can perform any IBE calculations related to the 353 message that he has received, the recipient of an IBE- 354 encrypted message needs to obtain the IBE public parameters 355 that were used in the encryption operation. This operation is 356 shown below in Figure 3. 358 IBE Public Parameter Request 359 -----------------------------> 360 Recipient PPS 361 <----------------------------- 362 IBE Public Parameters 364 Figure 3 Requesting IBE Public Parameters 366 1.2.2. Recipient Obtains IBE Private Key from PKG 368 To obtain an IBE private key, the recipient of an IBE- 369 encrypted message provides the IBE public key used to encrypt 370 the message and their authentication credentials to a PKG and 371 requests the private key that corresponds to the IBE public 372 key. Section 4 of this document defines the protocol for 373 communicating with a PKG as well as a minimum interoperable 374 way to authenticate to a PKG that all IBE implementations MUST 375 support. Because the security of IBE private keys is vital to 376 the overall security of an IBE system, IBE private keys MUST 377 be transported to recipients over a secure protocol. PKGs MUST 378 support TLS 1.1 [TLS] for transport of IBE private keys. This 379 operation is shown below in Figure 4. 381 IBE Private Key Request 382 ----------------------------> 383 Recipient PKG 384 <---------------------------- 385 IBE Private Key 387 Figure 4 Obtaining an IBE Private Key 389 1.2.3. Recipient Decrypts IBE-encrypted Message 391 After obtaining the necessary IBE private key, the recipient 392 uses that IBE private key and the corresponding IBE public 393 parameters to decrypt the CEK. This operation is shown below 394 in Figure 5. He then uses the CEK to decrypt the encrypted 395 message content (for example, as specified in [IBECMS]). 397 IBE-encrypted CEK ----> Recipient ----> CEK 399 ^ 400 | 401 | 403 IBE Private Key 404 and IBE Public Parameters 406 Figure 5 Using an IBE Public-key Algorithm to Decrypt 408 2. Notation and definitions 410 2.1. Notation 412 This section summarizes the notions and definitions regarding 413 identity-based cryptosystems on elliptic curves. The reader is 414 referred to [ECC] for the mathematical background and to [2, 415 3] regarding all notions pertaining to identity-based 416 encryption. 418 F_p denotes finite field of prime characteristic p; F_p^2 419 denote its extension field of degree 2. 421 Let E/F_p: y^2 = x^3 + a * x + b be an elliptic curve over 422 F_p. For an extension of degree 2, the curve E/F_p defines a 423 group (E(F_p^2), +), which is the additive group of points of 424 affine coordinates (x, y) in (F_p^2)^2 satisfying the curve 425 equation over F_p^2, with null element, or point at infinity, 426 denoted 0. 428 Let q be a prime such that E(F_p) has a cyclic subgroup G1' of 429 order q. 431 Let G1'' be a cyclic subgroup of E(F_p^2) of order q, and G2 432 be a cyclic subgroup of (F_p^2)* of order p. 434 Under these conditions, a mathematical construction known as 435 the Tate pairing provides an efficiently computable map e: G1' 436 x G1'' -> G2 that is linear in both arguments and believed 437 hard to invert [BF]. If an efficiently computable non-rational 438 endomorphism phi: G1' -> G1'' is available for the selected 439 elliptic curve on which the Tate pairing is computed, then we 440 can construct a function e': G1' x G1'' -> G2, defined as 441 e'(A, B) = e(A, phi(B)), called the modified Tate pairing. We 442 generically call a pairing either the Tate pairing e or the 443 modified Tate pairing e', depending on the chosen elliptic 444 curve used in a particular implementation. 446 The following additional notation is used throughout this 447 document. 449 p - A 512-bit to 7680-bit prime which is the order of the 450 finite field F_p. 452 F_p - The base finite field of order p over which the elliptic 453 curve of interest E/F_p is defined. 455 #G - The size of the set G. 457 F* - The multiplicative group of the non-zero elements in the 458 field F; e.g., (F_p)* is the multiplicative group of the 459 finite field F_p. 461 E/F_p - The equation of an elliptic curve over the field F_p, 462 which, when p is neither 2 nor 3, is of the form E/F_p: y^2 = 463 x^3 + a * x + b, for specified a, b in F_p. 465 0 - The null element of any additive group of points on an 466 elliptic curve, also called the point at infinity. 468 E(F_p) - The additive group of points of affine coordinates 469 (x, y), with x, y in F_p, that satisfy the curve equation 470 E/F_p, including the point at infinity 0. 472 q - A 160-bit to 512-bit prime that is the order of the cyclic 473 subgroup of interest in E(F_p). 475 k - The embedding degree of the cyclic subgroup of order q in 476 E(F_p). For type-1 curves this is always equal to 2. 478 F_p^2 - The extension field of degree 2 of the field F_p. 480 E(F_p^2) - The group of points of affine coordinates in F_p^2 481 satisfying the curve equation E/F_p, including the point at 482 infinity 0. 484 Z_p - The additive group of integers modulo p. 486 lg - The base 2 logarithm function, so that 2^lg(x) = x. 488 The term "object identifier" will be abbreviated "OID." 490 A Solinas prime is a prime of the form 2^a (+/-) 2^b (+/-) 1. 492 The following conventions are assumed for curve operations. 494 Point addition - If A and B are two points on a curve E, their 495 sum is denoted A + B. 497 Point multiplication - If A is a point on a curve, and n an 498 integer, the result of adding A to itself a total of n times 499 is denoted [n]A. 501 The following class of elliptic curves is exclusively 502 considered for pairing operations in the present version of 503 this document, which are referred to as "type-1" curves. 505 Type-1 curves - The class of curves of type 1 is defined as 506 the class of all elliptic curves of equation E/F_p: y^2 = x^3 507 + 1 for all primes p congruent to 11 modulo 12. This class 508 forms a subclass of the class of supersingular curves. These 509 curves satisfy #E(F_p) = p + 1, and the p points (x, y) in 510 E(F_p) \ {0} have the property that x = (y^2 - 1)^(1/3) (mod 511 p). Type-1 curves always have an embedding degree k = 2. 513 Groups of points on type-1 curves are plentiful and easy to 514 construct by random selection of a prime p of the appropriate 515 form. Therefore, rather than to standardize upon a small set 516 of common values of p, it is henceforth assumed that all type- 517 1 curves are freshly generated at random for the given 518 cryptographic application (an example of such generation will 519 be given in Algorithm 5.1.2 (BFsetup1) or Algorithm 6.1.2 520 (BBsetup1)). Implementations based on different classes of 521 curves are currently unsupported. 523 We assume that the following concrete representations of 524 mathematical objects are used. 526 Base field elements - The p elements of the base field F_p are 527 represented directly using the integers from 0 to p - 1. 529 Extension field elements - The p^2 elements of the extension 530 field F_p^2 are represented as ordered pairs of elements of 531 F_p. An ordered pair (a_0, a_1) is interpreted as the complex 532 number a_0 + a_1 * i, where i^2 = -1. This allows operations 533 on elements of F_p^2 to be implemented as follows. Suppose 534 that a = (a_0, a_1) and b = (b_0, b_1) are elements of F_p^2. 535 Then a + b = ((a_0 + b_0)(mod p), (a_1 + b_1)(mod p)) and a * 536 b = ((a_1 * b_1 - a_0 * b_0)(mod p), (a_1 * b_0 + a_0 * 537 b_1)(mod p)). 539 Elliptic curve points - Points in E(F_p^2) with the point P = 540 (x, y) in F_p^2 x F_p^2 satisfying the curve equation E/F_p. 541 Points not equal to 0 are internally represented using the 542 affine coordinates (x, y), where x and y are elements of 543 F_p^2. 545 2.2. Definitions 547 The following terminology is used to describe an IBE system. 549 Public parameters - The public parameters are set of common 550 system-wide parameters generated and published by the private 551 key server (PKG). 553 Master secret - The master secret is the master key generated 554 and privately kept by the key server, and used to generate the 555 private keys of the users. 557 Identity - An identity an arbitrary string, usually a human- 558 readable unambiguous designator of a system user, possibly 559 augmented with a time stamp and other attributes. 561 Public key - A public key is a string that is algorithmically 562 derived from an identity. The derivation may be performed by 563 anyone, autonomously. 565 Private key - A private key is issued by the key server to 566 correspond to a given identity (and the public key that 567 derives from it), under the published set of public 568 parameters. 570 Plaintext - A plaintext is an unencrypted representation, or 571 in the clear, of any block of data to be transmitted securely. 572 For the present purposes, plaintexts are typically session 573 keys, or sets of session keys, for further symmetric 574 encryption and authentication purposes. 576 Ciphertext - A ciphertext is an encrypted representation of 577 any block of data, including a plaintext, to be transmitted 578 securely. 580 3. Basic elliptic curve algorithms 582 This section describes algorithms for performing all needed 583 basic arithmetic operations on elliptic curves. The 584 presentation is specialized to the type of curves under 585 consideration for simplicity of implementation. General 586 algorithms may be found in [ECC]. 588 3.1. The group action in affine coordinates 590 3.1.1. Implementation for type-1 curves 592 Algorithm 3.1.1 (PointDouble1): adds a point to itself on a 593 type-1 elliptic curve. 595 Input: 597 o A point A in E(F_p^2), with A = (x, y) or 0 599 o An elliptic curve E/F_p: y^2 = x^3 + 1 601 Output: 603 o The point [2]A = A + A 605 Method: 607 1. If A = 0 or y = 0, then return 0 609 2. Let lambda = (3 * x^2) / (2 * y) 611 3. Let x' = lambda^2 - 2 * x 613 4. Let y' = (x - x') * lambda - y 615 5. Return (x', y') 617 Algorithm 3.1.2 (PointAdd1): adds two points on a type-1 618 elliptic curve. 620 Input: 622 o A point A in E(F_p^2), with A = (x_A, y_A) or 0 624 o A point B in E(F_p^2), with B = (x_B, y_B) or 0 626 o An elliptic curve E/F_p: y^2 = x^3 + 1 628 Output: 630 o The point A + B 632 Method: 634 1. If A = 0, return B 636 2. If B = 0, return A 638 3. If x_A = x_B: 640 (a) If y_A = -y_B, return 0 642 (b) Else return [2]A computed using Algorithm 3.1.1 643 (PointDouble1) 644 4. Otherwise: 646 (a) Let lambda = (y_B - y_A) / (x_B - x_A) 648 (b) Let x' = lambda^2 - x_A - x_B 650 (c) Let y' = (x_A - x') * lambda - y_A 652 (d) Return (x', y') 654 3.2. Point multiplication 656 Algorithm 3.2.1 (SignedWindowDecomposition): computes the 657 signed m-ary window representation of a positive integer 658 [ECC]. 660 Input: 662 o An integer k > 0, where k has the binary representation k = 663 {Sum(k_j * 2^j, for j = 0 to l} where each k_j is either 0 664 or 1 and k_l = 0 666 o An integer window bit-size r > 0 668 Output: 670 o An integer d and the unique d-element sequence {(b_i, e_i), 671 for i = 0 to d - 1} such that k = {Sum(b_i * 2^(e_i), for i 672 = 0 to d - 1}, each b_i = +/- 2^j for some 0 < j <= r - 1 673 and each e_i is a non-negative integer 675 Method: 677 1. Let d = 0 679 2. Let j = 0 681 3. While j <= l, do: 683 (a) If k_j = 0 then: 685 i. Let j = j + 1 687 (b) Else: 689 i. Let t = min{l, j + r - 1} 690 ii. Let h_d = (k_t, k_(t - 1), ..., k_j) (base 2) 692 iii. If h_d > 2^(r - 1) then: 694 A. Let b_d = h_d - 2^r 696 B. Increment the number (k_l, k_(l-1),...,k_j) (base 697 2) by 1 699 iv. Else: 701 A. Let b_d = h_d 703 v. Let e_d = j 705 vi. Let d = d + 1 707 vii. Let j = t + 1 709 4. Return d and the sequence {(b_0, e_0), ..., (b_(d - 1), 710 e_(d - 1))} 712 Algorithm 3.2.2 (PointMultiply): scalar multiplication on an 713 elliptic curve using the signed m-ary window method. 715 Input: 717 o A point A in E(F_p^2) 719 o An integer l > 0 721 o An elliptic curve E/F_p: y^2 = x^3 + a * x + b 723 Output: 725 o The point [l]A 727 Method: 729 1. (Window decomposition) 731 (a) Let r > 0 be an integer (fixed) bit-wise window size, 732 e.g., r = 5 734 (b) Let l' = l where l = {Sum(l_j * 2^j), for j = 0 to 735 len_l} is the binary expansion of l, where len_l = 736 Ceiling(lg(l)) 737 (c) Compute (d, {(b_i, e_i), for i = 0 to d - 1} = 738 SignedWindowDecomposition(l, r), the signed 2^r-ary window 739 representation of l using Algorithm 3.2.1 740 (SignedWindowDecomposition) 742 2. (Precomputation) 744 (a) Let A_1 = A 746 (b) Let A_2 = [2]A, using Algorithm 3.1.1 (PointDouble1) 748 (c) For i = 1 to 2^(r - 2) - 1, do: 750 i. Let A_(2 * i + 1) = A_(2 * i - 1) + A_2 using 751 Algorithm 3.1.2 (PointAdd1) 753 (d) Let Q = A_(b_(d - 1)) 755 3. Main loop 757 (a) For i = d - 2 to 0 by -1, do: 759 i. Let Q = [2^(e_(i + 1) - e_i)]Q, using repeated 760 applications of Algorithm 3.1.1 (PointDouble1) e_(i + 1) - e_i 761 times 763 ii. If b_i > 0 then: 765 A. Let Q = Q + A_(b_i) using Algorithm 3.1.2 766 (PointAdd1) 768 iii. Else: 770 A. Let Q = Q - A_(-(b_i)) using Algorithm 3.1.2 771 (PointAdd1) 773 (b) Calculate Q = [2^(e_0)]Q using repeated applications of 774 Algorithm 3.1.1 (PointDouble1) e_0 times 776 4. Return Q. 778 3.3. Operations in Jacobian projective coordinates 780 3.3.1. Implementation for type-1 curves 782 Algorithm 3.3.1 (ProjectivePointDouble1): adds a point to 783 itself in Jacobian projective coordinates for type-1 curves. 785 Input: 787 o A point (x, y, z) = A in E(F_p^2) in Jacobian projective 788 coordinates 790 o An elliptic curve E/F_p: y^2 = x^3 + 1 792 Output: 794 o The point [2]A in Jacobian projective coordinates 796 Method: 798 1. If z = 0 or y = 0, return (0, 1, 0) = 0, otherwise: 800 2. Let lambda_1 = 3 * x^2 802 3. Let z' = 2 * y * z 804 4. Let lambda_2 = y^2 806 5. Let lambda_3 = 4 * lambda_2 * x 808 6. Let x' = lambda_1^2 - 2 * lambda_3 810 7. Let lambda_4 = 8 * lambda_2^2 812 8. Let y' = lambda_1 * (lambda_3 - x') - lambda_4 814 9. Return (x', y', z') 816 Algorithm 3.3.2 (ProjectivePointAccumulate1): adds a point in 817 affine coordinates to an accumulator in Jacobian projective 818 coordinates, for type-1 curves. 820 Input: 822 o A point (x_A, y_A, z_A) = A in E(F_p^2) in Jacobian 823 projective coordinates 825 o A point (x_B, y_B) = B in E(F_p^2) \ {0} in affine 826 coordinates 828 o An elliptic curve E/F_p: y^2 = x^3 + 1 830 Output: 832 o The point A + B in Jacobian projective coordinates 834 Method: 836 1. If z_A = 0 return (x_B, y_B, 1) = B, otherwise: 838 2. Let lambda_1 = z_A^2 840 3. Let lambda_2 = lambda_1 * x_B 842 4. Let lambda_3 = x_A - lambda_2 844 5. If lambda_3 = 0 then return (0, 1, 0), otherwise: 846 6. Let lambda_4 = lambda_3^2 848 7. Let lambda_5 = lambda_1 * y_B * z_A 850 8. Let lambda_6 = lambda_4 - lambda_5 852 9. Let lambda_7 = x_A + lambda_2 854 10. Let lambda_8 = y_A + lambda_5 856 11. Let x' = lambda_6^2 - lambda_7 * lambda_4 858 12. Let lambda_9 = lambda_7 * lambda_4 - 2 * x' 860 13. Let y' = (lambda_9 * lambda_6 - 862 lambda_8 * lambda_3 * lambda_4) / 2 864 14. Let z' = lambda_3 * z_A 866 15. Return (x', y', z') 868 3.4. Divisors on elliptic curves 870 3.4.1. Implementation in F_p^2 for type-1 curves 872 Algorithm 3.4.1 (EvalVertical1): evaluates the divisor of a 873 vertical line on a type-1 elliptic curve. 875 Input: 877 o A point B in E(F_p^2) with B != 0 878 o A point A in E(F_p) 880 o A description of a type-1 elliptic curve E/F_p 882 Output: 884 o An element of F_p^2 that is the divisor of the vertical 885 line going through A evaluated at B 887 Method: 889 1. Let r = x_B - x_A 891 2. Return r 893 Algorithm 3.4.2 (EvalTangent1): evaluates the divisor of a 894 tangent on a type-1 elliptic curve. 896 Input: 898 o A point B in E(F_p^2) with B != 0 900 o A point A in E(F_p) 902 o A description of a type-1 elliptic curve E/F_p 904 Output: 906 o An element of F_p^2 that is the divisor of the line tangent 907 to A evaluated at B 909 Method: 911 1. (Special cases) 913 (a) If A = 0 return 1 915 (b) If y_A = 0 return EvalVertical1(B, A) using Algorithm 916 3.4.1 (EvalVertical1) 918 2. (Line computation) 920 (a) Let a = -3 * (x_A)^2 922 (b) Let b = 2 * y_A 924 (c) Let c = -b * y_A - a * x_A 926 3. (Evaluation at B) 928 (a) Let r = a * x_B + b * y_B + c 930 4. Return r 932 Algorithm 3.4.3 (EvalLine1): evaluates the divisor of a line 933 on a type-1 elliptic curve. 935 Input: 937 o A point B in E(F_p^2) with B != 0 939 o Two points A', A'' in E(F_p) 941 o A description of a type-1 elliptic curve E/F_p 943 Output: 945 o An element of F_p^2 that is the divisor of the line going 946 through A' and A'' evaluated at B 948 Method: 950 1. (Special cases) 952 (a) If A' = 0 return EvalVertical1(B, A'') using Algorithm 953 3.4.1 (EvalVertical1) 955 (b) If A'' = 0 return EvalVertical1(B, A') using Algorithm 956 3.4.1 (EvalVertical1) 958 (c) If A' = -A'' return EvalVertical1(B, A') using 959 Algorithm 3.4.1 (EvalVertical1) 961 (d) If A' = A'' return EvalTangent1(B, A') using Algorithm 962 3.4.2 (EvalTangent1) 964 2. (Line computation) 966 (a) Let a = y_A' - y_A'' 968 (b) Let b = x_A'' - x_A' 970 (c) Let c = -b * y_A' - a * x_A' 972 3. (Evaluation at B) 973 (a) Let r = a * x_B + b * y_B + c 975 4. Return r 977 3.5. The Tate pairing 979 3.5.1. Tate pairing calculation 981 Algorithm 3.5.1 (Tate): computes the Tate pairing on an 982 elliptic curve. 984 Input: 986 o A point A of order q in E(F_p) 988 o A point B of order q in E(F_p^2) 990 o A description of an elliptic curve E/F_p such that E(F_p) 991 and E(F_p^2) have a subgroup of order q 993 Output: 995 o The value e(A, B) in F_p^2, computed using the Miller 996 algorithm 998 Method: 1000 1. For a type-1 curve E, execute Algorithm 3.5.2 1001 (TateMillerSolinas) 1003 3.5.2. The Miller algorithm for type-1 curves 1005 Algorithm 3.5.2 (TateMillerSolinas): computes the Tate pairing 1006 on a type-1 elliptic curve. 1008 Input: 1010 o A point A of order q in E(F_p) 1012 o A point B of order q in E(F_p^2) 1014 o A description of a type-1 supersingular elliptic curve 1015 E/F_p such that E(F_p) and E(F_p^2) have a subgroup of 1016 Solinas prime order q where q = 2^a + s * 2^b + c, where c 1017 and s are limited to the values +/-1 1019 Output: 1021 o The value e(A, B) in F_p^2, computed using the Miller 1022 algorithm 1024 Method: 1026 1. (Initialization) 1028 (a) Let v_num = 1 in F_p^2 1030 (b) Let v_den = 1 in F_p^2 1032 (c) Let V = (x_V , y_V , z_V ) = (x_A, y_A, 1) in (F_p)^3, 1033 being the representation of (x_A, y_A) = A using Jacobian 1034 projective coordinates 1036 (d) Let t_num = 1 in F_p^2 1038 (e) Let t_den = 1 in F_p^2 1040 2. (Calculation of the (s * 2^b) contribution) 1042 (a) (Repeated doublings) For n = 0 to b - 1: 1044 i. Let t_num = t_num^2 1046 ii. Let t_den = t_den^2 1048 iii. Let t_num = t_num * EvalTangent1(B, (x_V / z_V^2, 1049 y_V / z_V^3)) using Algorithm 3.4.2 (EvalTangent1) 1051 iv. Let V = (x_V , y_V , z_V ) = [2]V using Algorithm 1052 3.3.1 (ProjectivePointDouble1) 1054 v. Let t_den = t_den * EvalVertical1(B, (x_V / z_V^2, 1055 y_V / z_V^3)using Algorithm 3.4.1 (EvalVertical1) 1057 (b) (Normalization) 1059 i. Let V_b = (x_(V_b) , y_(V_b)) 1061 = (x_V / z_V^2, s * y_V / z_V^3) in (F_p)^2, 1063 resulting in a point V_b in E(F_p) 1065 (c) (Accumulation) Selecting on s: 1067 i. If s = -1: 1069 A. Let v_num = v_num * t_den 1071 B. Let v_den = v_den * t_num * EvalVertical1(B, (x_V 1072 / z_V^2, y_V / z_V^3))) using Algorithm 3.4.1 (EvalVertical1) 1074 ii. If s = 1: 1076 A. Let v_num = v_num * t_num 1078 B. Let v_den = v_den * t_den 1080 3. (Calculation of the 2^a contribution) 1082 (a) (Repeated doublings) For n = b to a - 1: 1084 i. Let t_num = t_num^2 1086 ii. Let t_den = t_den^2 1088 iii. Let t_num = t_num * EvalTangent1(B, (x_V / z_V^2, 1089 y_V / z_V^3))) using Algorithm 3.4.2 (EvalTangent1) 1091 iv. Let V = (x_V , y_V , z_V) = [2]V using Algorithm 1092 3.3.1 (ProjectivePointDouble1) 1094 v. Let t_den = t_den * EvalVertical1(B, (x_V / z_V^2, 1095 y_V / z_V^3))) using Algorithm 3.4.1 (EvalVertical1) 1097 (b) (Normalization) 1099 i. Let V_a = (x_(V_a) , y_(V_a)) = 1101 (x_V /z_V^2, s * x_V / z_V^3) in (F_p)^2, 1103 resulting in a point V_a in E(F_p) 1105 (c) (Accumulation) 1107 i. Let v_num = v_num * t_num 1109 ii. Let v_den = v_den * t_den 1111 4. (Correction for the (s * 2^b) and (c) contributions) 1113 (a) Let v_num = v_num * EvalLine1(B, V_a, V_b) using 1114 Algorithm 3.4.3 (EvalLine1) 1115 (b) Let v_den = v_den * EvalVertical1(B, V_a + V_b) using 1116 Algorithm 3.4.1 (EvalVertical1) 1118 (c) If c = -1 then: 1120 i. Let v_den = v_den * EvalVertical1(B, A) using 1121 Algorithm 3.4.1 (EvalVertical1) 1123 5. (Correcting exponent) 1125 (a) Let eta = (p^2 - 1) / q 1127 6. (Final result) 1129 (a) Return (v_num / v_den)^eta 1131 4. Supporting algorithms 1133 This section describes a number of supporting algorithms for 1134 encoding and hashing. 1136 4.1. Integer range hashing 1138 4.1.1. Hashing to an integer range 1140 HashToRange(s, n, hashfcn) takes a string s, an integer n and 1141 a cryptographic hash function hashfcn as input, and returns an 1142 integer in the range 0 to n - 1 by cryptographic hashing. The 1143 input n MUST be less than 2^(hashlen) where hashlen is the 1144 number of octets comprising the output of the hash function 1145 hashfcn. Based on Merkle's method for hashing [MERKLE], which 1146 is provably as secure as the underlying hash function hashfcn. 1148 Algorithm 4.1.1 (HashToRange): cryptographically hashes 1149 strings to integers in a range. 1151 Input: 1153 o A string s of length |s| octets 1155 o A positive integer n represented as Ceiling(lg(n) / 8) 1156 octets. 1158 o A cryptographic hash function hashfcn 1160 Output: 1162 o A positive integer v in the range 0 to n - 1 1164 Method: 1166 1. Let hashlen be the number of octets comprising the output 1167 of hashfcn 1169 2. Let v_0 = 0 1171 3. Let h_0 = 0x00...00, a string of null octets with a length 1172 of hashlen 1174 4. For i = 1 to 2, do: 1176 (a) Let t_i = h_(i - 1) || s, which is the (|s| + hashlen)- 1177 octet string concatenation of the strings h_(i - 1) and s 1179 (b) Let h_i = hashfcn(t_i), which is a hashlen-octet string 1180 resulting from the hash algorithm hashfcn on the input t_i 1182 (c) Let a_i = Value(h_i) be the integer in the range 0 to 1183 256^hashlen - 1 denoted by the raw octet string h_i 1184 interpreted in the unsigned big endian convention 1186 (d) Let v_i = 256^hashlen * v_(i - 1) + a_i 1188 5. Let v = v_l (mod n) 1190 4.2. Pseudo-random byte generation by hashing 1192 4.2.1. Keyed pseudo-random bytes generator 1194 HashBytes(b, p, hashfcn) takes an integer b, a string p and a 1195 cryptographic hash function hashfcn as input, and returns a b- 1196 octet pseudo-random string r as output. The value of b MUST be 1197 less than or equal to the number of bytes in the output of 1198 hashfcn. Based on Merkle's method for hashing [MERKLE], which 1199 is provably as secure as the underlying hash function hashfcn. 1201 Algorithm 4.2.1 (HashBytes): keyed cryptographic pseudo-random 1202 bytes generator. 1204 Input: 1206 o An integer b 1208 o A string p 1209 o A cryptographic hash function hashfcn 1211 Output: 1213 o A string r comprising b octets 1215 Method: 1217 1. Let hashlen be the number of octets comprising the output 1218 of hashfcn 1220 2. Let K = hashfcn(p) 1222 2. Let h_0 = 0x00...00, a string of null octets with a length 1223 of hashlen 1225 3. Let l = Ceiling(b / hashlen) 1227 4. For each i in 1 to l do: 1229 (a) Let h_i = hashfcn(h_(i - 1)) 1231 (b) Let r_i = hashfcn(h_i || K), where h_i || K is the (2 * 1232 hashlen)-octet concatenation of h_i and K 1234 5. Let r = LeftmostOctets(b, r_1 || ... || r_l), i.e., r is 1235 formed as the concatenation of the r_i, truncated to the 1236 desired number of octets 1238 4.3. Canonical encodings of extension field elements 1240 4.3.1. Encoding an extension element as a string 1242 Canonical(p, k, o, v) takes an element v in F_p^k, and returns 1243 a canonical octet-string of fixed length representing v. The 1244 parameter o MUST be either 0 or 1, and specifies the ordering 1245 of the encoding. 1247 Algorithm 4.3.1 (Canonical): encodes elements of an extension 1248 field F_p^2 as strings. 1250 Input: 1252 o An element v in F_p^2 1254 o A description of F_p^2 1255 o A ordering parameter o, either 0 or 1 1257 Output: 1259 o A fixed-length string s representing v 1261 Method: 1263 1. For a type-1 curve, execute Algorithm 4.3.2 (Canonical1) 1265 4.3.2. Type-1 curve implementation 1267 Canonical1(p, o, v) takes an element v in F_p^2 and returns a 1268 canonical representation of v as a octet-string s of fixed 1269 size. The parameter o MUST be either 0 or 1, and specifies the 1270 ordering of the encoding. 1272 Algorithm 4.3.2 (Canonical1): canonically represents elements 1273 of an extension field F_p^2. 1275 Input: 1277 o An element v in F_p^2 1279 o A description of p, where p is congruent to 3 modulo 4 1281 o A ordering parameter o, either 0 or 1 1283 Output: 1285 o A string s of size 2 * Ceiling(lg(p) / 8) octets 1287 Method: 1289 1. Let l = Ceiling(lg(p) / 8), the number of octets needed to 1290 represent integers in Z_p 1292 2. Let v = a + b * i, where i^2 = -1. 1294 3. Let a_(256^l) be the big-endian zero-padded fixed-length 1295 octet-string representation of a in Z_p 1297 4. Let b_(256^l) be the big-endian zero-padded fixed-length 1298 octet-string representation of b in Z_p 1300 5. Depending on the choice of ordering o: 1302 (a) If o = 0, then let s = a_(256^l) || b_(256^l), which is 1303 the concatenation of a_(256^l) followed by b_(256^l) 1305 (b) If o = 1, then let s = b_(256^l) || a_(256^l), which is 1306 the concatenation of b_(256^l) followed by a_(256^l) 1308 6. Return s 1310 4.4. Hashing onto a subgroup of an elliptic curve 1312 4.4.1. Hashing a string onto a subgroup of an elliptic curve 1314 HashToPoint(E, p, q, id, hashfcn) takes an identity string id 1315 and the description of a subgroup of prime order q in E(F_p) 1316 or E(F_p^2) and a cryptographic hash function hashfcn and 1317 returns a point Q_id of order q in E(F_p) or E(F_p^2). 1319 Algorithm 4.4.1 (HashToPoint): cryptographically hashes 1320 strings to points on elliptic curves. 1322 Input: 1324 o An elliptic curve E 1326 o A prime p 1328 o A prime q 1330 o A string id 1332 o A cryptographic hash function hashfcn 1334 Output: 1336 o A point Q_id = (x, y) of order q n E(F_p) 1338 Method: 1340 1. For a type-1 curve E, execute Algorithm 4.4.2 1341 (HashToPoint1) 1343 4.4.2. Type-1 curve implementation 1345 HashToPoint1(p, q, id, hashfcn) takes an identity string id 1346 and the description of a subgroup of order q in E(F_p) where 1347 E: y^2 = x^3 + 1 with p congruent to 11 modulo 12, and returns 1348 a point Q_id of order q in E(F_p) that is calculated using the 1349 cryptgraphic has function hashfcn. The parameters p, q and 1350 hashfcn MUST be part of a valid set of public parameters as 1351 defined in section 5.1.2 or section 6.1.2. 1353 Algorithm 4.4.2 (HashToPoint1). Cryptographically hashes 1354 strings to points on type-1 curves. 1356 Input: 1358 o A prime p 1360 o A prime q 1362 o A string id 1364 o A cryptographic hash function hashfcn 1366 Output: 1368 o A point Q_id of order q in E(F_p) 1370 Method: 1372 1. Let y = HashToRange(id, p, hashfcn), using Algorithm 4.1.1 1373 (HashToRange), an element of F_p 1375 2. Let x = (y^2 - 1)^((2 * p - 1) / 3) modulo p, an element of 1376 F_p 1378 3. Let Q' = (x, y), a non-zero point in E(F_p) 1380 4. Let Q = [(p + 1) / q ]Q', a point of order q in E(F_p) 1382 4.5. Bilinear mapping 1384 4.5.1. Regular or modified Tate pairing 1386 Pairing(E, p, q, A, B) takes two points A and B, both of order 1387 q, and, in the type-1 case, returns the modified pairing e'(A, 1388 phi(B)) in F_p^2 where A and B are both in E(F_p). 1390 Algorithm 4.5.1 (Pairing): computes the regular or modified 1391 Tate pairing depending on the curve type. 1393 Input: 1395 o A description of an elliptic curve E/F_p such that E(F_p) 1396 and E(F_p^2) have a subgroup of order q 1398 o Two points A and B of order q in E(F_p) or E(F_p^2) 1400 Output: 1402 o On supersingular curves, the value of e'(A, B) in F_p^2 1403 where A and B are both in E(F_p) 1405 Method: 1407 1. If E is a type-1 curve, execute Algorithm 4.5.2 (Pairing1) 1409 4.5.2. Type-1 curve implementation 1411 Algorithm 4.5.2 (Pairing1): computes the modified Tate pairing 1412 on type-1 curves. The values of p and q MUST be part of a 1413 valid set of public parameters as defined in section 5.1.2 or 1414 section 6.1.2. 1416 Input: 1418 o A curve E/F_p: y^2 = x^3 + 1 where p is congruent to 11 1419 modulo 12 and E(F_p) has a subgroup of order q 1421 o Two points A and B of order q in E(F_p) 1423 Output: 1425 o The value of e'(A, B) = e(A, phi(B)) in F_p^2 1427 Method: 1429 1. Compute B' = phi(B), as follows: 1431 (a) Let (x, y) in F_p x F_p be the coordinates of B in 1432 E(F_p) 1434 (b) Let zeta = (a_zeta , b_zeta), where a_zeta = (p - 1) / 1435 2 and b_zeta = 3^((p + 1) / 4) (mod p), an element of F_p^2 1437 (c) Let x' = x * zeta in F_p^2 1439 (d) Let B' = (x', y) in F_p^2 x F_p 1441 2. Compute the Tate pairing e(A, B') = e(A, phi(B)) in F_p^2 1442 using the Miller method, as in Algorithm 3.5.1 (Tate) 1443 described in Section 3.5 1445 4.6. Ratio of bilinear pairings 1447 4.6.1. Ratio of regular or modified Tate pairings 1449 PairingRatio(E, p, q, A, B, C, D) takes four points as input, 1450 and computes the ratio of the two bilinear pairings, 1451 Pairing(E, p, q, A, B) / Pairing(E, p, q, C, D), or, 1452 equivalently, the product, Pairing(E, p, q, A, B) * Pairing(E, 1453 p, q, C, -D). 1455 On type-1 curves, all four points are of order q in E(F_p), 1456 and the result is an element of order q in the extension field 1457 F_p^2 . 1459 The motivation for this algorithm is that the ratio of two 1460 pairings can be calculated more efficiently than by computing 1461 each pairing separately and dividing one into the other, since 1462 certain calculations that would normally appear in each of the 1463 two pairings can be combined and carried out at once. Such 1464 calculations include the repeated doublings in steps 2(a)i, 1465 2(a)ii, 3(a)i, and 3(a)ii of Algorithm 3.5.2 1466 (TateMillerSolinas), as well as the final exponentiation in 1467 step 6(a) of Algorithm 3.5.2 (TateMillerSolinas). 1469 Algorithm 4.6.1 (PairingRatio): computes the ratio of two 1470 regular or modified Tate pairings depending on the curve type. 1472 Input: 1474 o A description of an elliptic curve E/F_p such that E(F_p) 1475 and E(F_p^2) have a subgroup of order q 1477 o Four points A, B, C, and D, of order q in E(F_p) or 1478 E(F_p^2) 1480 Output: 1482 o On supersingular curves, the value of e'(A, B) / e'(C, D) 1483 in F_p^2 where A, B, C, D are all in E(F_p) 1485 Method: 1487 1. If E is a type-1 curve, execute Algorithm 4.6.2 1488 (PairingRatio1) 1490 4.6.2. Type-1 curve implementation 1492 Algorithm 4.6.2 (PairingRatio1). Computes the ratio of two 1493 modified Tate pairings on type-1 curves. The values of p and q 1494 MUST be part of a valid set of public parameters as defined in 1495 section 5.1.2 or section 6.1.2. 1497 Input: 1499 o A curve E/F_p: y^2 = x^3 + 1, where p is congruent to 11 1500 modulo 12 and E(F_p) has a subgroup of order q 1502 o Four points A, B, C, and D, of order q in E(F_p) 1504 Output: 1506 o The value of e'(A, B) / e'(C, D) = e(A, phi(B)) / e(C, 1507 phi(D)) = e(A, phi(B)) * e(-C, phi(D)), in F_p^2 1509 Method: 1511 1. The step-by-step description of the optimized algorithm is 1512 omitted in this normative specification 1514 The correct result can always be obtained, although more 1515 slowly, by computing the product of pairings Pairing1(E, p, q, 1516 A, B) * Pairing1(E, p, q, -C, D) by using two invocations of 1517 Algorithm 4.5.2 (Pairing1). 1519 5. The Boneh-Franklin BF cryptosystem 1521 This chapter describes the algorithms constituting the Boneh- 1522 Franklin identity-based cryptosystem as described in [BF]. 1524 5.1. Setup 1526 5.1.1. Master secret and public parameter generation 1528 Algorithm 5.1.1 (BFsetup): randomly selects a master secret 1529 and the associated public parameters. 1531 Input: 1533 o A integer version number 1534 o A security parameter n (MUST take values either 1024, 2048, 1535 3072, 7680, 15360) 1537 Output: 1539 o A set of public parameters (version, E, p, q, P, P_pub, 1540 hashfcn) 1542 o A corresponding master secret s 1544 Method: 1546 1. Depending on the selected type t: 1548 (a) If version = 2, then execute Algorithm 5.1.2 (BFsetup1) 1550 2. The resulting master secret and public parameters are 1551 separately encoded as per the application protocol 1552 requirements 1554 5.1.2. Type-1 curve implementation 1556 BFsetup1 takes a security parameter n as input. For type-1 1557 curves, the scale of n corresponds to the modulus bit-size 1558 believed [BF] of comparable security in the classical Diffie- 1559 Hellman or RSA public-key cryptosystems. 1561 Algorithm 5.1.2 (BFsetup1): establishes a master secret and 1562 public parameters for type-1 curves. 1564 Input: 1566 o A security parameter n which MUST be either 1024, 2048, 1567 3072, 7680 or 15360 1569 Output: 1571 o A set of common public parameters (version, p, q, P, Ppub, 1572 hashfcn) 1574 o A corresponding master secret s 1576 Method: 1578 1. Set the version to version = 2. 1580 2. Determine the subordinate security parameters n_p and n_q 1581 as follows: 1583 (a) If n = 1024 then let n_p = 512, n_q = 160, hashfcn = 1584 1.3.14.3.2.26 (SHA-1 [SHA]. 1586 (b) If n = 2048 then let n_p = 1024, n_q = 224, hashfcn = 1587 2.16.840.1.101.3.4.2.4 (SHA-224 [SHA]). 1589 (c) If n = 3072 then let n_p = 1536, n_q = 256, hashfcn = 1590 2.16.840.1.101.3.4.2.1 (SHA-256 [SHA]). 1592 (d) If n = 7680 then let n_p = 3840, n_q = 384, hashfcn = 1593 2.16.840.1.101.3.4.2.2 (SHA-384 [SHA]). 1595 (e) If n = 15360 then let n_p = 7680, n_q = 512, hashfcn = 1596 2.16.840.1.101.3.4.2.3 (SHA-512 [SHA]). 1598 3. Construct the elliptic curve and its subgroup of interest, 1599 as follows: 1601 (a) Select an arbitrary n_q-bit Solinas prime q 1603 (b) Select a random integer r such that p = 12 * r * q - 1 1604 is an n_p-bit prime 1606 4. Select a point P of order q in E(F_p), as follows: 1608 (a) Select a random point P' of coordinates (x', y') on the 1609 curve E/F_p: y^2 = x^3 + 1 (mod p) 1611 (b) Let P = [12 * r]P' 1613 (c) If P = 0, then start over in step 3a 1615 5. Determine the master secret and the public parameters as 1616 follows: 1618 (a) Select a random integer s in the range 2 to q - 1 1620 (b) Let P_pub = [s]P 1622 6. (version, E, p, q, P, P_pub) are the public parameters 1623 where E: y^2 = x^3 + 1 is represented by the OID 1624 2.16.840.1.114334.1.1.1.1. 1626 7. The integer s is the master secret 1628 5.2. Public key derivation 1630 5.2.1. Public key derivation from an identity and public 1631 parameters 1633 BFderivePubl takes an identity string id and a set of public 1634 parameters, and returns a point Q_id. The public parameters 1635 used MUST be a valid set of public parameters as defined by 1636 section 5.1.2. 1638 Algorithm 5.2.1 (BFderivePubl): derives the public key 1639 corresponding to an identity string. 1641 Input: 1643 o An identity string id 1645 o A set of public parameters (version, E, p, q, P, P_pub, 1646 hashfcn) 1648 Output: 1650 o A point Q_id of order q in E(F_p) or E(F_p^2) 1652 Method: 1654 1. Q_id = HashToPoint(E, p, q, id, hashfcn), using Algorithm 1655 4.4.1 (HashToPoint) 1657 5.3. Private key extraction 1659 5.3.1. Private key extraction from an identity, a set of public 1660 parameters and a master secret 1662 BFextractPriv takes an identity string id, and a set of public 1663 parameters and corresponding master secret, and returns a 1664 point S_id. The public parameters used MUST be a valid set of 1665 public parameters as defined by section 5.1.2. 1667 Algorithm 5.3.1 (BFextractPriv): extracts the private key 1668 corresponding to an identity string. 1670 Input: 1672 o An identity string id 1673 o A set of public parameters (version, E, p, q, P, P_pub, 1674 hashfcn) 1676 Output: 1678 o A point S_id of order q in E(F_p). 1680 Method: 1682 1. Let Q_id = HashToPoint(E, p, q, id, hashfcn) using 1683 Algorithm 4.4.1 (HashToPoint) 1685 2. Let S_id = [s]Q_id 1687 5.4. Encryption 1689 5.4.1. Encrypt a session key using an identity and public 1690 parameters 1692 BFencrypt takes three inputs: a public parameter block, an 1693 identity id, and a plaintext m. The plaintext MUST be a random 1694 symmetric session key. The public parameters used MUST be a 1695 valid set of public parameters as defined by section 5.1.2. 1697 Algorithm 5.4.1 (BFencrypt): encrypts a random session key for 1698 an identity string. 1700 Input: 1702 o A plaintext string m of size |m| octets 1704 o A recipient identity string id 1706 o A set of public parameters (version, E, p, q, P, P_pub, 1707 hashfcn) 1709 Output: 1711 o A ciphertext tuple (U, V, W) in E(F_p) x {0, ... , 1712 255}^hashlen x {0, ... , 255}^|m| 1714 Method: 1716 1. Let hashlen be the length of the output of the 1717 cryptographic hash function hashfcn from the public 1718 parameters. 1720 2. Q_id = HashToPoint(E, p, q, id, hashfcn), using Algorithm 1721 4.4.1 (HashToPoint), which results in a point of order q in 1722 E(F_p). 1724 3. Select a random hashlen-bit vector rho, represented as 1725 (hashlen / 8)-octet string in big-endian convention 1727 4. Let t = hashfcn(m), a hashlen-octet string resulting from 1728 applying the hashfcn algorithm to the input m 1730 5. Let l = HashToRange(rho || t, q, hashfcn), an integer in 1731 the range 0 to q - 1 resulting from applying Algorithm 4.1.1 1732 (HashToRange) to the (2 * hashlen)-octet concatenation of rho 1733 and t 1735 6. Let U = [l]P, which is a point of order q in E(F_p) 1737 7. Let theta = Pairing(E, p, q, P_pub, Q_id), which is an 1738 element of the extension field F_p^2 obtained using the 1739 modified Tate pairing of Algorithm 4.5.1 (Pairing) 1741 8. Let theta' = theta^l, which is theta raised to the power of 1742 l in F_p^2 1744 9. Let z = Canonical(p, k, 0, theta'), using Algorithm 4.3.1 1745 (Canonical), the result of which is a canonical string 1746 representation of theta' 1748 10. Let w = hashfcn(z) using the hashfcn hashing algorithm, 1749 the result of which is a hashlen-octet string 1751 11. Let V = w XOR rho, which is the hashlen-octet long bit- 1752 wise XOR of w and rho 1754 12. Let W = HashBytes(|m|, rho, hashfcn) XOR m, which is the 1755 bit-wise XOR of m with the first |m| octets of the pseudo- 1756 random bytes produced by Algorithm 4.2.1 (HashBytes) with seed 1757 rho 1759 13. The ciphertext is the triple (U, V, W) 1761 5.5. Decryption 1763 5.5.1. Decrypt an encrypted session key using public parameters, 1764 a private key 1766 BFdecrypt takes three inputs: a public parameter block, a 1767 private key block key, and a ciphertext parsed as (U', V', 1768 W'). The public parameters used MUST be a valid set of public 1769 parameters as defined by section 5.1.2. 1771 Algorithm 5.5.1 (BFdecrypt): decrypts an encrypted session key 1772 using a private key. 1774 Input: 1776 o A private key point S_id of order q in E(F_p) 1778 o A ciphertext triple (U, V, W) in E(F_p) x {0, ... , 1779 255}^hashlen x {0, ... , 255}* 1781 o A set of public parameters (version, E, p, q, P, P_pub, 1782 hashfcn) 1784 Output: 1786 o A decrypted plaintext m, or an invalid ciphertext flag 1788 Method: 1790 1. Let hashlen be the length of the output of the hash 1791 function hashlen measured in octets 1793 2. Let theta = Pairing(E, p ,q, U, S_id) by applying the 1794 modified Tate pairing of Algorithm 4.5.1 (Pairing) 1796 3. Let z = Canonical(p, k, 0, theta) using Algorithm 4.3.1 1797 (Canonical), the result of which is a canonical string 1798 representation of theta 1800 4. Let w = hashfcn(z), using the hashfcn hashing algorithm, 1801 the result of which is a hashlen-octet string 1803 5. Let rho = w XOR V, the bit-wise XOR of w and V 1805 6. Let m = HashBytes(|W|, rho, hashfcn) XOR W, which is the 1806 bit-wise XOR of m with the first |W| octets of the pseudo- 1807 random bytes produced by Algorithm 4.2.1 (HashBytes) with seed 1808 rho 1810 7. Let t = hashfcn(m) using the hashfcn algorithm 1812 8. Let l = HashToRange(rho || t, q, hashfcn) using Algorithm 1813 4.1.1 (HashToRange) on the (2 * hashlen)-octet concatenation 1814 of rho and t 1816 9. Verify that U = [l]P: 1818 (a) If this is the case, then the decrypted plaintext m is 1819 returned 1821 (b) Otherwise, the ciphertext is rejected and no plaintext 1822 is returned 1824 6. The Boneh-Boyen BB1 cryptosystem 1826 This section describes the algorithms constituting the first 1827 of the two Boneh-Boyen identity-based cryptosystems proposed 1828 in [BB1]. The description follows the practical implementation 1829 given in [BB1]. 1831 6.1. Setup 1833 6.1.1. Generate a master secret and public parameters 1835 Algorithm 6.1.1 (BBsetup). Randomly selects a set of master 1836 secrets and the associated public parameters. 1838 Input: 1840 o An integer version number 1842 o An integer security parameter n (MUST take values either 1843 1024, 2048, 3072, 7680, or 15360. 1845 Output: 1847 o A set of public parameters 1849 o A corresponding master secret 1851 Method: 1853 1. Depending on the version: 1855 (a) If version = 2, then execute Algorithm 6.1.2 (BBsetup1) 1857 6.1.2. Type-1 curve implementation 1859 BBsetup1 takes a security parameter n as input. For type-1 1860 curves, n corresponds to the modulus bit-size believed [BF] of 1861 comparable security in the classical Diffie-Hellman or RSA 1862 public-key cryptosystems. For this implementation n MUST be 1863 one of 1024, 2048, 3072, 7680 and 15360, which correspond to 1864 the equivalent bit security levels of 80, 112, 128, 192 and 1865 256 bits respectively. 1867 Algorithm 6.1.2 (BBsetup1): randomly establishes a master 1868 secret and public parameters for type-1 curves. 1870 Input: 1872 o A security parameter n, either 1024, 2048, 3072, 7680, or 1873 15360 1875 Output: 1877 o A set of public parameters (version, k, E, p, q, P, P_1, 1878 P_2, P_3, v, hashfcn) 1880 o A corresponding triple of master secrets (alpha, beta, 1881 gamma) 1883 Method: 1885 1. Determine the subordinate security parameters n_p and n_q 1886 as follows: 1888 (a) If n = 1024 then let n_p = 512, n_q = 160, hashfcn = 1889 1.3.14.3.2.26 (SHA-1 [SHA] 1891 (b) If n = 2048 then let n_p = 1024, n_q = 224, hashfcn = 1892 2.16.840.1.101.3.4.2.4 (SHA-224 [SHA]) 1894 (c) If n = 3072 then let n_p = 1536, n_q = 256, hashfcn = 1895 2.16.840.1.101.3.4.2.1 (SHA-256 [SHA]) 1897 (d) If n = 7680 then let n_p = 3840, n_q = 384, hashfcn = 1898 2.16.840.1.101.3.4.2.2 (SHA-384 [SHA]) 1900 (e) If n = 15360 then let n_p = 7680, n_q = 512, hashfcn = 1901 2.16.840.1.101.3.4.2.3 (SHA-512 [SHA]) 1902 2. Construct the elliptic curve and its subgroup of interest 1903 as follows: 1905 (a) Select a random n_q-bit Solinas prime q 1907 (b) Select a random integer r such that p = 12 * r * q - 1 1908 is an n_p-bit prime 1910 3. Select a point P of order q in E(F_p), as follows: 1912 (a) Select a random point P' of coordinates (x', y') on the 1913 curve E/F_p: y^2 = x^3 + 1 (mod p) 1915 (b) Let P = [12 * r]P' 1917 (c) If P = 0, then start over in step 3a 1919 4. Determine the master secret and the public parameters as 1920 follows: 1922 (a) Select three random integers alpha, beta, gamma, each 1923 of them in the range 1 to q - 1 1925 (b) Let P_1 = [alpha]P 1927 (c) Let P_2 = [beta]P 1929 (d) Let P_3 = [gamma]P 1931 (e) Let v = Pairing(E, p, q, P_1, P_2), which is an element 1932 of the extension field F_p^2 obtained using the modified Tate 1933 pairing of Algorithm 3.5.1 (Pairing) 1935 5. (version, E, p, q, P, P_1, P_2, P_3, v, hashfcn) are the 1936 public parameters 1938 6. (alpha, beta, gamma) constitute the master secret 1940 6.2. Public key derivation 1942 6.2.1. Derive a public key from an identity and public parameters 1944 Takes an identity string id and a set of public parameters, 1945 and returns an integer h_id. The public parameters used MUST 1946 be a valid set of public parameters as defined by section 1947 section 6.1.2. 1949 Algorithm 6.2.1 (BBderivePubl): derives the public key 1950 corresponding to an identity string. The public parameters 1951 used MUST be a valid set of public parameters as defined by 1952 section section 6.1.2. 1954 Input: 1956 o An identity string id 1958 o A set of common public parameters (version, k, E, p, q, P, 1959 P_1, P_2, P_3, v, hashfcn) 1961 Output: 1963 o An integer h_id modulo q 1965 Method: 1967 1. Let h_id = HashToRange(id, q, hashfcn), using Algorithm 1968 4.1.1 (HashToRange) 1970 6.3. Private key extraction 1972 6.3.1. Extract a private key from an identity, public parameters 1973 and a master secret 1975 BBextractPriv takes an identity string id, and a set of public 1976 parameters and corresponding master secrets, and returns a 1977 private key consisting of two points D_0 and D_1. The public 1978 parameters used MUST be a valid set of public parameters as 1979 defined by section section 6.1.2. 1981 Algorithm 6.3.1 (BBextractPriv): extracts the private key 1982 corresponding to an identity string. 1984 Input: 1986 o An identity string id 1988 o A set of public parameters (version, k, E, p, q, P, P_1, 1989 P_2, P_3, v, hashfcn) 1991 Output: 1993 o A pair of points (D_0, D_1), each of which has order q in 1994 E(F_p) 1996 Method: 1998 1. Select a random integer r in the range 1 to q - 1 2000 2. Calculate the point D_0 as follows: 2002 (a) Let hid = HashToRange(id, q, hashfcn), using Algorithm 2003 4.1.1 (HashToRange) 2005 (b) Let y = alpha * beta + r * (alpha * h_id + gamma) in 2006 F_q 2008 (c) Let D_0 = [y]P 2010 3. Calculate the point D_1 as follows: 2012 (a) Let D_1 = [r]P 2014 4. The pair of points (D_0, D_1) constitutes the private key 2015 for id 2017 6.4. Encryption 2019 6.4.1. Encrypt a session key using an identity and public 2020 parameters 2022 BBencrypt takes three inputs: a set of public parameters, an 2023 identity id, and a plaintext m. The plaintext MUST be a random 2024 session key. The public parameters used MUST be a valid set of 2025 public parameters as defined by section section 6.1.2. 2027 Algorithm 6.4.1 (BBencrypt): encrypts a session key for an 2028 identity string. 2030 Input: 2032 o A plaintext string m of size |m| octets 2034 o A recipient identity string id 2036 o A set of public parameters (version, k, E, p, q, P, P_1, 2037 P_2, P_3, v, hashfcn) 2039 Output: 2041 o A ciphertext tuple (u, C_0, C_1, y) in F_q x E(F_p) x 2042 E(F_p) x {0, ... , 255}^|m| 2044 Method: 2046 1. Select a random integer s in the range 1 to q - 1 2048 2. Let w = v^s, which is v raised to the power of s in F_p^2, 2049 the result is an element of order q in F_p^2 2051 3. Calculate the point C_0 as follows: 2053 (a) Let C_0 = [s]P 2055 4. Calculate the point C_1 as follows: 2057 (a) Let _hid = HashToRange(id, q, hashfcn), using Algorithm 2058 4.1.1 (HashToRange) 2060 (b) Let y = s * h_id in F_q 2062 (c) Let C_1 = [y]P_1 + [s]P_3 2064 5. Obtain canonical string representations of certain 2065 elements: 2067 (a) Let psi = Canonical(p, k, 1, w) using Algorithm 4.3.1 2068 (Canonical), the result of which is a canonical octet-string 2069 representation of w 2071 (b) Let l = Ceiling(lg(p) / 8), the number of octets needed 2072 to represent integers in F_p, and represent each of these F_p 2073 elements as a big-endian zero-padded octet-string of fixed 2074 length l: 2076 (x_0)_(256^l) to represent the x coordinate of C_0 2078 (y_0)_(256^l) to represent the y coordinate of C_0 2080 (x_1)_(256^l) to represent the x coordinate of C_1 2082 (y_1)_(256^l) to represent the y coordinate of C_1 2084 6. Encrypt the message m into the string y as follows: 2086 (a) Compute an encryption key h_0 as a two-pass hash of w 2087 via its representation psi: 2089 i. Let zeta = hashfcn(psi), using the hashing algorithm 2090 hashfcn 2091 ii. Let xi = hashfcn(zeta || psi), using the hashing 2092 algorithm hashfcn 2094 iii. Let h' = xi || zeta, the concatenation of the 2095 previous two hashfcn outputs 2097 (b) Let y = HashBytes(|m|, h', hashfcn) XOR m, which is the 2098 bit-wise XOR of m with the first |m| octets of the pseudo- 2099 random bytes produced by Algorithm 3.2.1 (HashBytes) with seed 2100 h' 2102 7. Create the integrity check tag u as follows: 2104 (a) Compute a one-time pad h'' as a dual-pass hash of the 2105 representation of (w, C_0, C_1, y): 2107 i. Let sigma = (y_1)_(256^l) || (x_1)_(256^l) || 2108 (y_0)_(256^l) || (x_0)_(256^l) || y || psi be the 2109 concatenation of y and the five indicated strings in the 2110 specified order 2112 ii. Let eta = hashfcn(sigma), using the hashing 2113 algorithm hashfcn 2115 iii. Let mu = hashfcn(eta || sigma), using the hashfcn 2116 hashing algorithm 2118 iv. Let h'' = mu || eta, the concatenation of the 2119 previous two outputs of hashfcn 2121 (b) Build the tag u as the encryption of the integer s with 2122 the one-time pad h'': 2124 i. Let rho = HashToRange(h'', q, hashfcn) to get an 2125 integer in Z_q 2127 ii. Let u = s + rho (mod q) 2129 8. The complete ciphertext is given by the quadruple (u, C_0, 2130 C_1, y) 2132 6.5. Decryption 2134 6.5.1. Decrypt using public parameters and private key 2136 BBdecrypt takes three inputs: a set of public parameters 2137 (version, k, E, p, q, P, P_1, P_2, P_3, v, hashfcn), a private 2138 key (D_0, D_1), and a ciphertext (u, C_0, C_1, y). It outputs 2139 a message m, or signals an error if the ciphertext is invalid 2140 for the given key. The public parameters used MUST be a valid 2141 set of public parameters as defined by section section 6.1.2. 2143 Algorithm 6.5.1 (BBdecrypt): decrypts a ciphertext using 2144 public parameters and a private key. 2146 Input: 2148 o A private key given as a pair of points (D_0, D_1) of order 2149 q in E(F_p) 2151 o A ciphertext quadruple (u, C_0, C_1, y) in Z_q x E(F_p) x 2152 E(F_p) x {0, ... , 255}* 2154 o A set of public parameters (version, k, E, p, q, P, P_1, 2155 P_2, P_3, v, hashfcn) 2157 Output: 2159 o A decrypted plaintext m, or an invalid ciphertext flag 2161 Method: 2163 1. Let w = PairingRatio(E, p, q, C_0, D_0, C_1, D_1), which 2164 computes the ratio of two Tate pairings (modified, for type-1 2165 curves) as specified in Algorithm 4.6.1 (PairingRatio) 2167 2. Obtain canonical string representations of certain 2168 elements: 2170 (a) Let psi = Canonical(p, k, 1, w), using Algorithm 4.3.1 2171 (Canonical); the result is a canonical octet-string 2172 representation of w 2174 (b) Let l = Ceiling(lg(p) / 8), the number of octets needed 2175 to represent integers in F_p, and represent each of these F_p 2176 elements as a big-endian zero-padded octet-string of fixed 2177 length l: 2179 (x_0)_(256^l) to represent the x coordinate of C_0 2181 (y_0)_(256^l) to represent the y coordinate of C_0 2183 (x_1)_(256^l) to represent the x coordinate of C_1 2184 (y_1)_(256^l) to represent the y coordinate of C_1 2186 3. Decrypt the message m from the string y as follows: 2188 (a) Compute the decryption key h' as a dual-pass hash of w 2189 via its representation psi: 2191 i. Let zeta = hashfcn(psi), using the hashing algorithm 2192 hashfcn 2194 ii. Let xi = hashfcn(zeta || psi), using the hashing 2195 algorithm hashfcn 2197 iii. Let h' = xi || zeta, the concatenation of the 2198 previous two hashfcn outputs 2200 (b) Let m = HashBytes(|y|, h', hashfcn)_XOR y, which is the 2201 bit-wise XOR of y with the first |y| octets of the pseudo- 2202 random bytes produced by Algorithm 4.2.1 (HashBytes) with 2203 seed h' 2205 4. Obtain the integrity check tag u as follows: 2207 (a) Recover the one-time pad h'' as a dual-pass hash of the 2208 representation of (w, C_0, C_1, y): 2210 i. Let sigma = (y_1)_(256^l) || (x_1)_(256^l) || 2211 (y_0)_(256^l) || (x_0)_(256^l) || y || psi be the 2212 concatenation of y and the five indicated strings in the 2213 specified order 2215 ii. Let eta = hashfcn(sigma) using the hashing algorithm 2216 hashfcn 2218 iii. Let mu = hashfcn(eta || sigma), using the hashing 2219 algorithm hashfcn 2221 iv. Let h'' = mu || eta, the concatenation of the 2222 previous two hashfcn outputs 2224 (b) Unblind the encryption randomization integer s from the 2225 tag u using h'': 2227 i. Let rho = HashToRange(h'', q, hashfcn) to get an 2228 integer in Z_q 2230 ii. Let s = u - rho (mod q) 2232 5. Verify the ciphertext consistency according to the 2233 decrypted values: 2235 (a) Test whether the equality w = v^s holds 2237 (b) Test whether the equality C_0 = [s]P holds 2239 6. Adjudication and final output: 2241 (a) If either of the tests performed in step 5 fails, the 2242 ciphertext is rejected, and no decryption is output 2244 (b) Otherwise, i.e., when both tests performed in step 5 2245 succeed, the decrypted message is output 2247 7. Test data 2249 The following data can be used to verify the correct operation 2250 of selected algorithms that are defined in this document. 2252 7.1. Algorithm 3.2.2 (PointMultiply) 2254 Input: 2256 q = 0xfffffffffffffffffffffffffffbffff 2258 p = 0xbffffffffffffffffffffffffffcffff3 2260 E/F_p: y^2 = x^3 + 1 2262 A = (0x489a03c58dcf7fcfc97e99ffef0bb4634, 2263 0x510c6972d795ec0c2b081b81de767f808) 2265 l = 0xb8bbbc0089098f2769b32373ade8f0daf 2267 Output: 2269 [l]A = (0x073734b32a882cc97956b9f7e54a2d326, 2270 0x9c4b891aab199741a44a5b6b632b949f7) 2272 7.2. Algorithm 4.1.1 (HashToRange) 2274 Input: 2276 s = 2277 54:68:69:73:20:41:53:43:49:49:20:73:74:72:69:6e:67:20:77:69:74 2278 :68:6f:75:74:20:6e:75:6c:6c:2d:74:65:72:6d:69:6e:61:74:6f:72 2279 ("This ASCII string without null-terminator") 2281 n = 0xffffffffffffffffffffefffffffffffffffffff 2283 hashfcn = 1.3.14.3.2.16 (SHA-1) 2285 Output: 2287 v = 0x79317c1610c1fc018e9c53d89d59c108cd518608 2289 7.3. Algorithm 4.5.1 (Pairing) 2291 q = 0xfffffffffffffffffffffffffffbffff 2293 p = 0xbffffffffffffffffffffffffffcffff3 2295 E/F_p: y^2 = x^3 + 1 2297 A = (0x489a03c58dcf7fcfc97e99ffef0bb4634, 2298 0x510c6972d795ec0c2b081b81de767f808) 2300 B = (0x40e98b9382e0b1fa6747dcb1655f54f75, 2301 0xb497a6a02e7611511d0db2ff133b32a3f) 2303 Output: 2305 e'(A, B) = (0x8b2cac13cbd422658f9e5757b85493818, 2306 0xbc6af59f54d0a5d83c8efd8f5214fad3c) 2308 7.4. Algorithm 5.2.1 (BFderivePubl) 2310 Input: 2312 id = 6f:42:62 ("Bob") 2314 version = 2 2316 p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb 2318 q = 0xffffffffffffffffffffffeffffffffffff 2320 P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d, 2321 0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab) 2323 P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108, 2324 0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f) 2325 Output: 2327 Q_id = (0x22fa1207e0d19e1a4825009e0e88e35eb57ba79391498f59, 2328 0x982d29acf942127e0f01c881b5ec1b5fe23d05269f538836) 2330 7.5. Algorithm 5.3.1 (BFextractPriv) 2332 Input: 2334 s = 0x749e52ddb807e0220054417e514742b05a0 2336 version = 2 2338 p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb 2340 q = 0xffffffffffffffffffffffeffffffffffff 2342 P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d, 2343 0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab) 2345 P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108, 2346 0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f) 2348 Output: 2350 Q_id = (0x8212b74ea75c841a9d1accc914ca140f4032d191b5ce5501, 2351 0x950643d940aba68099bdcb40082532b6130c88d317958657) 2353 7.6. Algorithm 5.4.1 (BFencrypt) 2355 (Note that the following values can also be used to test 2356 Algorithm 5.5.1 (BFdecrypt)) 2358 Input: 2360 m = 48:69:20:74:68:65:72:65:21 ("Hi there!") 2362 id = 6f:42:62 ("Bob") 2364 version = 2 2366 p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb 2368 q = 0xffffffffffffffffffffffeffffffffffff 2370 P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d, 2371 0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab) 2372 P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108, 2373 0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f) 2375 Output: 2377 Using the random value rho = 2378 0xed5397ff77b567ba5ecb644d7671d6b6f2082968, we get the 2379 following output: 2381 U = 2382 (0x1b5f6c461497acdfcbb6d6613ad515430c8b3fa23b61c585e9a541b199e 2383 2a6cb, 2384 0x9bdfbed1ae664e51e3d4533359d733ac9a600b61048a7d899104e826a0ec 2385 4fa4) 2387 V = 2388 e0:1d:ad:81:32:6c:b1:73:af:c2:8d:72:2e:7a:32:1a:7b:29:8a:aa 2390 W = f9:04:ba:40:30:e9:ce:6e:ff 2392 7.7. Algorithm 6.3.1 (BBextractPriv) 2394 Inputs: 2396 alpha = 0xa60c395285ded4d70202c8283d894bad4f0 2398 beta = 0x48bf012da19f170b13124e5301561f45053 2400 gamma = 0x226fba82bc38e2ce4e28e56472ccf94a499 2402 version = 2 2404 p = 0x91bbe2be1c8950750784befffffffffffff6e441d41e12fb 2406 q = 0xfffffffffbfffffffffffffffffffffffff 2408 P = (0x13cc538fe950411218d7f5c17ae58a15e58f0877b29f2fe1, 2409 0x8cf7bab1a748d323cc601fabd8b479f54a60be11e28e18cf) 2411 P_1 = (0x0f809a992ed2467a138d72bc1d8931c6ccdd781bedc74627, 2412 0x11c933027beaaf73aa9022db366374b1c68d6bf7d7a888c2) 2414 P_2 = (0x0f8ac99a55e575bf595308cfea13edb8ec673983919121b0, 2415 0x3febb7c6369f5d5f18ee3ea6ca0181448a4f3c4f3385019c) 2417 P_3 = (0x2c10b43991052e78fac44fdce639c45824f5a3a2550b2a45, 2418 0x6d7c12d8a0681426a5bbc369c9ef54624356e2f6036a064f) 2419 v = (0x38f91032de6847a89fc3c83e663ed0c21c8f30ce65c0d7d3, 2420 0x44b9aa10849cc8d8987ef2421770a340056745da8b99fba2) 2422 id = 6f:42:62 ("Bob") 2424 Output: 2426 Using the random value r = 2427 0x695024c25812112187162c08aa5f65c7a2c, we get the following 2428 output: 2430 D_0 = (0x3264e13feeb7c506493888132964e79ad657a952334b9e53, 2431 0x3eeaefc14ba1277a1cd6fdea83c7c882fe6d85d957055c7b) 2433 D_1 = (0x8d7a72ad06909bb3bb29b67676d935018183a905e7e8cb18, 2434 0x2b346c6801c1db638f270af915a21054f16044ab67f6c40e) 2436 7.8. Algorithm 6.4.1 (BBencrypt) 2438 (Note that the following values can also be used to test 2439 Algorithm 5.5.1 (BFdecrypt)) 2441 Input: 2443 m = 48:69:20:74:68:65:72:65:21 ("Hi there!") 2445 id = 6f:42:62 ("Bob") 2447 version = 2 2449 E: y^2 = x^3 + 1 2451 p = 0x91bbe2be1c8950750784befffffffffffff6e441d41e12fb 2453 q = 0xfffffffffbfffffffffffffffffffffffff 2455 P = (0x13cc538fe950411218d7f5c17ae58a15e58f0877b29f2fe1, 2456 0x8cf7bab1a748d323cc601fabd8b479f54a60be11e28e18cf) 2458 P_1 = (0x0f809a992ed2467a138d72bc1d8931c6ccdd781bedc74627, 2459 0x11c933027beaaf73aa9022db366374b1c68d6bf7d7a888c2) 2461 P_2 = (0x0f8ac99a55e575bf595308cfea13edb8ec673983919121b0, 2462 0x3febb7c6369f5d5f18ee3ea6ca0181448a4f3c4f3385019c) 2464 P_3 = (0x2c10b43991052e78fac44fdce639c45824f5a3a2550b2a45, 2465 0x6d7c12d8a0681426a5bbc369c9ef54624356e2f6036a064f) 2466 v = (0x38f91032de6847a89fc3c83e663ed0c21c8f30ce65c0d7d3, 2467 0x44b9aa10849cc8d8987ef2421770a340056745da8b99fba2) 2469 hashfcn = 1.3.14.3.2.26 (SHA-1) 2471 Output: 2473 Using the random value s = 2474 0x62759e95ce1af248040e220263fb41b965e, we get the following 2475 output: 2477 u = 0xad1ebfa82edf0bcb5111e9dc08ff0737c68 2479 C_0 = (0x79f8f35904579f1aaf51897b1e8f1d84e1c927b8994e81f9, 2480 0x1cf77bb2516606681aba2e2dc14764aa1b55a45836014c62) 2482 C_1 = (0x410cfeb0bccf1fa4afc607316c8b12fe464097b20250d684, 2483 0x8bb76e7195a7b1980531b0a5852ce710cab5d288b2404e90) 2485 y = 82:a6:42:b9:bb:e9:82:c4:57 2487 8. ASN.1 module 2489 This section defines the ASN.1 module for the encodings 2490 discussed in this document. 2492 IBCS { joint-iso-itu-t(2) country(16) us(840) organization(1) 2493 identicrypt(114334) ibcs(1) module(5) version(1) } 2495 DEFINITIONS IMPLICIT TAGS ::= BEGIN 2497 -- 2498 -- Identity-based cryptography standards (IBCS): 2499 -- supersingular curve implementations of 2500 -- the BF and BB1 cryptosystems 2501 -- 2502 -- This version only supports IBE using 2503 -- type-1 curves, i.e., the curve y^2 = x^3 + 1. 2504 -- 2506 ibcs OBJECT IDENTIFIER ::= { 2507 joint-iso-itu-t(2) country(16) us(840) organization(1) 2508 identicrypt(114334) ibcs(1) 2509 } 2511 -- 2512 -- IBCS1 2513 -- 2514 -- IBCS1 defines the algorithms used to implement IBE 2515 -- 2517 ibcs1 OBJECT IDENTIFIER ::= { 2518 ibcs ibcs1(1) 2519 } 2521 -- 2522 -- An elliptic curve is specified by an OID. 2523 -- A type1curve is defined by the equation y^2 = x^3 + 1. 2524 -- 2526 type1curve OBJECT IDENTIFIER ::= { 2527 ibcs1 curve-types(1) type1-curve(1) 2528 } 2530 -- 2531 -- Supporting types 2532 -- 2534 -- 2535 -- Encoding of a point on an elliptic curve E/F_p 2536 -- An FpPoint can either represent an element of 2537 -- F_p^2 or an element of (F_p)^2. 2539 FpPoint ::= SEQUENCE { 2540 x INTEGER, 2541 y INTEGER 2542 } 2544 -- 2545 -- The following hash functions are supported: 2546 -- 2547 -- SHA-1 2548 -- 2549 -- id-sha1 OBJECT IDENTIFIER ::= { 2550 -- iso(1) identified-organization(3) oiw(14) 2551 -- secsig(3) algorithms(2) hashAlgorithmIdentifier(26) 2552 -- } 2553 -- 2554 -- SHA-224 2555 -- 2556 -- id-sha224 OBJECT IDENTIFIER ::= { 2557 -- joint-iso-itu-t(2)country(16) us(840) 2558 -- organization(1) gov(101) 2559 -- csor(3) nistAlgorithm(4) hashAlgs(2) sha224(4) 2560 -- } 2561 -- 2562 -- SHA-256 2563 -- 2564 -- id-sha256 OBJECT IDENTIFIER ::= { 2565 -- joint-iso-itu-t(2)country(16) us(840) 2566 -- organization(1) gov(101) 2567 -- csor(3) nistAlgorithm(4) hashAlgs(2) sha256(1) 2568 -- } 2569 -- 2570 -- SHA-384 2571 -- 2572 -- id-sha384 OBJECT IDENTIFIER ::= { 2573 -- joint-iso-itu-t(2)country(16) us(840) 2574 -- organization(1) gov(101) 2575 -- csor(3) nistAlgorithm(4) hashAlgs(2) sha384(2) 2576 -- } 2577 -- 2578 -- SHA-512 2579 -- 2580 -- id-sha512 OBJECT IDENTIFIER ::= { 2581 -- joint-iso-itu-t(2) country(16) us(840) 2582 -- organization(1) gov(101) 2583 -- csor(3) nistAlgorithm(4) hashAlgs(2) sha512(3) 2584 -- } 2585 -- 2586 -- 2587 -- Algorithms 2588 -- 2590 ibe-algorithms OBJECT IDENTIFIER ::= { 2591 ibcs1 ibe-algorithms(2) 2592 } 2594 --- 2595 --- Boneh-Franklin IBE 2596 --- 2598 bf OBJECT IDENTIFIER ::= { ibe-algorithms bf(1) } 2600 -- 2601 -- Encoding of a BF public parameters block. 2602 -- The only version currently supported is version 2. 2603 -- The values p and q define a subgroup of E(F_p) of order q. 2604 -- 2606 BFPublicParameters ::= SEQUENCE { 2607 version INTEGER { v2(2) }, 2608 curve OBJECT IDENTIFIER, 2609 p INTEGER, 2610 q INTEGER, 2611 pointP FpPoint, 2612 pointPpub FpPoint, 2613 hashfcn OBJECT IDENTIFIER 2614 } 2616 -- 2617 -- A BF private key is a point on an elliptic curve, 2618 -- which is an FpPoint. 2619 -- The only version supported is version 2. 2620 -- 2622 BFPrivateKeyBlock ::= SEQUENCE { 2623 version INTEGER { v2(2) }, 2624 privateKey FpPoint 2625 } 2627 -- 2628 -- A BF master secret is an integer. 2629 -- The only version supported is version 2. 2630 -- 2631 BFMasterSecret ::= SEQUENCE { 2632 version INTEGER {v2(2) }, 2633 masterSecret INTEGER 2634 } 2636 -- 2637 -- BF ciphertext block 2638 -- The only version supported is version 2. 2639 -- 2641 BFCiphertextBlock ::= SEQUENCE { 2642 version INTEGER { v2(2) }, 2643 u FpPoint, 2644 v OCTET STRING, 2645 w OCTET STRING 2646 } 2648 -- 2649 -- Boneh-Boyen (BB1) IBE 2650 -- 2652 bb1 OBJECT IDENTIFIER ::= { ibe-algorithms bb1(2) } 2654 -- 2655 -- Encoding of a BB1 public parameters block. 2656 -- The version is currently fixed to 2. 2657 -- 2658 -- 2660 BB1PublicParameters ::= SEQUENCE { 2661 version INTEGER { v2(2) }, 2662 curve OBJECT IDENTIFIER, 2663 p INTEGER, 2664 q INTEGER, 2665 pointP FpPoint, 2666 pointP1 FpPoint, 2667 pointP2 FpPoint, 2668 pointP3 FpPoint, 2669 v FpPoint, 2670 hashfcn OBJECT IDENTIFIER 2671 } 2673 -- 2674 -- BB1 master secret block 2675 -- The only version supported is version 2. 2676 -- 2677 BB1MasterSecret ::= SEQUENCE { 2678 version INTEGER { v2(2) }, 2679 alpha INTEGER, 2680 beta INTEGER, 2681 gamma INTEGER 2682 } 2684 -- 2685 -- BB1 private Key block 2686 -- The only version supported is version 2. 2687 -- 2689 BB1PrivateKeyBlock ::= SEQUENCE { 2690 version INTEGER { v2(2) }, 2691 pointD0 FpPoint, 2692 pointD1 FpPoint 2693 } 2695 -- 2696 -- BB1 ciphertext block 2697 -- The only version supported is version 2. 2698 -- 2700 BB1CiphertextBlock ::= SEQUENCE { 2701 version INTEGER {v2(2) }, 2702 pointChi0 FpPoint, 2703 pointChi1 FpPoint, 2704 nu INTEGER, 2705 y OCTET STRING 2706 } 2708 END 2710 9. Security considerations 2712 This document describes cryptographic algorithms, for which we 2713 assume that the security of the algorithm relies entirely on 2714 the secrecy of the relevant private key, so that an adversary 2715 will need to intercept encrypted messages and perform 2716 computationally-intensive cryptanalytic attacks against the 2717 ciphertext that he obtains in this way to recover either 2718 plaintext or a secret cryptographic key. 2720 We assume that users of the algorithms described in this 2721 document will require one of five levels of cryptographic 2722 strength: the equivalent of 80 bits, 112 bits, 128 bits, 192 2723 bits or 256 bits. The 80-bit level is suitable for legacy 2724 applications and SHOULD NOT be used to protect information 2725 whose useful life extends past the year 2010. The 112-bit 2726 level is suitable for use in key transport of Triple-DES keys 2727 and should be adequate to protect information whose useful 2728 life extends up to the year 2030. The 128-bit levels and 2729 higher are suitable for use in the transport of AES keys of 2730 the corresponding length or less and are adequate to protect 2731 information whose useful life extends past the year 2030. 2733 Table 1 summarizes the security parameters for the BF and BB1 2734 algorithms that will attain these levels of security. In this 2735 table, |p| represents the number of bits in a prime number p 2736 and |q| represents the number of bits in a subprime q. This 2737 table assumes that a Type-1 supersingular curve is used. 2739 Bits of Security |p| |q| 2740 80 512 160 2741 112 1024 224 2742 128 1536 256 2743 192 3840 384 2744 256 7680 512 2746 Table 1: Sizes of BF and BB1 parameters required to attain 2747 standard levels of bit security [SP800-57]. 2749 If an IBE key is used to transport a symmetric key that 2750 provides more bits of security than the bit strength of the 2751 IBE key, users should understand that the security of the 2752 system is then limited by the strength of the weaker IBE key. 2753 So if an IBE key that provides 112 bits of security is used to 2754 transport a 128-bit AES key, then the security provided is 2755 limited by the 112 bits of security of the IBE key. 2757 Note that this document specifies the use of the NIST hashing 2758 algorithms [SHA] to hash identities to either a point on an 2759 elliptic curve or an integer. Recent attacks on SHA-1 [SHA] 2760 have discovered ways to find collisions with less work than 2761 the expected 2^80 hashes required based on the size of the 2762 output of the hash function alone. If an attacker can find a 2763 collision then they could use the colliding preimages to 2764 create two identities which have the same IBE private key. The 2765 practical use of such a SHA-1 [SHA] collision is extremely 2766 unlikely, however. 2768 Identities are typically not random strings, like the 2769 preimages of a hash collision would be. In particular, this is 2770 true if IBE is used as described in [IBECMS], in which 2771 components of an identity are defined to be an e-mail address, 2772 a validity period and a URI. In this case, the unpredictable 2773 results of a collision are extremely unlikely to fit the 2774 format of a valid identity, and thus are of no use to an 2775 attacker. Any protocol using IBE MUST define an identity in a 2776 way that makes collisions in a hash function essentially 2777 useless to an attacker. Because random strings are rarely used 2778 as identities, this requirement should not be unduly difficult 2779 to fulfill. 2781 The randomness of the random values that are required by the 2782 cryptographic algorithms is vital to the security provided by 2783 the algorithms. Any implementation of these algorithms MUST 2784 use a source of random values that provides an adequate level 2785 of security. Appropriate algorithms to generate such values 2786 include [FIPS186-2] and [X9.62]. This will ensure that the 2787 random values used to mask plaintext messages in sections 5.4 2788 and 6.4 are not reused with a significant probability. 2790 The strength of a system using the algorithms described in 2791 this document relies on the strength of the mechanism used to 2792 authenticate a user requesting a private key from a PKG, as 2793 described in step 2 of section 1.2 of this document. This is 2794 analogous to way in which the strength of a system using 2795 digital certificates [X.509] is limited by the strength of the 2796 authentication required of users before certificates are 2797 granted to them. In either case, a weak mechanism for 2798 authenticating users will result in a weak system that relies 2799 on the technology. A system that uses the algorithms described 2800 in this document MUST require users to authenticate in a way 2801 that is suitably strong, particularly if IBE private keys will 2802 be used for authentication. 2804 Note that IBE systems have different properties than other 2805 asymmetric cryptographic schemes when it comes to key 2806 recovery. If a master secret is maintained on a secure PKG 2807 then the PKG and any administrator with the appropriate level 2808 of access will be able to create arbitrary private keys, so 2809 that controls around such administrators and logging of all 2810 actions performed by such administrators SHOULD be part of a 2811 functioning IBE system. 2813 On the other hand, it is also possible to create IBE private 2814 keys using a master secret and to then destroy the master 2815 secret, making any key recovery impossible. If this property 2816 is not desired, an administrator of an IBE system SHOULD 2817 require that the format of the identity used by the system 2818 contain a component that is short-lived. The format of 2819 identity that is defined in [IBECMS], for example, contains 2820 information about the time period of validity of the key that 2821 will be calculated from the identity. Such an identity can 2822 easily be changed to allow the rekeying of users if their IBE 2823 private key is somehow compromised. 2825 10. IANA considerations 2827 No further action by the IANA is necessary for this document. 2829 11. Acknowledgments 2831 This document is based on the IBCS #1 v2 document of Voltage 2832 Security, Inc. Any substantial use of material from this 2833 document should acknowledge Voltage Security, Inc. as the 2834 source of the information. 2836 12. References 2838 12.1. Normative references 2840 [KEYWORDS] S. Bradner, "Key words for use in RFCs to Indicate 2841 Requirement Levels", BCP 14, RFC 2119, March 1997. 2843 [TLS] T. Dierks and E. Rescorla, "The Transport Layer Security 2844 (TLS) Protocol Version 1.1," RFC 4346, April 2006. 2846 12.2. Informative references 2848 [BB1] D. Boneh and X. Boyen, "Efficient selective-ID secure 2849 identity based encryption without random oracles," In Proc. of 2850 EUROCRYPT 04, LNCS 3027, pp. 223-238, 2004. 2852 [BF] D. Boneh and M. Franklin, "Identity-based encryption from 2853 the Weil pairing," in Proc. of CRYPTO 01, LNCS 2139, pp. 213- 2854 229, 2001. 2856 [CMS] R. Housley, "Cryptographic Message Syntax," RFC 3852, 2857 July 2004. 2859 [ECC] I. Blake, G. Seroussi, and N. Smart, Elliptic Curves in 2860 Cryptography, Cambridge University Press, 1999. 2862 [FIPS186-2] National Institute of Standards and Technology, 2863 "Digital Signature Standard," Federal Information Processing 2864 Standard 186-2, August 2002. 2866 [IBEARCH] G. Appenzeller, L. Martin, and M. Schertler, 2867 "Identity-based Encryption Architecture," draft-ietf-smime- 2868 ibearch-05.txt, April 2007. 2870 [IBECMS] L. Martin and M. Schertler, "Using the Boneh- 2871 Franklin and Boneh-Boyen identity-based encryption algorithms 2872 with the Cryptographic Message Syntax (CMS)" draft-ietf- 2873 smime-bfibecms-06.txt, June 2007. 2875 [MERKLE] R. Merkle, "A fast software one-way hash function," 2876 Journal of Cryptology, Vol. 3 (1990), pp. 43-58. 2878 [P1363] IEEE P1363-2000, "Standard Specifications for Public 2879 Key Cryptography," 2001. 2881 [SP800-57] E. Barker, W. Barker, W. Burr, W. Polk and M. Smid, 2882 "Recommendation for Key Management - Part 1: General 2883 (Revised)," NIST Special Publication 800-57, March 2007. 2885 [SHA] National Institute for Standards and Technology, "Secure 2886 Hash Standard," Federal Information Processing Standards 2887 Publication 180-2, August 2002, with Change Notice 1, February 2888 2004. 2890 [X9.62] American National Standards Institute, "Public Key 2891 Cryptography for the Financial Services Industry: The Elliptic 2892 Curve Digital Signature Algorithm (ECDSA)," American National 2893 Standard for Financial Services X9.62-2005, November 2005. 2895 [X.509] ITU-T Recommendation X.509 (2000) | ISO/IEC 9594- 2896 8:2001, Information Technology - Open Systems Interconnection 2897 - The Directory: Public-key and Attribute Certificate 2898 Frameworks. 2900 Authors' Addresses 2902 Xavier Boyen 2903 Voltage Security 2904 1070 Arastradero Rd Suite 100 2905 Palo Alto, CA 94304 2907 Email: xavier@voltage.com 2909 Luther Martin 2910 Voltage Security 2911 1070 Arastradero Rd Suite 100 2912 Palo Alto, CA 94304 2914 Email: martin@voltage.com 2916 Intellectual Property Statement 2918 The IETF takes no position regarding the validity or scope of 2919 any Intellectual Property Rights or other rights that might be 2920 claimed to pertain to the implementation or use of the 2921 technology described in this document or the extent to which 2922 any license under such rights might or might not be available; 2923 nor does it represent that it has made any independent effort 2924 to identify any such rights. Information on the procedures 2925 with respect to rights in RFC documents can be found in BCP 78 2926 and BCP 79. 2928 Copies of IPR disclosures made to the IETF Secretariat and any 2929 assurances of licenses to be made available, or the result of 2930 an attempt made to obtain a general license or permission for 2931 the use of such proprietary rights by implementers or users of 2932 this specification can be obtained from the IETF on-line IPR 2933 repository at http://www.ietf.org/ipr. 2935 The IETF invites any interested party to bring to its 2936 attention any copyrights, patents or patent applications, or 2937 other proprietary rights that may cover technology that may be 2938 required to implement this standard. Please address the 2939 information to the IETF at ietf-ipr@ietf.org. 2941 Disclaimer of Validity 2943 This document and the information contained herein are 2944 provided on an "AS IS" basis and THE CONTRIBUTOR, THE 2945 ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), 2946 THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET 2947 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR 2948 IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE 2949 USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR 2950 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A 2951 PARTICULAR PURPOSE. 2953 Copyright Statement 2955 Copyright (C) The IETF Trust (2007). 2957 This document is subject to the rights, licenses and 2958 restrictions contained in BCP 78, and except as set forth 2959 therein, the authors retain all their rights. 2961 Acknowledgment 2963 Funding for the RFC Editor function is currently provided by 2964 the Internet Society.