Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems
RFC 5091

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 07

Network Working Group                                           X. Boyen
Request for Comments: 5091                                     L. Martin
Category: Informational                                 Voltage Security
                                                           December 2007

            Identity-Based Cryptography Standard (IBCS) #1:
  Supersingular Curve Implementations of the BF and BB1 Cryptosystems

Status of This Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

IESG Note

   This document specifies two mathematical algorithms for identity
   based encryption (IBE).  Due to its specialized nature, this document
   experienced limited review within the IETF.  Readers of this RFC
   should carefully evaluate its value for implementation and
   deployment.

Abstract

   This document describes the algorithms that implement Boneh-Franklin
   (BF) and Boneh-Boyen (BB1) Identity-based Encryption.  This document
   is in part based on IBCS #1 v2 of Voltage Security's Identity-based
   Cryptography Standards (IBCS) documents, from which some irrelevant
   sections have been removed to create the content of this document.

Boyen & Martin               Informational                      [Page 1]
RFC 5091                        IBCS #1                    December 2007

Table of Contents

   1. Introduction ....................................................4
      1.1. Sending a Message That Is Encrypted Using IBE ..............5
           1.1.1. Sender Obtains Recipient's Public Parameters ........6
           1.1.2. Construct and Send an IBE-Encrypted Message .........6
      1.2. Receiving and Viewing an IBE-Encrypted Message .............7
           1.2.1. Recipient Obtains Public Parameters from PPS ........8
           1.2.2. Recipient Obtains IBE Private Key from PKG ..........8
           1.2.3. Recipient Decrypts IBE-Encrypted Message ............9
   2. Notation and Definitions ........................................9
      2.1. Notation ...................................................9
      2.2. Definitions ...............................................12
   3. Basic Elliptic Curve Algorithms ................................12
      3.1. The Group Action in Affine Coordinates ....................13
           3.1.1. Implementation for Type-1 Curves ...................13
      3.2. Point Multiplication ......................................14
      3.3. Operations in Jacobian Projective Coordinates .............17
           3.3.1. Implementation for Type-1 Curves ...................17
      3.4. Divisors on Elliptic Curves ...............................19
           3.4.1. Implementation in F_p^2 for Type-1 Curves ..........19
      3.5. The Tate Pairing ..........................................21
           3.5.1. Tate Pairing Calculation ...........................21
           3.5.2. The Miller Algorithm for Type-1 Curves .............21
   4. Supporting Algorithms ..........................................24
      4.1. Integer Range Hashing .....................................24
           4.1.1. Hashing to an Integer Range ........................24
      4.2. Pseudo-Random Byte Generation by Hashing ..................25
           4.2.1. Keyed Pseudo-Random Bytes Generator ................25
      4.3. Canonical Encodings of Extension Field Elements ...........26
           4.3.1. Encoding an Extension Element as a String ..........26
           4.3.2. Type-1 Curve Implementation ........................27
      4.4. Hashing onto a Subgroup of an Elliptic Curve ..............28
           4.4.1. Hashing a String onto a Subgroup of an
                  Elliptic Curve .....................................28
           4.4.2. Type-1 Curve Implementation ........................29
      4.5. Bilinear Mapping ..........................................29
           4.5.1. Regular or Modified Tate Pairing ...................29
           4.5.2. Type-1 Curve Implementation ........................30
      4.6. Ratio of Bilinear Pairings ................................31
           4.6.1. Ratio of Regular or Modified Tate Pairings .........31
           4.6.2. Type-1 Curve Implementation ........................32
   5. The Boneh-Franklin BF Cryptosystem .............................32
      5.1. Setup .....................................................32
           5.1.1. Master Secret and Public Parameter Generation ......32
           5.1.2. Type-1 Curve Implementation ........................33
      5.2. Public Key Derivation .....................................34

Boyen & Martin               Informational                      [Page 2]
RFC 5091                        IBCS #1                    December 2007

           5.2.1. Public Key Derivation from an Identity and
                  Public Parameters ..................................34