RFC 5091
Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems
RFC 5091: Identity-Based Cryptography Standard (IBCS) #1 💖
Okay bestie, this one is RFC 5091 ✨ The full title is Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems. X. Boyen and L. Martin wrote it, both from Voltage Security 🎀 It's in the Network Working Group stream, it's Informational (so not a standard 🙈), and it's dated December 2007. The title block doesn't list anything it obsoletes or updates, so it's standing all on its own 🦋
Status of This Memo
Quick vibe check: this memo is just info for the Internet community. It does not specify an Internet standard of any kind 💅 Distribution is unlimited, so share it with everyone you know 🌸
IESG Note
The IESG wants you to know that this document specifies two mathematical algorithms for identity based encryption (IBE) 🧚 Because it's pretty specialized, it only got limited review inside the IETF. So readers should carefully evaluate whether it's actually worth implementing and deploying. Do your homework first, babe 📚
Abstract
So this doc describes the algorithms behind Boneh-Franklin (BF) and Boneh-Boyen (BB1) Identity-based Encryption 🔐 It's partly based on IBCS #1 v2 from Voltage Security's Identity-based Cryptography Standards (IBCS) documents, but some irrelevant sections were cut out to make this one 💜
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
5.2.1. Public Key Derivation from an Identity and
Public Parameters ..................................34
5.3. Private Key Extraction ....................................35
5.3.1. Private Key Extraction from an Identity, a
Set of Public ......................................35
5.4. Encryption ................................................36
5.4.1. Encrypt a Session Key Using an Identity and
Public Parameters ..................................36
5.5. Decryption ................................................37
5.5.1. Decrypt an Encrypted Session Key Using
Public Parameters, a Private Key ...................37
6. The Boneh-Boyen BB1 Cryptosystem ...............................38
6.1. Setup .....................................................38
6.1.1. Generate a Master Secret and Public Parameters .....38
6.1.2. Type-1 Curve Implementation ........................39
6.2. Public Key Derivation .....................................41
6.2.1. Derive a Public Key from an Identity and
Public Parameters ..................................41
6.3. Private Key Extraction ....................................41
6.3.1. Extract a Private Key from an Identity,
Public Parameters and a Master Secret ..............41
6.4. Encryption ................................................42
6.4.1. Encrypt a Session Key Using an Identity and
Public Parameters ..................................42
6.5. Decryption ................................................45
6.5.1. Decrypt Using Public Parameters and Private Key ....45
7. Test Data ......................................................47
7.1. Algorithm 3.2.2 (PointMultiply) ...........................47
7.2. Algorithm 4.1.1 (HashToRange) .............................48
7.3. Algorithm 4.5.1 (Pairing) .................................48
7.4. Algorithm 5.2.1 (BFderivePubl) ............................49
7.5. Algorithm 5.3.1 (BFextractPriv) ...........................49
7.6. Algorithm 5.4.1 (BFencrypt) ...............................50
7.7. Algorithm 6.3.1 (BBextractPriv) ...........................51
7.8. Algorithm 6.4.1 (BBencrypt) ...............................52
8. ASN.1 Module ...................................................53
9. Security Considerations ........................................58
10. Acknowledgments ...............................................60
11. References ....................................................60
11.1. Normative References .....................................60
11.2. Informative References ...................................601. Introduction ✨
Okay, so this doc gives you a set of specs for building identity-based encryption (IBE) systems that run on bilinear pairings 🦋 Two cryptosystems get covered: the IBE system from Boneh and Franklin (BF) [BF], and the one from Boneh and Boyen (BB1) [BB1]. Both come with fully secure, practical implementations, including the core IBE algorithms plus some extra hybrid pieces that protect against active attacks 🛡️ These specs are limited to a family of supersingular elliptic curves over finite fields of large prime characteristic, which the doc calls "type-1" curves (see Section 2.1). Anything built on other kinds of curves is currently out of scope, so don't go looking for it here 🙈
IBE is a public-key tech, but it's a little different from the rest in a way that matters a lot 💜 The keys get calculated instead of being generated randomly, and that makes a system built on IBE look really different architecturally from one built on other public-key tech. If you want the full tea on how these differences work and how an IBE system runs, check out [IBEARCH] 📚
Identity-based encryption (IBE) is a public-key encryption tech where the public key can be calculated from an identity, and the matching private key can be calculated from the public key 🔑 Both keys can be worked out whenever they're needed, so you get just-in-time key material ⏰ That's different from other public-key systems [P1363], where keys get generated randomly and handed out before secure chatting starts. Being able to calculate someone's public key is the big win here, because the sender and receiver in an IBE messaging system don't need to talk to each other first, whether directly or through something like a directory server 🫶
This doc describes an IBE-based messaging system and how its parts work together. A complete IBE messaging system needs the following components:
- a Private-key Generator (PKG). The PKG holds the cryptographic material, known as a master secret, that's used to generate an individual's IBE private key. A PKG takes an IBE user's private key request and, after authenticating them successfully in some way, returns the IBE private key 🗝️
- a Public Parameter Server (PPS). IBE System Parameters include publicly sharable cryptographic material, known as IBE public parameters, plus policy info for the PKG. A PPS gives you a well-known spot for securely distributing the IBE public parameters and the policy info for the IBE PKG 🌈
A logical setup would be one PKG/PPS per name space, like a DNS zone 🍓 The organization that controls the DNS zone would also control the PKG/PSS, which means it decides which PKG/PSS gets used when making public and private keys for its members. In this case, the PPS URI can be uniquely created from the form of the identity it supports. This setup makes it crystal clear which set of public parameters to use, and where to fetch them for any given identity 👑
IBE-encrypted messages can use standard message formats, like the Cryptographic Message Syntax (CMS) [CMS]. How to use IBE with CMS is covered in [IBECMS] 💅
Heads up: IBE algorithms are only used for encryption. So if you need digital signatures, you'll have to get them from some other mechanism 🙈
The key words in this document are the BCP 14 terms, and they're interpreted as described in [KEYWORDS]. Here they are, verbatim: "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" 💜
1.1. Sending a Message That Is Encrypted Using IBE
okay so if you wanna send an encrypted message with IBE, there are two steps you need to nail 💌
- Get the recipient's public parameters. 🔑
The recipient's IBE public parameters are what let anyone make their unique public and private keys. Once a user has the public parameters for an IBE system, they can work out the recipient's public key on their own. After that, IBE-encrypted messages are good to go ✨
- Build and send the IBE-encrypted message. 💌
All you need besides the IBE public parameters is the recipient's identity, so you can generate their public key for encrypting. When that identity is the same one the message is addressed to, you don't need any more info to send a secure message than you'd need for an unsecured one. 🫶 Literally one of the biggest perks of an IBE-based secure messaging system. Identities can be an individual, a group, or a role identifier 🎀
1.1.1. Sender Obtains Recipient's Public Parameters
the sender grabs the IBE public parameters they need to work out the recipient's IBE public key from a PPS sitting at a well-known URI 🌸 The parameters have everything the sender needs to make an IBE-encrypted message, except for the recipient's identity. [IBEARCH] covers where the PPS lives, what the IBE public parameters look like, and how to get them.
The URI where users pick up their IBE public parameters MUST be authenticated somehow. PPS servers MUST support Transport Layer Security (TLS) 1.1 [TLS] to meet this, and MUST verify that the subject name in the server certificate matches the URI of the PPS. 🔐 [IBEARCH] also explains how identity formats get defined, plus a minimum interoperable format that all PPSs and PKGs MUST support 💅 Here's what that step looks like:
IBE Public Parameter Request
----------------------------->
Sender PPS
<-----------------------------
IBE Public Parameters
Figure 1. Requesting IBE Public ParametersThe sender picks the PPS and the matching PKG based on their own local security policy 👑 Different PPSs might hand out parameters for different IBE algorithms or different key strengths, for example. Some might also require PKGs that want different levels of authentication before they'll release IBE private keys. Main character energy in choosing your setup 🦋
1.1.2. Construct and Send an IBE-Encrypted Message
To IBE-encrypt a message, the sender picks a content encryption key (CEK) and uses it to encrypt the message. Then they encrypt that CEK with the recipient's IBE public key (for example, as described in [CMS]) 🍓 Here's the flow:
CEK ----> Sender ----> IBE-encrypted CEK
^
|
|
Recipient's Identity
and IBE Public Parameters
Figure 2. Using an IBE Public-Key Algorithm to EncryptThis document describes the algorithms you need to implement two forms of IBE 🧚 For how to use the Cryptographic Message Syntax (CMS) to wrap the encrypted message together with the IBE info the recipient needs to decrypt it, see [IBECMS] 💜
1.2. Receiving and Viewing an IBE-Encrypted Message
to read an encrypted message, the recipient parses it first (for example, as described in [IBECMS]) 📬 That gives them the URI they need to grab the IBE public parameters for the IBE calculations, plus the identity that was used to encrypt the message. Then the recipient works through these steps:
- Obtain the recipient's public parameters. 🌈
An IBE system's public parameters let it create public and private keys in a unique way. The recipient can decrypt an IBE-encrypted message as long as they have both the IBE public parameters and the right IBE private key. The PPS can also point to the URI of the PKG, which is where the recipient can get the IBE private keys 🎀
- Obtain the IBE private key from the PKG. 🗝️
To decrypt, the recipient needs the private key that matches the public key the sender used, on top of the IBE public parameters. They get it after successfully authenticating to a private key generator (PKG), which is a trusted third party that calculates private keys for users 🫧 The key comes back over an HTTPS connection. The URI of a PKG MUST be authenticated in some way, and PKG servers MUST support TLS 1.1 [TLS] to satisfy this requirement 🔒
- Decrypt the IBE-encrypted message. ✨
The IBE private key decrypts the CEK, and then the CEK decrypts the encrypted message 💫
Heads up: the PKG might let users other than the intended recipient receive some IBE private keys 👀 For example, a mail filtering appliance could be given permission to get IBE private keys on behalf of users. That lets the appliance decrypt and scan encrypted messages for viruses or other malicious stuff 🙈
1.2.1. Recipient Obtains Public Parameters from PPS
before the recipient can do any IBE math on the message they got, they need the IBE public parameters that were used for the encryption 💖 Here's how that goes:
IBE Public Parameter Request
----------------------------->
Recipient PPS
<-----------------------------
IBE Public Parameters
Figure 3. Requesting IBE Public Parameters1.2.2. Recipient Obtains IBE Private Key from PKG
to get an IBE private key, the recipient sends the IBE public key that was used to encrypt the message, along with their authentication credentials, to a PKG. Then they ask for the private key that matches that IBE public key 🔑 Section 4 of this document defines the protocol for talking to a PKG, plus a minimum interoperable way to authenticate to a PKG that all IBE implementations MUST support 🧁
IBE private keys are super important to the security of the whole IBE system, so they MUST be sent to recipients over a secure protocol. PKGs MUST support TLS 1.1 [TLS] for transporting IBE private keys 🛡️ Here's the exchange:
IBE Private Key Request
---------------------------->
Recipient PKG
<----------------------------
IBE Private Key
Figure 4. Obtaining an IBE Private Key1.2.3. Recipient Decrypts IBE-Encrypted Message
once the recipient has the right IBE private key, they use it together with the matching IBE public parameters to decrypt the CEK 💅 Then they use that CEK to decrypt the encrypted message content (for example, as specified in [IBECMS]) 🦋
IBE-encrypted CEK ----> Recipient ----> CEK
^
|
|
IBE Private Key
and IBE Public Parameters
Figure 5. Using an IBE Public-Key Algorithm to Decrypt2. Notation and Definitions ✨
2.1. Notation ✨
Okay bestie, this section is the math part, and I'm obsessed. It sums up the notions and definitions for identity-based cryptosystems on elliptic curves 🦋 For the mathy background, go read [ECC]. For everything about identity-based encryption, check [BF] and [IBEARCH].
F_p is a finite field of prime characteristic p, and F_p^2 is its extension field of degree 2 💖
Next, E/F_p: y^2 = x^3 + a * x + b is an elliptic curve over F_p. For the degree 2 extension, E/F_p defines a group (E(F_p^2), +). That's the additive group of points with affine coordinates (x, y) in (F_p^2)^2 that satisfy the curve equation over F_p^2. Its null element, the point at infinity, is written 0 ✨
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 let G2 be a cyclic subgroup of (F_p^2)* of order p. 🌸
Under these conditions, the Tate pairing gives an efficiently computable map e: G1' x G1'' -> G2. It's linear in both arguments and believed hard to invert [BF]. If an efficiently computable non-rational endomorphism phi: G1' -> G1'' is available for the chosen curve, then we can build e'(A, B) = e(A, phi(B)), called the modified Tate pairing. We generically call either one a "pairing," depending on the curve used in a given implementation 💅
Here's the extra notation used throughout this document:
p- A 512-bit to 7680-bit prime, the order of the finite fieldF_p.F_p- The base finite field of orderpthat the curveE/F_pis defined over.#G- The size of the setG.F*- The multiplicative group of the nonzero elements in the fieldF. For example,(F_p)*is the multiplicative group of the finite fieldF_p.E/F_p- The equation of an elliptic curve overF_p. Whenpis neither 2 nor 3, it has the formE/F_p: y^2 = x^3 + a * x + b, for specifieda,binF_p.0- The 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), withx,yinF_p, that satisfy the curve equationE/F_p, including the point at infinity0.q- A 160-bit to 512-bit prime that is the order of the cyclic subgroup of interest inE(F_p).k- The embedding degree of the cyclic subgroup of orderqinE(F_p). For type-1 curves, this is always equal to 2.F_p^2- The extension field of degree 2 of the fieldF_p.E(F_p^2)- The group of points of affine coordinates inF_p^2satisfying the curve equationE/F_p, including the point at infinity0.Z_p- The additive group of integers modulop.lg- The base 2 logarithm function, so that2^lg(x) = x.
The term "object identifier" will be shortened to "OID" 🙈 A Solinas prime is a prime of the form 2^a (+/-) 2^b (+/-) 1.
For curve operations, these are the conventions we assume:
- Point addition: If
AandBare two points on a curveE, their sum is writtenA + B. - Point multiplication: If
Ais a point on a curve andnis an integer, the result of addingAto itself a total ofntimes is written[n]A.
Now the curve class we're focusing on for pairings in this version of the document. These are called "type-1" curves, and they're the only ones considered here 🫶
- Type-1 curves: This is the class of all elliptic curves with equation
E/F_p: y^2 = x^3 + 1for all primespcongruent to 11 modulo 12. It's a subclass of the supersingular curves. These curves satisfy#E(F_p) = p + 1, and theppoints(x, y)inE(F_p) \ {0}have the property thatx = (y^2 - 1)^(1/3) (mod p). Type-1 curves always have an embedding degreek = 2.
Type-1 groups are plentiful and easy to build by randomly picking a prime p of the right form. So instead of standardizing on a small set of common values of p, we assume that every type-1 curve gets freshly generated at random for its cryptographic application. You can see an example of that generation in Algorithm 5.1.2 (BFsetup1) or Algorithm 6.1.2 (BBsetup1). Implementations based on other classes of curves are currently unsupported 😭
Here's how we represent the math objects:
- Base field elements: The
pelements of the base fieldF_pare represented directly using the integers from 0 top - 1. - Extension field elements: The
p^2elements of the extension fieldF_p^2are represented as ordered pairs of elements ofF_p. An ordered pair(a_0, a_1)is read as the complex numbera_0 + a_1 * i, wherei^2 = -1. That lets us do operations onF_p^2elements like this. Saya = (a_0, a_1)andb = (b_0, b_1)are elements ofF_p^2. Then:
a + b = ((a_0 + b_0)(mod p), (a_1 + b_1)(mod p))
a * b = ((a_1 * b_1 - a_0 * b_0)(mod p), (a_1 * b_0 + a_0 * b_1)(mod p))- Elliptic curve points: Points in
E(F_p^2)areP = (x, y)inF_p^2 x F_p^2that satisfy the curve equationE/F_p. Points not equal to0are stored internally using affine coordinates(x, y), wherexandyare elements ofF_p^2.
2.2. Definitions 🎀
Here's the terminology we use to describe an IBE system. These are the words you'll see all over the place, so get comfy with them 🌈
- Public parameters: A set of common, system-wide parameters generated and published by the private key generator (PKG).
- Master secret: The master key generated and kept private by the key server, which is used to generate the private keys of the users.
- 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 string that is algorithmically derived from an identity. Anyone can do the derivation, autonomously.
- Private key: A private key is issued by the key server to correspond to a given identity (and the public key derived from it) under the published set of public parameters.
- Plaintext: An unencrypted representation, or "in the clear," of any block of data to be transmitted securely. For our purposes, plaintexts are typically session keys, or sets of session keys, for further symmetric encryption and authentication 🧚
- Ciphertext: An encrypted representation of any block of data, including plaintext, to be transmitted securely.
3. Basic Elliptic Curve Algorithms ✨
This section has the algorithms for all the basic arithmetic operations on elliptic curves. It's tailored to the type of curves we're looking at, which keeps implementation simple. If you want the general algorithms, check [ECC] 💜
3.1. The Group Action in Affine Coordinates
3.1.1. Implementation for Type-1 Curves
Here's the doubling algorithm for type-1 curves, which adds a point to itself 💅
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')Next up is the addition algorithm for two points on a type-1 curve 🦋
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
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 3.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
Now the big one: point multiplication, which is basically how we multiply a point by a scalar efficiently 🔥 It starts with a window decomposition step.
Algorithm 3.2.1 (SignedWindowDecomposition): computes the signed
m-ary window representation of a positive integer [ECC].
Input:
o An integer k > 0, where k has the binary representation k =
{Sum(k_j * 2^j, for j = 0 to l} where each k_j is either 0 or 1
and k_l = 0
o An integer window bit-size r > 0
Output:
o An integer d and the unique d-element sequence {(b_i, e_i), for i
= 0 to d - 1} such that k = {Sum(b_i * 2^(e_i), for i = 0 to d -
1}, each b_i = +/- 2^j for some 0 < j <= r - 1 and each e_i is a
non-negative integer
Method:
1. Let d = 0
2. Let j = 0
3. While j <= l, do:
(a) If k_j = 0, then:
i. Let j = j + 1
(b) Else:
i. Let t = min{l, j + r - 1}
ii. Let h_d = (k_t, k_(t - 1), ..., k_j) (base 2)
iii. If h_d > 2^(r - 1), then:
A. Let b_d = h_d - 2^r
B. Increment the number (k_l, k_(l-1),...,k_j) (base 2) by 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))}With that in hand, here's the scalar multiplication algorithm itself. It uses the signed m-ary window method 🌸
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
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)
(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 ✨
okay bestie, now we're doubling points in Jacobian projective coordinates 💅 type-1 curves get their own version, and it's giving pure precision 🦋
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.
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), 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')3.4. Divisors on Elliptic Curves 🌸
3.4.1. Implementation in F_p^2 for Type-1 Curves
these are the divisor helpers 🧚 they evaluate vertical lines, tangents, and lines on a type-1 curve, all at a point B in E(F_p^2) 💖
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 3.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
(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)
(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 r3.5. The Tate Pairing 🔥
3.5.1. Tate Pairing Calculation
the Tate pairing is the main event 👑 this top-level algorithm just hands the work off to the Miller algorithm for type-1 curves
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 a type-1 curve E, execute Algorithm 3.5.2 (TateMillerSolinas)3.5.2. The Miller Algorithm for Type-1 Curves
and now the real glow-up 🦋 this is the Miller algorithm, and it's big, so take a breath bestie 😭
Algorithm 3.5.2 (TateMillerSolinas): computes the Tate pairing on a
type-1 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 a type-1 supersingular elliptic curve E/F_p such
that E(F_p) and E(F_p^2) have a subgroup of Solinas prime order q
where q = 2^a + s * 2^b + c, where c and s are limited to the
values +/-1
Output:
o The value e(A, B) in F_p^2, computed using the Miller algorithm
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:
i. Let t_num = t_num^2
ii. Let t_den = t_den^2
iii. Let t_num = t_num * EvalTangent1(B, (x_V / z_V^2, y_V /
z_V^3)) 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, (x_V / z_V^2, y_V /
z_V^3)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, (x_V /
z_V^2, y_V / z_V^3))) 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, (x_V / z_V^2, y_V /
z_V^3))) 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, (x_V / z_V^2, y_V /
z_V^3))) 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
6. (Final result)
(a) Return (v_num / v_den)^eta4. Supporting Algorithms 🧚
this section is all about hashing and encoding 🍓 the stuff that turns strings into numbers and bytes, and keeps everything canonical
4.1. Integer Range Hashing
4.1.1. Hashing to an Integer Range
so HashToRange takes a string, an integer n, and a cryptographic hash function, and gives you back an integer from 0 to n - 1 🎀 the input n MUST be less than 2^(hashlen), where hashlen is how many octets the hash output has. it's based on Merkle's method [MERKLE], which is provably as secure as the hash underneath it, so no cap, it's solid 🔐
Algorithm 4.1.1 (HashToRange): cryptographically hashes strings to
integers in a range.
Input:
o A string s of length |s| octets
o A positive integer n represented as Ceiling(lg(n) / 8) octets.
o A cryptographic hash function hashfcn
Output:
o A positive integer v in the range 0 to n - 1
Method:
1. Let hashlen be the number of octets comprising the output of
hashfcn
2. Let v_0 = 0
3. Let h_0 = 0x00...00, a string of null octets with a length of
hashlen
4. For i = 1 to 2, do:
(a) Let t_i = h_(i - 1) || s, which is the (|s| + hashlen)- octet
string concatenation of the strings h_(i - 1) and s
(b) Let h_i = hashfcn(t_i), which is a hashlen-octet string
resulting from the hash algorithm hashfcn on the input t_i
(c) Let a_i = Value(h_i) be the integer in the range 0 to
256^hashlen - 1 denoted by the raw octet string h_i
interpreted in the unsigned big-endian convention
(d) Let v_i = 256^hashlen * v_(i - 1) + a_i
5. Let v = v_l (mod n)4.2. Pseudo-Random Byte Generation by Hashing 🌈
4.2.1. Keyed Pseudo-Random Bytes Generator
HashBytes takes an integer b, a string p, and a cryptographic hash function, and spits out a b-octet pseudo-random string r 🦋 the value of b MUST be less than or equal to the number of bytes in the output of hashfcn. like HashToRange, it's based on Merkle's method [MERKLE], so it's provably as secure as the hash function under it 💜
Algorithm 4.2.1 (HashBytes): keyed cryptographic pseudo-random bytes
generator.
Input:
o An integer b
o A string p
o A cryptographic hash function hashfcn
Output:
o A string r comprising b octets
Method:
1. Let hashlen be the number of octets comprising the output of
hashfcn
2. Let K = hashfcn(p)
3. Let h_0 = 0x00...00, a string of null octets with a length of
hashlen
4. Let l = Ceiling(b / hashlen)
5. For each i in 1 to l, do:
(a) Let h_i = hashfcn(h_(i - 1))
(b) Let r_i = hashfcn(h_i || K), where h_i || K is the (2 *
hashlen)-octet concatenation of h_i and K
6. Let r = LeftmostOctets(b, r_1 || ... || r_l), i.e., r is formed as
the concatenation of the r_i, truncated to the desired number of
octets4.3. Canonical Encodings of Extension Field Elements 💅
4.3.1. Encoding an Extension Element as a String
Canonical takes an element v in F_p^k and returns a canonical octet string of fixed length that represents it 🎀 the parameter o MUST be either 0 or 1, and it picks the ordering of the encoding. the algorithm below handles F_p^2 elements, and for type-1 curves it just hands the job to Canonical1 ✨
Canonical(p, k, o, v) takes an element v in F_p^k, and returns a
canonical octet 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^2
o A description of F_p^2
o An 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.2. Type-1 Curve Implementation ✨
okay so Canonical1(p, o, v) takes an element v in F_p^2 and spits out a canonical octet string s of fixed size 💅 the parameter o MUST be either 0 or 1, and it picks the ordering of the encoding 🦋
Algorithm 4.3.2 (Canonical1): canonically represents elements of an extension field F_p^2 🌸
Input:
- An element v in F_p^2
- A description of p, where p is congruent to 3 modulo 4
- A ordering parameter o, either 0 or 1
Output:
- A string s of size 2 * Ceiling(lg(p) / 8) octets
Method:
- Let l = Ceiling(lg(p) / 8), the number of octets needed to represent integers in Z_p
- Let v = a + b * i, where i^2 = -1
- Let a_(256^l) be the big-endian zero-padded fixed-length octet string representation of a in Z_p
- Let b_(256^l) be the big-endian zero-padded fixed-length octet string representation of b in Z_p
- 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)
- Return s
4.4. Hashing onto a Subgroup of an Elliptic Curve 🧚
4.4.1. Hashing a String onto a Subgroup of an Elliptic Curve
okay this is the HashToPoint(E, p, q, id, hashfcn) vibe 💖 it takes an identity string id, the description of a subgroup of prime order q in E(F_p) or E(F_p^2), and a cryptographic hash function hashfcn, and it gives back 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:
- An elliptic curve E
- A prime p
- A prime q
- A string id
- A cryptographic hash function hashfcn
Output:
- A point Q_id = (x, y) of order q n E(F_p)
Method:
- For a type-1 curve E, execute Algorithm 4.4.2 (HashToPoint1)
4.4.2. Type-1 Curve Implementation
HashToPoint1(p, q, id, hashfcn) 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. It returns a point Q_id of order q in E(F_p) that gets calculated using the cryptographic hash function hashfcn. The parameters p, q and hashfcn MUST be part of a valid set of public parameters as defined in Section 5.1.2 or Section 6.1.2 🫶
Algorithm 4.4.2 (HashToPoint1): cryptographically hashes strings to points on type-1 curves 🌈
Input:
- A prime p
- A prime q
- A string id
- A cryptographic hash function hashfcn
Output:
- A point Q_id of order q in E(F_p)
Method:
- Let y = HashToRange(id, p, hashfcn), using Algorithm 4.1.1 (HashToRange), an element of F_p
- Let x = (y^2 - 1)^((2 * p - 1) / 3) modulo p, an element of F_p
- Let Q' = (x, y), a non-zero point in E(F_p)
- Let Q = [(p + 1) / q ]Q', a point of order q in E(F_p)
4.5. Bilinear Mapping 🦋
4.5.1. Regular or Modified Tate Pairing
Pairing(E, p, q, A, B) takes two points A and B, both of order q. In the type-1 case, it 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:
- 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
- Two points A and B of order q in E(F_p) or E(F_p^2)
Output:
- On supersingular curves, the value of e'(A, B) in F_p^2 where A and B are both in E(F_p)
Method:
- If E is a type-1 curve, execute Algorithm 4.5.2 (Pairing1)
4.5.2. Type-1 Curve Implementation
Algorithm 4.5.2 (Pairing1): computes the modified Tate pairing on type-1 curves. The values of p and q MUST be part of a valid set of public parameters as defined in Section 5.1.2 or Section 6.1.2 🎀
Input:
- 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
- Two points A and B of order q in E(F_p)
Output:
- The value of e'(A, B) = e(A, phi(B)) in F_p^2
Method:
- 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 = (a_zeta , b_zeta), where a_zeta = (p - 1) / 2 and b_zeta = 3^((p + 1) / 4) (mod p), an element of F_p^2
- (c) Let x' = x * zeta in F_p^2
- (d) Let B' = (x', y) in F_p^2 x F_p
- 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 🌸
4.6.1. Ratio of Regular or Modified Tate 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 here is that the ratio of two pairings can be calculated more efficiently than computing each pairing separately and dividing one into the other. Certain calculations that would normally show up 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:
- 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
- Four points A, B, C, and D, of order q in E(F_p) or E(F_p^2)
Output:
- 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:
- If E is a type-1 curve, execute Algorithm 4.6.2 (PairingRatio1)
4.6.2. Type-1 Curve Implementation
Algorithm 4.6.2 (PairingRatio1): computes the ratio of two modified Tate pairings on type-1 curves. The values of p and q MUST be part of a valid set of public parameters as defined in Section 5.1.2 or Section 6.1.2 🙈
Input:
- 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
- Four points A, B, C, and D of order q in E(F_p)
Output:
- 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:
- The step-by-step description of the optimized algorithm is omitted in this normative specification
The correct result can always be obtained, although 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 walks through the algorithms that make up the Boneh-Franklin identity-based cryptosystem, as described in [BF] 🌈
5.1. Setup
5.1.1. Master Secret and Public Parameter Generation
Algorithm 5.1.1 (BFsetup): randomly selects a master secret and the associated public parameters 💖
Input:
- An integer version number
- A security parameter n (MUST take values either 1024, 2048, 3072, 7680, 15360)
Output:
- A set of public parameters (version, E, p, q, P, P_pub, hashfcn)
- A corresponding master secret s
Method:
- Depending on the selected type t:
- (a) If version = 2, then execute Algorithm 5.1.2 (BFsetup1)
- The resulting master secret and public parameters are separately encoded as per the application protocol requirements
5.1.2. 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 [BF] of comparable security in the classical Diffie-Hellman or RSA public-key cryptosystems 🦋
Algorithm 5.1.2 (BFsetup1): establishes a master secret and public parameters for type-1 curves ✨
Input:
- A security parameter n, which MUST be either 1024, 2048, 3072, 7680 or 15360
Output:
- A set of common public parameters (version, p, q, P, Ppub, hashfcn)
- A corresponding master secret s
Method:
- Set the version to version = 2.
- Determine the subordinate security parameters n_p and n_q as follows:
- (a) If n = 1024, then let n_p = 512, n_q = 160, hashfcn = 1.3.14.3.2.26 (SHA-1 [SHA]
- (b) If n = 2048, then let n_p = 1024, n_q = 224, hashfcn = 2.16.840.1.101.3.4.2.4 (SHA-224 [SHA])
- (c) If n = 3072, then let n_p = 1536, n_q = 256, hashfcn = 2.16.840.1.101.3.4.2.1 (SHA-256 [SHA])
- (d) If n = 7680, then let n_p = 3840, n_q = 384, hashfcn = 2.16.840.1.101.3.4.2.2 (SHA-384 [SHA])
- (e) If n = 15360, then let n_p = 7680, n_q = 512, hashfcn = 2.16.840.1.101.3.4.2.3 (SHA-512 [SHA])
- Construct the elliptic curve and its subgroup of interest, as follows:
- (a) Select an arbitrary n_q-bit Solinas prime q
- (b) Select a random integer r such that p = 12 * r * q - 1 is an n_p-bit prime
- 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
- 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
- (version, E, p, q, P, P_pub) are the public parameters where E: y^2 = x^3 + 1 is represented by the OID 2.16.840.1.114334.1.1.1.1.
- The integer s is the master secret
5.2. Public Key Derivation 🌸
5.2.1. Public Key Derivation from an Identity and Public Parameters
BFderivePubl takes an identity string id and a set of public parameters, and it returns a point Q_id. The public parameters used MUST be a valid set of public parameters as defined by Section 5.1.2 🍓
Algorithm 5.2.1 (BFderivePubl): derives the public key corresponding to an identity string 🧚
Input:
- An identity string id
- A set of public parameters (version, E, p, q, P, P_pub, hashfcn)
Output:
- A point Q_id of order q in E(F_p) or E(F_p^2)
Method:
- Q_id = HashToPoint(E, p, q, id, hashfcn), using Algorithm 4.4.1 (HashToPoint)
5.3. Private Key Extraction 🔑
5.3.1. Private Key Extraction from an Identity, a Set of Public Parameters and a Master Secret
BFextractPriv takes an identity string id, a set of public parameters, and corresponding master secret, and it returns a point S_id. The public parameters used MUST be a valid set of public parameters as defined by Section 5.1.2 💜
Algorithm 5.3.1 (BFextractPriv): extracts the private key corresponding to an identity string 👑
Input:
- An identity string id
- A set of public parameters (version, E, p, q, P, P_pub, hashfcn)
Output:
- A point S_id of order q in E(F_p)
Method:
- Let Q_id = HashToPoint(E, p, q, id, hashfcn) using Algorithm 4.4.1 (HashToPoint)
- Let S_id = [s]Q_id
5.4. Encryption ✨
5.4.1. Encrypt a Session Key Using an Identity and Public Parameters ✨
okay so BFencrypt 💖 takes three things: a public parameter block, an identity id, and a plaintext m. The plaintext MUST be a random symmetric session key 🔑, so no hand-picked vibes here. The public parameters you use MUST be a valid set, as defined in Section 5.1.2 🎀
Algorithm 5.4.1 (BFencrypt) 🦋 is the one that encrypts a random session key for an identity string. Here's how the whole thing goes:
Input:
- A plaintext string
mof size|m|octets - A recipient identity string
id - A set of public parameters (
version,E,p,q,P,P_pub,hashfcn)
Output:
- A ciphertext tuple
(U, V, W)inE(F_p) x {0, ... , 255}^hashlen x {0, ... , 255}^|m|
Method:
- Let
hashlenbe the length of the output of the cryptographic hash functionhashfcnfrom the public parameters. Q_id = HashToPoint(E, p, q, id, hashfcn), using Algorithm 4.4.1 (HashToPoint), which results in a point of orderqinE(F_p).- Select a random
hashlen-bit vectorrho, represented as(hashlen / 8)-octet string in big-endian convention. - Let
t = hashfcn(m), ahashlen-octet string resulting from applying thehashfcnalgorithm to the inputm. - Let
l = HashToRange(rho || t, q, hashfcn), an integer in the range 0 toq - 1, resulting from applying Algorithm 4.1.1 (HashToRange) to the(2 * hashlen)-octet concatenation ofrhoandt. - Let
U = [l]P, which is a point of orderqinE(F_p). - Let
theta = Pairing(E, p, q, P_pub, Q_id), which is an element of the extension fieldF_p^2obtained using the modified Tate pairing of Algorithm 4.5.1 (Pairing). - Let
theta' = theta^l, which isthetaraised to the power oflinF_p^2. - Let
z = Canonical(p, k, 0, theta'), using Algorithm 4.3.1 (Canonical), the result of which is a canonical string representation oftheta'. - Let
w = hashfcn(z)using thehashfcnhashing algorithm, the result of which is ahashlen-octet string. - Let
V = w XOR rho, which is thehashlen-octet long bit-wise XOR ofwandrho. - Let
W = HashBytes(|m|, rho, hashfcn) XOR m, which is the bit-wise XOR ofmwith the first|m|octets of the pseudo-random bytes produced by Algorithm 4.2.1 (HashBytes) with seedrho. - The ciphertext is the triple
(U, V, W).
5.5. Decryption 🌸
5.5.1. Decrypt an Encrypted Session Key Using Public Parameters, a Private Key 🔓
BFdecrypt takes three inputs: a public parameter block, a private key block key, and a ciphertext parsed as (U', V', W'). The public parameters used MUST be a valid set of public parameters as defined by Section 5.1.2 💅
Algorithm 5.5.1 (BFdecrypt) is the decryption side 🧚. It decrypts an encrypted session key using a private key.
Input:
- A private key point
S_idof orderqinE(F_p) - A ciphertext triple
(U, V, W)inE(F_p) x {0, ... , 255}^hashlen x {0, ... , 255}* - A set of public parameters (
version,E,p,q,P,P_pub,hashfcn)
Output:
- A decrypted plaintext
m, or an invalid ciphertext flag
Method:
- Let
hashlenbe the length of the output of the hash functionhashlenmeasured in octets. - Let
theta = Pairing(E, p ,q, U, S_id)by applying the modified Tate pairing of Algorithm 4.5.1 (Pairing). - Let
z = Canonical(p, k, 0, theta)using Algorithm 4.3.1 (Canonical), the result of which is a canonical string representation oftheta. - Let
w = hashfcn(z)using thehashfcnhashing algorithm, the result of which is ahashlen-octet string. - Let
rho = w XOR V, the bit-wise XOR ofwandV. - Let
m = HashBytes(|W|, rho, hashfcn) XOR W, which is the bit-wise XOR ofmwith the first|W|octets of the pseudo-random bytes produced by Algorithm 4.2.1 (HashBytes) with seedrho. - Let
t = hashfcn(m)using thehashfcnalgorithm. - Let
l = HashToRange(rho || t, q, hashfcn)using Algorithm 4.1.1 (HashToRange) on the(2 * hashlen)-octet concatenation ofrhoandt. - Verify that
U = [l]P:- (a) If this is the case, then the decrypted plaintext
mis returned - (b) Otherwise, the ciphertext is rejected and no plaintext is returned
- (a) If this is the case, then the decrypted plaintext
6. The Boneh-Boyen BB1 Cryptosystem 🦋
This section 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]. 🌈
6.1. Setup ⭐
6.1.1. Generate a Master Secret and Public Parameters
Algorithm 6.1.1 (BBsetup) randomly selects a set of master secrets and the associated public parameters.
Input:
- An integer version number
- An integer security parameter
n(MUST take values either 1024, 2048, 3072, 7680, or 15360)
Output:
- A set of public parameters
- A corresponding master secret
Method:
- Depending on the version:
- (a) If
version = 2, then execute Algorithm 6.1.2 (BBsetup1)
- (a) If
6.1.2. Type-1 Curve Implementation 🎀
BBsetup1 takes a security parameter n as input. For type-1 curves, n corresponds to the modulus bit-size believed [BF] of comparable security in the classical Diffie-Hellman or RSA public-key cryptosystems. For this implementation, n MUST be one of 1024, 2048, 3072, 7680 or 15360, which correspond to the equivalent bit security levels of 80, 112, 128, 192 and 256 bits respectively. 💜
Algorithm 6.1.2 (BBsetup1) randomly establishes a master secret and public parameters for type-1 curves.
Input:
- A security parameter
n, either 1024, 2048, 3072, 7680, or 15360
Output:
- A set of public parameters (
version,k,E,p,q,P,P_1,P_2,P_3,v,hashfcn) - A corresponding triple of master secrets (
alpha,beta,gamma)
Method:
- Determine the subordinate security parameters
n_pandn_qas follows:- (a) If
n = 1024, then letn_p = 512,n_q = 160,hashfcn = 1.3.14.3.2.26(SHA-1 [SHA] - (b) If
n = 2048, then letn_p = 1024,n_q = 224,hashfcn = 2.16.840.1.101.3.4.2.4(SHA-224 [SHA]) - (c) If
n = 3072, then letn_p = 1536,n_q = 256,hashfcn = 2.16.840.1.101.3.4.2.1(SHA-256 [SHA]) - (d) If
n = 7680, then letn_p = 3840,n_q = 384,hashfcn = 2.16.840.1.101.3.4.2.2(SHA-384 [SHA]) - (e) If
n = 15360, then letn_p = 7680,n_q = 512,hashfcn = 2.16.840.1.101.3.4.2.3(SHA-512 [SHA])
- (a) If
- Construct the elliptic curve and its subgroup of interest as follows:
- (a) Select a random
n_q-bit Solinas primeq - (b) Select a random integer
r, such thatp = 12 * r * q - 1is ann_p-bit prime
- (a) Select a random
- Select a point
Pof orderqinE(F_p), as follows:- (a) Select a random point
P'of coordinates(x', y')on the curveE/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
- (a) Select a random point
- 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 toq - 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 fieldF_p^2obtained using the modified Tate pairing of Algorithm 4.5.1 (Pairing)
- (a) Select three random integers
- (
version,E,p,q,P,P_1,P_2,P_3,v,hashfcn) are the public parameters - (
alpha,beta,gamma) constitute the master secret
6.2. Public Key Derivation 🧁
6.2.1. Derive a Public Key from an Identity and Public Parameters
Takes an identity string id and a set of public parameters and returns an integer h_id. The public parameters used MUST be a valid set of public parameters as defined by Section 6.1.2. 🍓
Algorithm 6.2.1 (BBderivePubl) derives the public key corresponding to an identity string. The public parameters used MUST be a valid set of public parameters as defined by Section 6.1.2.
Input:
- An identity string
id - A set of common public parameters (
version,k,E,p,q,P,P_1,P_2,P_3,v,hashfcn)
Output:
- An integer
h_idmoduloq
Method:
- Let
h_id = HashToRange(id, q, hashfcn), using Algorithm 4.1.1 (HashToRange)
6.3. Private Key Extraction 🔑
6.3.1. Extract a Private Key from an Identity, Public Parameters and a Master Secret 🗝️
BBextractPriv takes an identity string id, a set of public parameters, and corresponding master secrets, and it returns a private key consisting of two points D_0 and D_1. The public parameters used MUST be a valid set of public parameters as defined by Section 6.1.2. 🫶
Algorithm 6.3.1 (BBextractPriv) extracts the private key corresponding to an identity string.
Input:
- An identity string
id - A set of public parameters (
version,k,E,p,q,P,P_1,P_2,P_3,v,hashfcn)
Output:
- A pair of points (
D_0,D_1), each of which has orderqinE(F_p)
Method:
- Select a random integer
rin the range 1 toq - 1 - Calculate the point
D_0as follows:- (a) Let
hid = HashToRange(id, q, hashfcn)using Algorithm 4.1.1 (HashToRange) - (b) Let
y = alpha * beta + r * (alpha * h_id + gamma)inF_q - (c) Let
D_0 = [y]P
- (a) Let
- Calculate the point
D_1as follows:- (a) Let
D_1 = [r]P
- (a) Let
- The pair of points (
D_0,D_1) constitutes the private key forid👑
6.4. Encryption 💖
6.4.1. Encrypt a Session Key Using an Identity and Public Parameters ✨
okay bestie, BBencrypt is the encrypt function 🔐 and it takes three things: a set of public parameters, an identity id, and a plaintext m. The plaintext MUST be a random session key 🔑. The public parameters used MUST be a valid set of public parameters as defined by Section 6.1.2 💅
Algorithm 6.4.1 (BBencrypt): encrypts a session key for an identity string 🎀
Input:
- A plaintext string
mof size|m|octets - A recipient identity string
id - A set of public parameters
(version, k, E, p, q, P, P_1, P_2, P_3, v, hashfcn)
Output:
- A ciphertext tuple
(u, C_0, C_1, y)inF_q x E(F_p) x E(F_p) x {0, ... , 255}^|m|
Method:
- Select a random integer
sin the range1toq - 1🎲 - Let
w = v^s, which isvraised to the power ofsinF_p^2, the result is an element of orderqinF_p^2🦋 - Calculate the point
C_0as follows:- (a) Let
C_0 = [s]P
- (a) Let
- Calculate the point
C_1as follows:- (a) Let
_hid = HashToRange(id, q, hashfcn)using Algorithm 4.1.1 (HashToRange) - (b) Let
y = s * h_id in F_q - (c) Let
C_1 = [y]P_1 + [s]P_3
- (a) Let
- Obtain canonical string representations of certain elements 🧁:
- (a) Let
psi = Canonical(p, k, 1, w)using Algorithm 4.3.1 (Canonical), the result of which is a canonical octet string representation ofw - (b) Let
l = Ceiling(lg(p) / 8), the number of octets needed to represent integers inF_p, and represent each of theseF_pelements as a big-endian zero-padded octet string of fixed lengthl:(x_0)_(256^l)to represent the x coordinate ofC_0(y_0)_(256^l)to represent the y coordinate ofC_0(x_1)_(256^l)to represent the x coordinate ofC_1(y_1)_(256^l)to represent the y coordinate ofC_1
- (a) Let
- Encrypt the message
minto the stringyas follows 🔒:- (a) Compute an encryption key
h_0as a two-pass hash ofwvia its representationpsi:- i. Let
zeta = hashfcn(psi)using the hashing algorithmhashfcn - ii. Let
xi = hashfcn(zeta || psi)using the hashing algorithmhashfcn - iii. Let
h' = xi || zeta, the concatenation of the previous twohashfcnoutputs
- i. Let
- (b) Let
y = HashBytes(|m|, h', hashfcn) XOR m, which is the bit-wise XOR ofmwith the first|m|octets of the pseudo-random bytes produced by Algorithm 4.2.1 (HashBytes) with seedh'
- (a) Compute an encryption key
- Create the integrity check tag
uas follows ✨:- (a) Compute a 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 || psibe the concatenation ofyand the five indicated strings in the specified order - ii. Let
eta = hashfcn(sigma)using the hashing algorithmhashfcn - iii. Let
mu = hashfcn(eta || sigma)using thehashfcnhashing algorithm - iv. Let
h'' = mu || eta, the concatenation of the previous two outputs ofhashfcn
- i. Let
- (b) Build the tag
uas the encryption of the integerswith the one-time padh'':- i. Let
rho = HashToRange(h'', q, hashfcn)to get an integer inZ_q - ii. Let
u = s + rho (mod q)
- i. Let
- (a) Compute a one-time pad
- The complete ciphertext is given by the quadruple
(u, C_0, C_1, y)🎉
6.5. Decryption 🔓
6.5.1. Decrypt Using Public Parameters and Private Key
okay so BBdecrypt is the other half 🥹 it takes three inputs: a set of public parameters (version, k, E, p, q, P, P_1, P_2, P_3, v, hashfcn), a private key (D_0, D_1), and a ciphertext (u, C_0, C_1, y). It outputs a message m, or signals an error if the ciphertext is invalid for the given key 🙈 The public parameters used MUST be a valid set of public parameters as defined by Section 6.1.2 💖
Algorithm 6.5.1 (BBdecrypt): decrypts a ciphertext using public parameters and a private key 🌸
Input:
- A private key given as a pair of points
(D_0, D_1)of orderqinE(F_p) - A ciphertext quadruple
(u, C_0, C_1, y)inZ_q x E(F_p) x E(F_p) x {0, ... , 255}* - A set of public parameters
(version, k, E, p, q, P, P_1, P_2, P_3, v, hashfcn)
Output:
- A decrypted plaintext
m, or an invalid ciphertext flag
Method:
- 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) 🧮 - 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 octet string representation ofw - (b) Let
l = Ceiling(lg(p) / 8), the number of octets needed to represent integers inF_p, and represent each of theseF_pelements as a big-endian zero-padded octet string of fixed lengthl:(x_0)_(256^l)to represent the x coordinate ofC_0(y_0)_(256^l)to represent the y coordinate ofC_0(x_1)_(256^l)to represent the x coordinate ofC_1(y_1)_(256^l)to represent the y coordinate ofC_1
- (a) Let
- Decrypt the message
mfrom the stringyas follows 🔑:- (a) Compute the decryption key
h'as a dual-pass hash ofwvia its representationpsi:- i. Let
zeta = hashfcn(psi)using the hashing algorithmhashfcn - ii. Let
xi = hashfcn(zeta || psi)using the hashing algorithmhashfcn - iii. Let
h' = xi || zeta, the concatenation of the previous twohashfcnoutputs
- i. Let
- (b) Let
m = HashBytes(|y|, h', hashfcn)_XOR y, which is the bit-wise XOR ofywith the first|y|octets of the pseudo-random bytes produced by Algorithm 4.2.1 (HashBytes) with seedh'
- (a) Compute the decryption key
- Obtain the integrity check tag
uas 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 || psibe the concatenation ofyand the five indicated strings in the specified order - ii. Let
eta = hashfcn(sigma)using the hashing algorithmhashfcn - iii. Let
mu = hashfcn(eta || sigma)using the hashing algorithmhashfcn - iv. Let
h'' = mu || eta, the concatenation of the previous twohashfcnoutputs
- i. Let
- (b) Unblind the encryption randomization integer
sfrom the taguusingh'':- i. Let
rho = HashToRange(h'', q, hashfcn)to get an integer inZ_q - ii. Let
s = u - rho (mod q)
- i. Let
- (a) Recover the one-time pad
- Verify the ciphertext consistency according to the decrypted values 🕵️♀️:
- (a) Test whether the equality
w = v^sholds - (b) Test whether the equality
C_0 = [s]Pholds
- (a) Test whether the equality
- Adjudication and final output:
- (a) If either of the tests performed in step 5 fails, the ciphertext is rejected, and no decryption is output
- (b) Otherwise, i.e., when both tests performed in step 5 succeed, the decrypted message is the output
7. Test Data 🧪
the spec gives us test vectors so we can check that our code is doing the right thing 🥰 each one is copied exactly, so bring your calculator (and your patience) 💅
7.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:
[l]A = (0x073734b32a882cc97956b9f7e54a2d326,
0x9c4b891aab199741a44a5b6b632b949f7)7.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
hashfcn = 1.3.14.3.2.16 (SHA-1)
Output:
v = 0x79317c1610c1fc018e9c53d89d59c108cd5186087.3. Algorithm 4.5.1 (Pairing)
Input:
q = 0xfffffffffffffffffffffffffffbffff
p = 0xbffffffffffffffffffffffffffcffff3
E/F_p: y^2 = x^3 + 1
A = (0x489a03c58dcf7fcfc97e99ffef0bb4634,
0x510c6972d795ec0c2b081b81de767f808)
B = (0x40e98b9382e0b1fa6747dcb1655f54f75,
0xb497a6a02e7611511d0db2ff133b32a3f)
Output:
e'(A, B) = (0x8b2cac13cbd422658f9e5757b85493818,
0xbc6af59f54d0a5d83c8efd8f5214fad3c)7.4. Algorithm 5.2.1 (BFderivePubl)
Input:
id = 6f:42:62 ("Bob")
version = 2
p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb
q = 0xffffffffffffffffffffffeffffffffffff
P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d,
0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab)
P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108,
0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f)
Output:
Q_id = (0x22fa1207e0d19e1a4825009e0e88e35eb57ba79391498f59,
0x982d29acf942127e0f01c881b5ec1b5fe23d05269f538836)7.5. Algorithm 5.3.1 (BFextractPriv)
Input:
s = 0x749e52ddb807e0220054417e514742b05a0
version = 2
p = 0xa6a0ffd016103ffffffffff595f002fe9ef195f002fe9efb
q = 0xffffffffffffffffffffffeffffffffffff
P = (0x6924c354256acf5a0ff7f61be4f0495b54540a5bf6395b3d,
0x024fd8e2eb7c09104bca116f41c035219955237c0eac19ab)
P_pub = (0xa68412ae960d1392701066664d20b2f4a76d6ee715621108,
0x9e7644e75c9a131d075752e143e3f0435ff231b6745a486f)
Output:
Q_id = (0x8212b74ea75c841a9d1accc914ca140f4032d191b5ce5501,
0x950643d940aba68099bdcb40082532b6130c88d317958657)7.6. Algorithm 5.4.1 (BFencrypt)
Note: 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")
version = 2
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:ff7.7. Algorithm 6.3.1 (BBextractPriv) 🔑
okay bestie, this is the private key extraction for BB1 and it's giving main character energy 💅 Here are the inputs we feed in (the id is Bob, 6f:42:62 🫶):
alpha = 0xa60c395285ded4d70202c8283d894bad4f0
beta = 0x48bf012da19f170b13124e5301561f45053
gamma = 0x226fba82bc38e2ce4e28e56472ccf94a499
version = 2
p = 0x91bbe2be1c8950750784befffffffffffff6e441d41e12fb
q = 0xfffffffffbfffffffffffffffffffffffff
P = (0x13cc538fe950411218d7f5c17ae58a15e58f0877b29f2fe1,
0x8cf7bab1a748d323cc601fabd8b479f54a60be11e28e18cf)
P_1 = (0x0f809a992ed2467a138d72bc1d8931c6ccdd781bedc74627,
0x11c933027beaaf73aa9022db366374b1c68d6bf7d7a888c2)
P_2 = (0x0f8ac99a55e575bf595308cfea13edb8ec673983919121b0,
0x3febb7c6369f5d5f18ee3ea6ca0181448a4f3c4f3385019c)
P_3 = (0x2c10b43991052e78fac44fdce639c45824f5a3a2550b2a45,
0x6d7c12d8a0681426a5bbc369c9ef54624356e2f6036a064f)
v = (0x38f91032de6847a89fc3c83e663ed0c21c8f30ce65c0d7d3,
0x44b9aa10849cc8d8987ef2421770a340056745da8b99fba2)
id = 6f:42:62 ("Bob")Now the output. Using the random value r = 0x695024c25812112187162c08aa5f65c7a2c, we get:
D_0 = (0x3264e13feeb7c506493888132964e79ad657a952334b9e53,
0x3eeaefc14ba1277a1cd6fdea83c7c882fe6d85d957055c7b)
D_1 = (0x8d7a72ad06909bb3bb29b67676d935018183a905e7e8cb18,
0x2b346c6801c1db638f270af915a21054f16044ab67f6c40e)7.8. Algorithm 6.4.1 (BBencrypt) 🦋
Note: the following values can also be used to test Algorithm 5.5.1 (BFdecrypt). ✨
Here's the encryption input, again for Bob. The message is "Hi there!" 💌
m = 48:69:20:74:68:65:72:65:21 ("Hi there!")
id = 6f:42:62 ("Bob")
version = 2
E: y^2 = x^3 + 1
p = 0x91bbe2be1c8950750784befffffffffffff6e441d41e12fb
q = 0xfffffffffbfffffffffffffffffffffffff
P = (0x13cc538fe950411218d7f5c17ae58a15e58f0877b29f2fe1,
0x8cf7bab1a748d323cc601fabd8b479f54a60be11e28e18cf)
P_1 = (0x0f809a992ed2467a138d72bc1d8931c6ccdd781bedc74627,
0x11c933027beaaf73aa9022db366374b1c68d6bf7d7a888c2)
P_2 = (0x0f8ac99a55e575bf595308cfea13edb8ec673983919121b0,
0x3febb7c6369f5d5f18ee3ea6ca0181448a4f3c4f3385019c)
P_3 = (0x2c10b43991052e78fac44fdce639c45824f5a3a2550b2a45,
0x6d7c12d8a0681426a5bbc369c9ef54624356e2f6036a064f)
v = (0x38f91032de6847a89fc3c83e663ed0c21c8f30ce65c0d7d3,
0x44b9aa10849cc8d8987ef2421770a340056745da8b99fba2)
hashfcn = 1.3.14.3.2.26 (SHA-1)Using the random value s = 0x62759e95ce1af248040e220263fb41b965e, the outputs come out as:
u = 0xad1ebfa82edf0bcb5111e9dc08ff0737c68
C_0 = (0x79f8f35904579f1aaf51897b1e8f1d84e1c927b8994e81f9,
0x1cf77bb2516606681aba2e2dc14764aa1b55a45836014c62)
C_1 = (0x410cfeb0bccf1fa4afc607316c8b12fe464097b20250d684,
0x8bb76e7195a7b1980531b0a5852ce710cab5d288b2404e90)
y = 82:a6:42:b9:bb:e9:82:c4:578. ASN.1 Module 🎀
okay so this section is the ASN.1 module, which is the official "dictionary" for how all the encodings in this doc get written down 📖 It's the part that lets different implementations agree on what the bytes mean, so it's lowkey the backbone of the whole thing 🦴✨
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 only supports IBE using
-- 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)
}
--
-- An elliptic curve is specified by an OID.
-- A type1curve is defined by the equation y^2 = x^3 + 1.
--
type1curve OBJECT IDENTIFIER ::= {
ibcs1 curve-types(1) type1-curve(1)
}
--
-- Supporting types
--
--
-- Encoding of a point on an elliptic curve E/F_p
-- An FpPoint can either represent an element of
-- F_p^2 or an element of (F_p)^2.
FpPoint ::= SEQUENCE {
x INTEGER,
y INTEGER
}
--
-- The following hash functions are supported:
--
-- SHA-1
--
-- id-sha1 OBJECT IDENTIFIER ::= {
-- iso(1) identified-organization(3) oiw(14)
-- secsig(3) algorithms(2) hashAlgorithmIdentifier(26)
-- }
--
-- SHA-224
--
-- id-sha224 OBJECT IDENTIFIER ::= {
-- joint-iso-itu-t(2)country(16) us(840)
-- organization(1) gov(101)
-- csor(3) nistAlgorithm(4) hashAlgs(2) sha224(4)
-- }
--
-- SHA-256
--
-- id-sha256 OBJECT IDENTIFIER ::= {
-- joint-iso-itu-t(2)country(16) us(840)
-- organization(1) gov(101)
-- csor(3) nistAlgorithm(4) hashAlgs(2) sha256(1)
-- }
--
-- SHA-384
--
-- id-sha384 OBJECT IDENTIFIER ::= {
-- joint-iso-itu-t(2)country(16) us(840)
-- organization(1) gov(101)
-- csor(3) nistAlgorithm(4) hashAlgs(2) sha384(2)
-- }
--
-- SHA-512
--
-- id-sha512 OBJECT IDENTIFIER ::= {
-- joint-iso-itu-t(2) country(16) us(840)
-- organization(1) gov(101)
-- csor(3) nistAlgorithm(4) hashAlgs(2) sha512(3)
-- }
--
--
-- 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.
-- The only version currently supported is version 2.
-- The values p and q define a subgroup of E(F_p) of order q.
--
BFPublicParameters ::= SEQUENCE {
version INTEGER { v2(2) },
curve OBJECT IDENTIFIER,
p INTEGER,
q INTEGER,
pointP FpPoint,
pointPpub FpPoint,
hashfcn OBJECT IDENTIFIER
}
--
-- A BF private key is a point on an elliptic curve,
-- which is an FpPoint.
-- The only version supported is version 2.
--
BFPrivateKeyBlock ::= SEQUENCE {
version INTEGER { v2(2) },
privateKey FpPoint
}
--
-- A BF master secret is an integer.
-- The only version supported is version 2.
--
BFMasterSecret ::= SEQUENCE {
version INTEGER {v2(2) },
masterSecret INTEGER
}
--
-- BF ciphertext block
-- The only version supported is version 2.
--
BFCiphertextBlock ::= SEQUENCE {
version INTEGER { v2(2) },
u FpPoint,
v OCTET STRING,
w OCTET STRING
}
--
-- Boneh-Boyen (BB1) IBE
--
bb1 OBJECT IDENTIFIER ::= { ibe-algorithms bb1(2) }
--
-- Encoding of a BB1 public parameters block.
-- The version is currently fixed to 2.
--
--
BB1PublicParameters ::= SEQUENCE {
version INTEGER { v2(2) },
curve OBJECT IDENTIFIER,
p INTEGER,
q INTEGER,
pointP FpPoint,
pointP1 FpPoint,
pointP2 FpPoint,
pointP3 FpPoint,
v FpPoint,
hashfcn OBJECT IDENTIFIER
}
--
-- BB1 master secret block
-- The only version supported is version 2.
--
BB1MasterSecret ::= SEQUENCE {
version INTEGER { v2(2) },
alpha INTEGER,
beta INTEGER,
gamma INTEGER
}
--
-- BB1 private Key block
-- The only version supported is version 2.
--
BB1PrivateKeyBlock ::= SEQUENCE {
version INTEGER { v2(2) },
pointD0 FpPoint,
pointD1 FpPoint
}
--
-- BB1 ciphertext block
-- The only version supported is version 2.
--
BB1CiphertextBlock ::= SEQUENCE {
version INTEGER {v2(2) },
pointChi0 FpPoint,
pointChi1 FpPoint,
nu INTEGER,
y OCTET STRING
}
END9. Security Considerations ✨
okay bestie, this is the serious section, so no skipping 💅. This document is all about cryptographic algorithms, and the security they give you depends entirely on keeping the relevant private key secret 🔐. To break them, an attacker would have to pull off seriously intense cryptanalysis to recover that private key 🙈.
We're assuming users will want one of five strength levels: the equivalent of 80, 112, 128, 192, or 256 bits 🌈.
- 80 bits: good for legacy apps, but it SHOULD NOT be used to protect info whose useful life goes past the year 2010 💀.
- 112 bits: works for transporting Triple-DES keys and should keep info safe until about the year 2030 🫶.
- 128 bits and up: works for transporting AES keys of that length or shorter, and keeps info safe past the year 2030 🔥.
Table 1 shows the security parameters for the BF and BB1 algorithms that hit these levels. Here, |p| is the number of bits in a prime p, and |q| is the number of bits in a subprime q. The table assumes a Type-1 supersingular curve is being used ✨.
Bits of Security |p| |q|
80 512 160
112 1024 224
128 1536 256
192 3840 384
256 7680 512Table 1: Sizes of BF and BB1 Parameters Required to Attain Standard Levels of Bit Security [SP800-57].
Here's a key thing to remember 🧠. If an IBE key is used to transport a symmetric key with more bits of security than the IBE key has, the whole system is only as strong as the weaker IBE key. So if a 112-bit IBE key carries a 128-bit AES key, the security is still capped at the 112 bits of the IBE key 😭.
Now the hashing bit 🍓. This document uses the National Institute of Standards and Technology (NIST) hash algorithms [SHA] to hash identities onto either a point on an elliptic curve or an integer. Recent attacks on SHA-1 [SHA] have found ways to produce collisions with less work than the 2^80 hashes you'd expect from the size of the output alone. If an attacker finds a collision, they could use the colliding preimages to make two identities that share the same IBE private key. Realistically though, using a SHA-1 [SHA] collision like this is extremely unlikely 🙈.
Identities usually aren't random strings like the preimages of a hash collision would be. That's especially true when IBE is used as described in [IBECMS], where the components of an identity are an e-mail address, a validity period, and a URI. In that case, the random-looking results of a collision almost never fit the format of a valid identity, so they're useless to an attacker 🦋. Any protocol using IBE MUST define an identity in a way that makes hash collisions essentially useless to an attacker. Since random strings are rarely used as identities, this shouldn't be too hard to pull off 💖.
Randomness is everything here 🎀. The random values these algorithms need are vital to the security they provide. Any implementation MUST use a source of random values that gives an adequate level of security. Suitable algorithms for generating those values include [FIPS186-2] and [X9.62]. This keeps the random values used to mask plaintext messages in Sections 5.4 and 6.4 from being reused with any significant probability 👑.
The strength of a system built on these algorithms also depends on how strong the mechanism is for authenticating a user who asks a PKG for a private key. This is described in step 2 of Section 1.2 of this document. It's kind of like digital certificates [X.509], where the system is only as strong as the authentication users go through before getting their certificates. Either way, a weak authentication step makes a weak system that relies on the tech 💀. A system using the algorithms in this document MUST require users to authenticate in a suitably strong way, especially if IBE private keys are going to be used for authentication 🔐.
IBE systems also behave differently from other asymmetric schemes when it comes to key recovery 👀. If the master secret lives on a secure PKG, then the PKG and any administrator with the right level of access can create any private key they want. That means controls over those administrators, plus logging of everything they do, SHOULD be part of a functioning IBE system 🧚.
It's also possible to create IBE private keys from a master secret and then destroy that master secret, which makes key recovery impossible 😱. If that's not what you want, an IBE administrator SHOULD require that the identity format includes a short-lived component. For example, the identity format defined in [IBECMS] includes the validity period of the key, which is used to calculate the key from the identity. An identity like that can be changed easily to rekey users if their IBE private key ever gets compromised 🔄.
10. Acknowledgments 🫶
This document is based on the IBCS #1 v2 document from Voltage Security, Inc. Any substantial use of material from this document should credit Voltage Security, Inc. as the source of the information 🌸.
11. References 📚
11.1. Normative References
[KEYWORDS] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[TLS] Dierks, T. and E. Rescorla, "The Transport Layer
Security (TLS) Protocol Version 1.1", RFC 4346, April
2006.11.2. Informative References
[BB1] D. Boneh and 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 and M. Franklin, "Identity-based encryption
from the Weil pairing," in Proc. of CRYPTO 01, LNCS
2139, pp. 213-229, 2001.
[CMS] Housley, R., "Cryptographic Message Syntax (CMS)", RFC
3852, July 2004.
[ECC] I. Blake, G. Seroussi, and N. Smart, "Elliptic Curves in
Cryptography", Cambridge University Press, 1999.
[FIPS186-2] National Institute of Standards and Technology, "Digital
Signature Standard," Federal Information Processing
Standard 186-2, August 2002.
[IBEARCH] G. Appenzeller, L. Martin, and M. Schertler, "Identity-
based Encryption Architecture", Work in Progress.
[IBECMS] L. Martin and M. Schertler, "Using the Boneh-Franklin
and Boneh-Boyen identity-based encryption algorithms
with the Cryptographic Message Syntax (CMS)", Work in
Progress.
[MERKLE] R. Merkle, "A fast software one-way hash function,"
Journal of Cryptology, Vol. 3 (1990), pp. 43-58.
[P1363] IEEE P1363-2000, "Standard Specifications for Public Key
Cryptography," 2001.
[SP800-57] E. Barker, W. Barker, W. Burr, W. Polk and M. Smid,
"Recommendation for Key Management - Part 1: General
(Revised)," NIST Special Publication 800-57, March 2007.
[SHA] National Institute for Standards and Technology, "Secure
Hash Standard," Federal Information Processing Standards
Publication 180-2, August 2002, with Change Notice 1,
February 2004.
[X9.62] American National Standards Institute, "Public Key
Cryptography for the Financial Services Industry: The
Elliptic Curve Digital Signature Algorithm (ECDSA),"
American National Standard for Financial Services
X9.62-2005, November 2005.
[X.509] ITU-T Recommendation X.509 (2000) | ISO/IEC 9594-8:2001,
Information Technology - Open Systems Interconnection -
The Directory: Public-key and Attribute Certificate
Frameworks.Authors' Addresses 🦋
Xavier Boyen
Voltage Security
1070 Arastradero Rd Suite 100
Palo Alto, CA 94304
EMail: xavier@voltage.com
Luther Martin
Voltage Security
1070 Arastradero Rd Suite 100
Palo Alto, CA 94304
EMail: martin@voltage.comFull Copyright Statement ⭐
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions contained in BCP 78 and at www.rfc-editor.org/copyright.html. Except as set forth there, the authors keep all their rights 💜.
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.
Intellectual Property 🎀
The IETF takes no position on the validity or scope of any Intellectual Property Rights or other rights that might be claimed to apply to implementing or using the technology described in this document. It also doesn't say whether any license under those rights might be available, and it hasn't made any independent effort to find such rights. Info on the procedures for rights in RFC documents is in BCP 78 and BCP 79 🌈.
Copies of IPR disclosures made to the IETF Secretariat, any assurances of licenses that will be made available, and the results of any attempt to get a general license or permission for implementers or users to use these proprietary rights can be found in the IETF online IPR repository at http://www.ietf.org/ipr 🔗.
The IETF invites any interested party to bring to its attention any copyrights, patents, patent applications, or other proprietary rights that may cover technology needed to implement this standard. Send that info to the IETF at ietf-ipr@ietf.org 💖.
📦 where this page comes from
- ietf: rfc5091 2007-12
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms