Network Working Group M. Groves
Internet Draft CESG
Intended Status: Informational June 29, 2010
Expires: December 31, 2010
Sakai-Kasahara Key Establishment (SAKKE)
draft-groves-sakke-00
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and 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/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on December 31, 2010.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the BSD License.
Groves Informational [Page 1]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
Abstract
In this document the Sakai-Kasahara Identifier-Based Encryption
algorithm (SAKKE) is described. This uses Identifier-Based
Encryption to exchange a shared secret from a Sender to a Receiver.
Table of Contents
1. Introduction.....................................................2
1.1. Requirements Terminology....................................3
2. Notation and Definitions.........................................3
2.1. Notation....................................................3
2.2. Definitions.................................................5
3. Elliptic Curves and Pairings.....................................6
3.1. E(F_p^2) and the Distortion Map.............................6
3.2. The Tate-Lichtenbaum Pairing................................6
4. Representation of Values.........................................8
5. Supporting Algorithms............................................9
5.1. Hashing to an Integer Range.................................9
6. The SAKKE Cryptosystem...........................................9
6.1. Setup.......................................................9
6.1.1. Secret Key Extraction.................................10
6.1.2. User Provisioning.....................................10
6.2. Key Exchange...............................................10
6.2.1. Sender................................................10
6.2.2. Receiver..............................................11
6.3. Group Communications.......................................11
7. Security Considerations.........................................12
8. References......................................................13
8.1. Normative References.......................................13
8.2. Informative References.....................................13
Appendix A. Test Data..............................................14
1. Introduction
This document defines an efficient use of Identifier-Based Encryption
(IBE) based on bilinear pairings. The Sakai-Kasahara IBE
cryptosystem [S-K] is described for establishment of a shared secret
value. This document adds to the IBE options available in [RFC5091],
providing an efficient primitive and an additional family of curves.
This document is restricted to a particular family of curves (see
Section 2.1) which have the benefit of a simple and efficient method
of calculating the pairing on which the Sakai-Kasahara IBE
cryptosystem is based.
Identifier-Based Encryption schemes allow public and private keys to
be derived from Identifiers. In fact, the Identifier can itself be
viewed as corresponding to a public key or certificate in a
traditional public key system. However, in IBE, the Identifier can
Groves Informational [Page 2]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
be formed by both Sender and Receiver, which obviates the necessity
of providing public keys through a third party or of transmitting
certified public keys during each session establishment.
Furthermore, in an IBE system, calculation of keys can occur as
needed, and indeed, messages can be sent to users who are yet to
enrol.
The Sakai-Kasahara primitive described in this document supports
simplex transmission of messages from a Sender to a Receiver. The
choice of elliptic curve pairing on which the primitive is based
allows simple and efficient implementations.
The Sakai-Kasahara Key Establishment scheme described in this
document is drawn from the SK-KEM scheme (as modified to support
multi-party communications) submitted to the IEEE P1363 Working Group
in [SK-KEM].
1.1. Requirements Terminology
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 [RFC2119].
2. Notation and Definitions
2.1. Notation
n A security parameter; the size of symmetric keys in bits to
be exchanged by SAKKE.
p A prime, which is the order of the finite field F_p. In
this document p is always congruent to 3 modulo 4.
F_p The finite field of order p.
F* The multiplicative group of the non-zero elements in the
field F; e.g., (F_p)* is the multiplicative group of the
finite field F_p.
q An odd prime that divides p + 1. To provide the desired
level of security, lg(q) MUST be greater than 2*n.
E An elliptic curve defined over F_p, having a subgroup of
order q. In this document we use supersingular curves with
equation y^2 = x^3 - 3 * x. This curve is chosen because of
the efficiency and simplicity advantages it offers. The
choice of -3 for the coefficient of x provides advantages
for elliptic curve arithmetic which are explained in
[P1363]. A further reason for this choice of curve is that
Groves Informational [Page 3]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
Barreto's trick [Barreto] of eliminating the computation of
the denominators when calculating the pairing applies.
E(F) The additive group of points of affine coordinates (x,y)
with x, y in the field F, that satisfy the curve equation
for E.
P A point of E(F_p) that generates the cyclic subgroup of
order q. The coordinates of P are given by P = (P_x,P_y).
These coordinates are in F_p, and they satisfy the curve
equation.
0 The null element of any additive group of points on an
elliptic curve, also called the point at infinity.
F_p^2 The extension field of degree 2 of the field F_p. In this
document we use a particular instantiation of this field;
F_p^2 = F_p[i] where i^2 + 1 = 0.
PF_p The projectivisation of F_p. We define this to be
(F_p^2)*/(F_p)*. Note that PF_p is cyclic and has order p +
1, which is divisible by q.
G[q] The q-torsion of a group G. This is the subgroup generated
by points of order q in G.
< , > A version of the Tate-Lichtenbaum pairing. In this document
this is a bilinear map from E(F_p)[q] x E(F_p)[q] onto the
subgroup of order q in PF_p. A full definition is given in
Section 3.2.
Hash A cryptographic hash function.
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 as A + B.
Scalar multiplication - If A is a point on a curve, and k an
integer, the result of adding A to itself a total of k times is
denoted [k]A.
We assume that the following concrete representations of mathematical
objects are used.
Elements of F_p - The p elements of F_p are represented directly
using the integers from 0 to p-1.
Elements of F_p^2 - The elements of F_p^2 = F_p[i] are represented
as x_1 + i * x_2, where x_1 and x_2 are elements of F_p.
Elements of PF_p - Elements of PF_p are cosets of (F_p)* in
Groves Informational [Page 4]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
(F_p^2)*. Every element of F_p^2 can be written unambiguously in
the form x_1 + i * x_2, where x_1 and x_2 are elements of F_p.
Thus elements of PF_p (except the unique element of order 2) can
be represented unambiguously by x_2 / x_1 in F_p. Since q is odd,
every element of PF_p[q] can be represented by an element of F_p
in this manner.
This representation of elements in PF_p[q] allows efficient
implementation of PF_p[q] group operations, as these can be defined
using arithmetic in F_p. If a and b are elements of F_p representing
elements A and B of PF_p[q] respectively, then A * B in PF_p[q] is
represented by (a + b)/(1 - a * b) in F_p.
2.2. Definitions
Identifier - Each user of an IBE system MUST have a unique,
unambiguous identifying string that can be easily derived by all
valid communicants. This string is the user's Identifier. An
Identifier is an integer in the range 2 to q-1. The method by
which Identifiers are formed MUST be defined for each
application.
Key Management Server (KMS) - The Key Management Server is a
trusted 3rd party for the IBE system. It derives system secrets
and distributes key material to those authorised to obtain it.
Applications MAY support the use mutual communication between the
users of multiple KMSs. We denote KMSs by KMS_T, KMS_S etc.
Public parameters - The public parameters are a set of parameters
that are held by all users of an IBE system. Such a system MAY
contain multiple KMSs. Each application of SAKKE MUST define the
set of public parameters to be used. The parameters needed are p,
q, E, P, g=
, Hash and n.
Master Secret (z_T) - The Master Secret z_T is the master key
generated and privately kept by KMS_T and is used by KMS_T to
generate the private keys of the users that it provisions; it is
an integer in the range 2 to q-1.
KMS Public Key: Z_T = [z_T]P - The KMS Public Key Z_T is used to
form Public Key Establishment Keys for all users provisioned by
KMS_T; it is a point of order q in E(F_p). It MUST be provisioned
by KMS_T to all who are authorised to send messages to users of
the IBE system.
Receiver Secret Key (RSK) - Each user enrolled in an IBE system is
provisioned with a Receiver Secret Key by its KMS. The RSK
provided to a user with Identifier a by KMS_T is denoted K_(a,T).
In SAKKE, the RSK is a point of order q in E(F_p).
Shared Secret Value - The aim of the SAKKE scheme is for the
Groves Informational [Page 5]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
Sender to securely transmit a Shared Secret Value to the
Receiver. The Shared Secret Value is an integer in the range 0 to
(2^n) - 1; it is denoted SSV.
Encapsulated Data - The Encapsulated Data are used to transmit
secret information securely to the Receiver. They can be computed
directly from the Receiver's Identifier, the public parameters,
the KMS Public Key, and the Shared Secret Value to be
transmitted. In SAKKE the Encapsulated Data are a point of order
q in E(F_p) and an integer in the range 0 to (2^n) - 1. They are
formatted as described in Section 4.
3. Elliptic Curves and Pairings
E is a supersingular elliptic curve (of j-invariant 1728). E(F_p)
contains a cyclic subgroup of order q, denoted E(F_p)[q], whereas the
larger object E(F_p^2) contains the direct product of two cyclic
subgroups of order q, denoted E(F_p^2)[q].
P is a generator of E(F_p)[q]. It is specified by the (affine)
coordinates (P_x,P_y) in F_p, satisfying the curve equation.
Routines for point addition and doubling on E(F_p) can be found in
Appendix A.10 of [P1363].
3.1. E(F_p^2) and the Distortion Map
If (Q_x,Q_y) are (affine) coordinates in F_p for some point (denoted
Q) on E(F_p)[q], then (-Q_x,iQ_y) are (affine) coordinates in F_p^2
for some point on E(F_p^2)[q]. This latter point is denoted [i]Q, by
analogy with the definition for scalar multiplication. The two
points P and [i]P together generate E(F_p^2)[q]. The map [i]: E(F_p)
-> E(F_p^2) is sometimes termed the distortion map.
3.2. The Tate-Lichtenbaum Pairing
We proceed to describe the pairing < , > to be used in SAKKE. We
will need to evaluate polynomials f_R that depend on points on
E(F_p)[q]. Miller's algorithm [Miller] provides a method for
evaluation of f_R(X), where X is some element of E(F_p^2)[q] and R is
some element of E(F_p)[q] and f_R is some polynomial over F_p whose
divisor is (q)(R) - (q)(0). Note that f_R is defined only up to
scalars of F_p.
The version of the Tate-Lichtenbaum pairing used in this document is
given by = f_R([i]Q)^c / (F_p)*. It satisfies the bilinear
relation <[x]R,Q> = = ^x for all Q, R in E(F_p)[q], for
all integers x. Note that the domain of definition is restricted to
E(F_p)[q] x E(F_p)[q] so that certain optimisations are natural.
Groves Informational [Page 6]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
We provide pseudocode for computing , with elliptic curve
arithmetic expressed in affine coordinates. We make use of Barreto's
trick [Barreto] for avoiding the calculation of denominators. Note
that this section does not fully describe the most efficient way of
computing the pairing; it is possible to compute the pairing without
any explicit reference to the extension field F_p^2. This reduces
the number and complexity of the operations needed to compute the
pairing.
Pseudocode begins:
Routine for computing the pairing :
Input R, Q points on E(F_p)[q];
Initialise variables:
v = (F_p)*; // An element of PF_p[q]
C = R; // An element of E(F_p)[q]
c = (p+1)/q; // An integer
for bits of q-1, starting with the second MSB, ending
with the LSB, do
// gradient of line through C, C, [-2]C.
l = 3*( C_x^2 - 1 ) / ( 2*C_y );
//accumulate line evaluated at [i]Q into v
v = v^2 * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) );
C = [2]C;
if bit is 1 then
// gradient of line through C, R, -C-R.
l = ( C_y - R_y )/( C_x - R_x );
//accumulate line evaluated at [i]Q into v
v = v * ( l*( Q_x + C_x ) + ( i*Q_y - C_y ) );
C = C+R;
end if;
end for;
t = v^c;
return representative in F_p of t;
End of routine;
Routine for computing representative in F_p of elements of PF_p:
Input t, in F_p^2, representing an element of PF_p;
Groves Informational [Page 7]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
Represent t as a + i*b, with a,b in F_p;
return b/a;
End of routine;
End of pseudocode;
4. Representation of Values
This section provides canonical representations of values which MUST
be used to ensure interoperability of implementations. The following
representations MUST be used for input into hash functions and for
transmission.
Integers Integers MUST be represented as an octet string,
with bit length a multiple of 8. To achieve this,
the integer is represented most significant bit
first, and padded with zero bits on the left until
an octet string of the necessary length is
obtained. This is the Octet String representation
described in Section 5.5.2 of [P1363].
F_p elements Elements of F_p MUST be represented as integers in
the range 0 to p-1 using the octet string
representation defined above. Such octet strings
MUST have length L = Ceiling(lg(p)/8).
PF_p elements Elements of PF_p MUST be represented as an element
of F_p using the algorithm in Section 3.2. They
are therefore represented as octet strings as
defined above and are L octets in length.
Representation of the unique element of order 2 in
PF_p will not be required.
Points on E Elliptic Curve Points MUST be represented in
Uncompressed representation as defined in Section
5.5.6 of [P1363a]. For an elliptic curve point (
x , y ) with x and y in F_p, this representation
is given by 0x00 || x' || y' , where x' is the
octet string representing x, y' is the octet
string representing y and 0x00 is a NULL octet.
The representation is 2*L+1 octets in length.
Encapsulated Data The Encapsulated Data MUST be represented as an
Elliptic Curve Point concatenated with an integer
in the range 0 to (2 ^ n) - 1. Since the length
of the representation of elements of F_p is well
defined given p, these data can be unambiguously
parsed to retrieve their components. The
Encapsulated Data is 2*L + n + 1 octets in
length.
Groves Informational [Page 8]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
5. Supporting Algorithms
5.1. Hashing to an Integer Range
We use the function HashToIntegerRange( s, n, hashfn) to hash strings
to an integer range. Given a string, s, a hash function, hashfn, and
an integer, n, this function returns a value between 0 and n - 1.
Input:
* an octet string, s
* an integer, n <= (2^hashlen)^hashlen
* a hash function, hashfn, with output length hashlen bits.
Output:
* an integer, v in the range 0 to n-1
Method:
1) Let A = hashfn( s )
2) Let h_0 = 00...00, a string of null bits of length hashlen bits
3) Let l = Ceiling( lg( n ) / hashlen )
4) For each i in 1 to l do:
a) Let h_i = hashfn(h_(i - 1))
b) Let v_i = hashfn(h_i || A), where || denotes concatenation
5) Let v' = v_1 || ... || v_l
6) Let v = v' mod n
6. The SAKKE Cryptosystem
This chapter describes the Sakai-Kasahara Key Establishment
algorithm. It draws from the cryptosystem first described in [S-K].
6.1. Setup
All users share a set of public parameters with a KMS. In most
circumstances it is expected that a system will only use a single
KMS. However, it is possible for users provisioned by different KMSs
Groves Informational [Page 9]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
to interoperate provided that they use a common set of public
parameters, and that they each possess the necessary KMS Public
Keys. In order to facilitate this interoperation, it is anticipated
that parameters will be published in application specific standards.
KMS_T chooses its KMS Master Secret, z_T. It MUST randomly select a
value in the range 2 to q-1, and assigns this value to z_T. It MUST
derive its KMS Public Key, Z_T, by performing the calculation Z_T =
[z_T]P.
6.1.1. Secret Key Extraction
The KMS derives each Receiver Secret Key from an Identifier and its
KMS Master Secret. It MUST derive a Receiver Secret Key for each
user that it provisions.
For Identifier 'a', the Receiver Secret Key K_(a,T) provided by KMS_T
MUST be derived by KMS_T as K_(a,T) = [(a + z_T)^-1]P, where 'a' is
interpreted as an integer, and the inversion is performed modulo q.
6.1.2. User Provisioning
The KMS MUST provide its KMS Public Key to all users through an
authenticated channel. Receiver Secret Keys MUST be supplied to all
users through a channel that provides confidentiality and mutual
authentication. The mechanisms that provide security for these
channels are beyond the scope of this document: they are application
specific.
Upon receipt of key material, each user MUST verify its Receiver
Secret Key. For Identifier 'a', Receiver Secret Keys from KMS_T are
verified by checking that the following equation holds: < [a]P + Z ,
K_(a,T) > = g, where 'a' is interpreted as an integer.
6.2. Key Exchange
A Sender forms Encapsulated Data and sends it to the Receiver, who
processes it. The result is a shared secret which can be used as
keying material for securing further communications. We denote the
Sender "A", with Identifier a; we denote the Receiver "B", with
Identifier b; Identifiers are to be interpreted as integers in the
algorithms below. Let A be provisioned by KMS_T and B be provisioned
by KMS_S.
6.2.1. Sender
In order to form Encapsulated Data to send to device B who is
provisioned by KMS_S, A needs to hold Z_S. It is anticipated that
Groves Informational [Page 10]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
this will have been provided to A by KMS_T along with its User
Private Keys. The Sender MUST carry out the following steps.
1) Select a random ephemeral integer value for the Shared Secret
Value SSV in the range 0 to 2^n - 1.
2) Compute r = HashToIntegerRange( SSV || b , q , Hash ).
3) Compute R_(b,S) = [r]([b]P + Z_S) in E(F_p).
4) Compute the Hint, H := SSV xor HashToIntegerRange( g^r, 2^n,
Hash ).
5) Form the Encapsulated Data ( R_(b,S) , H ) and transmit it to
B.
6) Output SSV for use to derive key material for the application
to be keyed.
6.2.2. Receiver
Device B receives Encapsulated Data from device A. In order to
process this, it requires its Receiver Secret Key, K_(b,S), which
will have been provisioned in advance by KMS_S. The method by which
keys are provisioned by the KMS is application specific. The
Receiver MUST carry out the following steps to derive and verify the
Shared Secret Value.
1) Parse the Encapsulated Data ( R_(b,S) , H ) and extract R_(b,S)
and H.
2) Compute w := < R_(b,S) , K_(b,S) >. Note that by bilinearity w
= g^r.
3) Compute SSV = H xor HashToIntegerRange( w, 2^n, Hash ).
4) Compute r = HashToIntegerRange( SSV || b , q , Hash ).
5) Compute TEST = [r]([b]P + Z_S) in E(F_p). If TEST does not
equal R_(b,S) then B MUST NOT use the SSV to derive key
material.
6) Output SSV for use to derive key material for the application
to be keyed.
6.3. Group Communications
The SAKKE scheme can be used to exchange Shared Secret Values for
group communications. To provide a Shared Secret to multiple
Receivers, a Sender MUST form Encapsulated Data for each of their
Groves Informational [Page 11]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
Identifiers, and transmit the appropriate data to each Receiver. Any
party possessing the group Shared Secret Value MAY extend the group
by forming Encapsulated Data for a new group member.
Whilst the Sender needs to form multiple Encapsulated Data, the fact
that the sending operation avoids pairings means that the extension
to multiple Receivers can be carried out more efficiently than for
alternative IBE schemes which require the Sender to compute a
pairing.
7. Security Considerations
This document describes the SAKKE cryptographic algorithm. We assume
that the security provided by this algorithm depends entirely on the
secrecy of the secret keys it uses, and that for an adversary to
defeat this security, he will need to perform computationally
intensive cryptanalytic attacks to recover a secret key. Note that a
security proof exists for SAKKE in the Random Oracle Model [SK-KEM].
When defining public parameters, guidance on parameter sizes from
[SP800-57] SHOULD be followed. Note that the size of the F_p^2
discrete logarithm on which the security rests is 2*lg(p). Table 1
shows bits of security afforded by various sizes of p. If k bits of
security are needed, then lg(q) SHOULD be chosen to be at least 2*k.
Similarly, if k bits of security are needed, then a Hash with output
size at least 2*k SHOULD be chosen.
Bits of Security | lg(p)
-------------------------
80 | 512
112 | 1024
128 | 1536
192 | 3840
256 | 7680
Table 1: Comparable strengths, taken from Table 2 of [SP800-57]
The KMS Master Secret provides the security for each device
provisioned by the KMS. It MUST NOT be revealed to any other
entity. Each user's Receiver Secret Key protects the SAKKE
communications it receives. This key MUST NOT be revealed to any
other entity than the trusted KMS and the authorised user.
In order to ensure that the Receiver Secret Key is received only by
an authorised device, it MUST be provided through a secure channel.
The security offered by this system is no greater than the security
provided by this delivery channel.
Note that IBE systems have different properties than other asymmetric
cryptographic schemes with regards to key recovery. The KMS (and
Groves Informational [Page 12]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
hence any administrator with appropriate privileges) can create
Receiver Secret Keys for arbitrary Identifiers, and procedures to
monitor the creation of Receiver Secret Keys such as logging of
administrator actions SHOULD be defined by any functioning
implementation of SAKKE.
Identifiers MUST be defined unambiguously by each application of
SAKKE. Note that it is not necessary to hash the data in a format
for Identifiers (except in the case where its size would be greater
than that of q). In this way any weaknesses that might be caused by
collisions in hash functions can be avoided without reliance on the
structure of the Identifier format. Applications of SAKKE MAY
include a time/date component in their Identifier format to ensure
that Identifiers (and hence Receiver Secret Keys) are only valid for
a fixed period of time.
The randomness of values stipulated to be selected at random in SAKKE
described in this document is essential to the security provided by
SAKKE. If the ephemeral value r selected by the Sender is not chosen
at random then the SSV, which is used to provide key material for
further communications, could be predictable.
8. References
8.1. Normative References
[MIKEY-SAKKE] Groves, M., "MIKEY-SAKKE: Sakai-Kasahara Key
Exchange in Multimedia Internet KEYing (MIKEY)",
draft-groves-MIKEY-SAKKE-00 [work in progress],
June 2010.
[P1363] IEEE P1363-2000, "Standard Specifications for
Public-Key Cryptography," 2001.
[P1363a] IEEE P1363a, "Standard Specifications for
Public-Key Cryptography - Amendment 1: Additional
Techniques", 2004.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
8.2. Informative References
[Barreto] Barreto, P., Kim, H., Lynn, B. and M. Scott
"Efficient Algorithms for Pairing-Based
Cryptosystems", Advances in Cryptology - Crypto
2002, LNCS 2442, Springer-Verlag (2002),
pp.354-368.
Groves Informational [Page 13]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
[Miller] Miller, V., "The Weil pairing, and its efficient
calculation", J. Cryptology 17 (2004), 235-261.
[RFC5091] Boyen, X. and L. Martin, "Identity Based
Cryptography Standard (IBCS) #1: Supersingular
Curve Implementations of the BF and BB1
Cryptosystems", RFC 5091, December 2007.
[S-K] Sakai, R., Ohgishi, K. and M. Kasahara, "ID based
cryptosystem with pairing on elliptic curve",
Symposium on Cryptography and Information Security
- SCIS, 2003.
[SK-KEM] Barbosa, M., Chen, L., Cheng, Z., Chimley, M.,
Dent, A., Farshim, P., Harrison, K., Malone-Lee,
J., Smart, N. and F. Vercauteren, "SK-KEM: An
Identity-Based KEM", submission for IEEE P1363.3,
June 2006.
(http://grouper.ieee.org/groups/1363/IBC/
submissions/Barbosa-SK-KEM-2006-06.pdf)
Appendix A. Test Data
This appendix provides test data for SAKKE with the public parameters
defined in Appendix A of [MIKEY-SAKKE]. "b" represents the
Identifier of the Responder. The value "mask" is the value used to
mask the SSV, and is defined to be HashToIntegerRange( g^r, 2^n, Hash
).
// --------------------------------------------------------
// KMS generates:
z = AFF429D3 5F84B110 D094803B 3595A6E2 998BC99F
Zx = 5958EF1B 1679BF09 9B3A030D F255AA6A
23C1D8F1 43D4D23F 753E69BD 27A832F3
8CB4AD53 DDEF4260 B0FE8BB4 5C4C1FF5
10EFFE30 0367A37B 61F701D9 14AEF097
24825FA0 707D61A6 DFF4FBD7 273566CD
DE352A0B 04B7C16A 78309BE6 40697DE7
47613A5F C195E8B9 F328852A 579DB8F9
9B1D0034 479EA9C5 595F47C4 B2F54FF2
Zy = 1508D375 14DCF7A8 E143A605 8C09A6BF
2C9858CA 37C25806 5AE6BF75 32BC8B5B
63383866 E0753C5A C0E72709 F8445F2E
6178E065 857E0EDA 10F68206 B63505ED
87E534FB 2831FF95 7FB7DC61 9DAE6130
1EEACC2F DA3680EA 4999258A 833CEA8F
C67C6D19 487FB449 059F26CC 8AAB655A
Groves Informational [Page 14]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
B58B7CC7 96E24E9A 39409575 4F5F8BAE
// --------------------------------------------------------
// Creating Encapsulated Data
b = 3230 31302D30 37007465 6C3A2B34
34313233 34353637 38393000
SSV = 12345678 9ABCDEF0 12345678 9ABCDEF0
r = HashToIntegerRange(
12345678 9ABCDEF0 12345678 9ABCDEF0
32303130 2D303700 74656C3A 2B343431
32333435 36373839 3000, q, SHA-256 )
= 14681280 2E82D50F 25EEA39F 75E4E91A
3E44619A F7AE649F E113CB65 D2B32E84
530A18FA E0FEFC62 757628F6 2F804059
7840FFF4 A517A7C7 F3F7E696 AB38F053
77E4851A D8294152 AAEB6FFC CE211425
6EB96269 757731DB 75868CCE ACF1202C
F2263A77 E7F4FA59 986152B4 C7A55506
5A329077 0C86F3BB 8ADE405C 526ED54B
Rbx = 157B9F35 6C8A3138 A9532EC2 62B04604
83EA33A8 26247411 D852136C E543020C
52BDF196 E5955121 FF83A183 21E90A5A
7EC1D0E1 B433FEFB FD082C96 8674682A
A935EFDA E984F557 2B677D51 31E8C90C
CC77519D 7C88B20C 5C829287 B2204A3E
E7DBEE5D F7975375 24D7215B 2F3D9698
86720EF4 5CB61745 CB69DA22 C87EE985
Rby = 5D9C7EC1 A67942D3 BF0F82F2 9CC1C1D5
5E0FDBA6 F51B0179 0DA75F06 0BE7E9B0
DCC06CE7 A200E8EB A0F77875 6DF2C587
DE65DE84 67A522EE DA10774C C7043F52
D7B61B65 2109DE22 209C1B80 D0744FCB
2A35C51F 335962FA DBFF52C9 4A60AF82
6795356C 16F0DB7F 995CF68B 7EF7D367
B5F96B76 FC8E4778 09406FC9 7DF810B3
g^r = 298A4F75 823B7B86 AEA87E11 57A4448F
DB4B2735 2F364150 47C05A9E 527BE983
1A0625B1 BB59360D EF5E7FA2 52E1A0EF
9E2166E3 B3E0A8BE C4854EED 14BD3B36
D43AA069 9F7D71BF 377149A2 37B95CCD
7C5A812A B69D0F48 0802B79D 620663B3
FF0D5C9B CC991DCD 77587560 D7E48B79
CD1FAB30 18DDDC9F 5342B76D F21D3E61
mask = HashToIntegerRange(
Groves Informational [Page 15]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
298A4F75 823B7B86 AEA87E11 57A4448F
DB4B2735 2F364150 47C05A9E 527BE983
1A0625B1 BB59360D EF5E7FA2 52E1A0EF
9E2166E3 B3E0A8BE C4854EED 14BD3B36
D43AA069 9F7D71BF 377149A2 37B95CCD
7C5A812A B69D0F48 0802B79D 620663B3
FF0D5C9B CC991DCD 77587560 D7E48B79
CD1FAB30 18DDDC9F 5342B76D F21D3E61, 2^128, SHA-256 )
= 6F22CF7F 87627451 4627917B AED7E828
H = 7D169907 1DDEAAA1 5413C703 346B36D8
// --------------------------------------------------------
// Receiver processing
// Device receives Kb from KMS
Kbx = 0AB631BD 80052A89 5AE44295 753842D5
0B64798C 723D55FC AC4048DC A7BF61C6
F42C26D1 C82A8558 C5C19D50 98F9F706
037793B9 FE2062C3 7BFFDFC6 D5E4308B
BD2C3FFB 24767D86 11C08A17 5DE13AE8
E4DB0F77 536877B5 A3262AAD AFD007B7
F07F9A1E 4263A1EC F73E050C CEE68AF6
741EE7BB CF0FB40E C31C2E10 6488EE82
Kby = 8614FA9A F6EAC87A 9FE1C996 13235038
A0473076 B5C0A0EB 1BB321AB AD030905
7A491EB0 4A2A98D1 EA1E57D8 DE924B0B
41642FFE 62642FCA 794F6DFF CCB03B2E
E2ACCCFA 469951D2 4778E032 125CE424
628A54FA F11DABCD CD23B72D D76401B5
62A655FB 9B56581A 46CEAC6E 0C0A5E2A
F23D30B3 1BC1D6B4 E0068701 646EDDE8
// Device processes Encapsulated Data
w = 298A4F75 823B7B86 AEA87E11 57A4448F
DB4B2735 2F364150 47C05A9E 527BE983
1A0625B1 BB59360D EF5E7FA2 52E1A0EF
9E2166E3 B3E0A8BE C4854EED 14BD3B36
D43AA069 9F7D71BF 377149A2 37B95CCD
7C5A812A B69D0F48 0802B79D 620663B3
FF0D5C9B CC991DCD 77587560 D7E48B79
CD1FAB30 18DDDC9F 5342B76D F21D3E61
SSV = 12345678 9ABCDEF0 12345678 9ABCDEF0
r = 14681280 2E82D50F 25EEA39F 75E4E91A
3E44619A F7AE649F E113CB65 D2B32E84
530A18FA E0FEFC62 757628F6 2F804059
Groves Informational [Page 16]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
7840FFF4 A517A7C7 F3F7E696 AB38F053
77E4851A D8294152 AAEB6FFC CE211425
6EB96269 757731DB 75868CCE ACF1202C
F2263A77 E7F4FA59 986152B4 C7A55506
5A329077 0C86F3BB 8ADE405C 526ED54B
TESTx = 157B9F35 6C8A3138 A9532EC2 62B04604
83EA33A8 26247411 D852136C E543020C
52BDF196 E5955121 FF83A183 21E90A5A
7EC1D0E1 B433FEFB FD082C96 8674682A
A935EFDA E984F557 2B677D51 31E8C90C
CC77519D 7C88B20C 5C829287 B2204A3E
E7DBEE5D F7975375 24D7215B 2F3D9698
86720EF4 5CB61745 CB69DA22 C87EE985
TESTy = 5D9C7EC1 A67942D3 BF0F82F2 9CC1C1D5
5E0FDBA6 F51B0179 0DA75F06 0BE7E9B0
DCC06CE7 A200E8EB A0F77875 6DF2C587
DE65DE84 67A522EE DA10774C C7043F52
D7B61B65 2109DE22 209C1B80 D0744FCB
2A35C51F 335962FA DBFF52C9 4A60AF82
6795356C 16F0DB7F 995CF68B 7EF7D367
B5F96B76 FC8E4778 09406FC9 7DF810B3
TEST == Rb
// --------------------------------------------------------
// HashToIntegerRange( M, q, SHA-256 ) Example
M = 12345678 9ABCDEF0 12345678 9ABCDEF0
32303130 2D303700 74656C3A 2B343431
32333435 36373839 3000
A = 8B788A5C BBB8C91D C6B723C4 8E11Ed05
46d670CC D415BF0B 2A910FF3 D71DC0AF
h0 = 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
h1 = 66687AAD F862BD77 6C8FC18B 8E9F8E20
08971485 6EE233B3 902A591D 0D5F2925
h2 = 2B32DB6C 2C0A6235 FB1397E8 225EA85E
0F0E6E8C 7B126D00 16CCBDE0 E667151E
h3 = 12771355 E46CD47C 71ED1721 FD5319B3
83CCA3A1 F9FCE3AA 1C8CD3BD 37AF20D7
h4 = FE15C0D3 EBE314FA D720A08B 839A004C
2E6386F5 AECC19EC 74807D19 20CB6AEB
v1 = 3AC6C147 F1186505 BF602805 AC990278
CE9F64D3 5EDB8538 50BA843B FFAB3510
v2 = 100CC3C4 D9BE0029 3E17F52B 7BE9A785
B2256CDC A309CA4E 41533093 D4D29A07
v3 = B07F9E3C A4C41487 BF362170 277B1B5D
DC655F93 81D87C7C 1F7A5BE3 34002297
v4 = 9A0B7023 BD9AC221 979A4CBD AA06B472
Groves Informational [Page 17]
Internet Draft draft-groves-sakke-00 Jun 29, 2010
7A64083B 37A5A75D 6479A07B 1218ED46
v mod q = 14681280 2E82D50F 25EEA39F 75E4E91A
3E44619A F7AE649F E113CB65 D2B32E84
530A18FA E0FEFC62 757628F6 2F804059
7840FFF4 A517A7C7 F3F7E696 AB38F053
77E4851A D8294152 AAEB6FFC CE211425
6EB96269 757731DB 75868CCE ACF1202C
F2263A77 E7F4FA59 986152B4 C7A55506
5A329077 0C86F3BB 8ADE405C 526ED54B
// --------------------------------------------------------
Author's Address
Michael Groves
CESG
Hubble Road
Cheltenham
GL51 8HJ
UK
Email: Michael.Groves@cesg.gsi.gov.uk
Acknowledgement
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Groves Informational [Page 18]