ISO/IEC 18033-2:2006
(Main)Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric ciphers
Information technology — Security techniques — Encryption algorithms — Part 2: Asymmetric ciphers
ISO/IEC 18033-2:2006 specifies encryption systems (ciphers) for the purpose of data confidentiality. The primary purpose of encryption (or encipherment) techniques is to protect the confidentiality of stored or transmitted data. An encryption algorithm is applied to data (often called plaintext or cleartext) to yield encrypted data (or ciphertext); this process is known as encryption. The encryption algorithm should be designed so that the ciphertext yields no information about the plaintext except, perhaps, its length. Associated with every encryption algorithm is a corresponding decryption algorithm, which transforms ciphertext back into its original plaintext. An asymmetric, i.e. public-key, encryption scheme allows a sender to use a recipient's public key to transmit an encryption of a message to the receiver, who can use his secret key to decrypt the given ciphertext, thereby obtaining the original message. Such a scheme should be secure in the sense that no information about the message should be leaked to a (resource-bounded) attacker, even if that attacker mounts a so-called 'chosen ciphertext' attack, in which he may obtain decryptions of other ciphertexts. This is the strongest type of attack that has been proposed for a public-key encryption scheme. ISO/IEC 18033-2:2006 specifies the functional interface of such a scheme, and in addition specifies a number of particular schemes that appear to be secure against chosen ciphertext attack. The different schemes offer different trade-offs between security properties and efficiency.
Technologies de l'information — Techniques de sécurité — Algorithmes de chiffrement — Partie 2: Chiffres asymétriques
General Information
Relations
Standards Content (Sample)
INTERNATIONAL ISO/IEC
STANDARD 18033-2
First edition
2006-05-01
Information technology — Security
techniques — Encryption algorithms —
Part 2:
Asymmetric ciphers
Technologies de l'information — Techniques de sécurité — Algorithmes
de chiffrement —
Partie 2: Chiffres asymétriques
Reference number
©
ISO/IEC 2006
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.
© ISO/IEC 2006
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2006 – All rights reserved
Contents Page
1 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Normative references . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3 De¯nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
4 Symbols and notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Mathematical conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.1 Functions and algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 Bit strings and octet strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.4 Elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6 Cryptographic transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1 Cryptographic hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.2 Key derivation functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
6.3 MAC algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.4 Block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.5 Symmetric ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7 Asymmetric ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.1 Plaintext length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
7.2 The use of labels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.3 Ciphertext format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.4 Encryption options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.5 Method of operation of an asymmetric cipher . . . . . . . . . . . . . . . . . . . 22
7.6 Allowable asymmetric ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8 Generic hybrid ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
8.1 Key encapsulation mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.2 Data encapsulation mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.3 HC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
9 Constructions of data encapsulation mechanisms . . . . . . . . . . . . . . . . . . . . 26
9.1 DEM1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
9.2 DEM2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
9.3 DEM3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
10 ElGamal-based key encapsulation mechanisms . . . . . . . . . . . . . . . . . . . . . 30
10.1 Concrete groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
10.2 ECIES-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
10.3 PSEC-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
10.4 ACE-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
11 RSA-based asymmetric ciphers and key encapsulation mechanisms . . . . . . . . . . 39
11.1 RSA key generation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
11.2 RSA Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
11.3 RSA encoding mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
11.4 RSAES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
11.5 RSA-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
12 Ciphers based on modular squaring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
© ISO/IEC 2006 – All rights reserved iii
12.1 HIME key generation algorithms . . . . . . . . . . . . . 45
12.2 HIME encoding mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
12.3 HIME(R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
AnnexA (normative) ASN.1 syntax for object identi¯ers . . . . . . . . 51
Annex B (informative) Security considerations . . . . . . . . . . . . . . . . . . . . . . . 61
B.1 MAC algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
B.2 Block ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
B.3 Symmetric ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
B.4 Asymmetric ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
B.5 Key encapsulation mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
B.6 Data encapsulation mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . 66
B.7 Security of HC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
B.8 Intractability assumptions related to concrete groups . . . . . . . . . . . . . . . 68
B.9 Security of ECIES-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
B.10 Security of PSEC-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
B.11 Security of ACE-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
B.12 The RSA inversion problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
B.13 Security of RSAES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
B.14 Security of RSA-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
B.15 Security of HIME(R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Annex C (informative) Test vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
C.1 Test vectors for DEM1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
C.2 Test vectors for ECIES-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
C.3 Test vectors for PSEC-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
C.4 Test vectors for ACE-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
C.5 Test vectors for RSAES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
C.6 Test vectors for RSA-KEM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
C.7 Test vectors for HC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
C.8 Test vectors for HIME(R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
iv © ISO/IEC 2006 – All rights reserved
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are
members of ISO or IEC participate in the development of International Standards through technical
committees established by the respective organization to deal with particular fields of technical
activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other
international organizations, governmental and non-governmental, in liaison with ISO and IEC, also
take part in the work. In the field of information technology, ISO and IEC have established a joint
technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives,
Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft
International Standards adopted by the joint technical committee are circulated to national bodies for
voting. Publication as an International Standard requires approval by at least 75 % of the national
bodies casting a vote.
ISO/IEC 18033-2 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information
technology, Subcommittee SC 27, IT Security techniques.
ISO/IEC 18033 consists of the following parts, under the general title Information technology —
Security techniques — Encryption algorithms:
— Part 1: General
— Part 2: Asymmetric ciphers
— Part 3: Block ciphers
— Part 4: Stream ciphers
© ISO/IEC 2006 – All rights reserved v
Introduction
The International Organization for Standardization (ISO) and International Electrotechnical
Commission (IEC) draw attention to the fact that it is claimed that compliance with this International
Standard may involve the use of patents.
The ISO and IEC take no position concerning the evidence, validity and scope of this patent right.
The holder of this patent right has assured the ISO and IEC that he is willing to negotiate licences
under reasonable and non-discriminatory terms and conditions with applicants throughout the world.
In this respect, the statement of the holder of this patent right is registered with the ISO and IEC.
Information may be obtained from:
ISO/IEC JTC 1/SC 27 Standing Document 8 (SD8) "Patent Information"
Standing Document 8 (SD8) is publicly available at: http://www.ni.din.de/sc27
Attention is drawn to the possibility that some of the elements of this International Standard may be
the subject of patent rights other than those identified above. ISO and IEC shall not be held
responsible for identifying any or all such patent rights.
vi © ISO/IEC 2006 – All rights reserved
INTERNATIONAL STANDARD
Information technology — Security techniques — Encryption
algorithms —
Part 2:
Asymmetric ciphers
1 Scope
This part of ISO/IEC 18033 specifies several asymmetric ciphers. These specifications prescribe the
functional interfaces and correct methods of use of such ciphers in general, as well as the precise functionality
and cipher text format for several specific asymmetric ciphers (although conforming systems may choose to
use alternative formats for storing and transmitting cipher-texts).
A normative annex (Annex A) gives ASN.1 syntax for object identifiers, public keys, and parameter structures
to be associated with the algorithms specified in this part of ISO/IEC 18033.
However, these specifications do not prescribe protocols for reliably obtaining a public key, for proof of
possession of a private key, or for validation of either public or private keys; see ISO/IEC 11770-3 for
guidance on such key management issues.
The asymmetric ciphers that are specified in this part of ISO/IEC 18033 are indicated in Clause 7.6.
NOTE Briefly, the asymmetric ciphers are:
⎯ ECIES-HC; PSEC-HC; ACE-HC: generic hybrid ciphers based on ElGamal encryption;
⎯ RSA-HC: a generic hybrid cipher based on the RSA transform;
⎯ RSAES: the OAEP padding scheme applied to the RSA transform;
⎯ HIME(R): a scheme based on the hardness of factoring.
2 Normative references
The following referenced documents are indispensable for the application of this document. For dated
references, only the edition cited applies. For undated references, the latest edition of the referenced document
(including any amendments) applies.
ISO/IEC 9797-1:1999, Information technology ― Security techniques ― Message Authentication Codes
(MACs) ― Part 1: Mechanisms using a block cipher
ISO/IEC 9797-2:2002, Information technology ― Security techniques― Message Authentication Codes
(MACs) ― Part 2: Mechanisms using a dedicated hash-function
ISO/IEC 10118-2:2000, Information technology ― Security techniques ― Hash-functions ― Part 2: Hash-
functions using an n-bit block cipher
ISO/IEC 10118-3:2004, Information technology ― Security techniques ― Hash-functions ― Part 3:
Dedicated hash-functions
ISO/IEC 18033-3:2005, Information technology ― Security techniques ― Encryption algorithms ―
Part 3: Block ciphers
© ISO/IEC 2006 – All rights reserved 1
3 Definitions
For the purposes of this document, the following terms and definitions apply.
NOTE Where appropriate, forward references are given to clauses which contain more detailed definitions and/or further
elaboration.
3.1
asymmetric cipher
system based on asymmetric cryptographic techniques whose public transformation is used for encryption and
whose private transformation is used for decryption
[ISO/IEC 18033-1]
NOTE See Clause 7.
3.2
asymmetric cryptographic technique
cryptographic technique that uses two related transformations, a public transformation (defined by the public
key) and a private transformation (defined by the private key). The two transformations have the property that,
given the public transformation, it is computationally infeasible to derive the private transformation.
[ISO/IEC 11770-1:1996]
3.3
asymmetric key pair
pair of related keys, a public key and a private key, where the private key defines the private transformation
and the public key defines the public transformation
[ISO/IEC 9798-1:1997]
NOTE See Clauses 7, 8.1.
3.4
bit
one of the two symbols `0' or `1'
NOTE See Clause 5.2.1.
3.5
bit string
sequence of bits
NOTE See Clause 5.2.1.
3.6
block
string of bits of a defined length
[ISO/IEC 18033-1]
NOTE In this part of ISO/IEC 18033, a block will be restricted to be an octet string (interpreted in a natural way as a bit string).
3.7
block cipher
symmetric cipher with the property that the encryption algorithm operates on a block of plain-text, i.e., a
string of bits of a defined length, to yield a block of cipher text
[ISO/IEC 18033-1]
NOTE See Clause 6.4.
NOTE In this part of ISO/IEC 18033, plaintext/cipher text blocks will be restricted to be octet strings (interpreted in a natural way
as bit strings).
2 © ISO/IEC 2006 – All rights reserved
3.8
cipher
cryptographic technique used to protect the confidentiality of data, and which consists of three component
processes: an encryption algorithm, a decryption algorithm, and a method for generating keys
[ISO/IEC 18033-1]
3.9
cipher text
data which has been transformed to hide its information content
[ISO/IEC 10116:1997]
3.10
concrete group
explicit description of a finite abelian group, together with algorithms for performing the group operation and
for encoding and decoding group elements as octet strings
NOTE See Clause 10.1.
3.11
cryptographic hash function
function that maps octet strings of any length to octet strings of fixed length, such that it is computationally
infeasible to find correlations between inputs and outputs, and such that given one part of the output, but not
the input, it is computationally infeasible to predict any bit of the remaining output. The precise security
requirements depend on the application.
NOTE See Clause 6.1.
3.12
data encapsulation mechanism
cryptographic mechanism, based on symmetric cryptographic techniques, which protects both the
confidentiality and the integrity of data
NOTE See Clause 8.2.
3.13
decryption
reversal of the corresponding encryption
[ISO/IEC 11770-1:1996]
3.14
decryption algorithm
process which transforms ciphertext into plaintext
[ISO/IEC 18033-1]
3.15
encryption
(reversible) transformation of data by a cryptographic algorithm to produce cipher text, i.e., to hide the
information content of the data
[ISO/IEC 9797-1]
© ISO/IEC 2006 – All rights reserved 3
3.16
explicitly given finite field
finite field that is represented explicitly in terms of its characteristic and a multiplication table for a basis of
the field over the underlying prime field
NOTE See Clause 5.3.
3.17
encryption algorithm
process which transforms plaintext into cipher text
[ISO/IEC 18033-1]
3.18
encryption option
option that may be passed to the encryption algorithm of an asymmetric cipher, or of a key encapsulation
mechanism, to control the formatting of the output cipher text
NOTE See Clauses 7, 8.1.
3.19
field
mathematical notion of a field, i.e., a set of elements, together with binary operations for addition and
multiplication on this set, such that the usual field axioms apply
3.20
finite abelian group
group such that the underlying set of elements is finite, and such that the underlying binary operation is
commutative
3.21
finite field
field such that the underlying set of elements is finite
3.22
group
mathematical notion of a group, i.e., a set of elements, together with a binary operation on this set, such that
the usual group axioms apply
3.23
hybrid cipher
asymmetric cipher that combines both asymmetric and symmetric cryptographic techniques
3.24
key
sequence of symbols that controls the operation of a cryptographic transformation (e.g., encryption,
decryption)
[ISO/IEC 11770-1:1996]
3.25
key derivation function
a function that maps octet strings of any length to octet strings of an arbitrary, specified length, such that it is
computationally infeasible to find correlations between inputs and outputs, and such that given one part of the
output, but not the input, it is computationally infeasible to predict any bit of the remaining output. The
precise security requirements depend on the application.
NOTE See Clause 6.2.
4 © ISO/IEC 2006 – All rights reserved
3.26
key encapsulation mechanism
similar to an asymmetric cipher, but the encryption algorithm takes as input a public key and generates a
secret key and an encryption of this secret key
NOTE See Clause 8.1.
3.27
key generation algorithm
method for generating asymmetric key pairs
NOTE See Clauses 7, 8.1.
3.28
label
octet string that is input to both the encryption and decryption algorithms of an asymmetric cipher, and of a
data encapsulation mechanism. A label is public information that is bound to the cipher text in a non-
malleable way
NOTE See Clauses 7, 8.2.
3.29
length
length of a string of digits or the representation of an integer
Specifically:
(1) length of a bit string is the number of bits in the string
NOTE See Clause 5.2.1.
(2) length of an octet string is the number of octets in the string
NOTE See Clause 5.2.2.
(3) bit length of a non-negative integer n is the number of bits in its binary representation,
i.e., dlog (n + 1)
NOTE See Clause 5.2.4.
(4) octet length of a non-negative integer n is the number of digits in its representation base 256, i.e.,
dlog (n + 1)
NOTE See Clause 5.2.4.
3.30
message authentication code (MAC)
string of bits which is the output of a MAC algorithm
[ISO/IEC 9797-1]
NOTE See Clause 6.3.
NOTE In this part of ISO/IEC 18033, a MAC will be restricted to be an octet string (interpreted in a natural way as a bit string).
3.31
MAC algorithm
algorithm for computing a function which maps strings of bits and a secret key to fixed-length strings of bits,
satisfying the following two properties:
- for any key and any input string, the function can be computed efficiently;
- for any fixed key, and given no prior knowledge of the key, it is computationally infeasible to compute the
function value on any new input string, even given knowledge of the set of input strings and corresponding
function values, where the value of the ith input string may have been chosen after observing the value of the
first i - 1 function values.
[ISO/IEC 9797-1]
NOTE See Clause 6.3.
NOTE In this part of ISO/IEC 18033, the input and output strings of a MAC algorithm will be restricted to be octet strings
(interpreted in a natural way as bit strings).
© ISO/IEC 2006 – All rights reserved 5
3.32
octet
a bit string of length 8
NOTE See Clause 5.2.2.
3.33
octet string
a sequence of octets
NOTE See Clause 5.2.2.
NOTE When appropriate, an octet string may be interpreted as a bit string, simply by concatenating all of the component octets.
3.34
plaintext
unencrypted information
[ISO/IEC 10116:1997]
3.35
prefix free set
a set S of bit/octet strings such that there do not exist strings x ≠ y ∈ S such that x is a prefix of y
3.36
primitive
a function used to convert between data types
3.37
private key
the key of an entity's asymmetric key pair which should only be used by that entity
[ISO/IEC 11770-1:1996]
NOTE See Clauses 7, 8.1.
3.38
public key
the key of an entity's asymmetric key pair which can be made public
[ISO/IEC 11770-1:1996]
NOTE See Clauses 7, 8.1.
3.39
secret key
key used with symmetric cryptographic techniques by a specified set of entities
[ISO/IEC 11770-3:1999]
3.40
symmetric cipher
cipher based on symmetric cryptographic techniques that uses the same secret key for both the
encryption and decryption algorithms
[ISO/IEC 18033-1]
3.41
system parameters
choice of parameters that selects a particular cryptographic scheme or function from a family of cryptographic
schemes or functions
6 © ISO/IEC 2006 – All rights reserved
4 Symbols and notation
For the purposes of this document, the following symbols and notation apply.
NOTE Where appropriate, forward references are given to clauses which contain more detailed definitions and/or further
elaboration.
⎣x⎦ the largest integer less than or equal to the real number x. For example,
⎣5⎦ = 5, ⎣5.3⎦ = 5, and ⎣−5.3⎦ = −6
⎡x⎤ the smallest integer greater than or equal to the real number x. For example,
⎡5⎤ = 5, ⎡5.3⎤ = 6, and ⎡−5.3⎤ = −6
[a.b] the interval of integers from a to b, including both a and b
[a.b) the interval of integers from a to b, including a but not b
⎜X ⎜ if X is a finite set, then the cardinality of X; if X is a finite abelian group or a finite field,
then the cardinality of the underlying set of elements; if X is a real number, then the
absolute value of X; if X is a bit/octet string, then the length in bits/octets of the string
NOTE See Clauses 5.2.1, 5.2.2.
x ⊕ y if x and y are bit/octet strings of the same length, the bit-wise exclusive-or (XOR) of the
two strings.
NOTE See Clauses 5.2.1, 5.2.2.
〈x , . . ., x〉 if x , . . ., x are bits/octets, the bit/octet string of length l consisting of the
1 1 1 1
bits/octets x1; : : : ; xl, in the given order
NOTE See Clauses 5.2.1, 5.2.2.
x ⎜⎜ y if x and y are bit/octet strings, the concatenation of the two strings x and y, resulting in the
string consisting of x followed by y
NOTE See Clauses 5.2.1, 5.2.2.
gcd(a, b) for integers a and b, the greatest common divisor of a and b, i.e., the largest positive
integer that divides both a and b (or 0 if a = b = 0)
a ⎜ b 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
a ≡ b (mod n) for a non-zero integer n, a relation between integers a and b that holds if and only if a and
b are congruent modulo n, i.e., n ⏐ (a − b)
a mod n for integer a and positive integer n, the unique integer r ∈ [0 . . n) such that r ≡ a (mod n)
−1
a mod n for integer a and positive integer n, such that gcd(a; n) = 1, the unique integer
b ∈ [0.n) such that ab ≡ 1 (mod n)
F* for a field F, the multiplicative group of units of F
0 for a field F, the additive identity (zero element) of F
F
1 for a field F, the multiplicative identity of F
F
BS2IP bit string to integer conversion primitive
NOTE See Clause 5.2.5.
© ISO/IEC 2006 – All rights reserved 7
EC2OSP elliptic curve to octet string conversion primitive. (See Clause 5.4.3.)
FE2OSP ¯eld element to octet string conversion primitive. (See Clause 5.3.1.)
FE2IP ¯eld element to integer conversion primitive. (See Clause 5.3.1.)
I2BSP integer to bit string conversion primitive. (See Clause 5.2.5.)
I2OSP integer to octet string conversion primitive. (See Clause 5.2.5.)
OS2ECP octet string to elliptic curve conversion primitive. (See Clause 5.4.3.)
OS2FEP octet string to ¯eld element conversion primitive. (See Clause 5.3.1.)
OS2IP octet string to integer conversion primitive. (See Clause 5.2.5.)
Oct(m) the octet whose integer value is m. (See Clause 5.2.4.)
L(n) the length in octets of an integer n. (See Clause 5.2.5.)
5 Mathematical conventions
This clause describes certain mathematical conventions used in this part of ISO/IEC 18033,
including the representation of mathematical objects, and primitives for data type conversion.
5.1 Functions and algorithms
For ease of presentation, functions and probabilistic functions (i.e., functions whose value de-
pends not only on the input value but also on a randomly chosen auxiliary value) are often
speci¯ed in algorithmic form. Except where explicitly noted, an implementor may choose to
employ any equivalent algorithm (i.e., one which yields the same function or probabilistic func-
tion). Moreover, in the case of probabilistic functions, when the algorithm describing the function
indicates that a random value should be generated, an implementor shall use an appropriate
random generator to generate this value (see ISO/IEC 18031 for more guidance on this issue).
In describing a function in algorithmic terms, the following convention is adopted. An algorithm
either computes a value, or alternatively, it may fail. By convention, if an algorithm fails, then
unless otherwise speci¯ed, another algorithm that invokes this algorithm as a sub-routine also
fails.
NOTE Thus, failing is analogous to the notion of \throwing an exception" in many programming
languages; however, it can also be viewed as returning a special value that is by de¯nition distinct from
all values returned by the algorithm when it does not fail. With this latter interpretation of failing, an
algorithm still properly describes a function. The details of how an implementation achieves the e®ect of
failing are not speci¯ed here. However, in a typical implementation, an algorithm may return an \error
code" of some sort to its environment that indicates the reason for the failure. It should be noted that in
some cases, for reasons of security, the implementation should take care not to reveal the precise cause
of certain types of errors.
c
8 °ISO 2006 | All rights reserved
5.2 Bit strings and octet strings
5.2.1 Bits and bit strings
A bit is one of the two symbols `0' or `1'.
A bit string is a sequence of bits. For bits x ; : : :; x ,hx ; : : :; x i denotes the bit string of length
1 l 1 l
l consisting of the bits x ; : : :; x , in the given order.
1 l
For a bit string x =hx ; : : :; x i, the length l of x is denoted byjxj, and if l > 0, x is called the
1 l 1
¯rst bit of x, and x the last bit of x.
l
For bit strings x and y, xk y denotes the concatenation of x and y; that is, if x =hx ; : : :; x i
l
and y =hy ; : : :; y i, then xk y =hx ; : : :; x ; y ; : : :; y i.
1 m 1 l 1 m
For bit strings x and y of equal length, x© y denotes the bit-wise exclusive-or (XOR) of x and
y.
The bit string of length zero is called the null bit string.
NOTE No special subscripting operator is de¯ned for bit strings. Thus, if x is a bit string, x does not
i
necessarily denote any particular bit of x.
5.2.2 Octets and octet strings
An octet is a bit string of length 8.
An octet string is a sequence of octets.
For octets x ; : : :; x , hx ; : : :; x i denotes the octet string of length l consisting of the octets
1 l 1 l
x ; : : :; x , in the given order.
1 l
For an octet string x =hx ; : : :; x i, the length l of x is denoted byjxj, and if l > 0, x is called
1 l 1
the ¯rst octet of x, and x the last octet of x.
l
For octet strings x and y, xk y denotes the concatenation of x and y; that is, if x =hx ; : : :; x i
1 l
and y =hy ; : : :; y i, then xk y =hx ; : : :; x ; y ; : : :; y i.
1 m 1 1 m
l
For octet strings x and y of equal length, x© y denotes the bit-wise exclusive-or (XOR) of x
and y.
The octet string of length zero is called the null octet string.
NOTE 1 No special subscripting operator is de¯ned for octet strings. Thus, if x is an octet string, x
i
does not necessarily denote any particular octet of x.
NOTE 2 Note that since an octet is a bit string of length 8, if x and y are octets, then xky is a bit
string of length 16, hxi and hyi are each octet strings of length 1, and hxikhyi = hx;yi is an octet
string of length 2.
c
°ISO 2006 | All rights reserved 9
5.2.3 Octet string/bit string conversion
Primitives OS2BSP and BS2OSP to convert between octet strings and bit strings are de¯ned
as follows.
The function OS2BSP(x) takes as input an octet string x = hx ; : : :; x i, and outputs the bit
1 l
string y = x k ¢¢¢ k x .
l
The function BS2OSP(y) takes as input a bit string y, whose length is a multiple of 8, and
outputs the unique octet string x such that y = OS2BSP(x).
5.2.4 Bit string/integer conversion
Primitives BS2IP and I2BSP to convert between bit strings and integers are de¯ned as follows.
The function BS2IP(x) maps a bit string x to an integer value x , as follows. If x =hx ; : : :; x i
l¡1 0
where x ; : : :; x are bits, then the value x is de¯ned as
0 l¡1
X
0 i
x = 2 :
0·i
x =`1'
i
The function I2BSP(m; l) takes as input two non-negative integers m and l, and outputs the
unique bit string x of length l such that BS2IP(x) = m, if such an x exists. Otherwise, the
function fails.
The length in bits of a non-negative integer n is the number of bits in its binary representation,
i.e., dlog (n + 1)e.
As a notational convenience, Oct(m) is de¯ned as Oct(m) = I2BSP(m; 8).
NOTE Note that I2BSP(m;l) fails if and only if the length of m in bits is greater than l.
5.2.5 Octet string/integer conversion
Primitives OS2IP and I2OSP to convert between octet strings and integers are de¯ned as follows.
The function OS2IP(x) takes as input an octet string, and outputs the integer
BS2IP(OS2BSP(x)).
The function I2OSP(m; l) takes as input two non-negative integers m and l, and outputs the
unique octet string x of length l such that OS2IP(x) = m, if such an x exists. Otherwise, the
function fails.
The length in octets of a non-negative integer n is the number of digits in its representation base
256, i.e., dlog (n + 1)e; this quantity is denoted L(n).
NOTE Note that I2OSP(m;l) fails if and only if the length of m in octets is greater than l.
5.3
Finite fields
This clause describes a very general framework for describing speci¯c ¯nite ¯elds. A ¯nite ¯eld
speci¯ed in this way is called an explicitly given ¯nite ¯eld, and it is determined by explicit data.
c
10 °ISO 2006 | All rights reserved
e
For a ¯nite ¯eld F of cardinality q = p , where p is prime and e¸ 1, explicit data for F consists
of p and e, along with a \multiplication table," which is a matrix T = (T ) , where each
ij 1·i;j·e
T is an e-tuple over [0 : : p).
ij
The set of elements of F is the set of all e-tuples over [0: : p). The entries of T are themselves
viewed as elements of F.
Addition in F is de¯ned element-wise: if
a = (a ; : : :; a )2 F and b = (b ; : : :; b )2 F;
1 e 1 e
then a + b = c, where
c = (c ; : : :; c ) and c = (a + b ) mod p (1· i· e):
1 e i i i
A scalar multiplication operation for F is also de¯ned element-wise: if
a = (a ; : : :; a )2 F and d2 [0 : : p);
1 e
then d¢ a = c, where
c = (c ; : : :; c ) and c = (d¢ a ) mod p (1· i· e):
1 e i i
Multiplication in F is de¯ned via the multiplication table T, as follows: if
a = (a ; : : :; a )2 F and b = (b ; : : :; b )2 F;
1 e 1 e
e e
XX
a¢ b = (a b mod p)T ;
i j ij
i=1 j=1
where the products (a b mod p)T are de¯ned using the above rule for scalar multiplication,
i j ij
and where these products are summed using the above rule for addition in F. It is assumed that
the multiplication table de¯nes an algebraic structure that satis¯es the usual axioms of a ¯eld;
in particular, there exist additive and multiplicative identities, every element has an additive
inverse, and every element besides the additive identity has a multiplicative inverse.
Observe that the additive identity of F, denoted 0 , is the all-zero e-tuple, and that the mul-
F
tiplicative identity of F, denoted 1 , is a non-zero e-tuple whose precise format depends on
F
T.
NOTE 1 The ¯eld F is a vector space of dimension e over the prime ¯eld F of cardinality p, where
scalar multiplication is de¯ned as above. The prime p is called the characteristic of F. For 1· i· e, let
µ denote the e-tuple over F whose ith component is 1, and all of whose other components are 0. The
i
elements µ ;::: ;µ form an ordered basis of F as a vector space over F . Note that for 1· i;j · e, we
1 e
have µ ¢ µ = T .
i j ij
NOTE 2 For e > 1, two types of standard bases are de¯ned that are commonly used in implementations
of ¯nite ¯eld arithmetic:
0 e¡i
| µ ;::: ;µ is called a polynomial basis for F over F if for some µ2 F, µ = µ for 1· i· e. Note
1 e i
that in this case, 1 = µ .
F e
i¡1
0 p
| µ ;::: ;µ is called a normal basis for F over F if for some µ 2 F, µ = µ for 1 · i · e. Note
1 e i
P
e
that in this case, 1 = c µ for some c2 [1::p); if p = 2, then the only possible choice for c is
F i
i=1
1; moreover, one can always choose a normal basis for which c = 1.
NOTE 3 The de¯nition given here of an explicitly given ¯nite ¯eld comes from [23].
c
°ISO 2006 | All rights reserved 11
5.3.1 Octet string and integer/¯nite ¯eld conversion
Primitives OS2FEP and FE2OSP to convert between octet strings and elements of an ex-
F F
plicitly given ¯nite ¯eld F, as well as the primitive FE2IP to convert elements of F to integer
F
values, are de¯ned as follows.
The function FE2IP maps an element a2 F to an integer value a , as follows. If the cardinality
F
e
of F is q = p , where p is prime and e ¸ 1, then an element a of F is an e-tuple (a ; : : :; a ),
1 e
where a 2 [0 : : p) for 1· i· e, and the value a is de¯ned as
i
e
X
0 i¡1
a = a p :
i
i=1
The function FE2OSP (a) takes as input an element a of the ¯eld F and outputs the octet string
F
0 0
I2OSP(a ; l), where a = FE2IP (a), and l is the length in octets ofjFj¡1, i.e., l =dlog jFje.
F
Thus, the output of FE2OSP (a) is always an octet string of length exactly dlog jFje.
F 256
The function OS2FEP (x) takes as input an octet string x, and outputs the (unique) ¯eld
F
element a 2 F such that FE2OSP (a) = x, if any such a exists, and otherwise fails. Note
F
that OS2FEP (x) fails if and only if either x does not have length exactly dlog jFje, or
F
OS2IP(x)¸jFj.
5.4 Elliptic curves
An elliptic curve E over an explicitly given ¯nite ¯eld F is a set of points P = (x; y), where x
and y are elements of F that satisfy a certain equation, together with the \point at in¯nity,"
denoted by O. For the purposes of this part of ISO/IEC 18033, the curve E is speci¯ed by two
¯eld elements a; b2 F, called the coe±cients of E.
Let p be the characteristic of F.
3 2
If p > 3, then a and b shall satisfy 4a + 27b6= 0 , and every point P = (x; y) on E (other
F
than O) shall satisfy the equation
2 3
y = x + ax + b:
If p = 2, then b shall satisfy b6= 0 , and every point P = (x; y) on E (other thanO) shall satisfy
F
the equation
2 3 2
y + xy = x + ax + b:
If p = 3, then a and b shall satisfy a6= 0 and b6= 0 , and every point P = (x; y) on E (other
F F
than O) shall satisfy the equation
2 3 2
y = x + ax + b:
The points on an elliptic curve form a ¯nite abelian group, where O is the identity element.
There exist e±cient algorithms to perform the group operation of an elliptic curve, but the
implementation of such algorithms is out of the scope of this part of ISO/IEC 18033.
NOTE See, for example, ISO/IEC 15946-1, as well as [9], for more information on how to e±ciently
implement elliptic curve group operations.
c
12 °ISO 2006 | All rights reserved
5.4.1 Compressed elliptic curve points
Let E be an elliptic curve over an explicitly given ¯nite ¯eld F, where F has characteristic p.
A point P6=O can be represented in either compressed, uncompressed, or hybrid form.
If P = (x; y), then (x; y) is the uncompressed form of P.
Let P = (x; y) be a point on the curve E, as above. The compressed form of P is the pair (x;y~),
where y~2f0; 1g is determined as follows.
| If p6= 2 and y = 0 , then y~ = 0.
F
0 f 0
| If p6= 2 and y6= 0 , then y~ = ((y =p ) mod p) mod 2, where y = FE2IP (y), and where f
F F
f 0
is the largest non-negative integer such that p j y .
| If p = 2 and x = 0 , then y~ = 0.
F
0 f 0
| If p = 2 and x6= 0 , then y~ =bz =2 c mod 2, where z = y=x, where z = FE2IP (z), and
F F
f
where f is the largest non-negative integer such that 2 divides FE2IP (1 ).
F F
The hybrid form of P = (x; y) is the triple (x;y~; y), where y~ is as in the previous paragraph.
5.4.2 Point decompression algorithms
There exist e±cient procedures for point decompression, i.e., computing y from (x;y~). These
are brie°y described here.
| Assume p6= 2, and let (x;y~) be the compressed form of (x; y). The point (x; y) satis¯es an
equation y = f(x) for a polynomial f(x) over F in x. If f(x) = 0 , then there is only one
F
possible choice for y, namely, y = 0 . Otherwise, if f(x)6= 0, then there are two possible
F
choices of y, which di®er only in sign, and the correct choice is determined by y~. There are
well-known algorithms for computing square roots in ¯nite ¯elds, and so the two choices of
y are easily computed.
| Assume p = 2, and let (x;y~) be the compressed form of (x; y). The point (x; y) satis¯es
2 3 2 2
an equation y + xy = x + ax + b. If x = 0 , then we have y = b, from which y is
F
uniquely determined and easily computed. Otherwise, if x6= 0 , then setting z = y=x, we
F
2 ¡2
have z + z = g(x), where g(x) = (x + a + bx ). The value of y is uniquely determined by,
and easily computed from, the values z and x, and so it su±ces to compute z. To compute
z, observe that for a ¯xed x, if z is one solution to the equation z +z = g(x), then there is
exactly one other solution, namely z +1 . It is easy to compute these two candidate values
F
of z, and the correct choice of z is easily seen to be determined by y~.
5.4.3 Octet string/elliptic curve conversion
Primitives EC2OSP and OS2ECP for converting between points on an elliptic curve E and
E E
octet strings are de¯ned as follows.
Let E be an elliptic curve over an explicitly given ¯nite ¯eld F.
c
°ISO 2006 | All rights reserved 13
The function EC2OSP (P;fmt) takes as input a point P on E and a format speci¯er fmt, which
E
is one of the symbolic values compressed, uncompressed, or hybrid. The output is an octet string
EP, computed as follows.
| If P =O, then EP =hOct(0)i.
| If P = (x; y)6=O, with compressed form (x;y~), then
EP =hHikXk Y;
where
| H is a single octet of the form Oct(4U + C¢ (2 + y~)), where
| U = 1 if fmt is either uncompressed or hybrid, and otherwise, U = 0;
| C = 1 if fmt is either compressed or hybrid, and otherwise, C = 0;
| X is the octet string FE2OSP (x);
F
| Y is the octet string FE2OSP (y) if fmt is either uncompressed or hybrid, and otherwise
F
Y is the null octet string.
NOTE If the format speci¯er fmt is uncompressed, then the value y~ need not be computed.
The function OS2ECP (EP) takes as input an octet string EP. If there exists a point P on
E
the curve E and a format speci¯er fmt such that EC2OSP (P;fmt) = EP, then the function
E
outputs P (in uncompressed form), and otherwise, the function fails. Note that the point P, if
it exists, is uniquely de¯ned, and so the function OS2ECP (EP) is well de¯ned.
E
6 Cryptographic transformations
This clause describes several cryptographic transformations that will be referred to in subse-
quent clauses. The types of transformations are cryptographic hash functions, key derivation
functions, message authentication codes, block ciphers, and symmetric ciphers. For each type
of transformation, the abstract input/output characteristics are given, and then speci¯c imple-
mentations of these transformations that are allowed for use in this part of ISO/IEC 18033 are
speci¯ed.
6.1 Cryptographic hash functions
A cryptographic hash function is essentially a function that maps an octet string of variable
length to an octet string of ¯xed length. More precisely, a cryptographic hash function Hash
speci¯es
| a positive integer Hash.len that denotes the length of the hash function output,
| a positive integer Hash.MaxInputLen that denotes the maximum length hash input,
| and a function Hash.eval that denotes the hash function itself, which maps octet strings of
length at most Hash.MaxInputLen to octet strings of length Hash.len.
The invocation of Hash.eval fails if and only if the input length exceeds Hash.MaxInputLen.
c
14 °ISO 2006 | All rights reserved
6.1.1 Allowable cryptographic hash functions
For the purposes of this part of ISO/IEC 18033, the allowable cryptographic hash functions are
those described in ISO/IEC 10118-2 and ISO/IEC 10118-3, with the following provisos:
| The hash functions described in ISO/IEC 10118 map bit strings to bit strings, whereas in
this part of ISO/IEC 18033, they map octet strings to octet strings. Therefore, a hash
function in ISO/IEC 10118-2 or ISO/IEC 10118-3 is allowed in this part of ISO/IEC 18033
only if the length in bits of the output is a multiple of 8, in which case the mapping between
octet strings and bit strings is a®ected by the functions OS2BSP and BS2OSP.
| Whereas the hash functions in ISO/IEC 10118 are not de¯ned for inputs exceeding a given
length, a hash function in this part of ISO/IEC 18033 is de¯ned to fail for such inputs.
6.2 Key derivation functions
A key derivation function is a function KDF(x; l) that takes as input an octet string x and
an integer l ¸ 0, and outputs an octet string of length l. The string x is of arbitrary length,
although an implementation may de¯ne a (very large) maximum length for x and maximum size
for l, and fail if these bounds are exceeded.
NOTE In some o
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.
Loading comments...