PSEC-KEM Specification
version 2.2
NTT Information Sharing Platform Laboratories,
NTT Corporation
April 14, 2008

History
version 2.2

Apr. 14, 2008

version 2.1
version 2.01

Jan. 18, 2008
Sep. 3, 2007

version 2.0
version 1.1
version 1.0

Jun 14, 2007
May 14, 2002
Sep. 26, 2001

Fixed conversions in Section 3, revised paragraphs in sections,
1, 3, and 5, and cleaned up the document.
Revised appendices and corrected typos.
Added SHA-1, SHA-224, SHA-256, SHA-384,
and SHA-512 in the allowable hash functions.
Revised as compatible with ISO/IEC 18033-2.
Fixed conversions in Section 3, and corrected typos.

2

Contents
1 Introduction

4

2 Notations
2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Elliptic Curve Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44
4

3 Data types and conversions
3.1 Integer-to-BitString Conversion (I2BSP) . . . . . . . . . . . . . . . . . . . . . . .
3.2 BitString-to-Integer Conversion (BS2IP) . . . . . . . . . . . . . . . . . . . . . . .
3.3 BitString-to-OctetString Conversion (BS2OSP) . . . . . . . . . . . . . . . . . . .
3.4 OctetString-to-BitString Conversion (OS2BSP) . . . . . . . . . . . . . . . . . . .
3.5 Integer-to-OctetString Conversion (I2OSP) . . . . . . . . . . . . . . . . . . . . .
3.6 OctetString-to-Integer Conversion (OS2IP) . . . . . . . . . . . . . . . . . . . . .
3.7 FieldElement-to-Integer Conversion (FE2IP) . . . . . . . . . . . . . . . . . . . .
3.8 Integer-to-FieldElement Conversion (I2FEP) . . . . . . . . . . . . . . . . . . . .
3.9 FieldElement-to-OctetString Conversion (FE2OSP) . . . . . . . . . . . . . . . . .
3.10 OctetString-to-FieldElement Conversion (OS2FEP) . . . . . . . . . . . . . . . . .
3.11 EllipticCurvePoint-to-OctetString Conversion (ECP2OSP) . . . . . . . . . . . . .
3.12 OctetString-to-EllipticCurvePoint Conversion (OS2ECPP) . . . . . . . . . . . . .
3.13 Partial EllipticCurvePoint-to-OctetString Conversion (PECP2OSP) . . . . . . .

5
5
6
7
7
8
8
8
9
10
10
10
12
13

4 PSEC-KEM system parameters, and private and public keys
4.1 PSEC-KEM system parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 PSEC-KEM private key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 PSEC-KEM public key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13
13
13
13

5 Key encapsulation mechanism PSEC-KEM
5.1 KGP-PSEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 ES-PSEC-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Encryption operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Decryption operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14
14
14
14
15

6 Auxiliary techniques
6.1 Hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Key derivation functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 MGF1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15
15
15
15

A Security requirements of parameters

17

B Recommended parameters for secure implementation

17

C ASN.1 Syntax

17

3

1

Introduction

This document specifies key encapsulation mechanism PSEC-KEM.
A key encapsulation mechanism (KEM) is asymmetric cryptographic techniques to encrypta secret key that can be used to encrypt an actual message using symmetric cryptographic
techniques, called a data encapsulation mechanism (DEM). These techniques combined arecalled the KEM-DEM framework for realizing an asymmetric (hybrid) cipher. See Clause 8 in
ISO/IEC 18033-2 [1] for definitions and usages of these terms.
The implementations based on this document are compatible with the counterparts of PSECKEM specified in ISO/IEC 18033-2 [1].

2Notations2.1

Notationsbit
bit string
octet
octet stringRZN
a := b
Fqm
O
k
⊕
dye
byc
a|b
a mod ma−1 mod m

2.2

one of the two symbols ‘0’ or ‘1’.
an ordered sequence of bits.
a bit string of length 8.
an ordered sequence of octets.
the set of real numbers.
the set of integers.
the set of positive integers.
an operation of assigning b to a.
a finite field with q m elements, where q is a prime.
a point at infinity on an elliptic curve.
a concatenation operator for two bit strings or for two octet strings. This
operator is often omitted for simplicity.
the bit-wise exclusive-or operation.
for y ∈ R, the least integer greater than or equal to y.
for y ∈ R, the greatest integer less than or equal to y.
relation between integers a and b that holds if and only if a divides b, i.e., there
exists an integer c such that b = ac.
for a ∈ Z, m ∈ N, the least non-negative integer b that satisfies m|(a − b).
for a ∈ Z, m ∈ N, the least non-negative integer b that satisfies ab mod m = 1.

Elliptic Curve Parameter

An elliptic curve parameter E in this document is specified by the following 9-tuple (q, m, f (β),
a, b, P , p, pLen, qmLen), where the components have the following meanings:• q, a prime number, such that q 6= 3;• m,a positive integer;• f (β), a monic irreducible polynomial of degree m over Fq ;• a, an element in Fqm ;• b, an element in Fqm ;• P,

a point (x, y) on an elliptic curve, where– x, an element in Fqm , and
4

– y,

an element in Fqm ,such that– y 2 = x3 + ax + b and 4a3 + 27b2 6= 0 if q > 3,
– y 2 + xy = x3 + ax2 + b and b 6= 0 if q = 2;
• p,

the order of P , a prime number;• pLen, the value of dlog256 pe;• qmLen, the value of dlog256 q m e.

3

Data types and conversions

The scheme specified in this document involves operations using several different data types.
Five data types are employed in this document: non-negative integers (I), field elements (FE),octet strings (OS), bit strings (BS), and elliptic curve points (ECP). The classification is meant
to be abstract; throughout this document we make clear distinction between the five notions.
So, for example, an octet string is regarded as distinct from a bit string.
In the following we describe how to convert one data type into another. A conversion function
takes data represented in one of the five types, sometimes accepting an auxiliary input, and thenoutputs the data represented in a different type. Figure 1 illustrates which conversion function
transforms which data type into another.
A conversion function always rejects unexpected input values by outputting a special symbol
INVALID. The set of valid inputs is a subset of the set of the valid data type and is explicitly
defined by the function. Several conversions described below are realized by composition ofother conversions. When handling such a composition of conversion functions, we demand thatthe entire function should output INVALID, whenever one of the component functions outputs
INVALID.

3.1

Integer-to-BitString Conversion (I2BSP)

Integers should be converted to bit strings as described in this section. Formally, the conversion
routine, I2BSP(x, l), is specified as follows:
Input:
Output:Error:
Steps:

x a non-negative integerlthe bit length of the output, a non-negative integer
B a bit string of length l
INVALID

1. If x ≥ 2l , output INVALID and stop.
2. If l = 0, output the empty bit string and stop.
3. Represent x in binary such thatx = xl−1 2l−1 + xl−2 2l−2 + · · · + x1 2 + x0 ,where xi ∈ {0, 1}.
4. Set binary string B := B0 B1 · · · Bl−1 , such that Bi := xl−1−i for 0 ≤ i ≤ l − 1.
5. Output B.
5

'

$

Point on an
Elliptic CurveOS2ECPP(M )P = (x, y) or O&

ECP2OSP(P, R) -Â¿

Octet String MÁ%À

Mi is an octet.

x, y : Field Element

Â

Octet String
M = M0 M1 · · · Mn−1

À

6

I2

O
SP
O
(x
S2
,n
IP
)
(M
)


>

 Á

a) 

7
(

SP )2O  M
FE  EP(  2F OS




=


/
'
$
»
FE2IP(a) - Non-Negative¿¼ I2FEP(x)Integer x

&

%

x,
P(

l)

)
(B
IP

2
BS

BS
I2

S
oS
SS
SS
SS
SS
SS
SS
w
SS
Â

OS2BSP(M )Field Element a½

BS2OSP(B)¾?

Bit String
B = B0 B1 · · · Bl−1Á¿ÀBi ∈ {0, 1}
Figure 1: Conversions between data types

3.2

BitString-to-Integer Conversion (BS2IP)

Bit strings should be converted to integers as described in this section. Informally, the idea issimply to view the bit string as the binary representation of the integer. Formally, the conversion
routine, BS2IP(B), is specified as follows:
Input:
Output:Steps:

Bx

a bit string of length la non-negative integer

Convert B = B0 B1 · · · Bl−1 to an integer x as follows:
1. If l = 0, output 0 and stop.
2. View each Bi as an integer in {0, 1}, set xi := Bi for 0 ≤ i ≤ l − 1, and compute
x :=

l−1
X
i=0

6

2(l−1−i) xi .

3. Output x.

3.3

BitString-to-OctetString Conversion (BS2OSP)

Bit strings should be converted to octet strings as described in this section. Informally, the idea
is to pad the bit string with 0’s on the left to make its length a multiple of 8, then chop theresult up into octets. Formally, the conversion routine, BS2OSP(B), is specified as follows:
Input:

B

Output:M

a bit string of length l» ¼l
an octet string of length n =8Steps:
Convert the bit string B = B0 B1 · · · Bl−1 to an octet string M = M0 M1 · · · Mn−1 as follows:
1. If l = 0, output the empty octet string and stop.
2. For j ∈ {0, . . . , 8n − 1}, let:½
ej =B
3. For i ∈ {0, . . . , n − 1}, set:Bj−(8n−l)0

if j ≥ 8n − l,if j < 8n − l.

e8i Be8i+1 · · · B
e8i+7
Mi := B

4. Output M .

3.4

OctetString-to-BitString Conversion (OS2BSP)

Octet strings should be converted to bit strings as described in this section. Informally, the idea
is simply to view the octet string as a bit string. Formally, the conversion routine, OS2BSP(M ),is specified as follows:
Input:
Output:Steps:

MB

an octet string of length na bit string of length l = 8n

Convert the octet string M = M0 M1 · · · Mn−1 to a bit string B = B0 B1 · · · Bl−1 as follows:
1. If l = 0, output the empty bit string and stop.
2. For i ∈ {0, . . . , n − 1}, j ∈ {0, . . . , 7}, set B8i+j ∈ {0, 1} as
Mi = B8i B8i+1 · · · B8i+7
3. Output B.

7

3.5

Integer-to-OctetString Conversion (I2OSP)

Integers should be converted to octet strings as described in this section. Informally, the idea
is to represent the integer in binary and then convert the resulting bit string to an octet string.
Formally, the conversion routine, I2OSP(x, n), is specified as follows:
Input:
Output:Error:
Steps:xa non-negative integernthe octet length of output.
M an octet string of length n
INVALID

1. Let M := BS2OSP(I2BSP(x, 8n)).
2. Output M .

3.6

OctetString-to-Integer Conversion (OS2IP)

Octet strings should be converted to integers as described in this section. Informally, the idea
is to represent the octet string as a bit string and then view the resulting bit string as thebinary representation of the integer. Formally, the conversion routine, OS2IP(M ), is specified
as follows:
Input:
Output:Steps:

Mx

an octet string of length na non-negative integer

1. Let x := BS2IP(OS2BSP(M )).
2. Output x.

3.7

FieldElement-to-Integer Conversion (FE2IP)

Field elements should be converted to integers as described in this section. A field element
should be represented as a polynomial with integer coefficients, which can be represented as asequence of the coefficients. Informally, the idea is simply to view the sequence of the coefficientsas the radix-q representation of the integer, where q is the characteristic of the field. Formally,
the conversion routine, FE2IP(a), is specified as follows:
System parameters:

Fqm

Input:
Output:Steps:

ax

a finite field with q m elements where q is a prime, and m > 0
is an integer
a field element in Fqm
an integer in {0, . . . , q m − 1}

Convert field element a to integer x as follows:
if m = 1:
Field element a must be represented as an integer in {0, . . . , q − 1}.
1. Let x := a.
2. Output x.

8

if m > 1:
Field element a must be represented as a polynomial of at most (m−1)-th degreewith coefficients in {0, . . . , q − 1}. Let β be the variable of the polynomial.
1. Determine the coefficients ai ∈ {0, . . . , q − 1} for i ∈ {0, . . . , m − 1} thatsatisfym−1
Xa=ai β i .
i=0

2. Compute
x :=

m−1
X

ai q i .

i=03: Output x.

3.8

Integer-to-FieldElement Conversion (I2FEP)

Integers should be converted to field elements as described in this section. A field element
should be represented as a polynomial with integer coefficients, and it can be represented as asequence of the coefficients. Informally, the idea is to represent the integer with radix-q positional
number system where q is the characteristic of the field, and then convert the each digit to theeach coefficient of the polynomial. Formally, the conversion routine, I2FEP(x), is specified asfollows:
System parameters:

Fqm

Input:
Output:Steps:xaa finite field with q m elements where q is a prime, and m > 0
is an integer
an integer in {0, . . . , q m − 1}a field element in Fqm

Convert integer x to field element a as follows:
if m = 1:
A field element of Fqm must be represented as an integer in {0, . . . , q − 1}.
1. Let a := x.
2. Output a.
if m > 1:
A field element of Fqm must be represented as a polynomial of at most (m−1)-thdegree with coefficients in {0, . . . , q−1}. Let β be the variable of the polynomial.
1. Expand x into it’s radix q representation xi ∈ {0, . . . , q − 1} for i ∈{0, . . . , m − 1} that satisfies
x=

m−1
X

xi q i .

i=0

2. Compute
a :=

m−1
X
i=0

3: Output a.
9xi β i .

3.9

FieldElement-to-OctetString Conversion (FE2OSP)The conversion routine, FE2OSP(a), is specified as follows:
System parameters:

Fqmn

Input:
Output:Steps:aM

a finite field with q m elements where q is a prime, and m > 0
is an integer¼»
m log2 q
an integer equivalent to8
a field element in Fqm
an octet string

1. Let
M := I2OSP(FE2IP(a), n).
2. Output M .
Note: The system parameters should be equivalent in FE2IP and FE2OSP.

3.10

OctetString-to-FieldElement Conversion (OS2FEP)The conversion routine, OS2FEP(M ), is specified as follows:
System parameters:

Input:
Output:Error:
Steps:

a finite field with q m elements where q is a prime, and m > 0
is an integer¼»
m log2 qnan integer equivalent to8M
an octet stringaa field element in Fqm
INVALID
Fqm

1. Leta := I2FEP(OS2IP(M )).
2. Output a.
Note: The system parameters should be equivalent in I2FEP and OS2FEP.

3.11

EllipticCurvePoint-to-OctetString Conversion (ECP2OSP)Elliptic curve points should be converted to octet strings as described in this section. Informallythe idea is that, if point compression is being used, the compressed y-coordinate is placed in
the leftmost octet of the octet string along with an indication that point compression is on, andthe x-coordinate is placed in the remainder of the octet string; otherwise if point compression
is off, the leftmost octet indicates that point compression is off, and remainder of the octet
string contains the x-coordinate followed by the y-coordinate. Formally, the conversion routine,
ECP2OSP(P, R), is specified as follows:10System parameters:
Input:
Output:E an elliptic curve parameterPa point on an elliptic curve over Fqm
R Compressed, Uncompressed, or Hybrid
 M an octet string of length n
if P = O, n = 1»¼
m log2 q
n=+1
if P 6= O and R is Compressed,
where
» 8
¼


m log2 q+ 1 if P 6= O and R is Uncompressed or Hybrid.
 n=2
8

Steps:
Convert P to an octet string M = M0 M1 · · · Mn−1 as follows:
1. If P = O, output M := I2OSP(0, 1) .
2. If P = (x, y) 6= O and R = Compressed, proceed as follows:
2.1. Set octet string X := FE2OSP(x).
2.2. Derive from y a single bit ỹ as follows (this allows the y-coordinate to be represented
compactly using a single bit):
2.2.1. If q is an odd number, set ỹ := 0 if y = 0, otherwise set ỹ := yi mod 2, wherey = ym−1 β m−1 + · · · + y1 β + y0 , and i is the smallest integer such that yi 6= 0.
2.2.2. If q = 2, set ỹ := 0 if x = 0, otherwise compute z = zm−1 β m−1 + · · · + z1 β + z0
such that z = yx−1 and set ỹ := z0 .
2.3. If ỹ = 0, assign the value I2OSP(2, 1) to the single octet L. If ỹ = 1, assign the value
I2OSP(3, 1) to the single octet L.
2.4. Output M := L k X.
3. If P = (x, y) 6= O and R = Uncompressed, proceed as follows:
3.1. Set octet string X := FE2OSP(x).
3.2. Set octet string Y := FE2OSP(y).
3.3. Output M := I2OSP(4, 1) k X k Y .
4. If P = (x, y) 6= O and R = Hybrid, proceed as follows:
4.1. Set octet string X := FE2OSP(x).
4.2. Set octet string Y := FE2OSP(y).
4.3. Derive from y a single bit ỹ as follows (this allows the y-coordinate to be represented
compactly using a single bit):
4.3.1. If q is an odd number, set ỹ := 0 if y = 0, otherwise set ỹ := yi mod 2, wherey = ym−1 β m−1 + · · · + y1 β + y0 , and i is the smallest integer such that yi 6= 0.
4.3.2. If q = 2, set ỹ := 0 if x = 0, otherwise compute z = zm−1 β m−1 + · · · + z1 β + z0
such that z = yx−1 and set ỹ := z0 .
4.4. If ỹ = 0, assign the value I2OSP(6, 1) to the single octet L. If ỹ = 1, assign the value
I2OSP(7, 1) to the single octet L.
4.5. Output M := L k X k Y .

11

3.12

OctetString-to-EllipticCurvePoint Conversion (OS2ECPP)

Octet strings should be converted to elliptic curve points as described in this section. Informally,
the idea is that, if the octet string represents a compressed point, the compressed y-coordinate
is recovered from the leftmost octet, the x-coordinate is recovered from the remainder of theoctet string, and then the point compression process is reversed; otherwise the leftmost octetof the octet string is removed, the x-coordinate is recovered from the left half of the remaining
octet string, and the y-coordinate is recovered from the right half of the remaining octet string.
Formally, the conversion routine, OS2ECPP(M ), is specified as follows:
System parameters:
Input:

Output:Error:
Steps:EM

an elliptic curve parameteran octet string that is either
the single octet I2OSP(0, 1), »¼
m log2 q+ 1, oran octet string of length n =» 8¼
m log2 q
an octet string of length n = 2+ 1.
8P
an elliptic curve point
INVALID

Convert M to a point P on E as follows:
1. If M = I2OSP(0, 1), output P := O.
»¼
m log2 q
2. If M has length+ 1 octets, proceed as follows:8»¼
m log2 q
2.1. Parse M = L k X as a single octet L followed byoctets X.
8
2.2. Set x := OS2FEP(X).
2.3. If L = I2OSP(2, 1), set ỹ := 0, and if L = I2OSP(3, 1), set ỹ := 1. Otherwise output
INVALID and stop.
2.4. Derive from x and ỹ elliptic curve point P := (x, y), where:
2.4.1. If q is an odd number, compute the field element w := x3 +ax+b, and computea square root γ of w in Fqm . Output INVALID and stop if there are no squareroots in Fqm . Otherwise set y = 0 if γ = 0, otherwise set y := γ if γi ≡ ỹ mod 2,
and set y := −γ if γi 6≡ ỹ mod 2, where γ = γm−1 β m−1 + · · · + γ1 β + γ0 , and iis the smallest integer such that γi 6= 0.
m−1
2.4.2. If q = 2 and x = 0, set y := b2
in Fqm .
2.4.3. If q = 2 and x 6= 0, compute the field element γ := x + a + bx−2 in Fqm , andfind an element z = zm−1 β m−1 + · · · + z1 β + z0 such that z 2 + z = γ in Fqm .
Output INVALID and stop if no such z exists, otherwise set y := xz in Fqm if
z0 = ỹ, and set y := x(z + 1) in Fqm if z0 6= ỹ.
2.5. Output P := (x, y).
»¼
m log2 q
3. If M has length 2+ 1 octets, proceed as follows:
8

12

»

¼
m log2 q
3.1. Parse M = L k X k Y as a single octet L followed byoctets X followed by
8¼»
m log2 q
octets Y .
83.2. Unless L is I2OSP(4, 1), I2OSP(6, 1) or I2OSP(7, 1), output INVALID and stop.
3.3. Set x := OS2FEP(X).
3.4. Set y := OS2FEP(Y ).
3.5. If P := (x, y) does not satisfy the defining equation of elliptic curve E, then output
INVALID and stop.
3.6. Output P := (x, y).

3.13

Partial EllipticCurvePoint-to-OctetString Conversion (PECP2OSP)The conversion routine, PECP2OSP(P ), is specified as follows:
System parameters:
Input:E
P

Output:M

an elliptic curve parametera point on an elliptic curve over
» Fqm ¼
m log2 q
an octet string of length n =8Steps:
Convert P to an octet string M = M0 M1 · · · Mn−1 as follows:
1. If P = O, output M := I2OSP(0, n) .
2. If P = (x, y) 6= O, output FE2OSP(x) .

4

PSEC-KEM system parameters, and private and public keys

4.1

PSEC-KEM system parameters

PSEC-KEM is parameterized by the following system parameters:• E,

an elliptic curve parameter specified in Section 2.2;

• KDF , the key derivation function described in Section 6.2;
• hLen, a positive integer;• keyLen,

4.2

a positive integer.

PSEC-KEM private key

A PSEC-KEM private key is the following:• s, a non-negative integer such that 0 ≤ s < p.

4.3

PSEC-KEM public key

A PSEC-KEM public key is the following:• W,

a point on E.
13

5

Key encapsulation mechanism PSEC-KEM

This section describes PSEC-KEM, which consists of the following three algorithms:• KGP-PSEC, the key generation algorithm, takes no input and outputs a pair of public
and private keys, (W, s),• ES-PSEC-KEM-Encrypt, the encryption operation, that takes as input public key W
and format R, and outputs a pair of a secret key and a ciphertext, (k, c0 ), and• ES-PSEC-KEM-Decrypt, the decryption operation, that takes as input private key s
and ciphertext c0 , and outputs secret key k.

5.1

KGP-PSEC

KGP-PSEC() is defined as follows:
Input:
Output:W
s

KGP-PSEC takes no input
the PSEC-KEM public key, a point on E
the PSEC-KEM private key, a non-negative integer, 0 ≤ s < p

Steps:
1. Generate a random integer s ∈ {0, · · · , p − 1}.
2. Compute W := sP .
3. Output W and s.

5.2
5.2.1

ES-PSEC-KEM
Encryption operation

ES-PSEC-KEM-Encrypt(W, R) is defined as follows:
Input:
Output:WRkc0

the PSEC-KEM public key, a point on E
Compressed, Uncompressed, or Hybrid
an octet stringan octet string

Steps:
1. Generate a random octet string, r, of length hLen (in octet).
2. Set H := KDF (I2OSP(0, 4) k r, pLen + 16 + keyLen).
3. Parse H = t k k, such that t is an octet string of length pLen + 16 (in octet) and k is anoctet string of length keyLen (in octet).
4. Compute α := OS2IP(t) mod p.
5. Compute C1 := αP .
6. Compute Q := αW .
7. Set c2 := r ⊕ KDF (I2OSP(1, 4) k ECP2OSP(C1 , R) k PECP2OSP(Q), hLen).
8. Set c0 := ECP2OSP(C1 , R) k c2 .
9. Output (k, c0 ).
14

5.2.2

Decryption operation

ES-PSEC-KEM-Decrypt(s, c0 ) is defined as follows:
Input:
Output:Error:
Steps:s the PSEC-KEM private key, a non-negative integer, 0 ≤ s < p
c0 an octet string
k an octet string
INVALID

1. If the octet length of c0 is less than hLen, output INVALID and stop.
2. Parse c0 = g k c2 , where g and c2 are octet strings such that the octet length of c2 is hLen.
3. Compute C1 := OS2ECPP(g). If OS2ECPP outputs INVALID, output INVALID and stop.
4. Compute Q := sC1 .
5. Set r := c2 ⊕ KDF (I2OSP(1, 4) k g k PECP2OSP(Q), hLen).
6. Set h := KDF (I2OSP(0, 4) k r, pLen + 16 + keyLen).
7. Parse h = t k k, such that t is an octet string of length pLen + 16 (in octet) and k is anoctet string of length keyLen (in octet).
8. Compute α := OS2IP(t) mod p.
9. Check C1 = αP . If it holds, output k. Otherwise, output INVALID and stop.

6

Auxiliary techniques

6.1

Hash functions

The allowable hash functions are SHA-1, SHA-224, SHA-256, SHA-384 and SHA-512, described in ISO/IEC 10118-3 [2].

6.2

Key derivation functions

As a key derivation function, the function described in Section 6.2.1 is recommended. The
function is referred to as KDF1 in ISO/IEC 18033-2 [1].
6.2.1

MGF1

MGF1 is a mask generation function, parameterized by a hash function, as described in Section 6.1. MGF1(M, n) is defined as follows:
System parameters:

HashhashLen

Input:Mnmask
INVALID

Output:Error:
Steps:

a hash function
the length in octets of the hash function output, a positive
integera seed from which a mask is generated, an octet string
the octet length of the output, a positive integera mask, an octet string of length n

15

1. Let n0 be the octet length of M . If n0 + 4 is greater than the input limitation for the hashfunction, output INVALID and stop.
lmn.
2. Let cThreshold :=hashLen
3. If cThreshold > 232 , output INVALID and stop.
4. Let M 0 be the empty octet string.
5. Let counter := 0, i.e., set counter as the integer zero.
(a) Convert counter to an octet string C of length 4 octets:
C := I2OSP(counter , 4).
(b) Concatenate M and C, and apply the hash function to the result to produce a hashvalue H of length hashLen octets:
H := Hash(M k C).
(c) Concatenate M 0 and H to the octet string M 0 :M 0 := M 0 k H.
(d) Let counter := counter + 1. If counter < cThreshold , go back to step 5a.
6. Let mask be the leftmost n octets of the octet string M 0 :0mask := M00 M10 · · · Mn−1.

7. Output mask .

References[1] ISO/IEC 18033 – Information technology – Security techniques – Encryption algorithms –Part 2: Asymmetric ciphers, ISO, 2005a.
[2] ISO/IEC 10118 – Information technology – Security techniques – Hash functions – Part 3:
Dedicated Hash functions, ISO, 2004.

16

Appendix
A

Security requirements of parameters

The following conditions are required:
pLen ≥ 20
hLen ≥ 16

B

Recommended parameters for secure implementation

The following conditions are recommended:
pLen ≥ 32
KDF(256bit)= MGF1(SHA-256, hashLen = 32)

hLen = 32
R = Compressed
keyLen = 32

(256bit)

It is known that some classes of elliptic curves are vulnerable or susceptible to the known attacks in the security sense. To avoid an inappropriate choice of curves, see SECG (http://www.secg.org/).

C

ASN.1 Syntax--###################################################################
ntt-ds OBJECT IDENTIFIER ::= {itu-t(0) networkoperator(3) ntt(4401) ds(5) }id-PSEC-KEM-v2
OBJECT IDENTIFIER ::={ ntt-ds 3 1 8 }DEFINITIONS EXPLICIT TAGS ::= BEGIN-- EXPORTS All; -IMPORTS
BlockAlgorithms
FROM EncryptionAlgorithms-3 { iso(1) standard(0)encryption-algorithms(18033) part(3)asn1-module(0) algorithm-object-identifiers(0) }HashFunctionAlgs, id-sha1, NullParms
FROM DedicatedHashFunctions { iso(1) standard(0)hash-functions(10118) part(3) asn1-module(1)dedicated-hash-functions(0) };--###################################################################-- oid definitions
OID ::= OBJECT IDENTIFIER -- alias-- Synonyms -is18033-2 OID ::= { iso(1) standard(0) is18033(18033) part2(2)}id-ac OID ::= { is18033-2 asymmetric-cipher(1) }id-kem OID ::= { is18033-2 key-encapsulation-mechanism(2) }17

id-dem OID ::= { is18033-2 data-encapsulation-mechanism(3) }id-sc OID ::= { is18033-2 symmetric-cipher(4) }id-kdf OID ::= { is18033-2 key-derivation-function(5) }id-rem OID ::= { is18033-2 rsa-encoding-method(6) }id-hem OID ::= { is18033-2 himer-encoding-method(7) }id-ft OID ::= { is18033-2 field-type(8) }-- Key encapsulation mechanisms -id-kem-psec OID ::= { id-kem psec(2) }-- Data encapsulation mechanisms -id-dem-dem1 OID ::= { id-dem dem1(1) }id-dem-dem2 OID ::= { id-dem dem2(2) }id-dem-dem3 OID ::= { id-dem dem3(3) }-- Symmetric ciphers -id-sc-sc1 OID ::= { id-sc sc1(1) }id-sc-sc2 OID ::= { id-sc sc2(2) }-- Key derivation functions -id-kdf-kdf1 OID ::= { id-kdf kdf1(1) }id-kdf-kdf2 OID ::= { id-kdf kdf2(2) }-- new field types oids-- id-ft-prime-field OID ::= { id-ft prime-field(1) }-- used only to define new basis typeid-ft-characteristic-two OID ::= { id-ft characteristic-two(2) }id-ft-odd-characteristic OID ::= { id-ft odd-characteristic(3) }id-ft-characteristic-two-basis OID ::={ id-ft-characteristic-two basisType(1) }charTwoPolynomialBasis OID ::={ id-ft-characteristic-two-basis
charTwoPolynomialBasis(1) }id-ft-odd-characteristic-basis OID ::= { id-ft-odd-characteristic
basisType(1)}oddCharPolynomialBasis OID ::= {id-ft-odd-characteristic-basis
oddCharPolynomialBasis(1)}-- MGF1 in PKCS #1 is equivalent to KDF1 here-- id-mgf1 should be used instead of id-kdf-kdf1 for compatibility-- with existing implementations
alg-mgf1-sha1 RsaesKeyDerivationFunction ::= {algorithm id-mgf1,
parameters HashFunction : alg-sha1}
alg-sha1 HashFunction ::= {algorithm id-sha1,
parameters NullParms : NULL}
pkcs-1 OID ::= {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 1}
id-mgf1 OBJECT IDENTIFIER ::= {pkcs-1 8}
id-itu-sha1 OBJECT IDENTIFIER ::= { iso(1)identified-organization(3) oiw(14)secsig(3) algorithms(2) 26 }id-itu-sha224 OBJECT IDENTIFIER ::= {{ joint-iso-itu-t(2)18country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 4 }id-itu-sha256 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 1 }id-itu-sha384 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 2 }id-itu-sha512 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 3 }id-camellia128-cbc OBJECT IDENTIFIER ::=iso(1) member-body(2) 392 200011 61 security(1)algorithm(1) symmetric-encryption-algorithm(1) camellia128-cbc(2)id-aes OBJECT IDENTIFIER ::= { joint-iso-itu-t(2) country(16) us(840)organization(1) gov(101) csor(3)_ nistAlgorithms(4) 1 }id-aes128-CBC OBJECT IDENTIFIER ::= { id-aes 2 }--###################################################################-- KEM information objects
KeyEncapsulationMechanism ::= AlgorithmIdentifier {{ KEMAlgorithms }}KEMAlgorithms ALGORITHM ::= {{ OID id-kem-psec PARMS PsecKemParameters } |{ OID id-PSEC-KEM-v2 PARMS PsecKemParameters },... -- Expect additional algorithms -}--###################################################################-- PSEC-KEM-- an element of the group given in PsecKemParameters (may be 0)
PsecKemPrivateKey ::= INTEGER
PsecKemPublicKey ::= FieldElement
PsecKemParameters ::= SEQUENCE {group Group OPTIONAL,
keyDerivationFunction KeyDerivationFunction,
seedLength INTEGER (1..MAX),
keyLength KeyLength -- Length by byte}-- DEM specifications
DataEncapsulationMechanism ::= AlgorithmIdentifier {{DEMAlgorithms}}
DEMAlgorithms ALGORITHM ::= {{ OID id-dem-dem1 PARMS Dem1Parameters } |{ OID id-dem-dem2 PARMS Dem2Parameters } |{ OID id-dem-dem3 PARMS Dem3Parameters },... -- Expect additional algorithms -}Dem1Parameters ::= SEQUENCE{
symmetricCipher SymmetricCipher,mac MacAlgorithm
19

}
Dem2Parameters ::= SEQUENCE{
symmetricCipher SymmetricCipher,mac MacAlgorithm,
labelLength INTEGER (0..MAX)}
Dem3Parameters ::= SEQUENCE{
mac MacAlgorithm,
msgLength INTEGER (0..MAX)}--###################################################################-- finite field, group, and elliptic curve representations
Group ::= CHOICE {groupOid OBJECT IDENTIFIER,
groupHashId OCTET STRING, -- defined in RFC2528
groupParameters GroupParameters}
GroupParameters ::= CHOICE {explicitFiniteFieldSubgroup[0] ExplicitFiniteFieldSubgroupParameters,
ellipticCurveSubgroup[1] EllipticCurveSubgroupParameters}
ExplicitFiniteFieldSubgroupParameters ::= SEQUENCE {fieldID FieldID {{FieldTypes}},
generator FieldElement,
subgroupOrder INTEGER,
subgroupIndex INTEGER}FIELD-ID ::= TYPE-IDENTIFIER
FieldID { FIELD-ID:IOSet } ::= SEQUENCE {fieldType FIELD-ID.&id({IOSet}),parameters FIELD-ID.&Type({IOSet}{@fieldType}) OPTIONAL}
FieldTypes FIELD-ID ::= {{ Prime-p IDENTIFIED BY prime-field } |{ Characteristic-two IDENTIFIED BY characteristic-two-field }|{ Odd-characteristic IDENTIFIED BY id-ft-odd-characteristic },... -- expect additional field types}-- prime fieds
Prime-p ::= INTEGER-- characteristic two fields
CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER-- when basis is gnBasis then the basis shall be an optimal-- normal basis of Type T where T is determined as follows:-- if an ONB of Type 2 exists for the given value of m then-- T shall be 2, otherwise if an ONB of Type 1 exists for the-- given value of m then T shall be 1, otherwise T shall be20

-- the least value for which an ONB of Type T exists for the-- given value of m-- when basis is gnBasis then m shall not be divisible by 8-- note: the above rule is from ANSI X9.62-- note: for the given m and T the ONB is unique
Characteristic-two ::= SEQUENCE {m INTEGER,-- extension degreebasis CHARACTERISTIC-TWO.&id({BasisTypes}),parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})}
BasisTypes CHARACTERISTIC-TWO ::= {{ NULL IDENTIFIED BY gnBasis } |{ Trinomial IDENTIFIED BY tpBasis } |{ Pentanomial IDENTIFIED BY ppBasis } |{ CharTwoPolynomial IDENTIFIED BY charTwoPolynomialBasis },... -- expect additional basis types}
Trinomial ::= INTEGER
Pentanomial ::= SEQUENCE {k1 INTEGER,
k2 INTEGER,
k3 INTEGER}-- characteric two general irreducible polynomial representation-- the irreducible polymial-- a(n)*x^n + a(n-1)*x^(n-1) + ... + a(1)*x + a(0)-- is encoded in the bit string with a(n) in the first bit, the-- following coefficients in the following bit positions and a(0)-- in the last bit of the bit string (one could omit a(n) and a(0)-- but it may be simpler and less error-prone to leave them in-- the encoding)-- the degree of the polynomial is to be inferred from the length-- of the bit string
CharTwoPolynomial ::= BIT STRING-- odd characteristic extension fields
ODD-CHARACTERISTIC ::= TYPE-IDENTIFIER
Odd-characteristic ::= SEQUENCE {characteristic INTEGER(3..MAX),
degree INTEGER(2..MAX),
basis ODD-CHARACTERISTIC.&id({OddCharBasisTypes}),parameters ODD-CHARACTERISTIC.&Type({OddCharBasisTypes}{@basis})}
OddCharBasisTypes ODD-CHARACTERISTIC ::= {{ OddCharPolynomial IDENTIFIED BY oddCharPolynomialBasis },... -- expect additional basis types}-- the monic irreducible polynomial is encoded as follows-- the leading coefficient is ignored-- the remaining coefficients define an element of the finite field21

-- which is encoded in an octet string using FE2OSP
OddCharPolynomial ::= FieldElement
EllipticCurveSubgroupParameters ::= SEQUENCE {version INTEGER { ecpVer1(1) } (ecpVer1),
fieldID FieldID {{ FieldTypes }},curve Curve,
generator ECPoint,-- Base point G
subgroupOrder INTEGER, -- Order mu of the base point
subgroupIndex INTEGER, -- The integer nu = #E(F)/mu...
}
Curve ::= SEQUENCE {aCoeff FieldElement,bCoeff FieldElement,
seed BIT STRING OPTIONAL}--###################################################################-- auxiliary definitions
FieldElement ::= OCTET STRING -- obtained through FE2OSPECPoint ::= OCTET STRING -- obtained through EC2OSPKeyLength ::= INTEGER (1..MAX)
MacAlgorithm ::= AlgorithmIdentifier {{ MACAlgorithms }}MACAlgorithms ALGORITHM ::= {{ OID hMAC-SHA1 PARMS NULL } ,... -- Expect additional algorithms -}HashFunction ::= AlgorithmIdentifier {{ HashFunctionAlgorithms }}HashFunctionAlgorithms ALGORITHM ::= {HashFunctionAlgs | -- from 10118-3{ NULL IDENTIFIED BY id-itu-sha1 } |{ NULL IDENTIFIED BY id-itu-sha224 } |{ NULL IDENTIFIED BY id-itu-sha256 } |{ NULL IDENTIFIED BY id-itu-sha384 } |{ NULL IDENTIFIED BY id-itu-sha512 },... -- expect additional algorithms}
KeyDerivationFunction ::= AlgorithmIdentifier {{ KDFAlgorithms }}KDFAlgorithms ALGORITHM ::= {{ OID id-kdf-kdf1 PARMS HashFunction } |{ OID id-kdf-kdf2 PARMS HashFunction } |{ OID id-mgf1 PARMS HashFunction },... -- Expect additional algorithms -}SymmetricCipher ::= AlgorithmIdentifier {{ SymmetricAlgorithms }}SymmetricAlgorithms ALGORITHM ::= {{ OID id-sc-sc1 PARMS BlockCipher } |{ OID id-sc-sc2 PARMS BlockCipher } |{ OID id-camellia128-cbc PARMS BlockCipher } |{ OID id-aes128-CBC PARMS BlockCipher },22

... -- Expect additional algorithms -}BlockCipher ::= AlgorithmIdentifier {{ BlockAlgorithms }}--###################################################################-- external OIDs-- HMAC-SHA1
hMAC-SHA1 OID ::= {iso(1) identified-organization(3) dod(6) internet(1) security(5)mechanisms(5) 8 1 2 }-- X9.62 finite field and basis types
ansi-X9-62 OID ::= { iso(1) member-body(2) us(840) 10045 }
id-fieldType OID ::= { ansi-X9-62 fieldType(1) }prime-field OID ::= { id-fieldType 1 }characteristic-two-field OID ::= { id-fieldType 2 }-- characteristic two basis
id-characteristic-two-basis OID ::= { characteristic-two-fieldbasisType(3) }gnBasis OID ::= { id-characteristic-two-basis 1 }tpBasis OID ::= { id-characteristic-two-basis 2 }ppBasis OID ::= { id-characteristic-two-basis 3 }--###################################################################-- Cryptographic algorithm identification -ALGORITHM ::= CLASS {&id OBJECT IDENTIFIER UNIQUE,&Type OPTIONAL}
WITH SYNTAX { OID &id [PARMS &Type] }AlgorithmIdentifier { ALGORITHM:IOSet } ::= SEQUENCE {algorithm ALGORITHM.&id( {IOSet} ),parameters ALGORITHM.&Type( {IOSet}{@algorithm} ) OPTIONAL}
END -- EncryptionAlgorithms-2 --23