[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: 00 01 02 03 04 05 06 07 RFC 5091

                                                              X. Boyen
                                                             L. Martin
     Internet Draft                                   Voltage Security
     Expires: September 2006                                March 2006
     
     
     
        Identity-Based Cryptography Standard (IBCS) #1: Supersingular
            Curve Implementations of the BF and BB1 Cryptosystems
     
     
                          <draft-martin-ibcs-03.txt>
     
     
     Status of this Memo
     
        By submitting this Internet-Draft, each author represents that
        any applicable patent or other IPR claims of which he or she
        is aware have been or will be disclosed, and any of which he
        or she becomes aware will be disclosed, in accordance with
        Section 6 of BCP 79.
     
        Internet-Drafts are working documents of the Internet
        Engineering Task Force (IETF), its areas, and its working
        groups. Note that other groups may also distribute working
        documents as Internet-Drafts.
     
        Internet-Drafts are draft documents valid for a maximum of six
        months and may be updated, replaced, or obsoleted by other
        documents at any time. It is inappropriate to use Internet-
        Drafts as reference material or to cite them other than as
        “work in progress.”
     
        The list of current Internet-Drafts can be accessed at
     
        http://www.ietf.org/1id-abstracts.html
     
        The list of Internet-Draft Shadow Directories can be accessed
        at
     
        http://www.ietf.org/shadow.html
     
     
     
     Abstract
     
        This document describes the algorithms that implement Boneh-
        Franklin and Boneh-Boyen Identity-based Encryption. This
        document is in part based on IBCS #1 v2 of Voltage Security's
        Identity-based Cryptography Standards (IBCS) documents.
     
     
     
     Boyen & Martin          Expires September 2007           [Page 1]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     
     
     Table of Contents
     
     
        1. Introduction..............................................3
        2. Notation and definitions..................................4
           2.1. Notation.............................................4
           2.2. Definitions..........................................7
        3. Basic elliptic curve algorithms...........................8
           3.1. The group action in affine coordinates...............8
              3.1.1. Implementation for type-1 curves................8
           3.2. Point multiplication.................................9
           3.3. Operations in Jacobian projective coordinates.......12
              3.3.1. Implementation for type-1 curves...............12
           3.4. Divisors on elliptic curves.........................14
              3.4.1. Implementation in F_p^2 for type-1 curves......14
           3.5. The Tate pairing....................................16
              3.5.1. The Miller algorithm for type-1 curves.........16
        4. Supporting algorithms....................................19
           4.1. Integer range hashing...............................20
           4.2. Pseudo-random generation by hashing.................21
           4.3. Canonical encodings of extension field elements.....22
              4.3.1. Type-1 curve implementation....................22
           4.4. Hashing onto a subgroup of an elliptic curve........23
              4.4.1. Type-1 curve implementation....................24
           4.5. Bilinear pairing....................................24
              4.5.1. Type-1 curve implementation....................25
           4.6. Ratio of bilinear pairings..........................26
              4.6.1. Type-1 curve implementation....................27
        5. The Boneh-Franklin BF cryptosystem.......................27
           5.1. Setup...............................................27
              5.1.1. Type-1 curve implementation....................28
           5.2. Public key derivation...............................29
           5.3. Private key extraction..............................30
           5.4. Encryption..........................................30
           5.5. Decryption..........................................32
        6. Wrapper methods for the BF system........................33
           6.1. Private key generator (PKG) setup...................33
           6.2. Private key extraction by the PKG...................34
           6.3. Session key encryption..............................35
        7. Concrete encoding guidelines for BF......................36
           7.1. Encoding of points on a curve.......................36
           7.2. Public parameters blocks............................37
              7.2.1. Type-1 implementation..........................38
           7.3. Master secret blocks................................39
           7.4. Private key blocks..................................40
     
     
     Boyen & Martin          Expires September 2007           [Page 2]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           7.5. Ciphertext blocks...................................41
        8. The Boneh-Boyen BB1 cryptosystem.........................42
           8.1. Setup...............................................42
              8.1.1. Type-1 curve implementation....................43
           8.2. Public key derivation...............................44
           8.3. Private key extraction..............................45
           8.4. Encryption..........................................46
           8.5. Decryption..........................................48
        9. Wrapper methods for the BB1 system.......................51
           9.1. Private key generator (PKG) setup...................51
           9.2. Private key extraction by the PKG...................51
           9.3. Session key encryption..............................52
        10. Concrete encoding guidelines for BB1....................54
           10.1. Encoding of points on a curve......................54
           10.2. Public parameters blocks...........................54
              10.2.1. Type-1 implementation.........................55
           10.3. Master secret blocks...............................57
           10.4. Private key blocks.................................58
           10.5. Ciphertext blocks..................................59
        11. Test vectors............................................60
           11.1. Algorithm 3.2.2 (PointMultiply)....................60
           11.2. Algorithm 4.1.1 (HashToRange)......................61
           11.3. Algorithm 4.5.1 (Pairing)..........................61
           11.4. Algorithm 5.2.1 (BFderivePubl).....................61
           11.5. Algorithm 5.3.1 (BFextractPriv)....................62
           11.6. Algorithm 5.4.1 (BFencrypt)........................62
           11.7. Algorithm 8.3.1 (BBextractPriv)....................63
           11.8. Algorithm 8.4.1 (BBencrypt)........................64
        12. ASN.1 module............................................65
        13. Security considerations.................................70
        14. IANA considerations.....................................71
        15. Acknowledgments.........................................71
        16. References..............................................72
           16.1. Normative references...............................72
           16.2. Informative references.............................72
        Authors' Addresses..........................................72
        Intellectual Property Statement.............................73
        Disclaimer of Validity......................................73
        Copyright Statement.........................................73
        Acknowledgment..............................................74
     
     1. Introduction
     
        This document provides a set of specifications for
        implementing identity-based encryption (IBE) systems based on
        bilinear pairings. Two cryptosystems are described: the IBE
        system proposed by Boneh and Franklin (BF) [BF], and the first
     
     
     Boyen & Martin          Expires September 2007           [Page 3]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        IBE system proposed by Boneh and Boyen (BB1) [BB1]. Fully
        secure and practical implementations are described for each
        system, comprising the core IBE algorithms as well as
        ancillary hybrid components used to achieve security against
        active attacks. These specifications are restricted to a
        family of supersingular elliptic curves over finite fields of
        large prime characteristic, referred to as "type-1" curves
        (see Section 2.1). Implementations based on other types of
        curves currently fall outside the scope of this document.
     
        The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
        NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
        "OPTIONAL" in this document are to be interpreted as described
        in [KEYWORDS].
     
     2. Notation and definitions
     
     2.1. Notation
     
        This section summarizes the essential notions and definitions
        regarding identity-based cryptosystems on elliptic curves. The
        reader is referred to [ECC] for the mathematical background
        and to [2, 3] regarding all notions pertaining to identity-
        based encryption.
     
     Let F_p be a finite field of large prime characteristic p, and
     let F_p^2 denote its extension field of degree 2. Let F*_p^2
     denote the multiplicative subgroup of F_p^2.
     
        Let E/F_p: y^2 = x^3 + a * x + b be an elliptic curve over
        F_p. For an extension of degree 2, the curve E/F_p defines a
        group (E(F_p^2), +), which is the additive group of points of
        affine coordinates (x, y) in (F_p^2)^2 satisfying the curve
        equation over F_p^2, with null element, or point at infinity,
        denoted 0. Let #E(F_p^2) be the size of E(F_p^2).
     
        Let q be a prime such that E(F_p) has a cyclic subgroup G1' of
        order q. Let G1'' be a cyclic subgroup of E(F_p^2) of order q,
        and G2 be a cyclic subgroup of F*_p^2 of order p.
     
        Under these conditions, two mathematical constructions known
        as the Weil pairing and the Tate pairing, each provide an
        efficiently computable map e: G1' x G1'' -> G2 that is linear
        in both arguments and believed hard to invert. If an
        efficiently computable isomorphism phi: G1' -> G1'' is
        available for the selected elliptic curve on which the Tate
        pairing is computed, then one can construct a function e': G1'
     
     
     Boyen & Martin          Expires September 2007           [Page 4]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        x G1'' -> G2, defined as e'(A, B) = e(A, phi(B)), called the
        modified Tate pairing. We generically call a pairing either
        the Tate pairing e or the modified Tate pairing e', depending
        on the chosen elliptic curve used in a particular
        implementation.
     
        The following additional notation is used throughout this
        document.
     
        P - A 512-bit to 1536-bit prime, being the order of the finite
        field F_p.
     
        F_p - The base finite field of size p over which the elliptic
        curve of interest E/F_p is defined.
     
        #G - The size of G, where G is a finite group.
     
        G* - The multiplicative group of the invertible elements in G;
        e.g., (F_p)* is the multiplicative group of the finite field
        F_p.
     
        E/F_p - The equation of an elliptic curve over the field F_p,
        which, when p is neither 2 nor 3, is of the form E/F_p: y^2 =
        x^3 + a * x + b, for specified a, b in F_p.
     
        0 - The conventional null element of any additive group of
        points on an elliptic curve, also called the point at
        infinity.
     
        E(F_p) - The additive group of points of affine coordinates
        (x, y), with x, y in F_p, that satisfy the curve equation
        E/F_p, including the point at infinity 0.
     
        q - A 160-bit to 256-bit prime, being the order of the cyclic
        subgroup of interest in E(F_p).
     
        k - The embedding degree, or security multiplier, of the
        cyclic subgroup of order q in E(F_p). For type-1 curves this
        is always equal to 2.
     
        F_p^2 - The extension field of degree 2 of the field F_p.
     
        E(F_p^2) - The group of points of affine coordinates in F_p^2
        satisfying the curve equation E/F_p, including the  point at
        infinity 0.
     
        Z_p - The additive group Z/pZ.
     
     
     Boyen & Martin          Expires September 2007           [Page 5]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        The following conventions are assumed for curve operations.
     
        Point addition - If A and B are two points on a curve E, their
        sum is denoted A + B.
     
        Point multiplication - If A is a point on a curve, and n an
        integer, the result of adding A to itself a total of n times
        is denoted [n]A.
     
        The following class of elliptic curves is exclusively
        considered for pairing operations in the present version of
        the IBCS#1 standard, referred to as "type-1."
     
        Type-1 curves - The class of curves of type 1 is defined as
        the class of all elliptic curves of equation E/F_p: y^2 = x^3
        + 1 for all primes p congruent to 11 modulo 12. This class
        forms a subclass of the class of supersingular curves. These
        curves satisfy #E(F_p) = p + 1, so that the p pairs of (x, y)
        coordinates corresponding to the p non-zero points E(F_p) \
        {0} satisfy a useful bijective relation x <-> y, with x = (y^2
        - 1)^(1/3) (mod p) and y = (x^3 + 1)^(1/2) (mod p). Type-1
        curves always lead to a security multiplier k = 2, where f(x)
        = (x^2 + 1) is always irreducible, allowing the uniform
        representation of F_p^2 = F[x] / (x^2 + 1). Type-1 curves are
        plentiful and easy to construct by random selection of a prime
        p of the appropriate form. Therefore, rather than to
        standardize upon a small set of common values of p, it is
        henceforth assumed that all type-1 curves are freshly
        generated at random for the given cryptographic application
        (an example of such generation will be given in Algorithm
        5.1.2 (BFsetup1) or Algorithm 8.1.2 (BBsetup1)).
        Implementations based on different classes of curves are
        currently unsupported.
     
        We assume that the following concrete representations of
        mathematical objects are used.
     
        Base field elements - The p elements of the base field F_p are
        represented directly using the integers from 0 to p - 1.
     
        Extension field elements - The p^2 elements of the extension
        field F_p^2 are represented as ordered pairs of elements of
        F_p. An ordered pair (a_0, a_1) is interpreted as the
        polynomial a_1 * x + a_0 in F_p[x] / (x^2 + 1).
     
        Type-1 curves - For type-1 curves, which are supersingular
        curves of equation E/F_p: y^2 = x^3 + 1 with p congruent to 11
     
     
     Boyen & Martin          Expires September 2007           [Page 6]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        modulo 12, and elements of F_p^2 are represented as
        polynomials a_1 *_x + a_0 in F_p[x] / (x^2 + 1).
     
        Elliptic curve points - Points in E(F_p^2) with the point P =
        (x, y) in F_p^2 x F_p^2 satisfying the curve equation E/F_p.
        Points not equal to 0 are internally represented using the
        affine coordinates (x, y), where x and y are elements of
        F_p^2.
     
     2.2. Definitions
     
        The following terminology is used to describe an IBE system.
     
        Public parameters - The public parameters are set of common
        system-wide parameters generated and published by the private
        key server (PKG).
     
        Master secret - The master secret is the master key generated
        and privately kept by the key server, and used to generate the
        private keys of the users.
     
        Identity - An identity an arbitrary string, usually a human-
        readable unambiguous designator of a system user, possibly
        augmented with a time stamp and other attributes.
     
        Public key - A public key is a string that is algorithmically
        derived from an identity. The derivation may be performed by
        anyone, autonomously.
     
        Private key - A private key is issued by the key server to
        correspond to a given identity (and the public key that
        derives from it), under the published set of public
        parameters.
     
        Plaintext - A plaintext is an unencrypted representation, or
        in the clear, of any block of data to be transmitted securely.
        For the present purposes, plaintexts are typically session
        keys, or sets of session keys, for further symmetric
        encryption and authentication purposes.
     
        Ciphertext - A ciphertext is an encrypted representation of
        any block of data, including a plaintext, to be transmitted
        securely.
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007           [Page 7]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     3. Basic elliptic curve algorithms
     
        This section describes algorithms for performing all needed
        basic arithmetic operations on elliptic curves. The
        presentation is specialized to the type of curves under
        consideration for simplicity of implementation. General
        algorithms may be found in [ECC].
     
     3.1.  The group action in affine coordinates
     
     3.1.1. Implementation for type-1 curves
     
        Algorithm 3.1.1 (PointDouble1): adds a point to itself on a
        type-1 elliptic curve.
     
        Input:
     
        o  A point A in E(F_p^2), with A = (x, y) or 0.
     
        o  An elliptic curve E/F_p: y^2 = x^3 + 1.
     
        Output:
     
        o  The point [2]A = A + A.
     
        Method:
     
        1. If A = 0 or y = 0, then return 0.
     
        2. Let lambda = (3 * x^2) / (2 * y).
     
        3. Let x' = lambda^2 - 2 * x.
     
        4. Let y' = (x - x') * lambda - y.
     
        5. Return (x', y').
     
        Algorithm 3.1.2 (PointAdd1): adds two points on a type-1
        elliptic curve.
     
        Input:
     
        o  A point A in E(F_p^2), with A = (x_A, y_A) or 0,
     
        o  A point B in E(F_p^2), with B = (x_B, y_B) or 0,
     
        o  An elliptic curve E/F_p: y^2 = x^3 + 1.
     
     
     Boyen & Martin          Expires September 2007           [Page 8]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Output:
     
        o  The point A + B.
     
        Method:
     
        1. If A = 0, return B.
     
        2. If B = 0, return A.
     
        3. If x_A = x_B:
     
           (a) If y_A = -y_B, return 0.
     
           (b) Else return [2]A computed using Algorithm 2.1.1
        (PointDouble1).
     
        4. Otherwise:
     
           (a) Let lambda = (y_B - y_A) / (x_B - x_A).
     
           (b) Let x' = lambda^2 - x_A - x_B.
     
           (c) Let y' = (x_A - x') * lambda - y_A.
     
           (d) Return (x', y').
     
     3.2. Point multiplication
     
        Algorithm 3.2.1 (SignedWindowDecomposition): computes the
        signed m-ary window representation of a positive integer.
     
        Input:
     
        o  An integer l > 0,
     
        o  An integer window bit-size r > 0.
     
        Output:
     
        o  The unique d-element sequence {(b_i, e_i), for i = 0 to d -
           1} such that l = {Sum(b_i * 2^(e_i), for i = 0 to d - 1}
           and b_i = +/- 2^j for some 0 <= j <= r - 1.
     
        Method:
     
        1. Let d = 0.
     
     
     Boyen & Martin          Expires September 2007           [Page 9]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        2. Let j = 0.
     
        3. While j <= l, do:
     
           (a) If l_k = 0 then:
     
              i. Let j = j + 1.
     
           (b) Else:
     
              i. Let t = min{j + r - 1, l}.
     
              ii. Let h_d = (l_t, l_(t - 1), ..., l_j) (base 2).
     
              iii. If h_d > 2^(r - 1) then:
     
                 A. Let b_d = h_d - 2^r.
     
                 B. Let l' = l' + 2^(t + 1).
     
              iv. Else:
     
                 A. Let b_d = h_d.
     
              v. Let e_d = j.
     
              vi. Let d  = d + 1.
     
              vii. Let j  = t + 1.
     
        4. Return d and the sequence {(b_0, e_0), ..., (b_(d - 1),
        e_(d - 1))}.
     
        Algorithm 3.2.2 (PointMultiply): scalar multiplication on an
        elliptic curve using the signed m-ary window method.
     
        Input:
     
        o  A point A in E(F_p^2),
     
        o  An integer l > 0,
     
        o  An elliptic curve E/F_p: y^2 = x^3 + a * x + b.
     
        Output:
     
        o  The point [l]A.
     
     
     Boyen & Martin          Expires September 2007          [Page 10]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Method:
     
        1. (Window decomposition)
     
           (a) Let r > 0 be an integer (fixed) bit-wise window size,
        e.g., r = 5.
     
           (b) Let l' = l where l = {Sum(l_j * 2^j), for j = 0 to
        len_l} is the binary expansion of l, where len_l =
        Ceiling(lg(l)).
     
           (c) Compute (d, {(b_i, e_i), for i = 0 to d - 1} =
        SignedWindowDecomposition(l, r), the signed 2^r-ary window
        representation of l using Algorithm 3.2.1
        (SignedWindowDecomposition).
     
        2. (Precomputation)
     
           (a) Let A_1 = A.
     
           (b) Let A_2 = [2]A, using Algorithm 3.1.1 (PointDouble1).
     
           (c) For i = 1 to 2^(r - 2) - 1, do:
     
              i. Let A_(2 * i + 1) = A_(2 * i - 1) + A_2 using
        Algorithm 3.1.2 (PointAdd1).
     
           (d) Let Q = A_(b_(d - 1)).
     
        3. Main loop
     
           (a) For i = d - 2 to 0 by -1, do:
     
              i. Let Q = [2^(e_(i + 1) - e_i)]Q, using repeated
        applications of Algorithm 3.1.1 (PointDouble1) e_(i + 1) - e_i
        times.
     
              ii. If b_i > 0 then:
     
                 A. Let Q = Q + A_(b_i) using Algorithm 3.1.2
        (PointAdd1).
     
              iii. Else:
     
                 A. Let Q = Q - A_(-b_i) using Algorithm 3.1.2
        (PointAdd1).
     
     
     
     Boyen & Martin          Expires September 2007          [Page 11]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (b) Calculate Q = [2^(e_0)]Q using repeated applications of
        Algorithm 3.1.1 (PointDouble1) e_0 times.
     
        4. Return Q.
     
     3.3. Operations in Jacobian projective coordinates
     
     3.3.1. Implementation for type-1 curves
     
        Algorithm 3.3.1 (ProjectivePointDouble1): adds a point to
        itself in Jacobian projective coordinates for type-1 curves.
     
        Input:
     
        o  A point (x, y, z) = A in E(F_p^2) in Jacobian projective
           coordinates,
     
        o  An elliptic curve E/F_p: y^2 = x^3 + 1.
     
        Output:
     
        o  The point [2]A in Jacobian projective coordinates.
     
        Method:
     
        1. If z = 0 or y = 0, return (0, 1, 0) = 0. Otherwise:
     
        2. Let lambda_1 = 3 * x^2.
     
        3. Let z' = 2 * y * z.
     
        4. Let lambda_2 = y^2.
     
        5. Let lambda_3 = 4 * lambda_2 * x.
     
        6. Let x' = lambda_1^2 - 2 * lambda_3.
     
        7. Let lambda_4 = 8 * lambda_2^2.
     
        8. Let y' = lambda_1 * (lambda_3 - x) - lambda_4.
     
        9. Return (x', y', z').
     
        Algorithm 3.3.2 (ProjectivePointAccumulate1): adds a point in
        affine coordinates to an accumulator in Jacobian projective
        coordinates, for type-1 curves.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 12]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Input:
     
        o  A point (x_A, y_A, z_A) = A in E(F_p^2) in Jacobian
           projective coordinates,
     
        o  A point (x_B, y_B) = B in E(F_p^2) \ {0} in affine
           coordinates,
     
        o  An elliptic curve E/F_p: y^2 = x^3 + 1.
     
        Output:
     
        o  The point A + B in Jacobian projective coordinates.
     
        Method:
     
        1. If z_A = 0 return (x_B, y_B, 1) = B. Otherwise:
     
        2. Let lambda_1 = z_A^2
     
        3. Let lambda_2 = lambda_1 * x_B.
     
        4. Let lambda_3 = x_A - lambda_2.
     
        5. If lambda_3 = 0 then return (0, 1, 0) = 0. Otherwise:
     
        6. Let lambda_4 = lambda_3^2.
     
        7. Let lambda_5 = lambda_1 * y_B * z_A.
     
        8. Let lambda_6 = lambda_4 - lambda_5.
     
        9. Let lambda_7 = x_A + lambda_2.
     
        10. Let lambda_8 = y_A + lambda_5.
     
        11. Let x' = lambda_6^2 - lambda_7 * lambda_4.
     
        12. Let lambda_9 = lambda_7 * lambda_4 - 2 * x'.
     
        13. Let y' = (lambda_9 * lambda_6 -
     
           lambda_8 * lambda_3 * lambda_4) / 2.
     
        14. Let z' = lambda_3 * z_A.
     
        15. Return (x', y', z').
     
     
     Boyen & Martin          Expires September 2007          [Page 13]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     3.4. Divisors on elliptic curves
     
     3.4.1. Implementation in F_p^2 for type-1 curves
     
        Algorithm 3.4.1 (EvalVertical1): evaluates the divisor of a
        vertical line on a type-1 elliptic curve.
     
        Input:
     
        o  A point B in E(F_p^2) with B != 0.
     
        o  A point A in E(F_p).
     
        o  A description of a type-1 elliptic curve E/F_p.
     
        Output:
     
        o  An element of F_p^2 that is the divisor of the vertical
           line going through A evaluated at B.
     
        Method:
     
        1. Let r = x_B - x_A.
     
        2. Return r.
     
        Algorithm 2.4.2 (EvalTangent1): evaluates the divisor of a
        tangent on a type-1 elliptic curve.
     
        Input:
     
        o  A point B in E(F_p^2) with B != 0.
     
        o  A point A in E(F_p).
     
        o  A description of a type-1 elliptic curve E/F_p.
     
        Output:
     
        o  An element of F_p^2 that is the divisor of the line tangent
           to A evaluated at B.
     
        Method:
     
        1. (Special cases)
     
           (a) If A = 0 return 1 = 1 + 0 * i.
     
     
     Boyen & Martin          Expires September 2007          [Page 14]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (b) If y_A = 0 return EvalVertical1(B, A) using Algorithm
        3.4.1 (EvalVertical1).
     
        2. (Line computation)
     
           (a) Let a = -3 * (x_A)^2.
     
           (b) Let b = 2 * y_A.
     
           (c) Let c = -b * y_A - a * x_A.
     
        3. (Evaluation at B)
     
        (a) Let r = a * x_B + b * y_B) + c.
     
        4. Return r.
     
        Algorithm 3.4.3 (EvalLine1): evaluates the divisor of a line
        on a type-1 elliptic curve.
     
        Input:
     
        o  A point B in E(F_p^2) with B != 0.
     
        o  Two points A', A'' in E(F_p).
     
        o  A description of a type-1 elliptic curve E/F_p.
     
        Output:
     
        o  An element of F_p^2 that is the divisor of the line going
           through A' and A'' evaluated at B.
     
        Method:
     
        1. (Special cases)
     
           (a) If A' = 0 return EvalVertical1(B, A'') using Algorithm
        3.4.1 (EvalVertical1).
     
           (b) If A'' = 0 return EvalVertical1(B, A') using Algorithm
        3.4.1 (EvalVertical1).
     
           (c) If A' = -A'' return EvalVertical1(B, A') using
        Algorithm 3.4.1 (EvalVertical1).
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 15]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (d) If A' = A'' return EvalTangent1(B, A') using Algorithm
        3.4.2 (EvalTangent1).
     
        2. (Line computation)
     
           (a) Let a = y_A' - y_A''.
     
           (b) Let b = x_A'' - x_A'.
     
           (c) Let c = -b * y_A' - a * x_A'.
     
        3. (Evaluation at B)
     
           (a) Let r = a * x_B + b * y_B + c.
     
        4. Return r.
     
     3.5. The Tate pairing
     
        Algorithm 3.5.1 (Tate): computes the Tate pairing on an
        elliptic curve.
     
        Input:
     
        o  A point A of order q in E(F_p),
     
        o  A point B of order q in E(F_p^2),
     
        o  A description of an elliptic curve E/F_p such that E(F_p)
           and E(F_p^2) have a subgroup of order q.
     
        Output:
     
        o  The value e(A, B) in F_p^2, computed using the Miller
           algorithm.
     
        Method:
     
        1. For type-1 curve E, proceed with Algorithm 3.5.2
        (TateMillerSolinas).
     
     3.5.1. The Miller algorithm for type-1 curves
     
        Algorithm 3.5.2 (TateMillerSolinas): computes the Tate pairing
        on a type-1 elliptic curve.
     
        Input:
     
     
     Boyen & Martin          Expires September 2007          [Page 16]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  A point A of order q in E(F_p),
     
        o  A point B of order q in E(F_p^2),
     
        o  A description of a type-1 supersingular elliptic curve
           E/F_p such that E(F_p) and E(F_p^2) have a subgroup of
           prime order q, where q = 2^a + s * 2^b + c with c and s
           equal to either 1 or -1.
     
        Output:
     
        o  The value e(A, B) in F_p^2, computed using the Miller
           algorithm.
     
        The following description assumes that F_p^2 = F_p[i], where
        i^2 = -1.
     
        Elements x in F_p^2 may be explicitly represented as a + i *
        b, with a, b in F_p.
     
        Points in E(F_p) may also be represented as coordinate pairs
        (x, y) with x, y in F_p.
     
        Points in E(F_p^2) may be represented either as (x, y), with
        x, y in F_p^2 or as (a + i * b, c + i * d), with a, b, c, d in
        F_p.
     
        Method:
     
        1. (Initialization)
     
           (a) Let v_num = 1 in F_p^2.
     
           (b) Let v_den = 1 in F_p^2.
     
           (c) Let V = (x_V , y_V , z_V ) = (x_A, y_A, 1) in (F_p)^3,
        being the representation of (x_A, y_A) = A using Jacobian
        projective coordinates.
     
           (d) Let t_num = 1 in F_p^2.
     
           (e) Let t_den = 1 in F_p^2.
     
        2. (Calculation of the (s * 2^b) contribution)
     
           (a) (Repeated doublings) For n = 0 to b - 1:
     
     
     
     Boyen & Martin          Expires September 2007          [Page 17]
     

     Internet Draft                 IBCS #1                March 2007
     
     
              i. Let t_num = t_num^2.
     
              ii. Let t_den = t_den^2.
     
              iii. Let t_num = t_num * EvalTangent1(B, V) using
        Algorithm 3.4.2 (EvalTangent1).
     
              iv. Let V = (x_V , y_V , z_V ) = [2]V  using Algorithm
        3.3.1 (ProjectivePointDouble1).
     
              v. Let t_den = t_den * EvalVertical1(B, V) using
        Algorithm 3.4.1 (EvalVertical1).
     
           (b) (Normalization)
     
              i. Let V_b = (x_(V_b) , y_(V_b))
     
                 = (x_V / z_V^2, s * y_V / z_V^3) in (F_p)^2,
     
                 resulting in a point V_b in E(F_p).
     
           (c) (Accumulation) Selecting on s:
     
              i. If s = -1:
     
                 A. Let v_num = v_num * t_den.
     
                 B. Let v_den = v_den * t_num * EvalVertical1(B, V)
        using Algorithm 3.4.1 (EvalVertical1).
     
              ii. If s = 1:
     
                 A. Let v_num = v_num * t_num.
     
                 B. Let v_den = v_den * t_den.
     
        3. (Calculation of the 2^a contribution)
     
           (a) (Repeated doublings) For n = b to a - 1:
     
              i. Let t_num = t_num^2.
     
              ii. Let t_den = t_den^2.
     
              iii. Let t_num = t_num * EvalTangent1(B, V) using
        Algorithm 3.4.2 (EvalTangent1).
     
     
     
     Boyen & Martin          Expires September 2007          [Page 18]
     

     Internet Draft                 IBCS #1                March 2007
     
     
              iv. Let V = (x_V , y_V , z_V) = [2]V  using Algorithm
        3.3.1 (ProjectivePointDouble1).
     
              v. Let t_den = t_den * EvalVertical1(B, V) using
        Algorithm 3.4.1 (EvalVertical1).
     
           (b) (Normalization)
     
              i. Let V_a = (x_(V_a) , y_(V_a)) =
     
                 (x_V /z_V^2, s * x_V / z_V^3) in (F_p)^2,
     
                 resulting in a point V_a in E(F_p).
     
           (c) (Accumulation)
     
              i. Let v_num = v_num * t_num.
     
              ii. Let v_den = v_den * t_den.
     
        4. (Correction for the (s * 2^b) and (c) contributions)
     
           (a) Let v_num = v_num * EvalLine1(B, V_a, V_b) using
        Algorithm 3.4.3 (EvalLine1).
     
           (b) Let v_den = v_den * EvalVertical1(B, V_a + V_b) using
        Algorithm 3.4.1 (EvalVertical1).
     
           (c) If c = -1 then:
     
              i. Let v_den = v_den * EvalVertical1(B,A) using
        Algorithm 3.4.1 (EvalVertical1).
     
        5. (Correcting exponent)
     
           (a) Let eta = (p^2 - 1) / q (an integer).
     
        6. (Final result)
     
           (a) Return (v_num / v_den)^eta in F_p^2.
     
     4. Supporting algorithms
     
        This section describes a number of supporting algorithms for
        encoding and hashing.
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 19]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     4.1. Integer range hashing
     
        HashToRangen(s, n) takes a string s and an integer n as input,
        and returns an integer in the range 0 to n - 1 by
        cryptographic hashing. The function performs a number l of
        SHA1 [SHA] applications, with l chosen in function of n so
        that, for random input, the output has an almost uniform
        distribution in the entire range 0 to n - 1 with a statistical
        relative non-uniformity no greater than 1/sqrt(n). I.e., for
        arbitrarily large n, for all v in 0 to n - 1, the probability
        that HashToRangen(s, n) = v lies in the interval [(1 - n^(-
        1/2)) / n, (1 + n^(-1/2)) / n].
     
        Algorithm 4.1.1 (HashToRange): cryptographically hashes
        strings to integers in a range.
     
        Input:
     
        o  A string s of length |s| bytes,
     
        o  A positive integer n represented as Ceiling(lg(n) / 8)
           bytes.
     
        Output:
     
        o  A positive integer v in the range 0 to n - 1.
     
        Method:
     
        1. Let v_0 = 0.
     
        2. Let h_0 = 0x0000000000000000000000000000000000000000, a
        string of 20 null bytes.
     
        3. Let l = Ceiling((3 / 5) * lg(n)).
     
        4. For each i in 1 to l, do:
     
           (a) Let t_i = h_(i - 1) || s, which is the (|s| + 20)-byte
        string concatenation of the strings h_(i - 1) and s.
     
           (b) Let h_i = SHA1(t_i), which is a 20-byte string
        resulting from the SHA1 algorithm [SHA] on input t_i.
     
           (c) Let a_i = Value(h_i) be the integer in the range 0 to
        256^20 - 1 denoted by the raw byte string h_i interpreted in
        the unsigned big endian convention.
     
     
     Boyen & Martin          Expires September 2007          [Page 20]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (d) Let v_i = 256^20 * v_(i - 1) + a_i.
     
        5. Let v = v_l (mod n).
     
     4.2. Pseudo-random generation by hashing
     
        HashStream(b, p) takes an integer b and a string p as input,
        and returns a b-byte pseudo-random string r as output. This
        function relies on the SHA1 cryptographic hashing algorithm
        [SHA], and has a 160-bit internal effective key space equal to
        the range of SHA1.
     
        Algorithm 4.2.1 (HashStream): keyed cryptographic pseudo-
        random stream generator.
     
        Input:
     
        o  An integer b,
     
        o  A string p.
     
        Output:
     
        o  A string r of size b bytes.
     
        Method:
     
        1. Let K = SHA1(p).
     
        2. Let h_0 = 0x0000000000000000000000000000000000000000, a
        string of 20 null bytes.
     
        3. Let l = Ceiling(b / 20).
     
        4. For each i in 1 to l do:
     
           (a) Let h_i = SHA1(h_(i - 1)).
     
           (b) Let r_i = SHA1(h_i || K), where h_i || K is the 40-byte
        concatenation of h_i and K.
     
        5. Let r = LeftmostBytes(b, r_1 || ... || r_l), i.e., r is
        formed as the concatenation of the r_i, truncated to the
        desired number of bytes.
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 21]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     4.3. Canonical encodings of extension field elements
     
        Canonical(p, k, o, v) takes an element v in F_p^k, and returns
        a canonical byte-string of fixed length representing v. The
        parameter o must be either 0 or 1, and specifies the ordering
        of the encoding.
     
        Algorithm 4.3.1 (Canonical): encodes elements of an extension
        field F_p^2 as strings.
     
        Input:
     
        o  An element v in F_p^k,
     
        o  A description of F_p^k,
     
        o  A ordering parameter o, either 0 or 1.
     
        Output:
     
        o  A fixed-length string s representing v.
     
        Method:
     
        1. For a type-1 curve, execute Algorithm 4.3.2 (Canonical1).
     
     4.3.1. Type-1 curve implementation
     
        Canonical1(p, o, v) takes an element v in F_p^2 and returns a
        canonical representation of v as a byte-string s of fixed
        size. The parameter o must be either 0 or 1, and specifies the
        ordering of the encoding.
     
        Algorithm 4.3.2 (Canonical1): canonically represents elements
        of an extension field F_p^2.
     
        Input:
     
        o  An element v in F_p^2,
     
        o  A description of p, where p is congruent to 3 modulo 4,
     
        o  A ordering parameter o, either 0 or 1.
     
        Output:
     
        o  A string s of size 2 * Ceiling(lg(p) / 8) bytes.
     
     
     Boyen & Martin          Expires September 2007          [Page 22]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Method:
     
        1. Let l = Ceiling(lg(p) / 8), the number of bytes needed to
        represent integers in Z_p.
     
        2. Let (a, b) = v, where (a, b) in (Z_p)^2 is the canonical
        representation of v in F_p^2 = F_p / (x^2 + 1) as a polynomial
        a +i * b with i^2 = -1.
     
        3. Let a_(256^l) be the big-endian zero-padded fixed-length
        byte-string representation of a in Z_p.
     
        4. Let b_(256^l) be the big-endian zero-padded fixed-length
        byte-string representation of b in Z_p.
     
        5. Depending on the choice of ordering o:
     
           (a) If o = 0, then let s = a_(256^l) || b_(256^l), which is
        the concatenation of a_(256^l) followed by b_(256^l).
     
           (b) If o = 1, then let s = b_(256^l) || a_(256^l), which is
        the concatenation of b_(256^l) followed by a_(256^l).
     
        6. The fixed-length encoding of v is output as the string s.
     
     4.4. Hashing onto a subgroup of an elliptic curve
     
        HashToPoint(E, p, q, id) takes an identity string id and the
        description of a subgroup of prime order q in E(F_p) or
        E(F_p^2) and returns a point Q_id of order q in E(F_p) or
        E(F_p^2).
     
        Algorithm 4.4.1 (HashToPoint): cryptographically hashes
        strings to points on elliptic curves.
     
        Input:
     
        o  A string id,
     
        o  A description of a subgroup of prime order q on a curve
           E/F_p.
     
        Output:
     
        o  A point Q_id = (x, y) of order q on E.
     
        Method:
     
     
     Boyen & Martin          Expires September 2007          [Page 23]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        1. For a type-1 curve E, execute Algorithm 4.4.2
        (HashToPoint1).
     
     4.4.1. Type-1 curve implementation
     
        HashToPoint1(E, p, q, id) takes an identity string id and the
        description of a subgroup of order q in E(F_p) where E: y^2 =
        x^3 + 1 with p congruent to 11 modulo 12, and returns a point
        Q_id of order q in E/F_p. This algorithm exploits the
        bijective mapping between the x and y coordinates of non-zero
        points on such supersingular curves.
     
        Algorithm 4.4.2 (HashToPoint1). Cryptographically hashes
        strings to points on type-1 curves.
     
        Input:
     
        o  A string id,
     
        o  A description of a subgroup of prime order q on a curve
           E/F_p: y^2 = x^3 + 1 where p is congruent to 11 modulo 12.
     
        Output:
     
        o  A point Q_id of order q on E(F_p).
     
        Method:
     
        1. Let y = HashToRangen(p, id), using Algorithm 4.1.1
           (HashToRange).
     
        2. Let x = (y^2 - 1)^(1/3) = (y^2 - 1)^((2 * p - 1) / 3).
     
        3. Let Q' = (x, y), a non-zero point in E(F_p).
     
        4. Let Q = [(p + 1) / q ]Q', a point of order q in E(F_p).
     
     4.5. Bilinear pairing
     
        Pairing(E, p, q, A, B) takes two points A and B, both of order
        q, and, in the type-1 case, returns the modified pairing e'(A,
        phi(B)) in F_p^2 where A and B are both in E(F_p).
     
        Algorithm 4.5.1 (Pairing): computes the regular or modified
        Tate pairing depending on the curve type.
     
        Input:
     
     
     Boyen & Martin          Expires September 2007          [Page 24]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  A description of an elliptic curve E/F_p such that E(F_p)
           and E(F_p^2) have a subgroup of order q,
     
        o  Two points A and B of order q in E(F_p) or E(F_p^2).
     
        Output:
     
        o  On supersingular curves, the value of e'(A, B) in F_p^2
           where A and B are both in E(F_p).
     
        Method:
     
        1. If E is a type-1 curve, execute Algorithm 4.5.2 (Pairing1).
     
     4.5.1. Type-1 curve implementation
     
        Algorithm 4.5.2 (Pairing1): computes the modified Tate pairing
        on type-1 curves.
     
        Input:
     
        o  A curve E/F_p: y^2 = x^3 + 1 where p is congruent to 11
           modulo 12 and E(F_p) has a subgroup of order q,
     
        o  Two points A and B of order q in E(F_p),
     
        Output:
     
        o  The value of e'(A, B) = e(A, phi(B)) in F_p^2.
     
        Method:
     
        1. Compute B' = phi(B), as follows:
     
           (a) Let (x, y) in F_p x F_p be the coordinates of B in
        E(F_p).
     
           (b) Let zeta = 1^(1/3) in F_p^2 , with zeta != 1.
        Specifically, as p is congruent to 3 modulo 4, and
        representing the elements of F_p^2 = F_p[x] / (x^2 + 1) as
        polynomials a + bx with x = (-1)^(1/2), the representation of
        zeta = (a_zeta , b_zeta) is obtained as:
     
              i. Let a_zeta = (p - 1) / 2.
     
              ii. Let b_zeta = 3^((p + 1) / 4) (mod p).
     
     
     
     Boyen & Martin          Expires September 2007          [Page 25]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (c) Let x' =  x * x_zeta in F_p^2,
     
           (d) Let B' = (x', y) in F_p^2 x F_p.
     
        2. Compute the Tate pairing e(A, B') = e(A, phi(B)) in F_p^2
        using the Miller method, as in Algorithm 3.5.1 (Tate)
        described in Section 3.5.
     
     4.6. Ratio of bilinear pairings
     
        PairingRatio(E, p, q, A, B, C, D) takes four points as input,
        and computes the ratio of the two bilinear pairings,
        Pairing(E, p, q, A, B) / Pairing(E, p, q, C, D), or,
        equivalently, the product, Pairing(E, p, q, A, B) * Pairing(E,
        p, q, C, -D).
     
        On type-1 curves, all four points are of order q in E(F_p),
        and the result is an element of order q in the extension field
        F_p^2 .
     
        The motivation for this algorithm is that the ratio of two
        pairings can be calculated more efficiently than by computing
        each pairing separately and dividing one into the other, since
        certain calculations that would normally appear in each of the
        two pairings can be combined and carried out at once. Such
        calculations include the repeated doublings in steps 2(a)i,
        2(a)ii, 3(a)i, and 3(a)ii of Algorithm 3.5.2
        (TateMillerSolinas), as well as the final exponentiation in
        step 6(a) of Algorithm 3.5.2 (TateMillerSolinas).
     
        Algorithm 4.6.1 (PairingRatio): computes the ratio of two
        regular or modified Tate pairings depending on the curve type.
     
        Input:
     
        o  A description of an elliptic curve E/F_p such that E(F_p)
           and E(F_p^2) have a subgroup of order q,
     
        o  Four points A, B, C, and D, of order q in E(F_p) or
           E(F_p^2).
     
        Output:
     
        o  On supersingular curves, the value of e'(A, B) / e'(C, D)
           in F_p^2 where A, B, C, D are all in E(F_p);
     
        Method:
     
     
     Boyen & Martin          Expires September 2007          [Page 26]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        1. If E is a type-1 curve, execute Algorithm 4.6.2
        (PairingRatio1).
     
     4.6.1. Type-1 curve implementation
     
        Algorithm 4.6.2 (PairingRatio1). Computes the ratio of two
        modified Tate pairings on type-1 curves.
     
        Input:
     
        o  A curve E/F_p: y^2 = x^3 + 1, where p is congruent to 11
           modulo 12 and E(F_p) has a subgroup of order q,
     
        o  Four points A, B, C, and D, of order q in E(F_p),
     
        Output:
     
        o  The value of e'(A, B) / e'(C, D) = e(A, phi(B)) / e(C,
           phi(D)) = e(A, phi(B)) * e(-C, phi(D)), in F_p^2.
     
        Method:
     
        1. The step-by-step description of the optimized algorithm is
        omitted in this normative specification.
     
        The correct result can always be obtained, albeit more slowly,
        by computing the product of pairings Pairing1(E, p, q, A, B) *
        Pairing1(E, p, q, -C, D) by using two invocations of Algorithm
        4.5.2 (Pairing1).
     
     5. The Boneh-Franklin BF cryptosystem
     
        This chapter describes the algorithms constituting the Boneh-
        Franklin identity-based cryptosystem as described in [BF].
     
     5.1. Setup
     
        Algorithm 5.1.1 (BFsetup): randomly selects a master secret
        and the associated public parameters.
     
        Input:
     
        o  A curve type t (currently required to be fixed to t = 1),
     
        o  A security parameter n (currently required to take values n
           >= 1024).
     
     
     
     Boyen & Martin          Expires September 2007          [Page 27]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Output:
     
        o  A set of common public parameters,
     
        o  A corresponding master secret.
     
        Method:
     
        1. Depending on the selected type t:
     
           (a) If t = 1, then Algorithm 5.1.2 (BFsetup1) is executed.
     
        2. The resulting master secret and public parameters are
        separately encoded as per the application protocol
        requirements.
     
     5.1.1. Type-1 curve implementation
     
        BFsetup1 takes a security parameter n as input. For type-1
        curves, the scale of n corresponds to the modulus bit-size
        believed of comparable security in the classical Diffie-
        Hellman or RSA public-key cryptosystems. For this
        implementation, the allowed value of n is limited to 1024,
        which corresponds to 80 bits of symmetric key security.
     
        Algorithm 5.1.2 (BFsetup1): randomly establishes a master
        secret and public parameters for type-1 curves.
     
        Input:
     
        o  A security parameter n, assumed to be equal to 1024.
     
        Output:
     
        o  A set of common public parameters (t, p, q, P, Ppub),
     
        o  A corresponding master secret s.
     
        Method:
     
        1. Determine the subordinate security parameters n_p and n_q
        as follows:
     
           (a) Let n_p = 512, which will determine the size of the
        field F_p.
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 28]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (b) Let n_q = 160, which will determine the size of the
        subgroup order q.
     
        2. Construct the elliptic curve and its subgroup of interest,
        as follows:
     
           (a) Select an arbitrary n_q-bit prime q, i.e., such that
        Ceiling(lg(q)) = n_q. For better performance, q is chosen as a
        Solinas prime, i.e., a prime of the form q = 2^a +/- 2^b +/- 1
        where 0 < b < a.
     
           (b) Select a random integer r such that p = 12 * r * q - 1
        is an n_p-bit prime, i.e., such that Ceiling(lg(p)) = n_p.
     
        3. Select a point P of order q in E(F_p), as follows:
     
           (a) Select a random point P' of coordinates (x', y') on the
        curve E/F_p: y^2 = x^3 + 1 (mod p).
     
           (b) Let P = [12 * r]P'.
     
           (c) If P = 0, then start over in step 3a.
     
        4. Determine the master secret and the public parameters as
        follows:
     
           (a) Select a random integer s in the range 2 to q - 1.
     
           (b) Let P_pub = [s]P.
     
        5. (t, E, p, q, P, P_pub) are the common public parameters,
        where E: y^2 = x^3 + 1.
     
        6. The integer s is the master secret.
     
     5.2. Public key derivation
     
        BFderivePubl takes an identity string id and a set of public
        parameters, and returns a point Q_id.
     
        Algorithm 5.2.1 (BFderivePubl): derives the public key
        corresponding to an identity string.
     
        Input:
     
        o  An identity string id,
     
     
     
     Boyen & Martin          Expires September 2007          [Page 29]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  A set of common public parameters (t, E, p, q, P, P_pub).
     
        Output:
     
        o  A point Q_id of order q in E(F_p) or E(F_p^2).
     
        Method:
     
        1. Q_id = HashToPoint(E, p, q, id), using Algorithm 4.4.1
        (HashToPoint).
     
     5.3. Private key extraction
     
        BFextractPriv takes an identity string id, and a set of public
        parameters and corresponding master secret, and returns a
        point S_id.
     
        Algorithm 5.3.1 (BFextractPriv): extracts the private key
        corresponding to an identity string.
     
        Input:
     
        o  An identity string id,
     
        o  A set of common public parameters (t, E, p, q, P, P_pub).
     
        Output:
     
        o  A point S_id or order q in E(F_p).
     
        Method:
     
        1. Let Q_id = HashToPoint(E, p, q, id) using Algorithm 4.4.1
        (HashToPoint).
     
        2. Let S_id = [s]Q_id.
     
     5.4. Encryption
     
        BFencrypt takes three inputs: a public parameter block, an
        identity id, and a plaintext m. The plaintext is intended to
        be a symmetric session key, although variable-sized short
        messages are allowed.
     
        Algorithm 5.4.1 (BFencrypt): encrypts a short message or
        session key for an identity string.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 30]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Input:
     
        o  A plaintext string m of size |m| bytes,
     
        o  A recipient identity string id,
     
        o  A set of public parameters.
     
        Output:
     
        o  A ciphertext tuple (U, V, W) in E(F_p) x {0, ... , 255}^20
           x {0, ... , 255}^|m|.
     
        Method:
     
        1. Let the public parameter set be comprised of a prime p, a
        curve E/F_p, the order q of a large prime subgroup of E(F_p),
        and two points P and P_pub of order q in E(F_p).
     
        2. Q_id = HashToPoint(E, p, q, id), using Algorithm 4.4.1
        (HashToPoint), which results in a point of order q in E(F_p)
        or E(F_p^2).
     
        3. Select s random 160-bit vector rho, represented as 20-byte
        string in big-endian convention.
     
        4. Let t = SHA1(m), a 20-byte string resulting from the SHA1
        algorithm [SHA].
     
        5. Let l = HashToRangeq(rho || t), an integer in the range 0
        to q - 1 resulting from applying Algorithm 4.1.1 (HashToRange)
        to the 40-byte concatenation of rho and t.
     
        6. Let U = [l]P, which is a point of order q in E(F_p).
     
        7. Let Theta = Pairing(E, p, q, P_pub, Q_id), which is an
        element of the extension field F_p^2 obtained using the
        modified Tate pairing of Algorithm 4.5.1 (Pairing).
     
        8. Let theta' = theta^l, which is theta raised to the power of
        l in F_p^2.
     
        9. Let z = Canonical(p, k, 0, theta'), using Algorithm 4.3.1
        (Canonical), the result of which is a canonical string
        representation of theta'.
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 31]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        10. Let w = SHA1(z) using the SHA1 hashing algorithm [SHA],
        the result of which is a 20-byte string.
     
        11. Let V = w XOR rho, which is the 20-byte long bit-wise
        exclusive-OR of w and rho.
     
        12. Let W = HashStream(|m|, rho XOR m), which is the bit-wise
        exclusive-OR of m with the first |m| bytes of the pseudo-
        random stream produced by Algorithm 4.2.1 (HashStream) with
        seed rho.
     
        13. The ciphertext is the triple (U, V, W).
     
     5.5. Decryption
     
        BFdecrypt takes three inputs: a public parameter block, a
        private key block key, and a ciphertext parsed as (U' , V' ,
        W').
     
        Algorithm 5.5.1 (BFdecrypt): decrypts a short message or
        session key using a private key.
     
        Input:
     
        o  A private key point S_id of order q in E(F_p),
     
        o  A ciphertext triple (U', V', W') in E(F_p) x {0, . . . ,
           255}^20 x {0, . . . , 255}*.
     
        o  A set of public parameters.
     
        Output:
     
        o  A decrypted plaintext m', or an invalid ciphertext flag.
     
        Method:
     
        1. Let the public parameter set be comprised of a prime p, a
        curve E/F_p, the order q of a large prime subgroup of E(F_p),
        and two points P and P_pub of order q in E(F_p).
     
        2. Let theta' = Pairing(E, p ,q, U', S_id) by applying the
        modified Tate pairing of Algorithm 4.5.1 (Pairing).
     
        3. Let z = Canonical(p, k, 0, theta') using Algorithm 4.3.1
        (Canonical), the result of which is a canonical string
        representation of theta'.
     
     
     Boyen & Martin          Expires September 2007          [Page 32]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        4. Let w' = SHA1(z), using the SHA1 hashing algorithm [SHA],
        the result of which is a 20-byte string.
     
        5. Let rho = w XOR V, the bit-wise XOR of w and V.
     
        6. Let m = HashStream(|W|, rho) XOR W, which is the bit-wise
        exclusive-OR of m with the first |W| bytes of the pseudo-
        random stream produced by Algorithm 4.2.1 (HashStream) with
        seed rho.
     
        7. Let t = SHA1(m) using the SHA1 algorithm [SHA].
     
        8. Let l = HashToRange(q, rho || t) using Algorithm 4.1.1
        (HashToRange) on the 40-byte concatenation of rho and t.
     
        9. Verify that U' = [l]P:
     
           (a) If this is the case, then the decrypted plaintext m is
        returned.
     
           (b) Otherwise, the ciphertext is rejected and no plaintext
        is returned.
     
     6. Wrapper methods for the BF system
     
        This chapter describes a number of wrapper methods providing
        the identity-based cryptosystem functionalities using concrete
        encodings. The following functions are presently given based
        on the Boneh-Franklin algorithms.
     
     6.1. Private key generator (PKG) setup
     
        Algorithm 6.1.1 (BFwrapperPKGSetup): randomly selects a PKG
        master secret and a set of public parameters.
     
        Input:
     
        o  A curve type t,
     
        o  A security parameter n.
     
        Output:
     
        o  A common public parameter block pi,
     
        o  A corresponding master secret block sigma.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 33]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Method:
     
        1. Perform Algorithm 5.1.1 (BFsetup) on parameters t and n,
        producing a public parameter set and a master secret.
     
        2. Apply Algorithm 7.2.1 (BFencodeParams) on the public
        parameter set obtained in step 1 to get the public parameter
        block pi.
     
        3. Apply Algorithm 7.3.1 (BFencodeMaster) on the master secret
        obtained in step 1 to get the master secret block sigma.
     
     6.2. Private key extraction by the PKG
     
        Algorithm 6.2.1 (BFwrapperPrivateKeyExtract): extraction by
        the PKG of a private key corresponding to an identity.
     
        Input:
     
        o  A master secret block sigma,
     
        o  A corresponding public parameter block pi,
     
        o  An identity string id.
     
        Output:
     
        o  A private key block kappa_id
     
        Method:
     
        1. Apply Algorithm 7.2.2 (BFdecodeParams) to the public
        parameter block pi to obtain the public parameters, comprising
        a prime p, a curve E/F_p, the order q of a large prime
        subgroup of E(F_p), and two points P and P_pub of order q in
        E(F_p).
     
        2. Apply Algorithm 7.3.2 (BFdecodeMaster) on the master secret
        block sigma to obtain the master secret s.
     
        3. Perform Algorithm 5.3.1 (BFextractPriv) on the identity id,
        using the decoded parameters and secret, to produce a private
        key point S_id.
     
        4. Apply Algorithm 7.4.1 (BFencodePrivate) to S_id to produce
        a private key block kappa_id.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 34]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     6.3. Session key encryption
     
        Algorithm 6.3.1 (BFwrapperSessionKeyEncrypt): encrypts a short
        message or session key for an identity.
     
        Input:
     
        o  A public parameter block pi,
     
        o  A recipient identity string id,
     
        o  A plaintext string m (possibly comprising the concatenation
           of a pair of random session keys for symmetric encryption
           and message authentication purposes on a larger plaintext).
     
        Output:
     
        o  A ciphertext block
     
        Method:
     
        1. Apply Algorithm 7.2.2 (BFdecodeParams) on the public
        parameter block pi to obtain a set of public parameters,
        comprising a prime p, a curve E/F_p, the order q of a large
        prime subgroup of E(F_p), and two points P and P_pub of order
        q in E(F_p).
     
        2. Perform Algorithm 5.4.1 (BFencrypt) on the plaintext m for
        identity id using the decoded set of parameters, to obtain a
        ciphertext tuple (U, V, W).
     
        3. Apply Algorithm 7.5.1 (BFencodeCiphertext) on (U, V, W) to
        obtain a serialized ciphertext string
     
        Algorithm 6.3.2 (BFwrapperSessionKeyDecrypt): decrypts a short
        message or session key using a private key.
     
        Input:
     
        o  A public parameter block pi,
     
        o  A private key block kappa,
     
        o  A ciphertext block gamma.
     
        Output:
     
     
     
     Boyen & Martin          Expires September 2007          [Page 35]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  A decrypted plaintext string m, or an error flag signaling
           an invalid ciphertext.
     
        Method:
     
        1. Apply Algorithm 7.2.2 (BFdecodeParams) on the public
        parameter block pi to obtain the public parameters, comprising
        a prime p, a curve E/F_p, the order q of a large prime
        subgroup of E(F_p), and two points P and P_pub of order q in
        E(F_p).
     
        2. Apply Algorithm 7.4.2 (BFdecodePrivate) to kappa to obtain
        a private key point S_id.
     
        3. Apply Algorithm 7.5.2 (BFdecodeCiphertext) to gamma to
        obtain a ciphertext triple (U', V', W').
     
        4. Perform Algorithm 5.5.1 (BFdecrypt) on (U', V', W') using
        the private key S_id and the decoded set of public parameters,
        to obtain decrypted plaintext m, or an invalid ciphertext
        flag.
     
           (a) If the decryption was successful, return the plaintext
        m.
     
           (b) Otherwise, raise an error condition.
     
     7. Concrete encoding guidelines for BF
     
        This section specifies a set of concrete encoding schemes for
        the inputs and outputs of the previously described algorithms.
        ASN.1 encodings are specified in Section 12 of this document.
        All values listed this section MUST be DER-encoded [DER].
     
     7.1. Encoding of points on a curve
     
        Algorithm 7.1.1 (EncodePoint): encodes a point in E(F_p) in an
        exportable format.
     
        Input:
     
        o  A non-zero point Q in E(F_p).
     
        Output:
     
        o  A fixed-length (for given p) byte-string encoding of Q.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 36]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Method:
     
        1. Let (x, y) in F_p x F_p be the coordinates of P, where (x,
        y) satisfy the equation of E.
     
        2. The point P is then DER-encoded [DER] as a FpPoint using
        the ASN.1 rules given in the ASN.1 module given in Section 12
        of this document.
     
        Algorithm 6.1.2 (DecodePoint): decodes a point in E(F_p) from
        an exportable format.
     
        Input:
     
        o  A byte-string encoding of a non-zero point Q in E(F_p).
     
        Output:
     
        o  Q = (x, y).
     
        Method:
     
        1. The string is parsed and decoded as a pair (x, y), where x
        and y are integers in Z_p.
     
        2. Q is reconstructed as (x, y).
     
     7.2. Public parameters blocks
     
        Algorithm 7.2.1 (BFencodeParams): encodes a BF public
        parameter set in an exportable format.
     
        Input:
     
        o  A set of public parameters (t, E, p, q, P, P_pub).
     
        Output:
     
        o  A public parameter block pi, represented as a byte string.
     
        Method:
     
        1. Separate encodings for E, p, q, P, P_pub are obtained as
        follows:
     
           (a) If t = 1, execute Algorithm 7.2.3 (BFencodeParams1).
     
     
     
     Boyen & Martin          Expires September 2007          [Page 37]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        2. The separate encodings as well as a type indicator flag for
        t are then serialized in any suitable manner as dictated by
        the application.
     
        Algorithm 7.2.2 (BFdecodeParams): imports a BF public
        parameter block from a serialized format.
     
        Input:
     
        o  A public parameter block pi, represented as a byte string.
     
        Output:
     
        o  A set of public parameters (t, E, p, q, P, P_pub).
     
        Method:
     
        1. Identify from the appropriate flag the type t of curve upon
        which the parameter block is based.
     
        2. Then:
     
           (a) If t = 1, execute Algorithm 7.2.4 (BFdecodeParams1).
     
     7.2.1. Type-1 implementation
     
        Algorithm 7.2.3 (BFencodeParams1): encodes a BF type-1 public
        parameter set in an exportable format.
     
        Input:
     
        o  A set of public parameters (t, E, p, q, P, P_pub) with t =
           1.
     
        Output:
     
        o  Separate encodings for each of the E, p, q, P, P_pub
           components.
     
        Method:
     
        1. E: y^2 = x^3 + a * x + b is represented as a constant
        string, such as the empty string, since a and b are invariant
        for type-1 curves.
     
        2. p = 12 * r * q - 1 is represented as the smaller integer r,
        encoded, e.g., using a big-endian byte-string representation.
     
     
     Boyen & Martin          Expires September 2007          [Page 38]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        3. q = 2^a + s * 2^b + c, where a, b are small and c and s are
        either 1 or -1, is compactly represented as the 4-tuple (a, b,
        c, s).
     
        4. P = (x_P , y_P ) in F_p x F_p is represented using the
        point compression technique of Algorithm 7.1.1 (EncodePoint).
     
        5. P_pub is similarly encoded using Algorithm 7.1.1
        (EncodePoint).
     
        Algorithm 7.2.4 (BFdecodeParams1): decodes the components of a
        BF type-1 public parameter block.
     
        Input:
     
        o  Separate encodings for each one of E, p, q, P, P_pub.
     
        Output:
     
        o  A set of public parameters (t, E, p, q, P, P_pub) with t =
           1.
     
        Method:
     
        1. The equation of E is set to E = E : y^2 = x^3 + 1, as is
        always the case for type-1 curves. The actual encoding of E is
        ignored.
     
        2. The encoding of q is parsed as (a, b, c, s), and its value
        set to q = 2^a + s * 2^b + c.
     
        3. The encoding of p is parsed as the integer r, from which p
        is given by p = 12 * r * q - 1.
     
        4. P is reconstructed from its encoding (x, y') using the
        point decompression technique of Algorithm 7.1.2
        (DecodePoint).
     
        5. P_pub is similarly reconstructed from its encoding using
        Algorithm 7.1.2 (DecodePoint).
     
     7.3. Master secret blocks
     
        Algorithm 7.3.1 (BFencodeMaster): encodes a BF master secret
        in an exportable format.
     
        Input:
     
     
     Boyen & Martin          Expires September 2007          [Page 39]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  A master secret integer s between 2 and q - 1.
     
        Output:
     
        o  A master secret block sigma, represented as a byte string.
     
        Method:
     
        1. Sigma is constructed as the unsigned big-endian byte-string
        encoding of s of length Ceiling(lg(p) / 8).
     
        Algorithm 7.3.2 (BFdecodeMaster): decodes a BF master secret
        from a block in exportable format.
     
        Input:
     
        o  A master secret block sigma, represented as a byte string.
     
        Output:
     
        o  A master secret integer s in between 2 and q - 1 .
     
        Method:
     
        1. Let s = Value(sigma), where sigma is interpreted in the
        unsigned big endian convention.
     
     7.4. Private key blocks
     
        Algorithm 7.4.1 (BFencodePrivate): encodes a BF private key
        point in an exportable format.
     
        Input:
     
        o  A private key point S_id in E(F_p).
     
        Output:
     
        o  A private key block kappa, represented as a byte string.
     
        Method:
     
        1. kappa is obtained by applying Algorithm 7.1.1 (EncodePoint)
        to S_id.
     
        Algorithm 7.4.2 (BFdecodePrivate): decodes a BF private key
        point from an exportable format.
     
     
     Boyen & Martin          Expires September 2007          [Page 40]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Input:
     
        o  A private key block kappa, represented as a byte string.
     
        Output:
     
        o  A private key point S_id in E(F_p).
     
        Method:
     
        1. Kappa is parsed and decoded into a point S_id in E(F_p)
        using Algorithm 7.1.2 (DecodePoint).
     
     7.5. Ciphertext blocks
     
        Algorithm 7.5.1 (BFencodeCiphertext): encodes a BF ciphertext
        tuple in an exportable format.
     
        Input:
     
        o  A ciphertext tuple (U, V, W) in E(F_p) x {0, . . . ,
           255}^20 x {0, . . . , 255}*.
     
        Output:
     
        o  A ciphertext block gamma, represented as a byte string.
     
        Method:
     
        1. U = (x, y) is first encoded as a fixed-length string using
        Algorithm 7.1.1 (EncodePoint).
     
        2.  The output gamma is obtained as the encoding of U,
        concatenated with the fixed-length string V, and the variable
        length string W, both already in byte-string format.
     
        Algorithm 7.5.2 (BFdecodeCiphertext): decodes a BF ciphertext
        tuple from an exportable format.
     
        Input:
     
        o  A ciphertext block gamma, represented as a byte string.
     
        Output:
     
        o  A ciphertext tuple (U, V, W) in E(F_p) x {0, . . . ,
           255}^20 x {0, . . . , 255}*.
     
     
     Boyen & Martin          Expires September 2007          [Page 41]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Method:
     
        1. The ciphertext block gamma is parsed as a 3-tuple
        comprising a fixed-length encoding of U, followed by a 20-byte
        string V, followed by an arbitrary-length string W.
     
        2. U in E(F_p) is then recovered by applying Algorithm 7.1.2
        (DecodePoint) on its encoding.
     
     8. The Boneh-Boyen BB1 cryptosystem
     
        This chapter describes the algorithms constituting the first
        of the two Boneh-Boyen identity-based cryptosystems proposed
        in [BB1]. The description follows the practical implementation
        given in [BB1].
     
     8.1. Setup
     
        Algorithm 8.1.1 (BBsetup). Randomly selects a set of master
        secrets and the associated public parameters.
     
        Input:
     
        o  A curve type t (currently required to be fixed to t = 1),
     
        o  A security parameter n (currently required to take values n
           >= 1024).
     
        Output:
     
        o  A set of common public parameters,
     
        o  A corresponding master secret.
     
        Method:
     
        1. Depending on the selected type t:
     
        (a) If t = 1, then Algorithm 8.1.2 (BBsetup1) is executed.
     
        2. The resulting master secret and public parameters are
        separately encoded as per the application protocol
        requirements.
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 42]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     8.1.1. Type-1 curve implementation
     
        BBsetup1 takes a security parameter n as input. For type-1
        curves, the scale of n corresponds to the modulus bit-size
        believed of comparable security in the classical Diffie-
        Hellman or RSA public-key cryptosystems. For this
        implementation, allowed values of n are limited to 1024, 2048,
        and 3072, which correspond to the equivalent security level
        ranging from 80-, 112- and 128-bit symmetric keys
        respectively.
     
        Algorithm 8.1.2 (BBsetup1): randomly establishes a master
        secret and public parameters for type-1 curves.
     
        Input:
     
        o  A security parameter n, either 1024, 2048 or 3072.
     
        Output:
     
        o  A set of common public parameters (t, k, E, p, q, P, P_1,
           P_2, P_3, v),
     
        o  A corresponding triple of master secrets (alpha, beta,
           gamma).
     
        Method:
     
        1. Determine the subordinate security parameters n_p and n_q
        as follows:
     
           (a) Let n_p = n / 2, which will determine the size of the
        field F_p.
     
           (b) If n = 1024, n_q = 160; if n = 2048, n_q = 224; if n =
        3072, n_q = 256, which will determine the size of the subgroup
        order q.
     
        2. Construct the elliptic curve and its subgroup of interest
        as follows:
     
           (a) Select an arbitrary n_q-bit prime q, i.e., such that
        Ceiling(lg(p)) = n_q. For better performance, q is chosen as a
        Solinas prime, i.e., a prime of the form q = 2^a +/- 2^b +/- 1
        where 0 < b < a.
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 43]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           (b) Select a random integer r such that p = 12 * r * q - 1
        is an n_p-bit prime, i.e., such that Ceiling(lg(p)) = n_p.
     
        3. Select a point P of order q in E(F_p), as follows:
     
           (a) Select a random point P' of coordinates (x', y') on the
        curve E/F_p: y2 = x3 + 1 (mod p).
     
           (b) Let P = [12 * r]P'.
     
           (c) If P = 1, then start over in step 3a.
     
        4. Determine the master secret and the public parameters as
        follows:
     
           (a) Select three random integers alpha, beta, gamma, each
        of them in the range 1 to q - 1.
     
           (b) Let P_1 = [alpha]P.
     
           (c) Let P_2 = [beta]P.
     
           (d) Let P_3 = [gamma]P.
     
           (e) Let v = Pairing(E, p, q, P_1, P_2), which is an element
        of the extension field F_p^2 obtained using the modified Tate
        pairing of Algorithm 3.5.1 (Pairing).
     
        5. (t, k, E, p, q, P, P_1, P_2, P_3, v) are the common public
        parameters, where t = 1, k = 2, and E: y^2 = x^3 + 1.
     
        6. (alpha, beta, gamma) constitute the master secret.
     
     8.2. Public key derivation
     
        takes an identity string id and a set of public parameters,
        and returns an integer h_id.
     
        Algorithm 8.2.1 (BBderivePubl): derives the public key
        corresponding to an identity string.
     
        Input:
     
        o  An identity string id,
     
        o  A set of common public parameters (t, k, E, p, q, P, P_1,
           P_2, P_3, v).
     
     
     Boyen & Martin          Expires September 2007          [Page 44]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Output:
     
        o  An integer h_id modulo q.
     
        Method:
     
        1. Let h_id = HashToRangeq(id), using Algorithm 3.1.1
        (HashToRange).
     
     8.3. Private key extraction
     
        BBextractPriv takes an identity string id, and a set of public
        parameters and corresponding master secrets, and returns a
        private key consisting of two points D_0 and D_1.
     
        Algorithm 8.3.1 (BBextractPriv): extracts the private key
        corresponding to an identity string.
     
        Input:
     
        o  An identity string id,
     
        o  A set of common public parameters (t, k, E, p, q, P, P_1,
           P_2, P_3, v).
     
        Output:
     
        o  A pair of points (D_0, D_1), each of which has order q in
           E(F_p).
     
        Method:
     
        1. Select a random integer r in the range 1 to q - 1.
     
        2. Calculate the point D_0 as follows:
     
           (a) Let hid = HashToRange(q, id), using Algorithm 3.1.1
        (HashToRange).
     
           (b) Let y = alpha * beta + r * (alpha * h_id * gamma) in
        F_q.
     
           (c) Let D_0 = [y]P.
     
        3. Calculate the point D_1 as follows:
     
           (a) Let D_1 = [r]P.
     
     
     Boyen & Martin          Expires September 2007          [Page 45]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        4. The pair of points (D_0, D_1) constitutes the private key
        for id.
     
     8.4. Encryption
     
        BBencrypt takes three inputs: a set of public parameters, an
        identity id, and a plaintext m. The plaintext is intended to
        be a short random session key, although messages of arbitrary
        size are in principle allowed.
     
        Algorithm 8.4.1 (BBencrypt): encrypts a short message or
        session key for an identity string.
     
        Input:
     
        o  A plaintext string m of size |m| bytes,
     
        o  A recipient identity string id,
     
        o  A set of public parameters (t, k, E, p, q, P, P_1, P_2,
           P_3, v).
     
        Output:
     
        o  A ciphertext tuple (u, C_0, C_1, y) in F_q x E(F_p) x
           E(F_p) x {0, . . . , 255}^|m|.
     
        Method:
     
        1. Let the public parameter set be comprised of a prime p, a
        curve E/F_p, the order q of a large prime subgroup of E(F_p),
        four points P, P_1, P_2, P_3, of order q in E(F_p), and an
        extension field element v of order q in F_p^2 .
     
        2. Select a random integer s in the range 1 to q - 1.
     
        3. Let w = v^s, which is v raised to the power of s in F_p^2,
        the result is an element of order q in F_p^2 .
     
        4. Calculate the point C_0 as follows:
     
           (a) Let C_0 = [s]P.
     
        5. Calculate the point C_1 as follows:
     
           (a) Let _hid = HashToRangeq(id), using Algorithm 3.1.1
        (HashToRange).
     
     
     Boyen & Martin          Expires September 2007          [Page 46]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        (b) Let y = s * h_id in F_q.
     
        (c) Let C_1 = [y]P_1 + [s]P_3.
     
        6. Obtain canonical string representations of certain
        elements:
     
           (a) Let psi = Canonical(p, k, 1, w) using Algorithm 3.3.1
        (Canonical), the result of which is a canonical byte-string
        representation of w.
     
           (b) Let l = Ceiling(lg(p) / 8), the number of bytes needed
        to represent integers in F_p, and represent each of these F_p
        elements as a big-endian zero-padded byte-string of fixed
        length l:
     
           (x_0)_(256^l) to represent the x coordinate of C_0.
     
           (y_0)_(256^l) to represent the y coordinate of C_0.
     
           (x_1)_(256^l) to represent the x coordinate of C_1.
     
           (y_1)_(256^l) to represent the y coordinate of C_1.
     
        7. Encrypt the message m into the string y as follows:
     
           (a) Compute an encryption key h_0 as a dual-pass hash of w
        via its representation psi:
     
              i. Let zeta = SHA1(psi), using the SHA1 hashing
        algorithm [SHA]; the result is a 20-byte string.
     
              ii. Let xi = SHA1(zeta || psi), using the SHA1 hashing
        algorithm [SHA]; the result is a 20-byte string.
     
              iii. Let h' = xi || zeta, the 40-byte concatenation of
        the previous two SHA1 outputs.
     
           (b) Let y = HashStream(|m|, h') XOR m, which is the bit-
        wise exclusive-OR of m with the first |m| bytes of the pseudo-
        random stream produced by Algorithm 3.2.1 (HashStream) with
        seed h'.
     
        8. Create the integrity check tag u as follows:
     
           (a) Compute a one-time pad h'' as a dual-pass hash of the
        representation of (w, C_0, C_1, y):
     
     
     Boyen & Martin          Expires September 2007          [Page 47]
     

     Internet Draft                 IBCS #1                March 2007
     
     
              i. Let sigma = (y_1)_(256^l) || (x_1)_(256^l) ||
        (y_0)_(256^l) || (x_0)_(256^l) || y || psi be the
        concatenation of y and the five indicated strings in the
        specified order.
     
              ii. Let eta = SHA1(sigma), using the SHA1 hashing
        algorithm [SHA] to get a 20-byte string.
     
              iii. Let mu = SHA1(eta || sigma), using the SHA1 hashing
        algorithm [SHA] to get a 20-byte string.
     
              iv. Let h'' = mu || eta, the 40-byte concatenation of
        the previous two SHA1 outputs.
     
           (b) Build the tag u as the encryption of the integer s with
        the one-time pad h'':
     
              i. Let rho = HashToRangeq(h'') to get an integer in Z_q.
     
              ii. Let u = s + rho (mod q).
     
        9. The complete ciphertext is given by the quadruple (u, C_0,
        C_1, y).
     
     8.5. Decryption
     
        BBdecrypt takes three inputs: a set of public parameters, a
        private key (D_0, D_1), and a ciphertext parsed as (u, C_0,
        C_1, y). It outputs a message m, or signals an error if the
        ciphertext is invalid for the given key.
     
        Algorithm 7.5.1 (BBdecrypt): decrypts a short message or
        session key using a private key.
     
        Input:
     
        o  A private key given as a pair of points (D_0, D_1) of order
           q in E(F_p),
     
        o  A ciphertext quadruple (u, C_0, C_1, y) in Z_q x E(F_p) x
           E(F_p) x {0, . . . , 255}*.
     
        o  A set of public parameters.
     
        Output:
     
        o  A decrypted plaintext m, or an invalid ciphertext flag.
     
     
     Boyen & Martin          Expires September 2007          [Page 48]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Method:
     
        1. Let the public parameter set be comprised of a prime p, a
        curve E/F_p, the order q of a large prime subgroup of E(F_p),
        four points P, P_1, P_2, P_3, of order q in E(F_p), and an
        extension field element v of order q in F_p^2 .
     
        2. Let w = PairingRatio(E, p, q, C_0, D_0, C_1, D_1), which
        computes the ratio of two Tate pairings (modified, for type-1
        curves) as specified in Algorithm 4.6.1 (PairingRatio).
     
        3. Obtain canonical string representations of certain
        elements:
     
           (a) Let psi = Canonical(p, k, 1, w), using Algorithm 4.3.1
        (Canonical); the result is a canonical byte-string
        representation of w.
     
           (b) Let l = Ceiling(lg(p) / 8), the number of bytes needed
        to represent integers in F_p, and represent each of these F_p
        elements as a big-endian zero-padded byte-string of fixed
        length l:
     
           (x_0)_(256^l) to represent the x coordinate of C_0.
     
           (y_0)_(256^l) to represent the y coordinate of C_0.
     
           (x_1)_(256^l) to represent the x coordinate of C_1.
     
           (y_1)_(256^l) to represent the y coordinate of C_1.
     
        4. Decrypt the message m from the string y as follows:
     
           (a) Compute the decryption key h' as a dual-pass hash of w
        via its representation psi:
     
              i. Let zeta = SHA1(psi), using the SHA1 hashing
        algorithm [SHA] to get a 20-byte string.
     
              ii. Let xi = SHA1(zeta || psi), using the SHA1 hashing
        algorithm [SHA] to get a 20-byte string.
     
              iii. Let h' = xi || zeta, the 40-byte concatenation of
        the previous two SHA1 outputs.
     
           (b) Let m = HashStream(|y|, h')_XOR y, which is the bit-
        wise exclusive-OR of y with the first |y| bytes of the pseudo-
     
     
     Boyen & Martin          Expires September 2007          [Page 49]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        random stream produced by Algorithm 3.2.1 (HashStream) with
        seed h'.
     
        5. Obtain the integrity check tag u as follows:
     
           (a) Recover the one-time pad h'' as a dual-pass hash of the
        representation of (w, C_0, C_1, y):
     
              i. Let sigma = (y_1)_(256^l) || (x_1)_(256^l) ||
        (y_0)_(256^l) || (x_0)_(256^l) || y || psi be the
        concatenation of y and the five indicated strings in the
        specified order.
     
              ii. Let eta = SHA1(sigma) using the SHA1 hashing
        algorithm [SHA] to get a 20-byte string.
     
              iii. Let mu = SHA1(eta || sigma), using the SHA1 hashing
        algorithm [SHA] to get a 20-byte string.
     
              iv. Let h'' = mu || eta, the 40-byte concatenation of
        the previous two SHA1 outputs.
     
           (b) Unblind the encryption randomization integer s from the
        tag u using h'':
     
              i. Let rho = HashToRangeq(h'') to get an integer in Z_q.
     
              ii. Let s = u - rho (mod q).
     
        6. Verify the ciphertext consistency according to the
        decrypted values:
     
           (a) Test whether the equality w = v^s holds in F_p^2 .
     
           (b) Test whether the equality C_0 = [s]P holds in E(F_p).
     
        7. Adjudication and final output:
     
           (a) If either of the tests performed in step 6 fails, the
        ciphertext is rejected, and no decryption is output.
     
           (b) Otherwise, i.e., when both tests performed in step 6
        succeed, the decrypted message is output.
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 50]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     9. Wrapper methods for the BB1 system
     
        This section describes a number of wrapper methods providing
        the identity-based cryptosystem functionalities using concrete
        encodings. The following functions are presently given based
        on the Boneh-Franklin algorithms.
     
     9.1. Private key generator (PKG) setup
     
        Algorithm 9.1.1 (BBwrapperPKGSetup): randomly selects a PKG
        master secret and a set of public parameters.
     
        Input:
     
        o  A curve type t,
     
        o  A security parameter n.
     
        Output:
     
        o  A common public parameter block pi,
     
        o  A corresponding master secret block sigma.
     
        Method:
     
        1. Perform Algorithm 8.1.1 (BBsetup) on parameters t and n,
        producing a set of public parameters and master secret.
     
        2. Apply Algorithm 10.2.1 (BBencodeParams) on the public
        parameters obtained in step 1 to get the public parameter
        block pi.
     
        3. Apply Algorithm 10.3.1 (BBencodeMaster) on the master
        secrets obtained in step 1 to get the master secret block
        sigma.
     
     9.2. Private key extraction by the PKG
     
        Algorithm 9.2.1 (BBwrapperPrivateKeyExtract): extraction by
        the PKG of a private key corresponding to an identity.
     
        Input:
     
        o  A master secret block sigma,
     
        o  A corresponding public parameter block pi,
     
     
     Boyen & Martin          Expires September 2007          [Page 51]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  An identity string id.
     
        Output:
     
        o  A private key block kappa_id.
     
        Method:
     
        1. Apply Algorithm 10.2.2 (BBdecodeParams) on the public
        parameter block pi to obtain the public parameters, comprising
        a prime p, the parameters of a curve E/F_p with embedding
        degree k = 2, the order q of a large prime subgroup of E(F_p),
        four points P, P_1, P_2, P_3, of order q in E(F_p), and an
        element v of order q in the extension field F_p^k of degree k.
     
        2. Apply Algorithm 10.3.2 (BBdecodeMaster) on the master
        secret block sigma to obtain the master secret (alpha, beta,
        gamma).
     
        3. Perform Algorithm 8.3.1 (BBextractPriv) on the identity id,
        using the decoded public parameters and master secret, to
        produce a private key (D_0, D_1).
     
        4. Apply Algorithm 10.4.1 (BBencodePrivate) on the private key
        to produce a private key block kappa_id.
     
     9.3. Session key encryption
     
        Algorithm 9.3.1 (BBwrapperSessionKeyEncrypt): encrypts a short
        message or session key for an identity.
     
        Input:
     
        o  A public parameter block pi,
     
        o  A recipient identity string id,
     
        o  A plaintext string m (possibly comprising the concatenation
           of a pair of random session keys for symmetric encryption
           and message authentication purposes on a larger plaintext).
     
        Output:
     
        o  A ciphertext block omega.
     
        Method:
     
     
     
     Boyen & Martin          Expires September 2007          [Page 52]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        1. Apply Algorithm 10.2.2 (BBdecodeParams) on the public
        parameter block pi to obtain the public parameters, comprising
        a prime p, the parameters of a curve E/F_p with embedding
        degree k = 2, the order q of a large prime subgroup of E(F_p),
        four points P, P_1, P_2, P_3, of order q in E(F_p), and an
        element v of order q in the extension field F_p^k .
     
        2. Perform Algorithm 8.4.1 (BBencrypt) on the plaintext m for
        identity id using the decoded set of parameters, to obtain a
        ciphertext quadruple (u, C_0, C_1, y).
     
        3. Apply Algorithm 10.5.1 (BBencodeCiphertext) on the
        ciphertext (u, C_0, C_1, y) to obtain a string representation
        of omega.
     
        Algorithm 9.3.2 (BBwrapperSessionKeyDecrypt): decrypts a short
        message or session key using a private key.
     
        Input:
     
        o  A public parameter block pi,
     
        o  A private key block kappa,
     
        o  A ciphertext block omega.
     
        Output:
     
        o  A decrypted plaintext string m, or an error flag signaling
           an invalid ciphertext.
     
        Method:
     
        1. Apply Algorithm 10.2.2 (BBdecodeParams) on the public
        parameter block pi to obtain the public parameters, comprising
        a prime p, the parameters of a curve E/F_p with embedding
        degree k = 2, the order q of a large prime subgroup of E(F_p),
        four points P, P_1, P_2, P_3, of order q in E(F_p), and an
        element v of order q in the extension field F_p^2.
     
        2. Apply Algorithm 10.4.2 (BBdecodePrivate) on kappa to obtain
        the private key points (D_0, D_1).
     
        3. Apply Algorithm 10.5.2 (BBdecodeCiphertext) on omega to
        obtain a ciphertext quadruple (u, C_0, C_1, y).
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 53]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        4. Perform Algorithm 8.5.1 (BBdecrypt) on (u, C_0, C_1, y)
        using the private key (D_0, D_1) and the decoded set of public
        parameters, to obtain decrypted plaintext m, or an invalid
        ciphertext flag.
     
           (a) If the decryption was successful, return the plaintext
        string m.
     
           (b) Otherwise, raise an error condition.
     
     10. Concrete encoding guidelines for BB1
     
        This section specifies a set of concrete encoding schemes for
        the inputs and outputs of the previously described algorithms.
        ASN.1 encodings are specified in Section 12 of this document.
        All values MUST be DER-encoded [DER].
     
     10.1. Encoding of points on a curve
     
        We refer to the description of Algorithm 7.1.1 (EncodePoint)
        and Algorithm 7.1.2 (DecodePoint).
     
     10.2. Public parameters blocks
     
        Algorithm 10.2.1 (BBencodeParams): encodes a BB1 public
        parameter set in an exportable format.
     
        Input:
     
        o  A set of public parameters (t, k, E, p, q, P, P_1, P_2,
           P_3, v).
     
        Output:
     
        o  A public parameter block pi, represented as a byte string.
     
        Method:
     
        1. Separate encodings for k, E, p, q, P, P_1, P_2, P_3 are
        obtained as follows:
     
           (a) If t = 1, execute Algorithm 10.2.3 (BBencodeParams1).
     
        2. The separate encodings as well as a type indicator flag for
        t are then serialized in any suitable manner as dictated by
        the application.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 54]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Algorithm 10.2.2 (BBdecodeParams): imports a BB1 public
        parameter block from a serialized format.
     
        Input:
     
        o  A public parameter block pi, represented as a byte string.
     
        Output:
     
        o  A set of public parameters (t, k, E, p, q, P, P_1, P_2,
           P_3, v).
     
        Method:
     
        1. Identify from the appropriate flag the type t of curve upon
        which the parameter block is based.
     
        2. Then:
     
           (a) If t = 1, execute Algorithm 10.2.4 (BBdecodeParams1).
     
     10.2.1. Type-1 implementation
     
        Algorithm 10.2.3 (BBencodeParams1): encodes a BB1 type-1
        public parameter set in an exportable format.
     
        Input:
     
        o  A set of public parameters (t, k, E, p, q, P, P_1, P_2,
           P_3, v) with t = 1.
     
        Output:
     
        o  Separate encodings for each of the k, E, p, q, P, P_1, P_2,
           P_3 components (v is redundant and omitted).
     
        Method:
     
        1. The elliptic curve E: y^2 = x^3 + a * x + b and the
        embedding degree k = 2 are represented as a constant string,
        such as the empty string, since the coefficients a and b and
        the embedding degree are invariant for type-1 curves.
     
        2. The integer p = 12 * r * q - 1 is represented as the
        smaller integer r, encoded, e.g., using a big-endian byte-
        string representation.
     
     
     
     Boyen & Martin          Expires September 2007          [Page 55]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        3. The integer q = 2^a + s* 2^b + c, where a, b are small and
        both c and s are either 1 or -1 is compactly represented as
        the 4-tuple (a, b, c, s).
     
        4. The point P = (x_P , y_P) in F_p x F_p is represented using
        the point compression technique of Algorithm 7.1.1
        (EncodePoint).
     
        5. Each of P_1, P_2, and P_3 is similarly encoded using
        Algorithm 7.1.1 (EncodePoint).
     
        Algorithm 10.2.4 (BBdecodeParams1): decodes the components of
        a BB1 type-1 public parameter block.
     
        Input:
     
        o  Separate encodings for each one of k, E, p, q, P, P_1, P_2,
           P_3.
     
        Output:
     
        o  A set of public parameters (t, k, E, p, q, P, P_1, P_2,
           P_3, v) with t = 1.
     
        Method:
     
        1. The equation of E is set to E: y^2 = x^3 + 1, as is always
        the case for type-1 curves.
     
        2. The embedding degree is set to k = 2 for type-1 curves.
     
        3. The encoding of q is parsed as (a, b, c, s), and its value
        set to q = 2^a + s * 2^b + c.
     
        4. The encoding of p is parsed as the integer r, from which p
        is given by p = 12 * r * q - 1.
     
        5. The point P is reconstructed from its encoding (x, y')
        using the point decompression technique of Algorithm 7.1.2
        (DecodePoint).
     
        6. Each of P_1, P_2, and P_3 is reconstructed in a similar
        manner from its encoding using Algorithm 7.1.2 (DecodePoint).
     
        7. The extension field element v is reconstructed as v =
        Pairing(E, p, q, P_1, P_2) using Algorithm 4.5.1 (Pairing).
     
     
     
     Boyen & Martin          Expires September 2007          [Page 56]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     10.3. Master secret blocks
     
        Algorithm 10.3.1 (BBencodeMaster): encodes a BB1 master secret
        in an exportable format.
     
        Input:
     
        o  A master secret triple of integers (alpha, beta, gamma) in
           (Z+_q) ^3.
     
        Output:
     
        o  A master secret block sigma, represented as a byte string.
     
        Method:
     
        1. Encode each integer as an unsigned big-endian byte-string
        of fixed length Ceiling(lg(q) / 8), or, when q is a Solinas
        prime q = 2^a +/- 2^b +/- 1, of length Ceiling((a + 1) / 8):
     
           (a) sigma_alpha to represent alpha.
     
           (b) sigma_beta to represent beta.
     
           (c) sigma_gamma to represent gamma.
     
        2. Sigma = sigma_alpha || sigma_beta || sigma_gamma is the
        concatenation of these strings.
     
        Algorithm 10.3.2 (BBdecodeMaster): decodes a BB1 master secret
        from a block in exportable format.
     
        Input:
     
        o  A master secret block sigma, represented as a byte string.
     
        Output:
     
        o  A master secret triple of integers (alpha, beta, gamma) in
           (Z+_q) ^3.
     
        Method:
     
        1. Parse sigma as sigma_alpha || sigma_beta || sigma_gamma,
        where each substring is a byte string of fixed length
        Ceiling(lg(q) / 8), or, when q is a Solinas prime q = 2^a +/-
        2^b +/- 1, of length Ceiling((a + 1) / 8)).
     
     
     Boyen & Martin          Expires September 2007          [Page 57]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        2. Decode each substring as an integer in unsigned big-endian
        byte-string representation:
     
        (a) Let alpha = Value(sigma_alpha).
     
        (b) Let beta = Value(sigma_beta).
     
        (c) Let gamma = Value(sigma_gamma).
     
     10.4. Private key blocks
     
        Algorithm 10.4.1 (BBencodePrivate): encodes a BB1 private key
        in an exportable format.
     
        Input:
     
        o  A private key pair of points (D_0, D_1) in E(F_p) x E(F_p).
     
        Output:
     
        o  A private key block kappa, represented as a byte string.
     
        Method:
     
        1. Encode each point separately:
     
           (a) The first component of kappa, kappa_0 is obtained by
        applying Algorithm 7.1.1 (EncodePoint) to D_0.
     
           (b) The second componente of kappa, kappa_1 is obtained by
        applying Algorithm 7.1.1 (EncodePoint) to D_0.
     
        2. Let kappa = kappa_0 || kappa_1.
     
        Algorithm 10.4.2 (BBdecodePrivate): decodes a BB1 private key
        from an exportable format.
     
        Input:
     
        o  A private key block kappa, represented as a byte string.
     
        Output:
     
        o  A private key pair of point (D_0, D_1) in E(F_p) x E(F_p).
     
        Method:
     
     
     
     Boyen & Martin          Expires September 2007          [Page 58]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        1. Decode each point separately:
     
           (a) The first prefix of kappa is parsed and decoded into a
        point D_0 in E(F_p) using Algorithm 7.1.2 (DecodePoint).
     
           (b) The remainder of kappa is parsed and decoded into a
        point D_1 in E(F_p) using Algorithm 7.1.2 (DecodePoint).
     
     10.5. Ciphertext blocks
     
        Algorithm 10.5.1 (BBencodeCiphertext). Encodes a BB1
        ciphertext tuple in an exportable format.
     
        Input:
     
        o  A ciphertext tuple (u, C_0, C_1, y) in Z_q x E(F_p) x
           E(F_p) x {0, . . . , 255}*.
     
        Output:
     
        o  A ciphertext block omega, represented as a byte string.
     
        Method:
     
        1. Let chi_0 be the fixed-length encoding of C_0 = (x_0, y_0)
        using Algorithm 7.1.1 (EncodePoint).
     
        2. Let chi_1 be the fixed-length encoding of C_1 = (x_1, y_1)
        using Algorithm 7.1.1 (EncodePoint).
     
        3. Let nu be the encoding of u as an unsigned big-endian byte-
        string of fixed length Ceiling(lg(q) / 8), or, when q is a
        Solinas prime q = 2^a +/- 2^b +/- 1, of length Ceiling((a +
        1)/8).
     
        4. The value of omega = chi_0 || chi_1 || nu || y is the
        concatenation of these three strings and y.
     
        Algorithm 10.5.2 (BBdecodeCiphertext): decodes a BB1
        ciphertext tuple from an exportable format.
     
        Input:
     
        o  A ciphertext block omega, represented as a byte string.
     
        Output:
     
     
     
     Boyen & Martin          Expires September 2007          [Page 59]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        o  A ciphertext tuple (u, C_0, C_1, y) in Z_q x E(F_p) x
           E(F_p) x {0, . . . , 255}*.
     
        Method:
     
        1. The value of omega is parsed as a quadruple comprising a
        fixed-length encoding of C_0, a fixed-length encoding of C_1,
        a fixed-length encoding of u, and the arbitrary-length string
        y:
     
        (a) C_0 in E(F_p) is first recovered by applying Algorithm
        7.1.2 (DecodePoint) on the first parsed component of omega.
     
        (b) C_1 in E(F_p) is next recovered by applying Algorithm
        7.1.2 (DecodePoint) on the second parsed component of omega.
     
        (c) The value of u in Z_q is then recovered from its unsigned
        big-endian byte-string representation in the third parsed
        component of omega, of length Ceiling(lg(q) / 8), or, when q
        is a Solinas prime q = 2^a +/- 2b +/- 1, of length Ceiling((a
        + 1)/8).
     
        (d) The value of y is finally taken as the remainder of omega.
     
     11. Test vectors
     
        The following data can be used to verify the correct operation
        of selected algorithms that are defined in this document.
     
     11.1. Algorithm 3.2.2 (PointMultiply)
     
        Input:
     
        q = 0xfffffffffffffffffffffffffffbffff
     
        p = 0xbffffffffffffffffffffffffffcffff3
     
        E/F_p: y^2 = x^3 + 1
     
        A = (0x489a03c58dcf7fcfc97e99ffef0bb4634,
        0x510c6972d795ec0c2b081b81de767f808)
     
        l = 0xb8bbbc0089098f2769b32373ade8f0daf
     
        Output:
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 60]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        [l]A = (0x073734b32a882cc97956b9f7e54a2d326,
        0x9c4b891aab199741a44a5b6b632b949f7)
     
     11.2. Algorithm 4.1.1 (HashToRange)
     
        Input:
     
        s =
        54:68:69:73:20:41:53:43:49:49:20:73:74:72:69:6e:67:20:77:69:74
        :68:6f:75:74:20:6e:75:6c:6c:2d:74:65:72:6d:69:6e:61:74:6f:72
        ("This ASCII string without null-terminator")
     
        n = 0xffffffffffffffffffffefffffffffffffffffff
     
        Output:
     
        v = 0x79317c1610c1fc018e9c53d89d59c108cd518608
     
     11.3. Algorithm 4.5.1 (Pairing)
     
        q = 0xfffffffffffffffffffffffffffbffff
     
        p = 0xbffffffffffffffffffffffffffcffff3
     
        E/F_p: y^2 = x^3 + 1
     
        A = (0x489a03c58dcf7fcfc97e99ffef0bb4634,
        0x510c6972d795ec0c2b081b81de767f808)
     
        B = (0x40e98b9382e0b1fa6747dcb1655f54f75,
        0xb497a6a02e7611511d0db2ff133b32a3f)
     
        Output:
     
        e'(A, B) = (0x8b2cac13cbd422658f9e5757b85493818,
        0xbc6af59f54d0a5d83c8efd8f5214fad3c) in F_p^2 where F_p^2 is
        represented as F_p[x]/(x^2 + 1)
     
     11.4. Algorithm 5.2.1 (BFderivePubl)
     
        Input:
     
        id = 6f:42:62 ("Bob")
     
        t = 1
     
        p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb
     
     
     Boyen & Martin          Expires September 2007          [Page 61]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        q = 0xffffffffffffffffffffffeffffffffffff
     
        P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d,
        0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab)
     
        P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108,
        0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f)
     
        Output:
     
        Q_id = (0x22fa1207e0d19e1a4825009e0e88e35eb57ba79391498f59,
        0x982d29acf942127e0f01c881b5ec1b5fe23d05269f538836)
     
     11.5. Algorithm 5.3.1 (BFextractPriv)
     
        Input:
     
        s = 0x749e52ddb807e0220054417e514742b05a0
     
        t = 1
     
        p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb
     
        q = 0xffffffffffffffffffffffeffffffffffff
     
        P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d,
        0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab)
     
        P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108,
        0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f)
     
        Output:
     
        Q_id = (0x8212b74ea75c841a9d1accc914ca140f4032d191b5ce5501,
        0x950643d940aba68099bdcb40082532b6130c88d317958657)
     
     11.6. Algorithm 5.4.1 (BFencrypt)
     
        (Note that the following values can also be used to test
        Algorithm 5.5.1 (BFdecrypt))
     
        Input:
     
        m = 48:69:20:74:68:65:72:65:21 ("Hi there!")
     
        id = 6f:42:62 ("Bob")
     
     
     
     Boyen & Martin          Expires September 2007          [Page 62]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        t = 1
     
        p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb
     
        q = 0xffffffffffffffffffffffeffffffffffff
     
        P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d,
        0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab)
     
        P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108,
        0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f)
     
        Output:
     
        Using the random value rho =
        0xed5397ff77b567ba5ecb644d7671d6b6f2082968, we get the
        following output:
     
        U =
        (0x1b5f6c461497acdfcbb6d6613ad515430c8b3fa23b61c585e9a541b199e
        2a6cb,
        0x9bdfbed1ae664e51e3d4533359d733ac9a600b61048a7d899104e826a0ec
        4fa4)
     
        V =
        e0:1d:ad:81:32:6c:b1:73:af:c2:8d:72:2e:7a:32:1a:7b:29:8a:aa
     
        W = f9:04:ba:40:30:e9:ce:6e:ff
     
     11.7. Algorithm 8.3.1 (BBextractPriv)
     
        Inputs:
     
        alpha = 0xa60c395285ded4d70202c8283d894bad4f0
     
        beta = 0x48bf012da19f170b13124e5301561f45053
     
        gamma = 0x226fba82bc38e2ce4e28e56472ccf94a499
     
        t = 1
     
        p = 0x91bbe2be1c8950750784befffffffffffff6e441d41e12fb
     
        q = 0xfffffffffbfffffffffffffffffffffffff
     
        P = (0x13cc538fe950411218d7f5c17ae58a15e58f0877b29f2fe1,
        0x8cf7bab1a748d323cc601fabd8b479f54a60be11e28e18cf)
     
     
     Boyen & Martin          Expires September 2007          [Page 63]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        P_1 = (0x0f809a992ed2467a138d72bc1d8931c6ccdd781bedc74627,
        0x11c933027beaaf73aa9022db366374b1c68d6bf7d7a888c2)
     
        P_2 = (0x0f8ac99a55e575bf595308cfea13edb8ec673983919121b0,
        0x3febb7c6369f5d5f18ee3ea6ca0181448a4f3c4f3385019c)
     
        P_3 = (0x2c10b43991052e78fac44fdce639c45824f5a3a2550b2a45,
        0x6d7c12d8a0681426a5bbc369c9ef54624356e2f6036a064f)
     
        v = (0x38f91032de6847a89fc3c83e663ed0c21c8f30ce65c0d7d3,
        0x44b9aa10849cc8d8987ef2421770a340056745da8b99fba2) in F_p^2
        where F_p^2 is represented as F_p[x]/(x^2 + 1)
     
        id = 6f:42:62 ("Bob")
     
        Output:
     
        Using the random value r =
        0x695024c25812112187162c08aa5f65c7a2c, we get the following
        output:
     
        D_0 = (0x3264e13feeb7c506493888132964e79ad657a952334b9e53,
        0x3eeaefc14ba1277a1cd6fdea83c7c882fe6d85d957055c7b)
     
        D_1 = (0x8d7a72ad06909bb3bb29b67676d935018183a905e7e8cb18,
        0x2b346c6801c1db638f270af915a21054f16044ab67f6c40e)
     
     11.8. Algorithm 8.4.1 (BBencrypt)
     
        (Note that the following values can also be used to test
        Algorithm 8.5.1 (BFdecrypt))
     
        Input:
     
        m = 48:69:20:74:68:65:72:65:21 ("Hi there!")
     
        id = 6f:42:62 ("Bob")
     
        t = 1
     
        k = 2
     
        E: y^2 = x^3 + 1
     
        p = 0x91bbe2be1c8950750784befffffffffffff6e441d41e12fb
     
        q = 0xfffffffffbfffffffffffffffffffffffff
     
     
     Boyen & Martin          Expires September 2007          [Page 64]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        P = (0x13cc538fe950411218d7f5c17ae58a15e58f0877b29f2fe1,
        0x8cf7bab1a748d323cc601fabd8b479f54a60be11e28e18cf)
     
        P_1 = (0x0f809a992ed2467a138d72bc1d8931c6ccdd781bedc74627,
        0x11c933027beaaf73aa9022db366374b1c68d6bf7d7a888c2)
     
        P_2 = (0x0f8ac99a55e575bf595308cfea13edb8ec673983919121b0,
        0x3febb7c6369f5d5f18ee3ea6ca0181448a4f3c4f3385019c)
     
        P_3 = (0x2c10b43991052e78fac44fdce639c45824f5a3a2550b2a45,
        0x6d7c12d8a0681426a5bbc369c9ef54624356e2f6036a064f)
     
        v = (0x38f91032de6847a89fc3c83e663ed0c21c8f30ce65c0d7d3,
        0x44b9aa10849cc8d8987ef2421770a340056745da8b99fba2) in F_p^2
        where F_p^2 is represented as F_p[x]/(x^2 + 1)
     
        Output:
     
        Using the random value s =
        0x62759e95ce1af248040e220263fb41b965e, we get the following
        output:
     
        u = 0xad1ebfa82edf0bcb5111e9dc08ff0737c68
     
        C_0 = (0x79f8f35904579f1aaf51897b1e8f1d84e1c927b8994e81f9,
        0x1cf77bb2516606681aba2e2dc14764aa1b55a45836014c62)
     
        C_1 = (0x410cfeb0bccf1fa4afc607316c8b12fe464097b20250d684,
        0x8bb76e7195a7b1980531b0a5852ce710cab5d288b2404e90)
     
        y = 82:a6:42:b9:bb:e9:82:c4:57
     
     12. ASN.1 module
     
        This section defines the ASN.1 module for the encodings
        discussed in sections 7 and 10. All values MUST be DER-encoded
        [DER].
     
     
     
     
     
     
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 65]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        IBCS { joint-iso-itu-t(2) country(16) us(840) organization(1)
           identicrypt(114334) ibcs(1) module(5) version(1) }
     
        DEFINITIONS IMPLICIT TAGS ::= BEGIN
     
        --
        -- Identity-based cryptography standards (IBCS): supersingular
        curve
        -- implementations of the BF and BB1 cryptosystems
        --
        -- This version of the IBCS standard only supports IBE over
        -- type-1 curves, i.e., the curve y^2 = x^3 + 1.
        --
     
        ibcs OBJECT IDENTIFIER ::= {
           joint-iso-itu-t(2) country(16) us(840) organization(1)
              identicrypt(114334) ibcs(1)
        }
     
        --
        -- IBCS1
        --
        -- IBCS1 defines the algorithms used to implement IBE
        --
     
        ibcs1 OBJECT IDENTIFIER ::= {
           ibcs ibcs1(1)
        }
     
        --
        -- Supporting types
        --
     
        --
        -- Encoding of a point on an elliptic curve E/Fp
        --
     
        FpPoint ::= SEQUENCE {
           x  INTEGER,
           y  INTEGER
        }
     
        --
        -- A type-1 curve is specified by an OID,
        -- with the coefficients of the curve in Weierstrass
        -- normal form being optional
        --
     
     
     Boyen & Martin          Expires September 2007          [Page 66]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     
        Type1Curve ::= SEQUENCE {
           curveID  OBJECT IDENTIFIER,
           a     OCTET STRING OPTIONAL,
           b     OCTET STRING OPTIONAL
        }
     
        type1curve OBJECT IDENTIFIER ::= {
           ibcs1 curve-types(1) type1-curve(1)
        }
     
        --
        -- Encoding of a Solinas prime
        --
        -- Encodes a Solinas prime of the form
        -- q = 2^a + s * 2^b +c with the integers a, b
        -- and c and s being +1 or -1
        --
     
        SolinasPrime ::= SEQUENCE {
           a  INTEGER,
           b  INTEGER,
           c  Sign,
           s  Sign
        }
     
        Sign ::= ENUMERATED {
           positive(1),
           negative(-1)
        }
     
        --
        -- Algorithms
        --
     
        ibe-algorithms OBJECT IDENTIFIER ::= {
           ibcs1 ibe-algorithms(2)
        }
     
        ---
        --- Boneh-Franklin IBE
        ---
     
        bf OBJECT IDENTIFIER ::= { ibe-algorithms bf(1) }
     
        --
        -- Encoding of a BF public parameters block.
     
     
     Boyen & Martin          Expires September 2007          [Page 67]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        -- The only version currently supported is version 1.
        -- For the BF prime p and subprime q, we have q * r = p + 1,
        -- and we encode the values of r and q in the public
        parameters.
        -- The points P and P_pub are encoded as pointP and pointPpub
        -- respectively.
        --
     
        BFPublicParamaters ::= SEQUENCE {
           version     INTEGER { v1(1) },
           curve    Type1Curve,
           r        INTEGER,
           q        SolinasPrime,
           pointP      FpPoint,
           pointPpub   FpPoint
        }
     
        --
        -- A BF private key is a point on an elliptic curve,
        -- which is an FpPoint.
        --
     
        BFPrivateKeyBlock ::= FpPoint
     
        --
        -- A BF master secret is an integer.
        --
     
        BFMasterSecret ::= INTEGER
     
        --
        -- BF ciphertext block
        --
     
        BFCiphertextBlock ::= SEQUENCE {
           u  FpPoint,
           v  OCTET STRING,
           w  OCTET STRING
        }
     
        --
        -- Boneh-Boyen (BB1) IBE
        --
     
        bb1 OBJECT IDENTIFIER ::= { ibe-algorithms bb1(2) }
     
        --
     
     
     Boyen & Martin          Expires September 2007          [Page 68]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        -- Encoding of a BB1 public parameters block.
        -- The version is currently fixed to 1.
        -- The embedding degree is currently fixed to 2.
        -- For type-1 curves, curve is set to NULL.
        -- For the BB1 prime p and subprime q, we have q * r = p + 1,
        -- and we encode the values of r and q in the public
        parameters.
        --
     
        BB1PublicParameters ::= SEQUENCE {
           version     INTEGER { v1(1) },
           embedding-degree  INTEGER { degree-2(2) },
           curve    Type1Curve,
           r        INTEGER,
           q        SolinasPrime,
           pointP      FpPoint,
           pointP1     FpPoint,
           pointP2     FpPoint,
           pointP3     FpPoint
        }
     
        --
        -- BB1 master secret block
        --
     
        BB1MasterSecret ::= SEQUENCE {
           alpha INTEGER,
           beta     INTEGER,
           gamma INTEGER
        }
     
        --
        -- BB1 private Key block
        --
     
        BB1PrivateKeyBlock ::= SEQUENCE {
           pointD0  FpPoint,
           pointD1  FpPoint
        }
     
        --
        -- BB1 ciphertext block
        --
     
        BB1CiphertextBlock ::= SEQUENCE {
           pointChi0FpPoint,
           pointChi1   FpPoint,
     
     
     Boyen & Martin          Expires September 2007          [Page 69]
     

     Internet Draft                 IBCS #1                March 2007
     
     
           nu    INTEGER,
           y     OCTET STRING
        }
     
        END
     
     13. Security considerations
     
        This document describes cryptographic algorithms, for which we
        assume that the security of the algorithm relies entirely on
        the secrecy of the relevant private key, so that an adversary
        will need to intercept encrypted messages and perform
        computationally-intensive cryptanalytic attacks against the
        ciphertext that he obtains in this way to recover either
        plaintext or a secret cryptographic key.
     
        We assume that users of the algorithms described in this
        document will require one of three levels of cryptographic
        strength: the equivalent of 80 bits, the equivalent of 112
        bits, or the equivalent of 128 bits. The 80-bit level is
        suitable for legacy applications and SHOULD not be used to
        protect information whose useful life extends past the year
        2010. The 112-bit level is suitable for use in key transport
        of Triple-DES keys and should be adequate to protect
        information whose useful life extends up to the year 2030. The
        128-bit level is suitable for use in key transport of 128-bit
        AES keys.
     
        The following table describes the security parameters for the
        BF and BB1 algorithms that will attain 80-bit, 112-bit and
        128-bit levels of security. In this table, |p| represents the
        number of bits in a prime number p and |q| represents the
        number of bits in a subprime q. This table assumes that a
        Type-1 supersingular curve is used.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 70]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Bits of Security   |p|    |q|
        80                 512    160
        112                1024   224
        128                1536   256
     
        Note that this document specifies the use of the SHA1 hashing
        algorithm [SHA] to hash identities to either a point on an
        elliptic curve or an integer. Recent attacks on SHA1 have
        discovered ways to find collisions in SHA1 with much less work
        that the 80 bits of strength in resistance to collisions that
        we would expect for a hashing algorithm that creates a 160-bit
        digest. If we can find a collision in SHA1 we could use the
        colliding preimages to create two identities which have the
        same IBE private key. The practical use of such a SHA1
        collision is extremely unlikely, particularly if IBE is used
        as described in [IBECMS], in which components of an identity
        are defined to be either a time or a URI. Any protocol using
        IBE SHOULD define part of an identity to avoid the possible
        use of collisions in SHA1 in this way.
     
     
     14. IANA considerations
     
        All of the OIDs used in this document were assigned by the
        National Institute of Standards and Technology (NIST), so no
        further action by the IANA is necessary for this document.
     
     15. Acknowledgments
     
        This document is based on the IBCS #1 v2 document of Voltage
        Security, Inc. Any substantial use of material from this
        document should acknowledge Voltage Security, Inc. as the
        source of the information.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 71]
     

     Internet Draft                 IBCS #1                March 2007
     
     
     16. References
     
     16.1. Normative references
     
        [DER] ITU-T Recommendation X.690 (2002) | ISO/IEC 8825-1:2002,
        Information technology - ASN.1 encoding rules: Specification
        of Basic Encoding Rules (BER), Canonical Encoding Rules (CER)
        and Distinguished Encoding Rules (DER).
     
        [IBECMS] L. Martin, M. Schertler, "Using the Boneh-Franklin
        identity-based encryption algorithm with the Cryptographic
        Message Syntax (CMS)," draft-ietf-smime-bfibecms-01.txt,
        September 2006.
     
        [KEYWORDS] S. Bradner, "Key words for use in RFCs to Indicate
        Requirement Levels", BCP 14, RFC 2119, March 1997.
     
        [SHA] Federal Information Processing Standards Publication
       (FIPS PUB)180-2, "Secure Hash Standard," August 2002.
     
     16.2. Informative references
     
        [BB1] D. Boneh, X. Boyen, "Efficient selective-ID secure
        identity based encryption without random oracles," In Proc. of
        EUROCRYPT 04, LNCS 3027, pp. 223-238, 2004.
     
        [BF] D. Boneh, M. Franklin, "Identity-based encryption from
        the Weil pairing," In Proc. of CRYPTO 01, LNCS 2139, pp. 213-
        229, 2001.
     
        [ECC] I. Blake, G. Seroussi, N. Smart, Elliptic Curves in
        Cryptography, Cambridge University Press, 1999.
     
     Authors' Addresses
     
        Xavier Boyen
        Voltage Security
        1070 Arastradero Rd Suite 100
        Palo Alto, CA 94304
     
        Email: xavier@voltage.com
     
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 72]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        Luther Martin
        Voltage Security
        1070 Arastradero Rd Suite 100
        Palo Alto, CA 94304
     
        Email: martin@voltage.com
     
     
     Intellectual Property Statement
     
        The IETF takes no position regarding the validity or scope of
        any Intellectual Property Rights or other rights that might be
        claimed to pertain to the implementation or use of the
        technology described in this document or the extent to which
        any license under such rights might or might not be available;
        nor does it represent that it has made any independent effort
        to identify any such rights.  Information on the procedures
        with respect to rights in RFC documents can be found in BCP 78
        and BCP 79.
     
        Copies of IPR disclosures made to the IETF Secretariat and any
        assurances of licenses to be made available, or the result of
        an attempt made to obtain a general license or permission for
        the use of such proprietary rights by implementers or users of
        this specification can be obtained from the IETF on-line IPR
        repository at http://www.ietf.org/ipr.
     
        The IETF invites any interested party to bring to its
        attention any copyrights, patents or patent applications, or
        other proprietary rights that may cover technology that may be
        required to implement this standard.  Please address the
        information to the IETF at ietf-ipr@ietf.org.
     
     Disclaimer of Validity
     
     This document and the information contained herein are provided
     on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
     REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY,
     THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM
     ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO
     ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT
     INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY
     OR FITNESS FOR A PARTICULAR PURPOSE.
     
     Copyright Statement
     
        Copyright (C) The IETF Trust (2007).
     
     
     Boyen & Martin          Expires September 2007          [Page 73]
     

     Internet Draft                 IBCS #1                March 2007
     
     
        This document is subject to the rights, licenses and
        restrictions contained in BCP 78, and except as set forth
        therein, the authors retain all their rights.
     
     Acknowledgment
     
        Funding for the RFC Editor function is currently provided by
        the Internet Society.
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     Boyen & Martin          Expires September 2007          [Page 74]
     

Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/