idnits 2.17.1 draft-ietf-smime-ibcs-00.txt: -(39): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(111): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(128): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(152): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(153): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(156): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(161): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(163): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(165): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(167): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(209): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(212): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(219): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(244): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(251): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(256): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(269): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(273): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(277): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(281): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(285): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(291): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(381): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(382): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(444): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(494): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(528): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(530): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(564): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(587): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(609): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(648): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(655): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(658): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(661): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(664): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(692): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(697): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(715): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(721): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(860): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1015): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1040): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1062): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1070): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1077): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1091): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1119): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1146): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1149): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1153): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1167): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1173): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1200): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1263): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1348): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1376): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1407): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1422): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1429): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1531): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1566): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1582): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1685): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1689): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1717): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1730): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1811): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1836): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1863): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1899): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1902): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1927): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1966): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1990): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(1995): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2032): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2036): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2092): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2095): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2114): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2120): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2139): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2142): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2182): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2191): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2194): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2200): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2213): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2219): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2320): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2357): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2402): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2428): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2446): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2451): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2477): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2481): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2497): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2513): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2544): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2616): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2647): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2871): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2872): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2875): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding -(2876): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding 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 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 2926. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 2903. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 2910. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 2916. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There are 299 instances of lines with non-ascii characters in the document. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 1) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. ** There are 453 instances of too long lines in the document, the longest one being 11 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 204 has weird spacing: '...ing the point...' -- 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 (June 2006) is 6523 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) No issues found here. Summary: 5 errors (**), 0 flaws (~~), 5 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 X. Boyen 3 S/MIME Working Group L. Martin 4 Internet Draft Voltage Security 5 Expires: December 2006 June 2006 7 Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve 8 Implementations of the BF and BB1 Cryptosystems 10 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware have been 16 or will be disclosed, and any of which he or she becomes aware will be 17 disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html 35 Abstract 37 This document describes the algorithms that implement Boneh-Franklin 38 and Boneh-Boyen Identity-based Encryption. This document is in part 39 based on IBCS #1 v2 of Voltage Security�s Identity-based Cryptography 40 Standards (IBCS) documents. 42 Table of Contents 44 1. Introduction...................................................3 45 2. Notation and definitions.......................................4 46 2.1. Notation..................................................4 47 2.2. Definitions...............................................6 48 3. Basic elliptic curve algorithms................................7 49 3.1. The group action in affine coordinates....................7 50 3.1.1. Implementation for type-1 curves.....................7 51 3.2. Point multiplication......................................9 52 3.3. Special operations in projective coordinates.............11 53 3.3.1. Implementation for type-1 curves....................11 54 3.4. Divisors on elliptic curves..............................13 55 3.4.1. Implementation in F_p^2 for type-1 curves...........13 56 3.5. The Tate pairing.........................................15 57 3.5.1. The Miller algorithm for type-1 curves..............16 58 4. Supporting algorithms.........................................18 59 4.1. Integer range hashing....................................19 60 4.2. Pseudo-random generation by hashing......................20 61 4.3. Canonical encodings of extension field elements..........20 62 4.3.1. Type-1 curve implementation.........................21 63 4.4. Hashing onto a subgroup of an elliptic curve.............22 64 4.4.1. Type-1 curve implementation.........................22 65 4.5. Bilinear pairing.........................................23 66 4.5.1. Type-1 curve implementation.........................24 67 4.6. Ratio of bilinear pairings...............................25 68 4.6.1. Type-1 curve implementation.........................25 69 5. The Boneh-Franklin BF cryptosystem............................26 70 5.1. Setup....................................................26 71 5.1.1. Type-1 curve implementation.........................27 72 5.2. Public key derivation....................................28 73 5.3. Private key extraction...................................28 74 5.4. Encryption...............................................29 75 5.5. Decryption...............................................30 76 6. Wrapper methods for the BF system.............................32 77 6.1. Private key generator (PKG) setup........................32 78 6.2. Private key extraction by the PKG........................32 79 6.3. Session key encryption...................................33 80 7. Concrete encoding guidelines for BF...........................35 81 7.1. Encoding of points on a curve............................35 82 7.2. Public parameters blocks.................................36 83 7.2.1. Type-1 implementation...............................36 84 7.3. Master secret blocks.....................................38 85 7.4. Private key blocks.......................................38 86 7.5. Ciphertext blocks........................................39 87 8. The Boneh-Boyen BB1 cryptosystem..............................40 88 8.1. Setup....................................................40 89 8.1.1. Type-1 curve implementation.........................41 90 8.2. Public key derivation....................................42 91 8.3. Private key extraction...................................43 92 8.4. Encryption...............................................44 93 8.5. Decryption...............................................46 94 9. Wrapper methods for the BB1 system............................48 95 9.1. Private key generator (PKG) setup........................48 96 9.2. Private key extraction by the PKG........................49 97 9.3. Session key encryption...................................50 98 10. Concrete encoding guidelines for BB1.........................51 99 10.1. Encoding of points on a curve...........................51 100 10.2. Public parameters blocks................................52 101 10.2.1. Type-1 implementation..............................53 102 10.3. Master secret blocks....................................54 103 10.4. Private key blocks......................................55 104 10.5. Ciphertext blocks.......................................56 105 11. ASN.1 syntax.................................................57 106 12. Security considerations......................................63 107 13. IANA considerations..........................................63 108 14. Acknowledgments..............................................63 109 15. References...................................................64 110 15.1. Informative references..................................64 111 Authors� Addresses...............................................64 112 Intellectual Property Statement..................................64 113 Disclaimer of Validity...........................................65 114 Copyright Statement..............................................65 115 Acknowledgment...................................................65 117 1. Introduction 119 This document provides a set of specifications for implementing 120 identity-based encryption (IBE) systems based on bilinear pairings. 121 Two cryptosystems are described: the IBE system proposed by Boneh and 122 Franklin (BF) [3], and the first IBE system proposed by Boneh and 123 Boyen (BB1) [2]. Fully secure and practical implementations are 124 described for each system, comprising the core IBE algorithms as well 125 as ancillary hybrid components used to achieve security against 126 active attacks. These specifications are restricted to a family of 127 supersingular elliptic curves over finite fields of large prime 128 characteristic, referred to as �type-1� curves (see Section 2.3). 129 Implementations based on other types of curves currently fall outside 130 the scope of this document. 132 2. Notation and definitions 134 2.1. Notation 136 This section summarizes the essential notions and definitions 137 regarding identity-based cryptosystems on elliptic curves. The reader 138 is referred to [1] for the mathematical background and to [2, 3] 139 regarding all notions pertaining to identity-based encryption. 141 Let F_p be a finite field of large prime characteristic p, and let 142 F_p^k denote its extension field of degree k. Denote by F*_p the 143 multiplicative group of F_p^k, for any k >= 1. 145 Let E/F_p : y^2 = x^3 + a * x + b be an elliptic curve over F_p. For 146 any extension degree k >= 1, the curve E/F_p defines a group 147 (E(F_p^k), +), which is the additive group of points of affine 148 coordinates (x, y) in (F_p^k)^2 satisfying the curve equation over 149 F_p^k, with null element, or point at infinity, denoted 0. Let 150 #E(F_p^k) be the size of E(F_p^k). 152 Let q be a prime such that E(F_p) has a cyclic subgroup G1� of order 153 q. Let k be the embedding degree or security multiplier of G1� in 154 E(F_p), or the smallest integer greater than or equal to 1 such that 155 q divides p^k . 1. Then E(F_p^k) contains a cyclic subgroup of order 156 q, denoted G1��, and F*_p^k contains a cyclic subgroup of order p, 157 denoted G2. 159 Under these conditions, two mathematical constructions known as the 160 Weil pairing and the Tate pairing, each provide an efficiently 161 computable map e : G1� x G1�� -> G2 that is linear in both arguments 162 and believed hard to invert. If an efficiently computable isomorphism 163 phi : G1� -> G1�� is available for the selected elliptic curve on 164 which the Tate pairing is computed, then one can construct a function 165 e� : G1� x G1�� -> G2, defined as e�(A, B) = e(A, phi(B)), called the 166 modified Tate pairing. We generically call a pairing either the Tate 167 pairing e or the modified Tate pairing e�, depending on the chosen 168 elliptic curve used in a particular implementation. 170 The following additional notation is used throughout this document. 172 P - a 512-bit to 1536-bit prime, being the order of the finite field 173 F_p. 175 F_p - the base finite field of size p over which the elliptic curve 176 of interest E/F_p is defined. 178 #G - the size of G, where G is a finite group. 180 G* - the multiplicative group of the invertible elements in G; e.g., 181 (F_p)* is the multiplicative group of the finite field F_p. 183 E/F_p - the equation of an elliptic curve over the field F_p, which, 184 when p is neither 2 nor 3, is of the form E/F_p : y^2 = x^3 + a * x + 185 b, for specified a, b in F_p. 187 0 - the conventional null element of any additive group of points on 188 an elliptic curve, also called the point at infinity. 190 E(F_p) - the additive group of points of affine coordinates (x, y), 191 with x, y in F_p, that satisfy the curve equation E/F_p, including 192 the point at infinity 0. 194 q - a 160�bit to 256-bit prime, being the order of the cyclic 195 subgroup of interest in E(F_p). 197 k - the embedding degree, or security multiplier, of the cyclic 198 subgroup of order q in E(F_p). 200 F_p^k - the extension field of the base field F_p of degree equal to 201 the security multiplier k. 203 E(F_p^k ) - the group of points of affine coordinates in F_p^k 204 satisfying the curve equation E/F_p, including the point at infinity 205 0. 207 The following conventions are assumed for curve operations. 209 Point addition � If A and B are two points on a curve E, their sum is 210 denoted A + B. 212 Point multiplication � If A is a point on a curve, and n an integer, 213 the result of adding A to itself a total of n times is denoted [n]A. 215 The following class of elliptic curves is exclusively considered for 216 pairing operations in the present version of the IBCS#1 standard, 217 referred to as �type-1.� 219 Type-1 curves � The class of curves of type 1 is defined as the class 220 of all elliptic curves of equation E/F_p : y^2 = x^3 + 1 for all 221 primes p congruent to 11 modulo 12. This class forms a subclass of 222 the class of supersingular curves. These curves satisfy #E(F_p) = p + 223 1, so that the p pairs of (x, y) coordinates corresponding to the p 224 non-zero points E(F_p) \ {0} satisfy a useful bijective relation x <- 225 > y, with x = (y^2 . 1)^(1/3) (mod p) and y = (x^3 + 1)^(1/2) (mod 226 p). Type-1 curves always lead to a security multiplier k = 2, where 227 f(x) = (x^2 + 1) is always irreducible, allowing the uniform 228 representation of F_p^2 = F[x] / (x^2 + 1). Type-1 curves are 229 plentiful and easy to construct by random selection of a prime p of 230 the appropriate form. Therefore, rather than to standardize upon a 231 small set of common values of p, it is henceforth assumed that all 232 type-1 curves are freshly generated at random for the given 233 cryptographic application (an example of such generation will be 234 given in Algorithm 5.1.2 (BFsetup1) or Algorithm 8.1.2 (BBsetup1)). 235 Implementations based on different classes of curves are currently 236 unsupported. 238 We assume that the following concrete representations of mathematical 239 objects are used. 241 Base field elements - The p elements of the base field F_p are 242 represented directly using the integers from 0 to p . 1. 244 Extension field elements � The p^k elements of the extension field 245 F_p^k are represented as k-tuples of elements of F_p. A k-tuple (a_0, 246 ..., a_(k.1) is interpreted as the polynomial a_(k . 1) * x^(k . 1) + 247 ... +a_1 * x + a_0 in F_p[x] / f(x), where f(x) is an irreducible 248 monic polynomial of order k. The actual polynomial f(x) chosen 249 depends on p and k. 251 Type-1 curves � For type-1 curves, which are supersingular curves of 252 equation E/F_p : y^2 = x^3 + 1 with p congruent to 11 modulo 12, the 253 extension degree k is always 2 and elements of F_p^2 are represented 254 as polynomials a_1 * x + a_0 in F_p[x] / (x^2 + 1). 256 Elliptic curve points � Points in E(F_p^k) for k >= 1 with the point 257 P = (x, y) in F_p^k x F_p^k satisfying the curve equation E/F_p. 258 Points not equal to 0 are internally represented using the affine 259 coordinates (x, y), where x and y are elements of F_p^k. 261 2.2. Definitions 263 The following terminology is used to describe an IBE system. 265 Public parameters � The public parameters are set of common 266 systemwide parameters generated and published by the private key 267 server (PKG). 269 Master secret � The master secret is the master key generated and 270 privately kept by the key server, and used to generate the private 271 keys of the users. 273 Identity � An identity an arbitrary string, usually a human-readable 274 unambiguous designator of a system user, possibly augmented with a 275 time stamp and other attributes. 277 Public key � A public key is a string that is algorithmically derived 278 from an identity. The derivation may be performed by anyone, 279 autonomously. 281 Private key � A private key is issued by the key server to correspond 282 to a given identity (and the public key that derives from it), under 283 the published set of public parameters. 285 Plaintext � A plaintext is an unencrypted representation, or in the 286 clear, of any block of data to be transmitted securely. For the 287 present purposes, plaintexts are typically session keys, or sets of 288 session keys, for further symmetric encryption and authentication 289 purposes. 291 Ciphertext � A ciphertext is an encrypted representation of any block 292 of data, including a plaintext, to be transmitted securely. 294 3. Basic elliptic curve algorithms 296 This section describes algorithms for performing all needed basic 297 arithmetic operations on elliptic curves. The presentation is 298 specialized to the type of curves under consideration for simplicity 299 of implementation. General algorithms may be found in [1]. 301 3.1. The group action in affine coordinates 303 3.1.1. Implementation for type-1 curves 305 Algorithm 3.1.1 (PointDouble1): adds a point to itself on a type-1 306 elliptic curve. 308 Input: 310 � a point A in E(F_p^k), with A = (x, y) or 0. 312 � an elliptic curve E/F_p : y^2 = x^3 + 1. 314 Output: 316 � the point [2]A = A + A. 318 Method: 320 1. If A = 0 or y = 0, then return 0. 322 2. lambda = (3 * x^2) / (2 * y). 324 3. x� = lambda^2 � 2 * x. 326 4. y� = (x � x�) * lambda � y. 328 5. Return (x�, y�). 330 Algorithm 3.1.2 (PointAdd1): adds two points on a type-1 elliptic 331 curve. 333 Input: 335 � a point A in E(F_p^k), with A = (x_A, y_A) or 0, 337 � a point B in E(F_p^k), with B = (x_B, y_B) or 0, 339 � an elliptic curve E/F_p : y^2 = x^3 + 1. 341 Output: 343 � the point A + B. 345 Method: 347 1. If A = 0, return B. 349 2. If B = 0, return A. 351 3. If x_A = x_B: 353 (a) If y_A = .y_B, return 0. 355 (b) Else return [2]A computed using Algorithm 2.1.1 356 (PointDouble1). 358 4. Otherwise: 360 (a) lambda = (y_B . y_A) / (x_B . x_A). 362 (b) x� = lambda^2 . x_A . x_B. 364 (c) y� = (x_A . x�) * lambda - y_A. 366 (d) Return (x�, y�). 368 3.2. Point multiplication 370 Algorithm 3.2.1 (SignedWindowDecomposition): computes the signed m- 371 ary window representation of a positive integer. 373 Input: 375 � an integer l > 0, 377 � an integer window bit-size r > 0. 379 Output: 381 � The unique d-element sequence {(b_i, e_i)} for i = 0 to d - 1 such 382 that l = {Sum(b_i * 2^(e_i) for i = 0 to d � 1} and b_i = +/- 2^j for 383 some 0 <= j <= r - 1. 385 Method: 387 1. d = 0. 389 2. j = 0. 391 3. While j <= l, do: 393 (a) If l_k = 0 then: 395 i. j = j + 1. 397 (b) Else: 399 i. t = min{j + r . 1, l}. 401 ii. h_d = (l_t, l_(t � 1), ..., l_j)(base 2). 403 iii. If h_d > 2^(r . 1) then: 405 A. b_d = h_d . 2^r. 407 B. l� = l� + 2^(t + 1). 409 iv. Else: 411 A. b_d = h_d. 413 v. e_d = j. 415 vi. d = d + 1. 417 vii. j = t + 1. 419 4. Return d and the sequence {(b_0, e_0), ..., (b_(d . 1), e_(d . 420 1))}. 422 Algorithm 3.2.2 (PointMultiply): scalar multiplication on an elliptic 423 curve using the signed m-ary window method. 425 Input: 427 � a point A in E(F_p^k), 429 � an integer l > 0, 431 � an elliptic curve E/F_p : y^2 = x^3 + a * x + b. 433 Output: 435 � the point [l]A. 437 Method: 439 1. (Window decomposition) 441 (a) Let r > 0 be an integer (fixed) bit-wise window size, e.g., r 442 = 5. 444 (b) Let l� = l where l = {Sum(l_j * 2^j), for j = 0 to l} is the 445 binary expansion of l. 447 (c) Compute (d, {(b_i, e_i) for i = 0 to d � 1} = 448 SignedWindowDecomposition(l, r), the signed 2^r-ary window 449 representation of l using Algorithm 3.2.1 450 (SignedWindowDecomposition). 452 2. (Precomputation) 454 (a) A_1 = A. 456 (b) A_2 = [2]A, using Algorithm 3.1.1 (PointDouble1). 458 (c) For i = 1 to 2^(r . 2) . 1, do: 460 i. A_(2 * i + 1) = A_(2 * i . 1) + A_2 using Algorithm 3.1.2 461 (PointAdd1). 463 (d) Q = A_(b_(d . 1)). 465 3. Main loop 467 (a) For i = d . 2 to 0 by .1, do: 469 i. Q = [2^(e_(i + 1) . e_i)]Q, using repeated applications of 470 Algorithm 3.1.1 (PointDouble1) e_(i + 1) . e_i times. 472 ii. If b_i > 0 then: 474 A. Q = Q + A_(b_i) using Algorithm 3.1.2 (PointAdd1). 476 iii. Else: 478 A. Q = Q . A_(.b_i) using Algorithm 3.1.2 (PointAdd1). 480 (b) Calculate Q = [2^(e_0)]Q using repeated applications of 481 Algorithm 3.1.1 (PointDouble1) e_0 times. 483 4. Return Q. 485 3.3. Special operations in projective coordinates 487 3.3.1. Implementation for type-1 curves 489 Algorithm 3.3.1 (ProjectivePointDouble1): adds a point to itself in 490 projective coordinates for type-1 curves. 492 Input: 494 � a point (x, y, z) = A in E(F_p^k ) in projective coordinates, 496 � an elliptic curve E/F_p : y^2 = x^3 + 1. 498 Output: 500 � the point [2]A in projective coordinates. 502 Method: 504 1. If z = 0 or y = 0, return (0, 1, 0) = 0. Otherwise: 506 2. lambda_1 = 3 * x^2. 508 3. z� = 2 * y * z. 510 4. lambda_2 = y^2. 512 5. lambda_3 = 4 * lambda_2 * x. 514 6. x� = lambda_1^2 � 2 * lambda_3. 516 7. lambda_4 = 8 * lambda_2^2. 518 8. y� = lambda_1 * (lambda_3 � x) � lambda_4. 520 9. Return (x�, y�, z�). 522 Algorithm 3.3.2 (ProjectivePointAccumulate1): adds a point in affine 523 coordinates to an accumulator in projective coordinates, for type-1 524 curves. 526 Input: 528 � a point (x_A, y_A, z_A) = A in E(F_p^k ) in projective coordinates, 530 � a point (x_B, y_B) = B in E(F_p^k ) \ {0} in affine coordinates, 532 � an elliptic curve E/F_p : y^2 = x^3 + 1. 534 Output: 536 � the point A + B in projective coordinates. 538 Method: 540 1. If z_A = 0 return (x_B, y_B, 1) = B. Otherwise: 542 2. lambda_1 = z_A^2 544 3. lambda_2 = lambda_1 * x_B. 546 4. lambda_3 = x_A � lambda_2. 548 5. If lambda_3 = 0 then return (0, 1, 0) = 0. Otherwise: 550 6. lambda_4 = lambda_3^2. 552 7. lambda_5 = lambda_1 * y_B * z_A. 554 8. lambda_6 = lambda_4 � lambda_5. 556 9. lambda_7 = x_A + lambda_2. 558 10. lambda_8 = y_A + lambda_5. 560 11. x� = lambda_6^2 � lambda_7 * lambda_4. 562 12. lambda_9 = lambda_7 * lambda_4 � 2 * x�. 564 13. y� = (lambda_9 * lambda_6 � lambda_8 * lambda_3 * lambda_4) / 2. 566 14. z� = lambda_3 * z_A. 568 15. Return (x�, y�, z�). 570 3.4. Divisors on elliptic curves 572 3.4.1. Implementation in F_p^2 for type-1 curves 574 Algorithm 3.4.1 (EvalVertical1): evaluates the divisor of a vertical 575 line on a type-1 elliptic curve. 577 Input: 579 � a point B in E(F_p^2) with B != 0. 581 � a point A in E(F_p). 583 � a description of a type-1 elliptic curve E/F_p. 585 Output: 587 � an element of F_p^2 that is the divisor of the vertical line going 588 through A evaluated at B. 590 Method: 592 1. r = x_B . x_A. 594 2. Return r. 596 Algorithm 2.4.2 (EvalTangent1): evaluates the divisor of a tangent on 597 a type-1 elliptic curve. 599 Input: 601 � a point B in E(F_p^2 ) with B != 0. 603 � a point A in E(F_p). 605 � a description of a type-1 elliptic curve E/F_p. 607 Output: 609 � an element of F_p^2 that is the divisor of the line tangent to A 610 evaluated at B. 612 Method: 614 1. (Special cases) 616 (a) If A = 0 return 1 = 1 + 0 * i. 618 (b) If y_A = 0 return EvalVertical1(B, A) using Algorithm 3.4.1 619 (EvalVertical1). 621 2. (Line computation) 623 (a) a = .3 * (x_A)^2. 625 (b) b = 2 * y_A. 627 (c) c = .b * y_A . a * x_A. 629 3. (Evaluation at B) 631 (a) r = a * x_B + b * y_B) + c. 633 4. Return r. 635 Algorithm 3.4.3 (EvalLine1): evaluates the divisor of a line on a 636 type-1 elliptic curve. 638 Input: 640 � a point B in E(F_p^2 ) with B != 0. 642 � two points A�, A�� in E(F_p). 644 � a description of a type-1 elliptic curve E/F_p. 646 Output: 648 � an element of F_p^2 that is the divisor of the line going through 649 A� and A�� evaluated at B. 651 Method: 653 1. (Special cases) 655 (a) If A� = 0 return EvalVertical1(B, A��) using Algorithm 3.4.1 656 (EvalVertical1). 658 (b) If A�� = 0 return EvalVertical1(B, A�) using Algorithm 3.4.1 659 (EvalVertical1). 661 (c) If A� = .A�� return EvalVertical1(B, A�) using Algorithm 3.4.1 662 (EvalVertical1). 664 ( d) If A� = A�� return EvalTangent1(B, A�) using Algorithm 3.4.2 665 (EvalTangent1). 667 2. (Line computation) 669 (a) a = y_A� . y_A��. 671 (b) b = x_A�� . x_A�. 673 (c) c = .b * y_A� . a * x_A�. 675 3. (Evaluation at B) 677 (a) r = a * x_B + b * y_B + c. 679 4. Return r. 681 3.5. The Tate pairing 683 Algorithm 3.5.1 (Tate): computes the Tate pairing on an elliptic 684 curve. 686 Input: 688 � a point A of order q in E(F_p), 690 � a point B of order q in E(F_p^k), 692 � a description of an elliptic curve E/F_p such that E(F_p) and 693 E(F_p^k) have a subgroup of order q. 695 Output: 697 � the value e(A, B) in F_p^k , computed using the Miller algorithm. 699 Method: 701 1. For type-1 curve E, proceed with Algorithm 3.5.2 702 (TateMillerSolinas). 704 3.5.1. The Miller algorithm for type-1 curves 706 Algorithm 3.5.2 (TateMillerSolinas): computes the Tate pairing on a 707 type-1 elliptic curve. 709 Input: 711 � a point A of order q in E(F_p), 713 � a point B of order q in E(F_p^2), 715 � a description of a type-1 supersingular elliptic curve E/F_p such 716 that E(F_p) and E(F_p^2) have a subgroup of prime order q, where q = 717 2^a + s * 2^b + c with c and s equal to either 1 or -1. 719 Output: 721 � the value e(A, B) in F_p^2 , computed using the Miller algorithm. 723 The following description assumes that F_p^2 = F_p[i], where i^2 = - 724 1. 726 Elements x in F_p^2 may be explicitly represented as a + i * b, with 727 a, b in F_p. 729 Points in E(F_p) may also be represented as coordinate pairs (x, y) 730 with x, y in F_p. 732 Points in E(F_p^2) may be represented either as (x, y), with x, y in 733 F_p^2 or as (a + i * b, c + i * d), with a, b, c, d in F_p. 735 Method: 737 1. (Initialization) 739 (a) v_num = 1 in F_p^2. 741 (b) v_den = 1 in F_p^2. 743 (c) V = (x_V , y_V , z_V ) = (x_A, y_A, 1) in (F_p)^3, being the 744 representation of (x_A, y_A) = A using projective coordinates. 746 (d) t_num = 1 in F_p^2. 748 (e) t_den = 1 in F_p^2. 750 2. (Calculation of the (s * 2^b) contribution) 752 (a) (Repeated doublings) For n = 0 to b . 1: 754 i. t_num = t_num^2. 756 ii. t_den = t_den^2. 758 iii. t_num = t_num * EvalTangent1(B, V ) using Algorithm 3.4.2 759 (EvalTangent1). 761 iv. V = (x_V , y_V , z_V ) = [2]V using Algorithm 3.3.1 762 (ProjectivePointDouble1). 764 v. t_den = t_den * EvalVertical1(B, V ) using Algorithm 3.4.1 765 (EvalVertical1). 767 (b) (Normalization) 769 i. V_b = (x_(V_b) , y_(V_b)) = (x_V / z_V^2, s * y_V / z_V^3) 770 in (F_p)^2, resulting in a point V_b in E(F_p). 772 (c) (Accumulation) Selecting on s: 774 i. If s = .1: 776 A. v_num = v_num * t_den. 778 B. v_den = v_den * t_num * EvalVertical1(B, V) using 779 Algorithm 3.4.1 (EvalVertical1). 781 ii. If s = 1: 783 A. v_num = v_num * t_num. 785 B. v_den = v_den * t_den. 787 3. (Calculation of the 2^a contribution) 789 (a) (Repeated doublings) For n = b to a . 1: 791 i. t_num = t_num^2. 793 ii. t_den = t_den^2. 795 iii. t_num = t_num * EvalTangent1(B, V) using Algorithm 3.4.2 796 (EvalTangent1). 798 iv. V = (x_V , y_V , z_V) = [2]V using Algorithm 3.3.1 799 (ProjectivePointDouble1). 801 v. t_den = t_den * EvalVertical1(B, V) using Algorithm 3.4.1 802 (EvalVertical1). 804 (b) (Normalization) 806 i. V_a = (x_(V_a) , y_(V_a)) = (x_V /z_V^2, s * x_V / z_V^3) in 807 (F_p)2, resulting in a point V_a in E(F_p). 809 (c) (Accumulation) 811 i. v_num = v_num * t_num. 813 ii. v_den = v_den * t_den. 815 4. (Correction for the (s * 2^b) and (c) contributions) 817 (a) v_num = v_num * EvalLine1(B, V_a, V_b) using Algorithm 3.4.3 818 (EvalLine1). 820 (b) v_den = v_den * EvalVertical1(B, V_a + V_b) using Algorithm 821 3.4.1 (EvalVertical1). 823 (c) If c = .1 then: 825 i. v_den = v_den * EvalVertical1(B,A) using Algorithm 3.4.1 826 (EvalVertical1). 828 5. (Correcting exponent) 830 (a) Let eta = (p^2 . 1) / q (an integer). 832 6. (Final result) 834 (a) Return (v_num / v_den)^eta in F_p^2 . 836 4. Supporting algorithms 838 This section describes a number of supporting algorithms for encoding 839 and hashing. 841 4.1. Integer range hashing 843 HashToRangen(s, n) takes a string s and an integer n as input, and 844 returns an integer in the range 0 to n . 1 by cryptographic hashing. 845 The function performs a number l of SHA1 applications, with l chosen 846 in function of n so that, for random input, the output has an almost 847 uniform distribution in the entire range 0 to n . 1 with a 848 statistical relative non-uniformity no greater than 1/sqrt(n). I.e., 849 for arbitrarily large n, for all v in 0 to n . 1, the probability 850 that HashToRangen(s, n) = v lies in the interval [(1 . n^(.1/2)) / n, 851 (1 + n^(.1/2)) / n]. 853 Algorithm 4.1.1 (HashToRange): cryptographically hashes strings to 854 integers in a range. 856 Input: 858 � a string s of length |s| bytes, 860 � a positive integer n represented as Ceiling(8 * lg(n)) bytes. 862 Output: 864 � a positive integer v in the range 0 to n . 1. 866 Method: 868 1. v_0 = 0. 870 2. h_0 = 0x0000000000000000000000000000000000000000, a string of 20 871 null bytes. 873 3. l = Ceiling((3 / 5) * lg(n)). 875 4. for each i in 1 to l, do: 877 (a) t_i = h_(i . 1) || s, which is the (|s| + 20)-byte string 878 concatenation of the strings h_(i . 1) and s. 880 (b) h_i = SHA1(t_i), which is a 20-byte string resulting from the 881 SHA1 algorithm on input t_i. 883 (c) Let a_i = Value(h_i) be the integer in the range 0 to 256^20 . 884 1 denoted by the raw byte string h_i interpreted in the unsigned big 885 endian convention. 887 (d) v_i = 256^20 * v_(i . 1) + a_i. 889 5. v = v_l (mod n). 891 4.2. Pseudo-random generation by hashing 893 HashStream(b, p) takes an integer b and a string p as input, and 894 returns a b-byte pseudo-random string r as output. This function 895 relies on the SHA1 cryptographic hashing algorithm, and has a 160-bit 896 internal effective key space equal to the range of SHA1. 898 Algorithm 4.2.1 (HashStream): keyed cryptographic pseudo-random 899 stream generator. 901 Input: 903 � an integer b, 905 � a string p. 907 Output: 909 � a string r of size b bytes. 911 Method: 913 1. K = SHA1(p). 915 2. h_0 = 0x0000000000000000000000000000000000000000 , a string of 20 916 null bytes. 918 3. l = Ceiling(b / 20). 920 4. for each i in 1 to l do: 922 (a) h_i = SHA1(h_(i . 1)). 924 (b) r_i = SHA1(h_i || K), where h_i || K is the 40-byte 925 concatenation of h_i and K. 927 5. r = LeftmostBytes(b, r_1 || ... || r_l), i.e., r is formed as the 928 concatenation of the r_i, truncated to the desired number of bytes. 930 4.3. Canonical encodings of extension field elements 932 Canonical(p, k, o, v) takes an element v in F_p^k, and returns a 933 canonical byte-string of fixed length representing v. The parameter o 934 must be either 0 or 1, and specifies the ordering of the encoding. 936 Algorithm 4.3.1 (Canonical): encodes elements of an extension field 937 F_p^k as strings. 939 Input: 941 � an element v in F_p^k, 943 � a description of F_p^k , 945 � a ordering parameter o, either 0 or 1. 947 Output: 949 � a fixed-length string s representing v. 951 Method: 953 1. For a type-1 curve, execute Algorithm 4.3.2 (Canonical1). 955 4.3.1. Type-1 curve implementation 957 Canonical1(p, o, v) takes an element v in F_p^2 and returns a 958 canonical representation of v as a byte-string s of fixed size. The 959 parameter o must be either 0 or 1, and specifies the ordering of the 960 encoding. 962 Algorithm 4.3.2 (Canonical1): canonically represents elements of an 963 extension field F_p^2. 965 Input: 967 � an element v in F_p^2, 969 � a description of p, where p is congruent to 3 modulo 4, 971 � a ordering parameter o, either 0 or 1. 973 Output: 975 � a string s of size Ceiling(16 * lg(p)) bytes. 977 Method: 979 1. l = 8 * Ceiling(lg(p)), the number of bytes needed to represent 980 integers in Zp. 982 2. (a, b) = v, where (a, b) in (Z_p)^2 is the canonical 983 representation of v in F_p^2 = F_p / (x^2 + 1) as a polynomial a +i * 984 b with i^2 = .1. 986 3. Let a_(256^l) be the big-endian zero-padded fixed-length byte- 987 string representation of a in Zp. 989 4. Let b_(256^l) be the big-endian zero-padded fixed-length byte- 990 string representation of b in Zp. 992 5. Depending on the choice of ordering o: 994 (a) If o = 0, then let s = a_(256^l) || b_(256^l), which is the 995 concatenation of a_(256^l) followed by b_(256^l). 997 (b) If o = 1, then let s = b_(256^l) || a_(256^l), which is the 998 concatenation of b_(256^l) followed by a_(256^l). 1000 6. The fixed-length encoding of v is output as the string s. 1002 4.4. Hashing onto a subgroup of an elliptic curve 1004 HashToPoint(E, p, q, id) takes an identity string id and the 1005 description of a subgroup of prime order q in E(F_p) or E(F_p^k) and 1006 returns a point Q_id of order q in E(F_p) or E(F_p^k). 1008 Algorithm 4.4.1 (HashToPoint): cryptographically hashes strings to 1009 points on elliptic curves. 1011 Input: 1013 � a string id, 1015 � a description of a subgroup of prime order q on a curve E/F_p. 1017 Output: 1019 � a point Q_id = (x, y) of order q on E. 1021 Method: 1023 1. For a type-1 curve E, execute Algorithm 4.4.2 (HashToPoint1). 1025 4.4.1. Type-1 curve implementation 1027 HashToPoint1(E, p, q, id) takes an identity string id and the 1028 description of a subgroup of order q in E(F_p) where E : y^2 = x^3 + 1029 1 with p congruent to 11 modulo 12, and returns a point Q_id of order 1030 q in E/F_p. This algorithm exploits the bijective mapping between the 1031 x and y coordinates of non-zero points on such supersingular curves. 1033 Algorithm 4.4.2 (HashToPoint1). Cryptographically hashes strings to 1034 points on type-1 curves. 1036 Input: 1038 � a string id, 1040 � a description of a subgroup of prime order q on a curve E/F_p : y^2 1041 = x^3 + 1 where p is congruent to 11 modulo 12. 1043 Output: 1045 � a point Q_id of order q on E(F_p). 1047 Method: 1049 1. n = q (compatibility mode) or p (preferred mode) 1051 2. y = HashToRangen(n, id), using Algorithm 4.1.1 (HashToRange). 1053 3. x = (y^2 . 1)^(1/3) = (y^2 . 1)^((2 * p . 1) / 3). 1055 4. Let Q� = (x, y), a non-zero point in E(F_p). 1057 5. Q = [(p + 1) / q ]Q�, a point of order q in E(F_p). 1059 4.5. Bilinear pairing 1061 Pairing(E, p, q, A, B) takes two points A and B, both of order q, 1062 and, in the type-1 case, returns the modified pairing e�(A, phi(B)) 1063 in F_p^2 where A and B are both in E(F_p). 1065 Algorithm 4.5.1 (Pairing): computes the regular or modified Tate 1066 pairing depending on the curve type. 1068 Input: 1070 � a description of an elliptic curve E/F_p such that E(F_p) and 1071 E(F_p^k) have a subgroup of order q, 1073 � two points A and B of order q in E(F_p) or E(F_p^k). 1075 Output: 1077 � on supersingular curves, the value of e�(A, B) in F_p^k where A and 1078 B are both in E(F_p); 1080 Method: 1082 1. If E is a type-1 curve, execute Algorithm 4.5.2 (Pairing1). 1084 4.5.1. Type-1 curve implementation 1086 Algorithm 4.5.2 (Pairing1): computes the modified Tate pairing on 1087 type-1 curves. 1089 Input: 1091 � a curve E/F_p : y^2 = x^3 + 1 where p is congruent to 11 modulo 12 1092 and E(F_p) has a subgroup of order q, 1094 � two points A and B of order q in E(F_p), 1096 Output: 1098 � the value of e�(A, B) = e(A, phi(B)) in F_p^k = F_p^2 . 1100 Method: 1102 1. Compute B� = phi(B), as follows: 1104 (a) Let (x, y) in F_p x F_p be the coordinates of B in E(F_p). 1106 (b) Let zeta = 1^(1/3) in F_p^2 , with zeta != 1. Specifically, as 1107 p is congruent to 3 modulo 4, and representing the elements of F_p^2 1108 = F_p[x] / (x^2 + 1) as polynomials a + bx with x = (.1)^(1/2), the 1109 representation of zeta = (a_zeta , b_zeta) is obtained as: 1111 i. a_zeta = (p . 1) / 2. 1113 ii. b_zeta = 3^((p + 1) / 4) (mod p). 1115 (c) x� = x * x_zeta in F_p^2 , 1117 (d) B� = (x�, y) in F_p^2 x F_p. 1119 2. Compute the Tate pairing e(A,B�) = e(A, phi(B)) in F_p^2 using the 1120 Miller method, as in Algorithm 4.5.1 (Tate) described in Section 4.5. 1122 4.6. Ratio of bilinear pairings 1124 PairingRatio(E, p, q, A, B, C, D) takes four points as input, and 1125 computes the ratio of the two bilinear pairings, Pairing(E, p, q, A, 1126 B) / Pairing(E, p, q, C, D), or, equivalently, the product, 1127 Pairing(E, p, q, A, B) * Pairing(E, p, q, C, .D). 1129 On type-1 curves, all four points are of order q in E(F_p), and the 1130 result is an element of order q in the extension field F_p^2 . 1132 The motivation for this algorithm is that the ratio of two pairings 1133 can be calculated more efficiently than by computing each pairing 1134 separately and dividing one into the other, since certain 1135 calculations that would normally appear in each of the two pairings 1136 can be combined and carried out at once. Such calculations include 1137 the repeated doublings in steps 2(a)i, 2(a)ii, 3(a)i, and 3(a)ii of 1138 Algorithm 4.5.2 (TateMillerSolinas), as well as the final 1139 exponentiation in step 6(a) of Algorithm 4.5.2 (TateMillerSolinas). 1141 Algorithm 4.6.1 (PairingRatio): computes the ratio of two regular or 1142 modified Tate pairings depending on the curve type. 1144 Input: 1146 � a description of an elliptic curve E/F_p such that E(F_p) and 1147 E(F_p^k) have a subgroup of order q, 1149 � four points A, B, C, and D, of order q in E(F_p) or E(F_p^k). 1151 Output: 1153 � on supersingular curves, the value of e�(A, B) / e�(C, D) in F_p^k 1154 where A, B, C, D are all in E(F_p); 1156 Method: 1158 1. If E is a type-1 curve, execute Algorithm 4.6.2 (PairingRatio1). 1160 4.6.1. Type-1 curve implementation 1162 Algorithm 4.6.2 (PairingRatio1). Computes the ratio of two modified 1163 Tate pairings on type-1 curves. 1165 Input: 1167 � a curve E/F_p : y^2 = x^3 + 1, where p is congruent to 11 modulo 12 1168 and E(F_p) has a subgroup of order q, 1169 � four points A, B, C, and D, of order q in E(F_p), 1171 Output: 1173 � the value of e�(A, B) / e�(C, D) = e(A, phi(B)) / e(C, phi(D)) = 1174 e(A, phi(B)) * e(.C, phi(D)), in F_p^k = F_p^2 . 1176 Method: 1178 1. The step-by-step description of the optimized algorithm is omitted 1179 in this normative specification. 1181 The correct result can always be obtained, albeit more slowly, by 1182 computing the product of pairings Pairing1(E, p, q, A, B) * 1183 Pairing1(E, p, q, .C, D) by using two invocations of Algorithm 4.5.2 1184 (Pairing1). 1186 5. The Boneh-Franklin BF cryptosystem 1188 This chapter describes the algorithms constituting the Boneh-Franklin 1189 identity-based cryptosystem as described in [3]. 1191 5.1. Setup 1193 Algorithm 5.1.1 (BFsetup): randomly selects a master secret and the 1194 associated public parameters. 1196 Input: 1198 � a curve type t (currently required to be fixed to t = 1), 1200 � a security parameter n (currently required to take values n >= 1201 1024). 1203 Output: 1205 � a set of common public parameters, 1207 � a corresponding master secret. 1209 Method: 1211 1. Depending on the selected type t: 1213 (a) If t = 1, then Algorithm 5.1.2 (BFsetup1) is executed. 1215 2. The resulting master secret and public parameters are separately 1216 encoded as per the application protocol requirements. 1218 5.1.1. Type-1 curve implementation 1220 BFsetup1 takes a security parameter n as input. For type-1 curves, 1221 the scale of n corresponds to the modulus bit-size believed of 1222 comparable security in the classical Diffie-Hellman or RSA public-key 1223 cryptosystems. For this implementation, the allowed value of n is 1224 limited to 1024, which corresponds to 80 bits of symmetric key 1225 security. 1227 Algorithm 5.1.2 (BFsetup1): randomly establishes a master secret and 1228 public parameters for type-1 curves. 1230 Input: 1232 � a security parameter n, assumed to be equal to 1024. 1234 Output: 1236 � a set of common public parameters (t, p, q, P, Ppub), 1238 � a corresponding master secret s. 1240 Method: 1242 1. Determine the subordinate security parameters n_p and n_q as 1243 follows: 1245 (a) n_p = 512, which will determine the size of the field F_p. 1247 (b) n_q = 160, which will determine the size of the subgroup order 1248 q. 1250 2. Construct the elliptic curve and its subgroup of interest, as 1251 follows: 1253 (a) Select an arbitrary n_q-bit prime q, i.e., such that 1254 Ceiling(lg(q)) = n_q. For better performance, q is chosen as a 1255 Solinas prime, i.e., a prime of the form q = 2^a +/- 2^b +/- 1 where 1256 0 < b < a. 1258 (b) Select a random integer r such that p = 12 * r * q . 1 is an 1259 n_p-bit prime, i.e., such that Floor(lg(p)) = n_p. 1261 3. Select a point P of order q in E(F_p), as follows: 1263 (a) Select a random point P� of coordinates (x�, y�) on the curve 1264 E/F_p : y^2 = x^3 + 1 (mod p). 1266 (b) Let P = [12 * r]P�. 1268 (c) If P = 0, then start over in step 3a. 1270 4. Determine the master secret and the public parameters as follows: 1272 (a) Select a random integer s in the range 2 to q . 1. 1274 (b) Let P_pub = [s]P. 1276 5. (t, E, p, q, P, P_pub) are the common public parameters, where E: 1277 y^2 = x^3 + 1. 1279 6. s is the master secret. 1281 5.2. Public key derivation 1283 BFderivePubl takes an identity string id and a set of public 1284 parameters, and returns a point Q_id. 1286 Algorithm 5.2.1 (BFderivePubl): derives the public key corresponding 1287 to an identity string. 1289 Input: 1291 � an identity string id, 1293 � a set of common public parameters (t, E, p, q, P, P_pub). 1295 Output: 1297 � a point Q_id of order q in E(F_p) or E(F_p^k). 1299 Method: 1301 1. Q_id = HashToPoint(E, p, q, id), using Algorithm 4.4.1 1302 (HashToPoint). 1304 5.3. Private key extraction 1306 BFextractPriv takes an identity string id, and a set of public 1307 parameters and corresponding master secret, and returns a point S_id. 1309 Algorithm 4.3.1 (BFextractPriv): extracts the private key 1310 corresponding to an identity string. 1312 Input: 1314 � an identity string id, 1316 � a set of common public parameters (t, E, p, q, P, P_pub). 1318 Output: 1320 � a point S_id or order q in E(F_p). 1322 Method: 1324 1. Q_id HashToPoint(E, p, q, id) using Algorithm 4.4.1 1325 (HashToPoint). 1327 2. S_id = [s]Q_id. 1329 5.4. Encryption 1331 BFencrypt takes three inputs: a public parameter block, an identity 1332 id, and a plaintext m. The plaintext is intended to be a symmetric 1333 session key, although variable-sized short messages are allowed. 1335 Algorithm 5.4.1 (BFencrypt): encrypts a short message or session key 1336 for an identity string. 1338 Input: 1340 � a plaintext string m of size |m| bytes, 1342 � a recipient identity string id, 1344 � a set of public parameters. 1346 Output: 1348 � a ciphertext tuple (U, V, W) in E(F_p) x {0, ... , 255}^20 x {0, 1349 ... , 255}^|m|. 1351 Method: 1353 1. Let the public parameter set be comprised of a prime p, a curve 1354 E/F_p, the order q of a large prime subgroup of E(F_p), and two 1355 points P and P_pub of order q in E(F_p). 1357 2. Q_id = HashToPoint(E, p, q, id), using Algorithm 4.4.1 1358 (HashToPoint), which results in a point of order q in E(F_p) or 1359 E(F_p^k). 1361 3. Select s random 160-bit vector rho, represented as 20-byte string 1362 in big-endian convention. 1364 4. t = SHA1(m), a 20-byte string resulting from the SHA1 algorithm. 1366 5. l = HashToRangeq(rho || t), an integer in the range 0 to q . 1 1367 resulting from applying Algorithm 4.1.1 (HashToRange) to the 40-byte 1368 concatenation of rho and t. 1370 6. U = [l]P, which is a point of order q in E(F_p). 1372 7. Theta = Pairing(E, p, q, P_pub, Q_id), which is an element of the 1373 extension field F_p^k obtained using the modified Tate pairing of 1374 Algorithm 4.5.1 (Pairing). 1376 8. Let theta� = theta^l, which is theta raised to the power of l in 1377 F_p^k . 1379 9. Let z = Canonical(p, k, 0, theta�), using Algorithm 4.3.1 1380 (Canonical), the result of which is a canonical string representation 1381 of theta�. 1383 10. Let w = SHA1(z) using the SHA1 hashing algorithm, the result of 1384 which is a 20-byte string. 1386 11. Let V = w XOR rho, which is the 20-byte long bit-wise exclusive- 1387 OR of w and rho. 1389 12. Let W = HashStream(|m|, rho XOR m), which is the bit-wise 1390 exclusive-OR of m with the first |m| bytes of the pseudo-random 1391 stream produced by Algorithm 4.2.1 (HashStream) with seed rho. 1393 13. The ciphertext is the triple (U, V, W). 1395 5.5. Decryption 1397 BFdecrypt takes three inputs: a public parameter block, a private key 1398 block key, and a ciphertext parsed as (U� , V� , W�). 1400 Algorithm 5.5.1 (BFdecrypt): decrypts a short message or session key 1401 using a private key. 1403 Input: 1405 � a private key point S_id of order q in E(F_p), 1407 � a ciphertext triple (U�, V�, W�) in E(F_p) x {0, . . . , 255}^20 x 1408 {0, . . . , 255}*. 1410 � a set of public parameters. 1412 Output: 1414 � a decrypted plaintext m�, or an invalid ciphertext flag. 1416 Method: 1418 1. Let the public parameter set be comprised of a prime p, a curve 1419 E/F_p, the order q of a large prime subgroup of E(F_p), and two 1420 points P and P_pub of order q in E(F_p). 1422 2. Let theta� = Pairing(E, p ,q, U�, S_id) by applying the modified 1423 Tate pairing of Algorithm 4.5.1 (Pairing). 1425 3. Let z = Canonical(p, k, 0, theta�) using Algorithm 4.3.1 1426 (Canonical), the result of which is a canonical string representation 1427 of theta�. 1429 4. Let w� = SHA1(z), using the SHA1 hashing algorithm, the result of 1430 which is a 20-byte string. 1432 5. Let rho = w XOR V, the bit-wise XOR of w and V. 1434 6. Let m = HashStream(|W|, rho) XOR W, which is the bit-wise 1435 exclusive-OR of m with the first |W| bytes of the pseudo-random 1436 stream produced by Algorithm 4.2.1 (HashStream) with seed rho. 1438 7. Let t = SHA1(m) using the SHA1 algorithm. 1440 8. Let l = HashToRange(q, rho || t) using Algorithm 4.1.1 1441 (HashToRange) on the 40-byte concatenation of rho and t. 1443 9. Verify that U� = [l]P: 1445 (a) If this is the case, then the decrypted plaintext m is 1446 returned. 1448 (b) Otherwise, the ciphertext is rejected and no plaintext is 1449 returned. 1451 6. Wrapper methods for the BF system 1453 This chapter describes a number of wrapper methods providing the 1454 identity-based cryptosystem functionalities using concrete encodings. 1455 The following functions are presently given based on the Boneh- 1456 Franklin algorithms. 1458 6.1. Private key generator (PKG) setup 1460 Algorithm 6.1.1 (BFwrapperPKGSetup): randomly selects a PKG master 1461 secret and a set of public parameters. 1463 Input: 1465 � a curve type t, 1467 � a security parameter n. 1469 Output: 1471 � a common public parameter block pi, 1473 � a corresponding master secret block sigma. 1475 Method: 1477 1. Perform Algorithm 5.1.1 (BFsetup) on parameters t and n, producing 1478 a public parameter set and a master secret. 1480 2. Apply Algorithm 7.2.1 (BFencodeParams) on the public parameter set 1481 obtained in step 1 to get the public parameter block pi. 1483 3. Apply Algorithm 7.3.1 (BFencodeMaster) on the master secret 1484 obtained in step 1 to get the master secret block sigma. 1486 6.2. Private key extraction by the PKG 1488 Algorithm 5.2.1 (BFwrapperPrivateKeyExtract): extraction by the PKG 1489 of a private key corresponding to an identity. 1491 Input: 1493 � a master secret block sigma, 1495 � a corresponding public parameter block pi, 1497 � an identity string id. 1499 Output: 1501 � a private key block kappa_id 1503 Method: 1505 1. Apply Algorithm 7.2.2 (BFdecodeParams) to the public parameter 1506 block pi to obtain the public parameters, comprising a prime p, a 1507 curve E/F_p, the order q of a large prime subgroup of E(F_p), and two 1508 points P and P_pub of order q in E(F_p). 1510 2. Apply Algorithm 7.3.2 (BFdecodeMaster) on the master secret block 1511 sigma to obtain the master secret s. 1513 3. Perform Algorithm 5.3.1 (BFextractPriv) on the identity id, using 1514 the decoded parameters and secret, to produce a private key point 1515 S_id. 1517 4. Apply Algorithm 7.4.1 (BFencodePrivate) to S_id to produce a 1518 private key block kid. 1520 6.3. Session key encryption 1522 Algorithm 5.3.1 (BFwrapperSessionKeyEncrypt): encrypts a short 1523 message or session key for an identity. 1525 Input: 1527 � a public parameter block pi, 1529 � a recipient identity string id, 1531 � a plaintext string m (possibly comprising the concatenation of a 1532 pair of random session keys for symmetric encryption and message 1533 authentication purposes on a larger plaintext). 1535 Output: 1537 � a ciphertext block 1539 Method: 1541 1. Apply Algorithm 7.2.2 (BFdecodeParams) on the public parameter 1542 block pi to obtain a set of public parameters, comprising a prime p, 1543 a curve E/F_p, the order q of a large prime subgroup of E(F_p), and 1544 two points P and P_pub of order q in E(F_p). 1546 2. Perform Algorithm 5.4.1 (BFencrypt) on the plaintext m for 1547 identity id using the decoded set of parameters, to obtain a 1548 ciphertext tuple (U, V, W). 1550 3. Apply Algorithm 7.5.1 (BFencodeCiphertext) on (U, V, W) to obtain 1551 a serialized ciphertext string 1553 Algorithm 6.3.2 (BFwrapperSessionKeyDecrypt): decrypts a short 1554 message or session key using a private key. 1556 Input: 1558 � a public parameter block pi, 1560 � a private key block kappa, 1562 � a ciphertext block gamma. 1564 Output: 1566 � a decrypted plaintext string m, or an error flag signaling an 1567 invalid ciphertext. 1569 Method: 1571 1. Apply Algorithm 7.2.2 (BFdecodeParams) on the public parameter 1572 block pi to obtain the public parameters, comprising a prime p, a 1573 curve E/F_p, the order q of a large prime subgroup of E(F_p), and two 1574 points P and P_pub of order q in E(F_p). 1576 2. Apply Algorithm 7.4.2 (BFdecodePrivate) to kappa to obtain a 1577 private key point S_id. 1579 3. Apply Algorithm 7.5.2 (BFdecodeCiphertext) to gamma to obtain a 1580 ciphertext triple (U�, V�, W�). 1582 4. Perform Algorithm 5.5.1 (BFdecrypt) on (U�, V�, W�) using the 1583 private key S_id and the decoded set of public parameters, to obtain 1584 decrypted plaintext m, or an invalid ciphertext flag. 1586 (a) If the decryption was successful, return the plaintext m. 1588 (b) Otherwise, raise an error condition. 1590 7. Concrete encoding guidelines for BF 1592 This section specifies a set of concrete encoding schemes for the 1593 inputs and outputs of the previously described algorithms. ASN.1 1594 encodings are specified in Section 11 of this document. 1596 7.1. Encoding of points on a curve 1598 Algorithm 7.1.1 (EncodePoint): encodes a point in E(F_p) in an 1599 exportable format. 1601 Input: 1603 � a non-zero point Q in E(F_p). 1605 Output: 1607 � a fixed-length (for given p) byte-string encoding of Q. 1609 Method: 1611 1. Let (x, y) in F_p x F_p be the coordinates of P, where (x, y) 1612 satisfy the equation of E. 1614 2. The point P is then encoded as a FpPoint using the ASN.1 rules 1615 given in the ASN.1 module given in Section 11 of this document. 1617 Algorithm 6.1.2 (DecodePoint): decodes a point in E(F_p) from an 1618 exportable format. 1620 Input: 1622 � a byte-string encoding of a non-zero point Q in E(F_p). 1624 Output: 1626 � Q = (x, y). 1628 Method: 1630 1. The string is parsed and decoded as a pair (x, y), where x and y 1631 are integers in Z_p. 1633 2. Q is reconstructed as (x, y). 1635 7.2. Public parameters blocks 1637 Algorithm 7.2.1 (BFencodeParams): encodes a BF public parameter set 1638 in an exportable format. 1640 Input: 1642 � a set of public parameters (t, E, p, q, P, P_pub). 1644 Output: 1646 � a public parameter block pi, represented as a byte string. 1648 Method: 1650 1. Separate encodings for E, p, q, P, P_pub are obtained as follows: 1652 (a) If t = 1, execute Algorithm 7.2.3 (BFencodeParams1). 1654 2. The separate encodings as well as a type indicator flag for t are 1655 then serialized in any suitable manner as dictated by the 1656 application. 1658 Algorithm 7.2.2 (BFdecodeParams): imports a BF public parameter block 1659 from a serialized format. 1661 Input: 1663 � a public parameter block pi, represented as a byte string. 1665 Output: 1667 � a set of public parameters (t, E, p, q, P, P_pub). 1669 Method: 1671 1. Identify from the appropriate flag the type t of curve upon which 1672 the parameter block is based. 1674 2. Then: 1676 (a) If t = 1, execute Algorithm 7.2.4 (BFdecodeParams1). 1678 7.2.1. Type-1 implementation 1680 Algorithm 7.2.3 (BFencodeParams1): encodes a BF type-1 public 1681 parameter set in an exportable format. 1683 Input: 1685 � a set of public parameters (t, E, p, q, P, P_pub) with t = 1. 1687 Output: 1689 � separate encodings for each of the E, p, q, P, P_pub components. 1691 Method: 1693 1. E : y^2 = x^3 + a * x + b is represented as a constant string, 1694 such as the empty string, since a and b are invariant for type-1 1695 curves. 1697 2. p = 12 * r * q . 1 is represented as the smaller integer r, 1698 encoded, e.g., using a big-endian byte-string representation. 1700 3. q = 2^a + s * 2^b + c, where a, b are small and c and s are either 1701 1 or -1, is compactly represented as the 4-tuple (a, b, c, s). 1703 4. P = (x_P , y_P ) in F_p x F_p is represented using the point 1704 compression technique of Algorithm 7.1.1 (EncodePoint). 1706 5. P_pub is similarly encoded using Algorithm 7.1.1 (EncodePoint). 1708 Algorithm 7.2.4 (BFdecodeParams1): decodes the components of a BF 1709 type-1 public parameter block. 1711 Input: 1713 � separate encodings for each one of E, p, q, P, P_pub. 1715 Output: 1717 � a set of public parameters (t, E, p, q, P, P_pub) with t = 1. 1719 Method: 1721 1. The equation of E is set to E = E : y^2 = x^3 + 1, as is always 1722 the case for type-1 curves. The actual encoding of E is ignored. 1724 2. The encoding of q is parsed as (a, b, c, s), and its value set to 1725 q = 2^a + s * 2^b + c. 1727 3. The encoding of p is parsed as the integer r, from which p is 1728 given by p = 12 * r * q . 1. 1730 4. P is reconstructed from its encoding (x, y�) using the point 1731 decompression technique of Algorithm 7.1.2 (DecodePoint). 1733 5. P_pub is similarly reconstructed from its encoding using Algorithm 1734 7.1.2 (DecodePoint). 1736 7.3. Master secret blocks 1738 Algorithm 6.3.1 (BFencodeMaster): encodes a BF master secret in an 1739 exportable format. 1741 Input: 1743 � a master secret integer s between 2 and q - 1. 1745 Output: 1747 � a master secret block sigma, represented as a byte string. 1749 Method: 1751 1. Sigma is constructed as the unsigned big-endian byte-string 1752 encoding of s of length 8 * Ceiling(lg(p)). 1754 Algorithm 7.3.2 (BFdecodeMaster): decodes a BF master secret from a 1755 block in exportable format. 1757 Input: 1759 � a master secret block sigma, represented as a byte string. 1761 Output: 1763 � a master secret integer s in between 2 and q - 1 . 1765 Method: 1767 1. s = Value(sigma), where sigma is interpreted in the unsigned big 1768 endian convention. 1770 7.4. Private key blocks 1772 Algorithm 6.4.1 (BFencodePrivate): encodes a BF private key point in 1773 an exportable format. 1775 Input: 1777 � a private key point S_id in E(F_p). 1779 Output: 1781 � a private key block kappa, represented as a byte string. 1783 Method: 1785 1. kappa is obtained by applying Algorithm 7.1.1 (EncodePoint) to 1786 S_id. 1788 Algorithm 7.4.2 (BFdecodePrivate): decodes a BF private key point 1789 from an exportable format. 1791 Input: 1793 � a private key block kappa, represented as a byte string. 1795 Output: 1797 � a private key point S_id in E(F_p). 1799 Method: 1801 1. Kappa is parsed and decoded into a point S_id in E(F_p) using 1802 Algorithm 7.1.2 (DecodePoint). 1804 7.5. Ciphertext blocks 1806 Algorithm 7.5.1 (BFencodeCiphertext): encodes a BF ciphertext tuple 1807 in an exportable format. 1809 Input: 1811 � a ciphertext tuple (U, V, W) in E(F_p) x {0, . . . , 255}^20 x {0, 1812 . . . , 255}*. 1814 Output: 1816 � a ciphertext block gamma, represented as a byte string. 1818 Method: 1820 1. U = (x, y) is first encoded as a fixed-length string using 1821 Algorithm 7.1.1 (EncodePoint). 1823 2. Gamma is obtained as the encoding of U, concatenated with the 1824 fixed-length string V, and the variable length string W, both already 1825 in byte-string format. 1827 Algorithm 7.5.2 (BFdecodeCiphertext): decodes a BF ciphertext tuple 1828 from an exportable format. 1830 Input: 1832 � a ciphertext block gamma, represented as a byte string. 1834 Output: 1836 � a ciphertext tuple (U, V, W) in E(F_p) x {0, . . . , 255}^20 x {0, 1837 . . . , 255}*. 1839 Method: 1841 1. Gamma is parsed as a 3-tuple comprising a fixed-length encoding 1842 of U, followed by a 20-byte string V, followed by an arbitrary-length 1843 string W. 1845 2. U in E(F_p) is then recovered by applying Algorithm 7.1.2 1846 (DecodePoint) on its encoding. 1848 8. The Boneh-Boyen BB1 cryptosystem 1850 This chapter describes the algorithms constituting the first of the 1851 two Boneh-Boyen identity-based cryptosystems proposed in [2]. The 1852 description follows the practical implementation given in [2]. 1854 8.1. Setup 1856 Algorithm 8.1.1 (BBsetup). Randomly selects a set of master secrets 1857 and the associated public parameters. 1859 Input: 1861 � a curve type t (currently required to be fixed to t = 1), 1863 � a security parameter n (currently required to take values n >= 1864 1024). 1866 Output: 1868 � a set of common public parameters, 1869 � a corresponding master secret. 1871 Method: 1873 1. Depending on the selected type t: 1875 (a) If t = 1, then Algorithm 8.1.2 (BBsetup1) is executed. 1877 2. The resulting master secret and public parameters are separately 1878 encoded as per the application protocol requirements. 1880 8.1.1. Type-1 curve implementation 1882 BBsetup1 takes a security parameter n as input. For type-1 curves, 1883 the scale of n corresponds to the modulus bit-size believed of 1884 comparable security in the classical Diffie-Hellman or RSA public-key 1885 cryptosystems. For this implementation, allowed values of n are 1886 limited to 1024, 2048, and 3072, which correspond to the equivalent 1887 security level ranging from 80-, 112- and 128-bit symmetric keys 1888 respectively. 1890 Algorithm 7.1.2 (BBsetup1): randomly establishes a master secret and 1891 public parameters for type-1 curves. 1893 Input: 1895 � a security parameter n, either 1024, 2048 or 3072. 1897 Output: 1899 � a set of common public parameters (t, k, E, p, q, P, P_1, P_2, P_3, 1900 v), 1902 � a corresponding triple of master secrets (alpha, beta, gamma). 1904 Method: 1906 1. Determine the subordinate security parameters n_p and n_q as 1907 follows: 1909 (a) n_p = n / 2, which will determine the size of the field F_p. 1911 (b) if n = 1024, n_q = 160; if n = 2048, n_q = 224; if n = 3072, 1912 n_q = 256, which will determine the size of the subgroup order q. 1914 2. Construct the elliptic curve and its subgroup of interest, as 1915 follows: 1917 (a) Select an arbitrary n_q-bit prime q, i.e., such that 1918 Ceiling(lg(p)) = n_q. For better performance, q is chosen as a 1919 Solinas prime, i.e., a prime of the form q = 2^a +/- 2^b +/- 1 where 1920 0 < b < a. 1922 (b) Select a random integer r such that p = 12 * r * q . 1 is an 1923 n_p-bit prime, i.e., such that Ceiling(lg(p)) = n_p. 1925 3. Select a point P of order q in E(F_p), as follows: 1927 (a) Select a random point P� of coordinates (x�, y�) on the curve 1928 E/F_p : y2 = x3 + 1 (mod p). 1930 (b) Let P = [12 * r]P�. 1932 (c) If P = 1, then start over in step 3a. 1934 4. Determine the master secret and the public parameters as follows: 1936 (a) Select three random integers alpha, beta, gamma, each of them 1937 in the range 1 to q . 1. 1939 (b) Let P_1 = [alpha]P. 1941 (c) Let P_2 = [beta]P. 1943 (d) Let P_3 = [gamma]P. 1945 (e) Let v = Pairing(E, p, q, P_1, P_2), which is an element of the 1946 extension field F_p2 obtained using the modified Tate pairing of 1947 Algorithm 3.5.1 (Pairing). 1949 5. (t, k, E, p, q, P, P_1, P_2, P_3, v) are the common public 1950 parameters, where t = 1, k = 2, and E : y^2 = x^3 + 1. 1952 6. (alpha, beta, gamma) constitute the master secret. 1954 8.2. Public key derivation 1956 BBderivePubl takes an identity string id and a set of public 1957 parameters, and returns an integer h_id. 1959 Algorithm 7.2.1 (BBderivePubl): derives the public key corresponding 1960 to an identity string. 1962 Input: 1964 � an identity string id, 1966 � a set of common public parameters (t, k, E, p, q, P, P_1, P_2, P_3, 1967 v). 1969 Output: 1971 � an integer h_id modulo q. 1973 Method: 1975 1. Let h_id HashToRangeq(id), using Algorithm 3.1.1 (HashToRange). 1977 8.3. Private key extraction 1979 BBextractPriv takes an identity string id, and a set of public 1980 parameters and corresponding master secrets, and returns a private 1981 key consisting of two points D_0 and D_1. 1983 Algorithm 8.3.1 (BBextractPriv): extracts the private key 1984 corresponding to an identity string. 1986 Input: 1988 � an identity string id, 1990 � a set of common public parameters (t, k, E, p, q, P, P_1, P_2, P_3, 1991 v). 1993 Output: 1995 � a pair of points (D_0, D_1), each of which has order q in E(F_p). 1997 Method: 1999 1. Select a random integer r in the range 1 to q . 1. 2001 2. Calculate the point D_0 as follows: 2003 (a) Let hid = HashToRange(q, id), using Algorithm 3.1.1 2004 (HashToRange). 2006 (b) Let y = alpha * beta + r * (alpha * h_id * gamma) in 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 for id. 2016 8.4. Encryption 2018 BBencrypt takes three inputs: a set of public parameters, an identity 2019 id, and a plaintext m. The plaintext is intended to be a short random 2020 session key, although messages of arbitrary size are in principle 2021 allowed. 2023 Algorithm 7.4.1 (BBencrypt): encrypts a short message or session key 2024 for an identity string. 2026 Input: 2028 � a plaintext string m of size |m| bytes, 2030 � a recipient identity string id, 2032 � a set of public parameters (t, k, E, p, q, P, P_1, P_2, P_3, v). 2034 Output: 2036 � a ciphertext tuple (u, C_0, C_1, y) in F_q x E(F_p) x E(F_p) x {0, 2037 . . . , 255}^|m|. 2039 Method: 2041 1. Let the public parameter set be comprised of a prime p, a curve 2042 E/F_p, the order q of a large prime subgroup of E(F_p), four points 2043 P, P_1, P_2, P_3, of order q in E(F_p), and an extension field 2044 element v of order q in F_p2 . 2046 2. Select a random integer s in the range 1 to q . 1. 2048 3. Let w = v^s, which is v raised to the power of s in F_p^2 , the 2049 result is an element of order q in F_p^2 . 2051 4. Calculate the point C_0 as follows: 2053 (a) Let C_0 = [s]P. 2055 5. Calculate the point C_1 as follows: 2057 (a) Let _hid = HashToRangeq(id), using Algorithm 3.1.1 2058 (HashToRange). 2060 (b) Let y = s * h_id in F_q. 2062 (c) Let C_1 = [y]P_1 + [s]P_3. 2064 6. Obtain canonical string representations of certain elements: 2066 (a) psi = Canonical(p, k, 1, w) using Algorithm 3.3.1 (Canonical), 2067 the result of which is a canonical byte-string representation of w. 2069 (b) Let l = Ceiling(8 * lg(p)), the number of bytes needed to 2070 represent integers in F_p, and represent each of these F_p elements 2071 as a big-endian zero-padded byte-string of fixed length l: 2073 � (x_0)_(256^l) to represent the x coordinate of C_0. 2075 � (y_0)_(256^l) to represent the y coordinate of C_0. 2077 � (x_1)_(256^l) to represent the x coordinate of C_1. 2079 � (y_1)_(256^l) to represent the y coordinate of C_1. 2081 7. Encrypt the message m into the string y as follows: 2083 (a) Compute an encryption key h_0 as a dual-pass hash of w via its 2084 representation psi: 2086 i. Let zeta = SHA1(psi), using the SHA1 hashing algorithm; the 2087 result is a 20-byte string. 2089 ii. Let xi = SHA1(zeta || psi), using the SHA1 hashing 2090 algorithm; the result is a 20-byte string. 2092 iii. Let h� = xi || zeta, the 40-byte concatenation of the 2093 previous two SHA1 outputs. 2095 (b) Let y = HashStream(|m|, h�) XOR m, which is the bit-wise 2096 exclusive-OR of m with the first |m| bytes of the pseudo-random 2097 stream produced by Algorithm 3.2.1 (HashStream) with seed h�. 2099 8. Create the integrity check tag u as follows: 2101 (a) Compute a one-time pad h�� as a dual-pass hash of the 2102 representation of (w, C_0, C_1, y): 2104 i. Let sigma = (y_1)_(256^l) || (x_1)_(256^l) || (y_0)_(256^l) 2105 || (x_0)_(256^l) || y || psi be the concatenation of y and the five 2106 indicated strings in the specified order. 2108 ii. Let eta = SHA1(sigma), using the SHA1 hashing algorithm to 2109 get a 20-byte string. 2111 iii. Let mu = SHA1(eta || sigma), using the SHA1 hashing 2112 algorithm to get a 20-byte string. 2114 iv. Let h�� = mu || eta, the 40-byte concatenation of the 2115 previous two SHA1 outputs. 2117 (b) Build the tag u as the encryption of the integer s with the 2118 one-time pad h��: 2120 i. Let rho = HashToRangeq(h��) to get an integer in Z_q. 2122 ii. Let u = s + rho (mod q). 2124 9. The complete ciphertext is given by the quadruple (u, C_0, C_1, 2125 y). 2127 8.5. Decryption 2129 BBdecrypt takes three inputs: a set of public parameters, a private 2130 key (D_0, D_1), and a ciphertext parsed as (u, C_0, C_1, y). It 2131 outputs a message m, or signals an error if the ciphertext is invalid 2132 for the given key. 2134 Algorithm 7.5.1 (BBdecrypt): decrypts a short message or session key 2135 using a private key. 2137 Input: 2139 � a private key given as a pair of points (D_0, D_1) of order q in 2140 E(F_p), 2142 � a ciphertext quadruple (u, C_0, C_1, y) in Z_q x E(F_p) x E(F_p) x 2143 {0, . . . , 255}*. 2145 � a set of public parameters. 2147 Output: 2149 � a decrypted plaintext m, or an invalid ciphertext flag. 2151 Method: 2153 1. Let the public parameter set be comprised of a prime p, a curve 2154 E/F_p, the order q of a large prime subgroup of E(F_p), four points 2155 P, P_1, P_2, P_3, of order q in E(F_p), and an extension field 2156 element v of order q in F_p^2 . 2158 2. Let w = PairingRatio(E, p, q, C_0, D_0, C_1, D_1), which computes 2159 the ratio of two Tate pairings (modified, for type-1 curves) as 2160 specified in Algorithm 4.6.1 (PairingRatio). 2162 3. Obtain canonical string representations of certain elements: 2164 (a) psi = Canonical(p, k, 1, w), using Algorithm 4.3.1 2165 (Canonical); the result is a canonical byte-string representation of 2166 w. 2168 (b) Let l = Ceiling(8 * lg(p)), the number of bytes needed to 2169 represent integers in F_p, and represent each of these F_p elements 2170 as a big-endian zero-padded byte-string of fixed length l: 2172 � (x_0)_(256^l) to represent the x coordinate of C_0. 2174 � (y_0)_(256^l) to represent the y coordinate of C_0. 2176 � (x_1)_(256^l) to represent the x coordinate of C_1. 2178 � (y_1)_(256^l) to represent the y coordinate of C_1. 2180 4. Decrypt the message m from the string y as follows: 2182 (a) Compute the decryption key h� as a dual-pass hash of w via its 2183 representation psi: 2185 i. Let zeta = SHA1(psi), using the SHA1 hashing algorithm to 2186 get a 20-byte string. 2188 ii. Let xi = SHA1(zeta || psi), using the SHA1 hashing 2189 algorithm to get a 20-byte string. 2191 iii. Let h� = xi || zeta, the 40-byte concatenation of the 2192 previous two SHA1 outputs. 2194 (b) Let m = HashStream(|y|, h�)_XOR y, which is the bit-wise 2195 exclusive-OR of y with the first |y| bytes of the pseudo-random 2196 stream produced by Algorithm 3.2.1 (HashStream) with seed h�. 2198 5. Obtain the integrity check tag u as follows: 2200 (a) Recover the one-time pad h�� as a dual-pass hash of the 2201 representation of (w, C_0, C_1, y): 2203 i. Let sigma = (y_1)_(256^l) || (x_1)_(256^l) || (y_0)_(256^l) 2204 || (x_0)_(256^l) || y || psi be the concatenation of y and the five 2205 indicated strings in the specified order. 2207 ii. Let eta = SHA1(sigma) using the SHA1 hashing algorithm to 2208 get a 20-byte string. 2210 iii. Let mu = SHA1(eta || sigma), using the SHA1 hashing 2211 algorithm to get a 20-byte string. 2213 iv. Let h�� = mu || eta, the 40-byte concatenation of the 2214 previous two SHA1 outputs. 2216 (b) Unblind the encryption randomization integer s from the tag u 2217 using h��: 2219 i. Let rho = HashToRangeq(h��) to get an integer in Z_q. 2221 ii. Let s = u - rho (mod q). 2223 6. Verify the ciphertext consistency according to the decrypted 2224 values: 2226 (a) Test whether the equality w = v^s holds in F_p2 . 2228 (b) Test whether the equality C_0 = [s]P holds in E(F_p). 2230 7. Adjudication and final output: 2232 (a) If either of the tests performed in step 6 fails, the 2233 ciphertext is rejected, and no decryption is output. 2235 (b) Otherwise, i.e., when both tests performed in step 6 succeed, 2236 the decrypted message is output. 2238 9. Wrapper methods for the BB1 system 2240 This section describes a number of wrapper methods providing the 2241 identity-based cryptosystem functionalities using concrete encodings. 2242 The following functions are presently given based on the Boneh- 2243 Franklin algorithms. 2245 9.1. Private key generator (PKG) setup 2247 Algorithm 9.1.1 (BBwrapperPKGSetup): randomly selects a PKG master 2248 secret and a set of public parameters. 2250 Input: 2252 � a curve type t, 2254 � a security parameter n. 2256 Output: 2258 � a common public parameter block pi, 2260 � a corresponding master secret block sigma. 2262 Method: 2264 1. Perform Algorithm 8.1.1 (BBsetup) on parameters t and n, producing 2265 a set of public parameters and master secret. 2267 2. Apply Algorithm 10.2.1 (BBencodeParams) on the public parameters 2268 obtained in step 1 to get the public parameter block pi. 2270 3. Apply Algorithm 10.3.1 (BBencodeMaster) on the master secrets 2271 obtained in step 1 to get the master secret block sigma. 2273 9.2. Private key extraction by the PKG 2275 Algorithm 9.2.1 (BBwrapperPrivateKeyExtract): extraction by the PKG 2276 of a private key corresponding to an identity. 2278 Input: 2280 � a master secret block sigma, 2282 � a corresponding public parameter block pi, 2284 � an identity string id. 2286 Output: 2288 � a private key block kappa_id. 2290 Method: 2292 1. Apply Algorithm 10.2.2 (BBdecodeParams) on the public parameter 2293 block pi to obtain the public parameters, comprising a prime p, the 2294 parameters of a curve E/F_p with some embedding degree k, the order q 2295 of a large prime subgroup of E(F_p), four points P, P_1, P_2, P_3, of 2296 order q in E(F_p), and an element v of order q in the extension field 2297 F_p^k of degree k. 2299 2. Apply Algorithm 10.3.2 (BBdecodeMaster) on the master secret block 2300 sigma to obtain the master secret (alpha, beta, gamma). 2302 3. Perform Algorithm 8.3.1 (BBextractPriv) on the identity id, using 2303 the decoded public parameters and master secret, to produce a private 2304 key (D_0, D_1). 2306 4. Apply Algorithm 10.4.1 (BBencodePrivate) on the private key to 2307 produce a private key block kappa_id. 2309 9.3. Session key encryption 2311 Algorithm 9.3.1 (BBwrapperSessionKeyEncrypt): encrypts a short 2312 message or session key for an identity. 2314 Input: 2316 � a public parameter block pi, 2318 � a recipient identity string id, 2320 � a plaintext string m (possibly comprising the concatenation of a 2321 pair of random session keys for symmetric encryption and message 2322 authentication purposes on a larger plaintext). 2324 Output: 2326 � a ciphertext block omega. 2328 Method: 2330 1. Apply Algorithm 10.2.2 (BBdecodeParams) on the public parameter 2331 block pi to obtain the public parameters, comprising a prime p, the 2332 parameters of a curve E/F_p with some embedding degree k, the order q 2333 of a large prime subgroup of E(F_p), four points P, P_1, P_2, P_3, of 2334 order q in E(F_p), and an element v of order q in the extension field 2335 F_p^k . 2337 2. Perform Algorithm 8.4.1 (BBencrypt) on the plaintext m for 2338 identity id using the decoded set of parameters, to obtain a 2339 ciphertext quadruple (u, C_0, C_1, y). 2341 3. Apply Algorithm 10.5.1 (BBencodeCiphertext) on the ciphertext (u, 2342 C_0, C_1, y) to obtain a string representation of omega. 2344 Algorithm 9.3.2 (BBwrapperSessionKeyDecrypt): decrypts a short 2345 message or session key using a private key. 2347 Input: 2349 � a public parameter block pi, 2351 � a private key block kappa, 2353 � a ciphertext block omega. 2355 Output: 2357 � a decrypted plaintext string m, or an error flag signaling an 2358 invalid ciphertext. 2360 Method: 2362 1. Apply Algorithm 10.2.2 (BBdecodeParams) on the public parameter 2363 block pi to obtain the public parameters, comprising a prime p, the 2364 parameters of a curve E/F_p with some embedding degree k, the order q 2365 of a large prime subgroup of E(F_p), four points P, P_1, P_2, P_3, of 2366 order q in E(F_p), and an element v of order q in the extension field 2367 F_p^k. 2369 2. Apply Algorithm 10.4.2 (BBdecodePrivate) on kappa to obtain the 2370 private key points (D_0, D_1). 2372 3. Apply Algorithm 10.5.2 (BBdecodeCiphertext) on omega to obtain a 2373 ciphertext quadruple (u, C_0, C_1, y). 2375 4. Perform Algorithm 8.5.1 (BBdecrypt) on (u, C_0, C_1, y) using the 2376 private key (D_0, D_1) and the decoded set of public parameters, to 2377 obtain decrypted plaintext m, or an invalid ciphertext flag. 2379 (a) If the decryption was successful, return the plaintext string 2380 m. 2382 (b) Otherwise, raise an error condition. 2384 10. Concrete encoding guidelines for BB1 2386 This section specifies a set of concrete encoding schemes for the 2387 inputs and outputs of the previously described algorithms. ASN.1 2388 encodings are specified in Section 11 of this document. 2390 10.1. Encoding of points on a curve 2392 We refer to the description of Algorithm 7.1.1 (EncodePoint) and 2393 Algorithm 7.1.2 (DecodePoint). 2395 10.2. Public parameters blocks 2397 Algorithm 10.2.1 (BBencodeParams): encodes a BB1 public parameter set 2398 in an exportable format. 2400 Input: 2402 � a set of public parameters (t, k, E, p, q, P, P_1, P_2, P_3, v). 2404 Output: 2406 � a public parameter block pi, represented as a byte string. 2408 Method: 2410 1. Separate encodings for k, E, p, q, P, P_1, P_2, P_3 are obtained 2411 as follows: 2413 (a) If t = 1, execute Algorithm 10.2.3 (BBencodeParams1). 2415 2. The separate encodings as well as a type indicator flag for t are 2416 then serialized in any suitable manner as dictated by the 2417 application. 2419 Algorithm 10.2.2 (BBdecodeParams): imports a BB1 public parameter 2420 block from a serialized format. 2422 Input: 2424 � a public parameter block pi, represented as a byte string. 2426 Output: 2428 � a set of public parameters (t, k, E, p, q, P, P_1, P_2, P_3, v). 2430 Method: 2432 1. Identify from the appropriate flag the type t of curve upon which 2433 the parameter block is based. 2435 2. Then: 2437 (a) If t = 1, execute Algorithm 10.2.4 (BBdecodeParams1). 2439 10.2.1. Type-1 implementation 2441 Algorithm 10.2.3 (BBencodeParams1): encodes a BB1 type-1 public 2442 parameter set in an exportable format. 2444 Input: 2446 � a set of public parameters (t, k, E, p, q, P, P_1, P_2, P_3, v) 2447 with t = 1. 2449 Output: 2451 � separate encodings for each of the k, E, p, q, P, P_1, P_2, P_3 2452 components (v is redundant and omitted). 2454 Method: 2456 1. E : y^2 = x^3 + a * x + b and k = 2 are represented as a constant 2457 string, such as the empty string, since the coefficients a and b and 2458 the embedding degree k are invariant for type-1 curves. 2460 2. p = 12 * r * q . 1 is represented as the smaller integer r, 2461 encoded, e.g., using a big-endian byte-string representation. 2463 3. q = 2^a + s* 2^b + c, where a, b are small and both c and s are 2464 either 1 or -1 is compactly represented as the 4-tuple (a, b, c, s). 2466 4. P = (x_P , y_P ) in F_p x F_p is represented using the point 2467 compression technique of Algorithm 7.1.1 (EncodePoint). 2469 5. Each of P_1, P_2, and P_3 is similarly encoded using Algorithm 2470 7.1.1 (EncodePoint). 2472 Algorithm 10.2.4 (BBdecodeParams1): decodes the components of a BB1 2473 type-1 public parameter block. 2475 Input: 2477 � separate encodings for each one of k, E, p, q, P, P_1, P_2, P_3. 2479 Output: 2481 � a set of public parameters (t, k, E, p, q, P, P_1, P_2, P_3, v) 2482 with t = 1. 2484 Method: 2486 1. The equation of E is set to E E : y^2 = x^3 + 1, as is always 2487 the case for type-1 curves. 2489 2. The embedding degree is set to k = 2 for type-1 curves. 2491 3. The encoding of q is parsed as (a, b, c, s), and its value set to 2492 q = 2^a + s * 2^b + c. 2494 4. The encoding of p is parsed as the integer r, from which p is 2495 given by p = 12 * r * q . 1. 2497 5. P is reconstructed from its encoding (x, y�) using the point 2498 decompression technique of Algorithm 7.1.2 (DecodePoint). 2500 6. Each of P_1, P_2, and P_3 is reconstructed in a similar manner 2501 from its encoding using Algorithm 7.1.2 (DecodePoint). 2503 7. The extension field element v is reconstructed as v = Pairing(E, 2504 p, q, P_1, P_2) using Algorithm 4.5.1 (Pairing). 2506 10.3. Master secret blocks 2508 Algorithm 10.3.1 (BBencodeMaster): encodes a BB1 master secret in an 2509 exportable format. 2511 Input: 2513 � a master secret triple of integers (alpha, beta, gamma) in (Z+_q 2514 )^3. 2516 Output: 2518 � a master secret block sigma, represented as a byte string. 2520 Method: 2522 1. Encode each integer as an unsigned big-endian byte-string of fixed 2523 length Ceiling(8 * lg(q)), or, when q is a Solinas prime q = 2^a +/- 2524 2^b +/- 1, of length Ceiling((a + 1) / 8): 2526 (a) sigma_alpha to represent alpha. 2528 (b) sigma_beta to represent beta. 2530 (c) sigma_gamma to represent gamma. 2532 2. Sigma = sigma_alpha || sigma_beta || sigma_gamma is the 2533 concatenation of these strings. 2535 Algorithm 10.3.2 (BBdecodeMaster): decodes a BB1 master secret from a 2536 block in exportable format. 2538 Input: 2540 � a master secret block sigma, represented as a byte string. 2542 Output: 2544 � a master secret triple of integers (alpha, beta, gamma) in (Z+_q 2545 )^3. 2547 Method: 2549 1. Parse sigma as sigma_alpha || sigma_beta || sigma_gamma, where 2550 each substring is a byte string of fixed length Ceiling(8 * lg(q)), 2551 or, when q is a Solinas prime q = 2^a +/- 2^b +/- 1, of length 2552 Ceiling((a + 1) / 8)). 2554 2. Decode each substring as an integer in unsigned big-endian byte- 2555 string representation: 2557 (a) alpha = Value(sigma_alpha). 2559 (b) beta = Value(sigma_beta). 2561 (c) gamma = Value(sigma_gamma). 2563 10.4. Private key blocks 2565 Algorithm 10.4.1 (BBencodePrivate): encodes a BB1 private key in an 2566 exportable format. 2568 Input: 2570 � a private key pair of points (D_0, D_1) in E(F_p) x E(F_p). 2572 Output: 2574 � a private key block kappa, represented as a byte string. 2576 Method: 2578 1. Encode each point separately: 2580 (a) kappa_0 is obtained by applying Algorithm 7.1.1 (EncodePoint) 2581 to D_0. 2583 (b) kappa_1 is obtained by applying Algorithm 7.1.1 (EncodePoint) 2584 to D_0. 2586 2. Kappa = kappa_0 || kappa_1. 2588 Algorithm 10.4.2 (BBdecodePrivate): decodes a BB1 private key from an 2589 exportable format. 2591 Input: 2593 � a private key block kappa, represented as a byte string. 2595 Output: 2597 � a private key pair of point (D_0, D_1) in E(F_p) x E(F_p). 2599 Method: 2601 1. Decode each point separately: 2603 (a) The first prefix of kappa is parsed and decoded into a point 2604 D_0 in E(F_p) using Algorithm 7.1.2 (DecodePoint). 2606 (b) The remainder of kappa is parsed and decoded into a point D_1 2607 in E(F_p) using Algorithm 7.1.2 (DecodePoint). 2609 10.5. Ciphertext blocks 2611 Algorithm 10.5.1 (BBencodeCiphertext). Encodes a BB1 ciphertext tuple 2612 in an exportable format. 2614 Input: 2616 � a ciphertext tuple (u, C_0, C_1, y) in Z_q x E(F_p) x E(F_p) x {0, 2617 . . . , 255}*. 2619 Output: 2621 � a ciphertext block omega, represented as a byte string. 2623 Method: 2625 1. Let chi_0 be the fixed-length encoding of C_0 = (x_0, y_0) using 2626 Algorithm 7.1.1 (EncodePoint). 2628 2. Let chi_1 be the fixed-length encoding of C_1 = (x_1, y_1) using 2629 Algorithm 7.1.1 (EncodePoint). 2631 3. Let nu be the encoding of u as an unsigned big-endian byte-string 2632 of fixed length Ceiling(8 * lg(q)), or, when q is a Solinas prime q = 2633 2^a +/- 2^b +/- 1, of length Ceiling((a + 1)/8). 2635 4. Omega = chi_0 || chi_1 || nu || y is the concatenation of these 2636 three strings and y. 2638 Algorithm 10.5.2 (BBdecodeCiphertext): decodes a BB1 ciphertext tuple 2639 from an exportable format. 2641 Input: 2643 � a ciphertext block omega, represented as a byte string. 2645 Output: 2647 � a ciphertext tuple (u, C_0 ,C_1, y) in Z_q x E(F_p) x E(F_p) x {0, 2648 . . . , 255}*. 2650 Method: 2652 1. Omega is parsed as a quadruple comprising a fixed-length encoding 2653 of C_0, a fixed-length encoding of C_1, a fixed-length encoding of u, 2654 and the arbitrary-length string y: 2656 (a) C_0 in E(F_p) is first recovered by applying Algorithm 7.1.2 2657 (DecodePoint) on the first parsed component of omega. 2659 (b) C_1 in E(F_p) is next recovered by applying Algorithm 7.1.2 2660 (DecodePoint) on the second parsed component of omega. 2662 (c) u in Z_q is then recovered from its unsigned big-endian byte- 2663 string representation in the third parsed component of omega, of 2664 length Ceiling(8 * lg(q)), or, when q is a Solinas prime q = 2^a +/- 2665 2b +/- 1, of length Ceiling((a + 1)/8). 2667 (d) y is finally taken as the remainder of omega. 2669 11. ASN.1 module 2671 This section defines the ASN.1 module for the encodings discussed in 2672 sections 7 and 10. 2674 IBCS { joint-iso-itu(2) country(16) us(840) organization(1) 2675 identicrypt(114334) ibcs(1) module(5) version(1) } 2677 DEFINITIONS IMPLICIT TAGS ::= BEGIN 2679 -- 2680 -- Identity-based cryptography standards (IBCS): supersingular curve 2681 -- implementations of the BF and BB1 cryptosystems. 2682 -- 2683 -- This version of the IBCS standard only supports IBE over 2684 -- type-1 curves. In the current version, the Curve type is 2685 -- always set to NULL, although future versions will use it. 2686 -- 2688 IMPORTS Curve 2689 FROM X9-62-module 2690 { iso(1) member-body(2) us(840) ansi-x9-62(10045) module(5) 1 2691 }; 2693 ibcs OBJECT IDENTIFIER ::= { 2694 joint-iso-itu(2) country(16) us(840) organization(1) 2695 identicrypt(114334) ibcs(1) 2696 } 2698 -- 2699 -- IBCS1 2700 -- 2701 -- IBCS1 defines the algorithms used to implement IBE 2702 -- 2704 ibcs1 OBJECT IDENTIFIER ::= { 2705 ibcs ibcs1(1) 2706 } 2707 -- 2708 -- Supporting types 2709 -- 2711 -- 2712 -- Encoding of a point on an elliptic curve E/Fp. 2713 -- 2715 FpPoint ::= SEQUENCE { 2716 x INTEGER, 2717 y INTEGER 2718 } 2720 -- 2721 -- Encoding of a Solinas prime. 2722 -- 2723 -- Encodes a Solinas prime of the form 2724 -- q = 2^a + s * 2^b +c with the integers a, b, c, and s. 2725 -- 2727 SolinasPrime ::= SEQUENCE { 2728 a INTEGER, 2729 b INTEGER, 2730 c INTEGER { positive(1), negative(-1) }, 2731 s INTEGER { positive(1), negative(-1) } 2732 } 2734 -- 2735 -- Algorithms 2736 -- 2738 ibe-algorithms OBJECT IDENTIFIER ::= { 2739 ibcs1 ibe-algorithms(2) 2741 } 2743 --- 2744 --- Boneh-Franklin IBE 2745 --- 2747 bf OBJECT IDENTIFIER ::= { ibe-algorithms bf(1) } 2749 -- 2750 -- Encoding of a BF public parameters block. 2751 -- The only version currently supported is version 1. 2752 -- For type-1 curves, the curve is fixed, so Curve is set to NULL 2753 -- For the BF prime p and subprime q, we have q * r = p + 1, 2754 -- and we encode the values of r and q in the public parameters. 2755 -- The points P and P_pub are encoded as pointP and pointPpub 2756 respectively. 2757 -- 2759 BFPublicParamaters ::= SEQUENCE { 2760 version INTEGER { v1(1) }, 2761 curve Curve { NULL }, 2762 r INTEGER, 2763 q SolinasPrime, 2764 pointP FpPoint, 2765 pointPpub FpPoint 2766 } 2768 -- 2769 -- A BF private key is a point on an elliptic curve, 2770 -- which is an FpPoint. 2771 -- 2773 BFPrivateKeyBlock ::= FpPoint 2774 -- 2775 -- A BF master secret is an integer. 2776 -- 2778 BFMasterSecret ::= INTEGER 2780 -- 2781 -- BF ciphertext block 2782 -- 2784 BFCiphertextBlock ::= SEQUENCE { 2785 U FpPoint, 2786 v OCTET STRING, 2787 w OCTET STRING 2788 } 2790 -- 2791 -- Boneh-Boyen (BB1) IBE 2792 -- 2794 bb1 OBJECT IDENTIFIER ::= {ibe-algorithms bb1(2) } 2796 -- 2797 -- Encoding of a BB1 public parameters block. 2798 -- The version is currently fixed to 1. 2799 -- The embedding degree is currently fixed to 2. 2800 -- For type-1 curves, curve is set to NULL. 2801 -- For the BB1 prime p and subprime q, we have q * r = p + 1, 2802 -- and we encode the values of r and q in the public parameters. 2803 -- 2805 BB1PublicParameters ::= SEQUENCE { 2806 Version INTEGER { v1(1) }, 2807 embedding-degree INTEGER { degree-2(2) }, 2808 curve Curve { NULL }, 2809 r INTEGER, 2810 q SolinasPrime, 2811 pointP FpPoint, 2812 pointP1 FpPoint, 2813 pointP2 FpPoint, 2814 pointP3 FpPoint 2815 } 2817 -- 2818 -- BB1 master secret block 2819 -- 2821 BB1MasterSecret ::= SEQUENCE { 2822 alpha INTEGER, 2823 beta INTEGER, 2824 gamma INTEGER 2825 } 2827 -- 2828 -- BB1 private Key block 2829 -- 2831 BB1PrivateKeyBlock ::= SEQUENCE { 2832 pointD0 FpPoint, 2833 pointD1 FpPoint 2834 } 2836 -- 2837 -- BB1 ciphertext block 2838 -- 2839 BB1CiphertextBlock ::= SEQUENCE { 2840 pointChi0 FpPoint, 2841 pointChi1 FpPoint, 2842 nu INTEGER, 2843 y OCTET STRING 2844 } 2845 END 2847 12. Security considerations 2849 This entire document discusses security considerations. 2851 13. IANA considerations 2853 All of the OIDs used in this document were assigned by the National 2854 Institute of Standards and Technology (NIST), so no further action by 2855 the IANA is necessary for this document. 2857 14. Acknowledgments 2859 This document is based on the IBCS #1 v2 document of Voltage 2860 Security, Inc. Any substantial use of material from this document 2861 should acknowledge Voltage Security, Inc. as the source of the 2862 information. 2864 15. References 2866 15.1. Informative references 2868 [1] I. Blake, G. Seroussi, N. Smart, Elliptic Curves in 2869 Cryptography, Cambridge University Press, 1999. 2871 [2] D. Boneh, X. Boyen, �Efficient selective-ID secure identity 2872 based encryption without random oracles,� In Proc. of EUROCRYPT 2873 �04, LNCS 3027, pp. 223�238, 2004. 2875 [3] D. Boneh, M. Franklin, �Identity-based encryption from the Weil 2876 pairing,� In Proc. of CRYPTO �01, LNCS 2139, pp. 213�229, 2001. 2878 Authors� Addresses 2880 Xavier Boyen 2881 Voltage Security 2882 1070 Arastradero Rd Suite 100 2883 Palo Alto, CA 94304 2885 Email: xavier@voltage.com 2887 Luther Martin 2888 Voltage Security 2889 1070 Arastradero Rd Suite 100 2890 Palo Alto, CA 94304 2892 Email: martin@voltage.com 2894 Intellectual Property Statement 2896 The IETF takes no position regarding the validity or scope of any 2897 Intellectual Property Rights or other rights that might be claimed to 2898 pertain to the implementation or use of the technology described in 2899 this document or the extent to which any license under such rights 2900 might or might not be available; nor does it represent that it has 2901 made any independent effort to identify any such rights. Information 2902 on the procedures with respect to rights in RFC documents can be 2903 found in BCP 78 and BCP 79. 2905 Copies of IPR disclosures made to the IETF Secretariat and any 2906 assurances of licenses to be made available, or the result of an 2907 attempt made to obtain a general license or permission for the use of 2908 such proprietary rights by implementers or users of this 2909 specification can be obtained from the IETF on-line IPR repository at 2910 http://www.ietf.org/ipr. 2912 The IETF invites any interested party to bring to its attention any 2913 copyrights, patents or patent applications, or other proprietary 2914 rights that may cover technology that may be required to implement 2915 this standard. Please address the information to the IETF at ietf- 2916 ipr@ietf.org. 2918 Disclaimer of Validity 2920 This document and the information contained herein are provided on an 2921 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 2922 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 2923 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 2924 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 2925 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 2926 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 2928 Copyright Statement 2930 Copyright (C) The Internet Society (2006). 2932 This document is subject to the rights, licenses and restrictions 2933 contained in BCP 78, and except as set forth therein, the authors 2934 retain all their rights. 2936 Acknowledgment 2938 Funding for the RFC Editor function is currently provided by the 2939 Internet Society.