Specification of Data Types and Conversions
version 1.0
NTT Secure Platform Laboratories,
NTT Corporation
March 2, 2015

1

Introduction

This document provides the specification of data operations using several diﬀerent data types[1].

2

Notations2.1

Notationsbit
bit string
octet
octet stringRZN
Zna := b
Fpm
O
∥
⌈y⌉
⌊y⌋
a|b
a mod ma−1 mod m
E
E(Fp )
E(Fpm )
E[q], E(Fp )[q], E(Fpm )[q]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.
the set of all integers x such that 0 ≤ x < n and x is prime to n.
an operation of assigning b to a.
a finite field with pm elements, where p 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.
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 satisfiesm|(a − b).
for a ∈ Z, m ∈ N, the least non-negative integer b that satisfies
ab mod m = 1.
elliptic curve
the subgroup of Fp -rational points.
the subgroup of Fpm -rational points.
the subgroup of q-torsion point of E, E(Fp ) and E(Fpm )Elliptic Curve Parameter

An elliptic curve parameter E in this document is specified by the following 8-tuple [2](Curve-ID, pb , pe , A, B, G = (x, y), q, h)
where the components have the following meanings:• Curve-ID is an identifier with which the curve can be referenced.
• pb is an odd prime specifying base field.
• pe is an irreducible polynomial specifying extension field with degree m.
• A and B are the coeﬃcients of the equation y 2 = x3 + Ax + B, (A, B ∈ Fqm ) defining E• G = (x, y) is the base point, i.e., a point with x and y being its x- and y-coordinates in
E, respectively.
2• q is the prime order of the group generated by G.
• h is a multiple of the cofactor of G in E.
In this document, we define h′ as a multiple of h in addtion to 8-tuple. By using this h′ inthe hashing to point function, we can calculate the hashing to point function in high speed.

3

Data types and Conversions

The scheme specified in this document involves operations using several diﬀerent 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 diﬀerent 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 + · · · + β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.

3

'

$

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

Octet String M%

Mi is an octet.

x, y : Field Element



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

Field Element a

FE2IP(a) I2FEP(x)

O
S2

I2
O

SP
(x
,n
IP
)
(M
)

6

- Non-Negative

Integer x

&

%

I2

SS
o
SS
SS
SS
SS
SS
SS
w
SS


BS2OSP(B)

OS2BSP(M )

>


 


a) 

7
(

P

S  )
2O  M
FE  EP(


 F


 S2


O







=

/
'
$




x,
P(
BS

l)

B)
P(
2I

BS

?

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
∑
i=0

4

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⌈ ⌉lan 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.

5

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. An finite field element
should be represented as a polynomial with subfiled coeﬃcients, which can be represented as asequence of the coeﬃcients. Informally, the idea is simply to view the sequence of the coeﬃcientsas the radix-pm representation of the base field elements, where pm is the number of the subfield
elements. Formally, the conversion routine, FE2IP(a), is specified as follows:
System parameters:

Fpm2 ⊇ Fpm1

Input:
Output:Steps:

ax

a field extension with an irreduceble polynomial Irr(Fpm2 /Fpm1 ; β) i.e.
Fpm2≃
Fpm1 [β]/(Irr(Fpm2 /Fpm1 ; β))a field element in Fpm2
an integer in {0, . . . , pm2 − 1}This Conversion procedure FE2IP is inductively defined. Convert field element a to integer
x as follows:
If m2 = 1 i.e. field Fpm2 is prime field:
Field element a must be represented as an integer in {0, . . . , p − 1}.
1. Let x := a.
6

2. Output x.
Else m2 > 1:
For the field extension Fpm2 ⊇ Fpm1 , we assume that FE2IP is defined on Fpm1
and outputs an integer in {0, . . . , pm1 }. Field element a must be represented asa polynomial of at most (m2 /m1 − 1)-th degree with coeﬃcients in the subfield
Fpm1 . Let β be the variable of the polynomial.
1. Determine the coeﬃcients ai ∈ Fpm1 for i ∈ {0, . . . , m2 /m1 −1} that satisfy
m2 /m1 −1∑a=ai β i .

i=0

2. Compute
m2 /m1 −1

x :=∑FE2IP(ai )(pm1 )i .

i=0

3: 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 subfield coeﬃcients, and it can be represented asa sequence of the coeﬃcients. Informally, the idea is to represent the integer with radix-pm
positional number system where pm is the number of the subfield element, and then convert theeach digit to the each coeﬃcient of the polynomial. Formally, the conversion routine, I2FEP(x),is specified as follows:
System parameters:

Fpm2 ⊇ Fpm1

Input:
Output:Steps:xaa field extension with an irreduceble polynomial Irr(Fpm2 /Fpm1 ; β) i.e.
Fpm2≃
Fpm1 [β]/(Irr(Fpm2 /Fpm1 ; β))an integer in {0, . . . , pm2 − 1}a field element in Fpm2

This Conversion procedure I2FEP is inductively defined. Convert integer x to field elementa as follows:
If m2 = 1 i.e. Fpm2 is prime field:
A field element of Fpm2 must be represented as an integer in {0, . . . , p − 1}.
1. Let a := x.
2. Output a.
Else m2 > 1:
For the field extension Fpm2 ⊇ Fpm1 , we assume that I2FEP is defined on
integers in {0, . . . , pm1 − 1} and outputs an element in Fpm1 .
A field element of Fpm2 must be represented as a polynomial of at most (m2 /m1 −1)-th degree with coeﬃcients in Fpm1 . Let β be the variable of the polynomial.
1. Expand x into it’s radix pm1 representation xi ∈ {0, . . . , pm1 − 1} for i ∈{0, . . . , m2 /m1 − 1} that satisfies
m2 /m1 −1

∑

x=

i=0

7

xi (pm1 )i .

2. Compute
m2 /m1 −1

a :=∑I2FEP(xi )β i .

i=03: Output a.

3.9

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

Fpmn

Input:
Output:Steps:aM

a finite field with pm elements where p is a prime, and m > 0
is an integer⌈⌉
m log2 p
an integer equivalent to8
a field element in Fpm
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 pm elements where p is a prime, and m > 0
is an integer⌉⌈
m log2 pnan integer equivalent to8M
an octet stringaa field element in Fpm
INVALID

Fpm

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 oﬀ, the leftmost octet indicates that point compression is oﬀ, 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:8E
an elliptic curve parameterPa point on an elliptic curve over Fpm
R Compressed, Uncompressed, or Hybrid
 M an octet string of length n
if P = O, n = 1⌈⌉m log2 p
n=+1
if P ̸= O and R is Compressed,
where
⌈ 8
⌉


m log2 p
+ 1 if P ̸= O and R is Uncompressed or Hybrid.
 n=2
8System parameters:
Input:
Output: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) ̸= 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 p 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 ̸= 0.
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 ∥ X.
3. If P = (x, y) ̸= 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) ∥ X ∥ Y .
4. If P = (x, y) ̸= 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. Set ỹ := 0 if y = 0, otherwise set ỹ := yi mod 2, where y = ym−1 β m−1 + · · · +y1 β + y0 , and i is the smallest integer such that yi ̸= 0.
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 ∥ X ∥ Y .

9

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 p
an octet string of length n =+ 1, or⌈ 8⌉
m log2 p
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+ 1 octets, proceed as follows:
2. If M has length8⌈⌉m log2 p
2.1. Parse M = L ∥ 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. Compute the field element w := x3 +Ax+B, and compute a square root γ of w
in Fpm . Output INVALID and stop if there are no square roots in Fpm . Otherwise
set y = 0 if γ = 0, otherwise set y := γ if γi ≡ ỹ mod 2, and set y := −γ if
γi ̸≡ ỹ mod 2, where γ = γm−1 β m−1 + · · · + γ1 β + γ0 , and i is the smallest integer
such that γi ̸= 0.
2.5. Output P := (x, y).
⌉⌈m log2 p+ 1 octets, proceed as follows:
3. If M has length 2
8⌈m log2 p
8⌉

3.1. Parse M = L ∥ X ∥ Y as a single octet L followed byoctets X followed⌈⌉
m log2 pbyoctets 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).
10

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
⌈ Fpm ⌉
m log2 p
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) ̸= O, output FE2OSP(x) .

4

Auxiliary

4.1

Key Derivation Functions (KDF)

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

MGF1

MGF1 is a mask generation function, parameterized by a hash function. 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

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.
⌈⌉n
2. Let cThreshold :=.
hashLen
3. If cThreshold > 232 , output INVALID and stop.
4. Let M ′ be the empty octet string.
5. Let counter := 0, i.e., set counter as the integer zero.
11

(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 ∥ C).
(c) Concatenate M ′ and H to the octet string M ′ :M ′ := M ′ ∥ 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 ′ :′mask := M0′ M1′ · · · Mn−1.

7. Output mask .
where, concrete hash function is SHA-256, SHA-384, SHA-512.

4.2Group Membership Test

GroupMembershipTest(E, P ) is a test function that an elliptic curve point is on the correct
curve and group. GroupMembershipTest is defined as follows:
Input:
Output:Error:
Steps:

EP = (x, y)bool
INVALIDan elliptic curve parameteran elliptic curve point
an integer in {0, 1}

1. If P = O, then output 1.
2. If P does not satisfy the elliptic curve equation i.e.
y 2 ̸= x3 + Ax + B,
output 0.
3. If h ̸= 1 and qP ̸= O , then output 0.
4. Output 1.

4.3
4.3.1

Hashing to Point
IHF1

Bit strign should be converted to hashed non-negative integer less than an assainged integer
as described in this section. Formally, the conversion routine, IHF1(s, n, Hash) is defined asfollows:
12

Input:Output:Steps:snHashv ∈ Zna bit string
an integera hash function

1. Set hashLen be the length of the output of the hash funtion Hash.
2. Set h0 be the zero string of length hashLen.
3. h1 := Hash(h0 ||s).
4. a1 := OS2IP(h1 ).
5. h2 := Hash(h1 ||s).
6. a2 := OS2IP(h2 ).
7. v := 2hlen a1 + a2 mod n.
8. Output v.
4.3.2

BS2FQEBit stirng should be converted to hashed finite field element as described in this section. Formally,
the conversion routine, BS2FQE(s, Hash, Fpm ) is defined as follows:
Input:

Output:Steps:

s
Hash
Fpm
a

a bit stringa hash function
a finite field with pm elements where p is a prime, and m > 0 is an integer.
a element in Fpm

1. For 0 ≤ i < m,(a) C := I2OSP(i, 2)(b) ti := IHF1(C||s, p, Hash)
2. a :=m−1∑

ti β i , where β is the variable of the polynomial.

i=0

3. Output a.
4.3.3

Hashing to Point

Hashed value should be converted to elliptic curve point as described in this section. Formally,
the conversion routine, HashingToPoint(E, M ), is specified as follows:
Input:
Output:Steps:E
M
P

an elliptic curve parameter.
an octet string
an elliptic curve point

1. Let i := 0.
13

2. C := I2OSP(i, 2).
3. x0 := BS2FQE(C||M, Hash, Fpm ) ∈ Fpm .
4. t := x30 + Ax0 + B.
5. If t = 0, then output P = (x0 , 0).
6. If t is not square in Fpm , put i := i + 1 and return step 2.
7. Set ±α are square roots of t.
8. Set y1 := FE2IP(α) and y2 := FE2IP(−α)
9. If y1 > y2 , then put y0 := −α. Else put y0 := α.
10. P := (x0 , y0 ).
11. Output h′ P .

References[1] IEEE Standard Specifications for Public-Key Cryptography, IEEE Std 1363-2000.
[2] K. Kasamatsu, S. Kanno, T. Kobayashi and Y. Kawahara: Barreto-Naehrig Curves draftKasamatsu-bncurves-01. Network Working Group Internet-Draft: (2014).

14