ISO/IEC 14888-3:2016

INTERNATIONAL ISO/IEC
STANDARD 14888-3
Third edition
2016-03-15
Corrected version
2017-09
Information technology — Security
techniques — Digital signatures with
appendix —
Part 3:
Discrete logarithm based mechanisms
Technologies de l'information — Techniques de sécurité — Signatures
numériques avec appendice —
Partie 3: Mécanismes basés sur un logarithme discret
Reference number
©
ISO/IEC 2016
© ISO/IEC 2016, Published in Switzerland
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized otherwise in any form
or by any means, electronic or mechanical, including photocopying, or posting on the internet or an intranet, without prior
written permission. Permission can be requested from either ISO at the address below or ISO’s member body in the country of
the requester.
ISO copyright office
Ch. de Blandonnet 8 • CP 401
CH-1214 Vernier, Geneva, Switzerland
Tel. +41 22 749 01 11
Fax +41 22 749 09 47
copyright@iso.org
www.iso.org
ii © ISO/IEC 2016 – All rights reserved

Contents Page
Foreword .vi
Introduction .vii
1 Scope . 1
2 Normative references . 1
3 Terms and definitions . 1
4 Symbols and abbreviated terms . 3
5 General model . 5
5.1 Parameter generation process . 5
5.1.1 Certificate-based mechanisms . 5
5.1.2 Identity-based mechanisms . 5
5.1.3 Parameter selection . 6
5.1.4 Validity of domain parameters and verification key . 7
5.2 Signature process . 7
5.2.1 General. 7
5.2.2 Producing the randomizer. 8
5.2.3 Producing the pre-signature . 8
5.2.4 Preparing the message for signing . 8
5.2.5 Computing the witness (the first part of the signature) . 8
5.2.6 Computing the assignment . 8
5.2.7 Computing the second part of the signature . 9
5.2.8 Constructing the appendix . 9
5.2.9 Constructing the signed message . 9
5.3 Verification process .10
5.3.1 General.10
5.3.2 Retrieving the witness .10
5.3.3 Preparing message for verification .11
5.3.4 Retrieving the assignment .11
5.3.5 Recomputing the pre-signature .11
5.3.6 Recomputing the witness .11
5.3.7 Verifying the witness .11
6 Certificate-based mechanisms .12
6.1 General .12
6.1 6.1 .
General .12
6.2 DSA .13
6.2.1 General.13
6.2.2 Parameters .13
6.2.3 Generation of signature key and verification key .14
6.2.4 Signature process .14
6.2.5 Verification process .15
6.3 KCDSA .16
6.3.1 General.16
6.3.2 Parameters .16
6.3.3 Generation of signature key and verification key .17
6.3.4 Signature process .17
6.3.5 Verification process .18
6.4 Pointcheval/Vaudenay algorithm .19
6.4.1 General.19
6.4.2 Parameters .19
6.4.3 Generation of signature key and verification key .19
6.4.4 Signature process .19
6.4.5 Verification process .20
© ISO/IEC 2016 – All rights reserved iii

6.5 SDSA .21
6.5.1 General.21
6.5.2 Parameters .22
6.5.3 Generation of signature key and verification key .22
6.5.4 Signature process .22
6.5.5 Verification process .23
6.6 EC-DSA .24
6.6.1 General.24
6.6.2 Parameters .24
6.6.3 Generation of signature key and verification key .25
6.6.4 Signature process .25
6.6.5 Verification process .26
6.7 EC-KCDSA.27
6.7.1 General.27
6.7.2 Parameters .27
6.7.3 Generation of signature key and verification key .28
6.7.4 Signature process .28
6.7.5 Verification process .29
6.8 EC-GDSA .30
6.8.1 General.30
6.8.2 Parameters .30
6.8.3 Generation of signature key and verification key .30
6.8.4 Signature process .30
6.8.5 Verification process .31
6.9 EC-RDSA .32
6.9.1 General.32
6.9.2 Parameters .33
6.9.3 Generation of signature key and verification key .33
6.9.4 Signature process .33
6.9.5 Verification process .34
6.10 EC-SDSA .35
6.10.1 General.35
6.10.2 Parameters .35
6.10.3 Generation of signature key and verification key .35
6.10.4 Signature process .36
6.10.5 Verification process .36
6.11 EC-FSDSA .37
6.11.1 General.37
6.11.2 Parameters .38
6.11.3 Generation of signature key and verification key .38
6.11.4 Signature process .38
6.11.5 Verification process .39
7 Identity-based mechanisms .40
7.1 General .40
7.1 7.1 .
General .40
7.2 IBS-1 .41
7.2.1 General.41
7.2.2 Parameters .41
7.2.3 Generation of master key and signature/verification key .41
7.2.4 Signature process .41
7.2.5 Verification process .42
7.3 IBS-2 .43
7.3.1 General.43
7.3.2 Parameters .43
7.3.3 Generation of master key and signature/verification key .43
7.3.4 Signature process .43
7.3.5 Verification process .44
iv © ISO/IEC 2016 – All rights reserved

Annex A (normative) Object identifier .46
Annex B (normative) Conversion functions (I) .49
Annex C (informative) Conversion functions (II) .54
Annex D (normative) Generation of DSA domain parameters .56
Annex E (informative) The Weil and Tate pairings .58
Annex F (informative) Numerical examples .61
Annex G (informative) Comparison of the signature schemes .127
Annex H (informative) Claimed features for choosing a mechanism .129
Bibliography .130
© ISO/IEC 2016 – All rights reserved v

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.
The procedures used to develop this document and those intended for its further maintenance are
described in the ISO/IEC Directives, Part 1. In particular the different approval criteria needed for
the different types of document should be noted. This document was drafted in accordance with the
editorial rules of the ISO/IEC Directives, Part 2 (see www.iso.org/directives).
Attention is drawn to the possibility that some of the elements of this document may be the subject
of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent
rights. Details of any patent rights identified during the development of the document will be in the
Introduction and/or on the ISO list of patent declarations received (see www.iso.org/patents).
Any trade name used in this document is information given for the convenience of users and does not
constitute an endorsement.
For an explanation on the voluntary nature of standards, the meaning of ISO specific terms and
expressions related to conformity assessment, as well as information about ISO's adherence to the
World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT) see the following
URL: www.iso.org/iso/foreword.html.
This document was prepared by Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
This third edition cancels and replaces the second edition (ISO/IEC 14888-3:2006), which has been
technically revised. It also incorporates the Amendments ISO/IEC 14888-3:2006/Amd 1:2010 and
ISO/IEC 14888-3:2006/Amd 2:2012 and the Technical Corrigenda ISO/IEC 14888-3:2006/Cor 1:2007
and ISO/IEC 14888-3:2006/Cor 2:2009.
This corrected version of ISO/IEC 14888-3:2016 incorporates the following corrections:
— the formula has been changed in 5.1.1.2;
-1
x
x-1
— “G ” has been changed to “ G ” in 6.3.1 and 6.3.3;
— “β” has been changed to “ β’ ” in 6.7.1, 6.7.4.4 and 6.7.4.5;
— the reference has been changed in 6.9.1;
— the code for K has been changed in F.9.2.4.
A list of all parts in the ISO/IEC 14888 series can be found on the ISO website.
vi © ISO/IEC 2016 – All rights reserved

Introduction
Digital signature mechanisms can be used to provide services such as entity authentication, data
origin authentication, non-repudiation and data integrity. A digital signature mechanism satisfies the
following requirements.
— Given either or both of the following two things:
— the verification key, but not the signature key;
— a set of signatures on a sequence of messages that an attacker has adaptively chosen;
it should be computationally infeasible for the attacker
— to produce a valid signature on a new message,
— in some circumstances, to produce a new signature on a previously signed message, or
— to recover the signature key;
— it should be computationally infeasible, even for the signer, to find two different messages with the
same signature.
NOTE 1 Computational feasibility depends on the specific security requirements and environment.
NOTE 2 In some applications, producing a new signature on a previously signed message without knowing the
signature key is allowed. One example of such applications is a membership credential in an anonymous digital
signature mechanism as specified in ISO/IEC 20008.
Digital signature mechanisms are based on asymmetric cryptographic techniques and involve the
following three basic operations:
— a process for generating pairs of keys, where each pair consists of a private signature key and the
corresponding public verification key;
— a process that uses the signature key, called the signature process;
— a process that uses the verification key, called the verification process.
The following are the two types of digital signature mechanisms:
— when, for a given signature key, any two signatures produced for the same message are always
identical, the mechanism is said to be deterministic (or non-randomized) (see ISO/IEC 14888-1 for
further details);
— when, for a given message and signature key, any two applications of the signature process produce
(with high probability) two distinct signatures, the mechanism is said to be randomized (or non-
deterministic).
The mechanisms specified in this part of ISO/IEC 14888 are all randomized.
Digital signature mechanisms can also be divided into the following two categories:
— when the whole message has to be stored and/or transmitted along with the signature, the
mechanism is termed a "signature mechanism with appendix" (such mechanisms are the subject of
ISO/IEC 14888);
— when the whole message, or part of it, can be recovered from the signature, the mechanism is
termed a "signature mechanism giving message recovery" (ISO/IEC 9796 specifies mechanisms in
this category).
The verification of a digital signature requires access to the signing entity’s verification key. It is, thus,
essential for a verifier to be able to associate the correct verification key with the signing entity, or more
© ISO/IEC 2016 – All rights reserved vii

precisely, with (parts of) the signing entity’s identification data. This association between the signer’s
identification data and the signer’s public verification key can either be guaranteed by an outside entity
or mechanism, or the association can be somehow inherent in the verification key itself. In the former
case, the scheme is said to be “certificate-based.” In the latter case, the scheme is said to be “identity
based.” Typically, in an identity-based scheme, the verifier can calculate the signer’s public verification
key from the signer’s identification data. The digital signature mechanisms specified in this part of
ISO/IEC 14888 are classified into certificate-based and identity-based mechanisms.
NOTE 3 For certificate-based mechanisms, various PKI standards can be used as the basis of key management.
For further information, see ISO/IEC 9594-8 (also known as X.509), ISO/IEC 11770-3 and ISO/IEC 15945.
The security of a signature mechanism is based on an intractable computational problem, i.e. a problem
for which, given current knowledge, finding a solution is computationally infeasible, such as the
factorization problem and the discrete logarithm problem. This part of ISO/IEC 14888 specifies digital
signature mechanisms with appendix based on the discrete logarithm problem, and ISO/IEC 14888-2
specifies digital signature mechanisms with appendix based on the factorization problem.
NOTE 4 The first edition of ISO/IEC 14888 grouped identity-based mechanisms into ISO/IEC 14888-2 and
certificate-based mechanisms into ISO/IEC 14888-3, with both parts covering mechanisms based on both the
discrete logarithm and the factorization problems. Since the second edition was published, the mechanisms
have been reorganized. ISO/IEC 14888-2 now contains integer factoring-based mechanisms, and this part of
ISO/IEC 14888 now contains discrete logarithm based mechanisms.
This part of ISO/IEC 14888 includes 12 mechanisms, two of which were in ISO/IEC 14888-3:1998, three
of which were from ISO/IEC 15946-2:2002 and three of which were added in ISO/IEC 14888-3:2006.
The Elliptic Curve Russian Digital Signature Algorithm (EC-RDSA) and three mechanisms based on
Schnorr digital signature are added in ISO/IEC 14888-3:2006/Amd.1:2010.
The mechanisms specified in this part of ISO/IEC 14888 use a collision resistant hash-function to hash
the message being signed (possibly in more than one part). ISO/IEC 10118 specifies hash-functions.
The International Organization for Standardization (ISO) and International Electrotechnical
Commission (IEC) draw attention to the fact that it is claimed that compliance with this part of
ISO/IEC 14888 may involve the use of patents.
The ISO and IEC take no position concerning the evidence, validity and scope of these patent rights.
The holder of these patent rights 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 regarding relevant patents is given in the following:
Certicom Corp.
4701 Tahoe Blvd., Building A, Mississauga, ON L4W0B5 Canada.
Attention is drawn to the possibility that some of the elements of this part of ISO/IEC 14888 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.
ISO (www.iso.org/patents) and IEC (http://patents.iec.ch) maintain on-line databases of patents
relevant to their standards. Users are encouraged to consult the databases for the most up to date
information concerning patents.
NOTE 5 The mechanisms of EC-DSA, EC-GDSA. EC-RDSA and EC-FSDSA may be vulnerable to a key substitution
[10]
attack. The attack is realized if an adversary can find two distinct public keys and one signature such that
the signature is valid for both public keys. There are several approaches of avoiding this attack and its possible
impact on the security of a cryptographic system. For example, the public key corresponding to the private
signing key can be added into the message to be signed.
viii © ISO/IEC 2016 – All rights reserved

INTERNATIONAL STANDARD ISO/IEC 14888-3:2016(E)
Information technology — Security techniques — Digital
signatures with appendix —
Part 3:
Discrete logarithm based mechanisms
1 Scope
This part of ISO/IEC 14888 specifies digital signature mechanisms with appendix whose security is
based on the discrete logarithm problem.
This part of ISO/IEC 14888 provides
— a general description of a digital signature with appendix mechanism, and
— a variety of mechanisms that provide digital signatures with appendix.
For each mechanism, this part of ISO/IEC 14888 specifies
— the process of generating a pair of keys,
— the process of producing signatures, and
— the process of verifying signatures.
2 Normative references
The following documents, in whole or in part, are normatively referenced in this document and are
indispensable for its application. For dated references, only the edition cited applies. For undated
references, the latest edition of the referenced document (including any amendments) applies.
ISO/IEC 10118-3, Information technology — Security techniques — Hash-functions
ISO/IEC 14888-1:2008, Information technology — Security techniques — Digital signatures with appendix
— Part 1: General
3 Terms and definitions
For the purposes of this document, the terms and definitions given in ISO/IEC 14888-1 and the
following apply.
3.1
finite commutative group
finite set E with the binary operation “*” such that
— for all group elements a, b ∈ E, a * b ∈ E;
— for all group elements a, b, c ∈ E, (a * b) * c = a * (b * c);
— there exists a group element e ∈ E with e * a = a for all a ∈ E, where e is called the identity element
of the group;
— for all group elements a ∈ E, there exists a group element b ∈ E with b * a = e;
© ISO/IEC 2016 – All rights reserved 1

— for all group elements a, b ∈ E, a * b = b * a
Note 1 to entry: In some cases, such as when E is the set of points on an elliptic curve, arithmetic in the finite set
E is described with additive notation.
3.2
cyclic group
finite commutative group (3.1), E, of n elements that contains a group element a ∈ E, called the generator,
of order n
3.3
elliptic curve group
cyclic group (3.2) defined on the points of an elliptic curve over a finite field
Note 1 to entry: Let F = GF(r) denote the Galois field with cardinality, r, where
m
either r is an odd prime, p, or r is equal to 2 , for some positive integer, m.
2 3
An elliptic curve defined over F can be determined by an affine curve formula, either of the form y = x + a x + a
1 2
2 3 2 m
(when r = p for some odd prime p) or of the form y + xy = x + a x + a (when r = 2 for some positive integer
1 2
m), where the coefficients a and a are (appropriately chosen) elements of F. The corresponding elliptic curve E
1 2
consists of a collection of certain affine points from F × F together with a special (non-affine) point “at infinity”.
An affine point P of E is one that can be represented as an ordered pair (P , P ) ∈ F × F, such that the selection of
x y
x = P and y = P satisfies the given affine curve formula when the indicated arithmetic is performed in the field, F.
x y
Let “+” denote the binary operation known as “elliptic-curve addition”, defined for (most) affine points of E by the
well-known secant-and-tangent rules. Once the collection of affine points of E is augmented by 0 , a special point
E
of E “at infinity” that serves as the identity element for “+” (but is not represented as an ordered pair), the set E
together with the binary operation “+” forms a finite, commutative, elliptic-curve group, E.
Note 2 to entry: The cardinality of the elliptic-curve group, E, is one more than the number of ordered pairs in
F × F that satisfy the affine curve formula for E.
3.4
order (of a group element a)
n n
least positive integer n such that a =e, where e is the identity element of the group, a is defined
0 n m-1
recursively such that a =e and a =a*a (m>0), and * is the group operation
3.5
pairing
function which takes two elements, P and Q, from an elliptic curve group (3.3) over a finite field, G , as
input, and produces an element from another cyclic group (3.2) over a finite field, G , as output, and
which has the following two properties (where it is assumed that the cyclic groups, G and G have order
1 2
q, for some prime q, and for any two elements P, Q, the output of the pairing function is written as )
— Bilinearity: If P, P , P , Q, Q , Q are elements of G , and a is an integer satisfying 1 ≤ a ≤ q − 1, then
1 2 1 2 1

=

*

,
1 2 1 2
= * , and
1 2 1 2
a
<[a]P, Q> = =
— Non-degeneracy: If P is a non-identity element of G , ≠ 1
3.6
trusted key generation centre
KGC
trusted third party, which, in an identity-based signature mechanism, generates a private signature
key for each signing entity
2 © ISO/IEC 2016 – All rights reserved

4 Symbols and abbreviated terms
a⊕b bitwise exclusive OR of a and b, where a and b are either bits or strings of bits of
the same length, and in the latter case, the XOR operation is performed bit-wise
a , a elliptic curve coefficients
1 2
a mod n for an arbitrary integer a and a positive integer n, the unique integer remainder
r, 0 ≤ r ≤ (n – 1), satisfying r = a – bn, for some integer b.
(A, B, C) the coefficients of the signature formula, which, for the mechanisms specified in
Clause 6, defines how the signature is computed
NOTE 1   The signature formula is specified in 5.2.1.
a parameter which specifies the relationship between the signature key and the
verification key
E an elliptic curve defined by two elliptic curve coefficients, a and a
1 2
E
a finite commutative group; for the mechanisms based on a multiplicative
*
group, the elements of E are in Z ; for the mechanisms based on an additive
p
group of elliptic curve points, the elements of E are the points on an elliptic
curve E over GF(r)
*
#E the cardinality of E; for the mechanisms based on a multiplicative group Z , #E
p
is p - 1; for the mechanisms based on an additive group of elliptic curve points,
#E is one more than the number of points on the elliptic curve E over GF(r)
[including 0 (the point at infinity)]
E
F a finite field
F a finite field of order p
p
gcd(N , N ) the greatest common divisor of integers N and N
1 2 1 2
G an element of order q in E
GF(r) the finite field of cardinality r, where r is a prime power
G a cyclic group of prime order q; elements of G are points on an elliptic curve
1 1
over GF(r)
G a cyclic group of prime order q; elements of G are elements of a finite field GF(r)
2 2
H a hash-function that converts a data string into an element in G
1 1
NOTE 2   The input data string is converted to an integer first, then the integer is
converted to a point on E over GF(r) by using the I2P function, specified in Annex C.
h, H hash-functions, i.e. one of the mechanisms specified in ISO/IEC 10118
ID a data string containing an identifier of the signer, used in Mechanisms IBS-1
and IBS-2
m an embedding degree (or extension degree)
© ISO/IEC 2016 – All rights reserved 3

[n]P multiplication operation that takes a positive integer n and a point P on the
curve E as input and produces as output another point Q on the curve E, where
Q = [n]P = P + P + … + P added n -1 times. The operation satisfies [0]P = 0 (the
E
point at infinity), and [-n]P = [n](-P)
P a generator of G which is used in Mechanisms IBS-1 and IBS-2
p a prime number or a power of a prime number
q a prime number that is a divisor of #E and the order of G and G
1 2
r the size of GF(r); in the mechanisms based on an additive group of elliptic curve
m
points, r is a prime power, p , for some prime p ≥ 2 and integer m ≥ 1.
T the assignment
T the first part of the assignment T
T the second part of the assignment T
U the KGC's master private key, generated as a randomly chosen integer, which is
used in mechanisms IBS-1 and IBS-2
V the KGC's master public key, an element G , of which is used in mechanisms
IBS-1 and IBS-2
*
Z the set of integers i with 0 < i < N and gcd (i, N) = 1, with arithmetic defined
N
modulo N
*
Z the set of integers i with 0 < i < p and p a prime number, which is a
p
multiplicative group
α the bit-length of the prime number (or prime power) p
β the bit-length of the prime number q
γ the output bit-length of hash-functions h and H
pre-signature
Õ
Õ
x-coordinate of Õ in which ∏= ∏∏, is an elliptic curve point
()
X
XY
Õ
y-coordinate of Õ in which ∏= ∏∏, is an elliptic curve point
()
Y
XY
Õ
first element of Õ in which ∏= ∏∏, is an element of an extension field
()
a
ab
of degree 2
Õ
second element of Õ in which ∏= ∏∏, is an element of an extension
()
b
ab
field of degree 2
0 the point at infinity on the elliptic curve E
E
< > a bilinear and non-degenerate pairing
|| X || Y is used to mean the result of the concatenation of data items X and Y in the
order specified.
4 © ISO/IEC 2016 – All rights reserved

5 General model
5.1 Parameter generation process
5.1.1 Certificate-based mechanisms
5.1.1.1 Generation of domain parameters
For digital signature mechanisms based on discrete logarithms, the set of domain parameters includes
the following parameters:
— E, a finite commutative group;
— q, a prime divisor of #E;
— G, an element of order q in E.
In the group E, multiplicative notation is used. It is worthwhile to note that the particular signature
mechanism chosen may place additional constraints on the choice of E, q, and G.
5.1.1.2 Generation of signature key and verification key
A signature key of a signing entity is a secretly generated random or pseudo-random integer X such that
0 < X < q. The corresponding public verification key Y is an element of E and is computed as
D
x
YG=
where D is a parameter defined by the mechanism to be used. The value of D is one of two values, -1 and 1.
NOTE An implementation is still considered compliant if it excludes a few integers from consideration as
possible X values. For example, the value 1 can be excluded because this value results in the user’s verification
key being the generator, G, which is easily detectable.
5.1.2 Identity-based mechanisms
5.1.2.1 Notation
The two identity-based mechanisms specified in Clause 7 are both based on the use of pairings over
elliptic curve groups. To specify identity-based mechanisms, the additive group notation is used.
5.1.2.2 Generation of domain parameters
The set of domain parameters includes the following parameters:
— E, a finite commutative group;
— GF(r), the Galois field of cardinality r;
— G , a cyclic group of prime order q;
— G , a cyclic group of prime order q;
— P, a generator of G ;
— q, a prime number — the cardinality of G and G ;
1 2
— < >, a bilinear and non-degenerate pairing
© ISO/IEC 2016 – All rights reserved 5

5.1.2.3 Generation of master key
A master priv
...