ISO/IEC 14888-3:2018

INTERNATIONAL ISO/IEC
STANDARD 14888-3
Fourth edition
2018-11
IT Security techniques — Digital
signatures with appendix —
Part 3:
Discrete logarithm based mechanisms
Techniques de sécurité IT — Signatures numériques avec
appendice —
Partie 3: Mécanismes basés sur un logarithme discret
Reference number
©
ISO/IEC 2018
© ISO/IEC 2018
All rights reserved. Unless otherwise specified, or required in the context of its implementation, 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
CP 401 • Ch. de Blandonnet 8
CH-1214 Vernier, Geneva
Phone: +41 22 749 01 11
Fax: +41 22 749 09 47
Email: copyright@iso.org
Website: www.iso.org
Published in Switzerland
ii © ISO/IEC 2018 – 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 . 9
5.2.5 Computing the witness (the first part of the signature) . 9
5.2.6 Computing the assignment . 9
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 .11
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.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 .20
6.4.5 Verification process .20
6.5 SDSA .21
6.5.1 General.21
© ISO/IEC 2018 – All rights reserved iii

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.26
6.7.1 General.26
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 .31
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
6.12 SM2 .39
6.12.1 General.39
6.12.2 Parameters .40
6.12.3 Generation of signature key and verification key .40
6.12.4 Signature process .40
6.12.5 Verification process .41
7 Identity-based mechanisms .42
7.1 General .42
7.2 IBS-1 .43
7.2.1 General.43
7.2.2 Parameters .43
7.2.3 Generation of master key and signature/verification key .43
7.2.4 Signature process .44
7.2.5 Verification process .45
7.3 IBS-2 .46
7.3.1 General.46
7.3.2 Parameters .46
7.3.3 Generation of master key and signature/verification key .46
iv © ISO/IEC 2018 – All rights reserved

7.3.4 Signature process .46
7.3.5 Verification process .47
7.4 Chinese IBS .48
7.4.1 General.48
7.4.2 Parameters .48
7.4.3 Generation of master key and signature/verification key .49
7.4.4 Signature process .49
7.4.5 Verification process .50
Annex A (normative) Object identifiers .52
Annex B (normative) Conversion functions (I) .55
Annex C (informative) Conversion functions (II) .60
Annex D (normative) Generation of DSA domain parameters .62
Annex E (informative) The Weil and Tate pairings .64
Annex F (informative) Numerical examples .67
Annex G (informative) Comparison of the signature schemes .150
Annex H (informative) Claimed features for choosing a mechanism .152
Bibliography .153
© ISO/IEC 2018 – 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.
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.o rg/patents) or the IEC
list of patent declarations received (see http:/ /patents.i ec. ch).
Any trade name used in this document is information given for the convenience of users and does not
constitute an endorsement.
For an explanation of 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 www. iso
.org/iso/foreword. html.
This document was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
This fourth edition cancels and replaces the third edition (ISO 14888-3:2016), of which it constitutes a
minor revision. The main changes compared to the previous edition are as follows:
— SM2 algorithm has been added to 6.12 and F.14;
— Chinese IBS algorithm has been added to 7.4 and F.15;
— numerical examples of KCDSA, ECDSA and EC-KCDSA have been added to F.3.4, F.6.6, F.6.7, F.6.8,
F.7.7, F.7.8 and F.7.9;
— several formulae and symbols have been corrected.
A list of all parts in the ISO/IEC 14888 series can be found on the ISO website.
Any feedback or questions on this document should be directed to the user’s national standards body. A
complete listing of these bodies can be found at www. iso. org/members. html.
vi © ISO/IEC 2018 – 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, produce a new signature on a previously signed message; or
— 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 document 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
the ISO/IEC 14888 series);
— when the whole message, or part of it, can be recovered from the signature, the mechanism is termed
a "signature mechanism giving message recovery" (the ISO/IEC 9796 series 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 2018 – 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 document
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 document 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 the ISO/IEC 14888 series 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 document
now contains discrete logarithm based mechanisms.
This document includes 14 mechanisms: two of which (DSA and Pointcheval/Vaudenay algorithm) were
in ISO/IEC 14888-3:1998, three of which (EC-DSA, EC-KCDSA, and EC-GDSA) were from ISO/IEC 15946-
2:2002 and three of which (KCDSA, IBS-1 and IBS-2) were added in ISO/IEC 14888-3:2006, four of which
(SRA, EC-RDSA, EC-SDSA and EC-FSDSA) were added in ISO/IEC 14888-3:2006/Amd 1:2010, and two of
which (SM2 and Chinese IBS) are added in this document.
The mechanisms specified in this document 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 document 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 ISO and IEC that he/she 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:
Certicom Corp. Beijing HuadaInfosec Technology Co., Ltd
4701 Tahoe Blvd, Building A 4F, Tower B, Yandong Bldg
MISSISSAUGA ON L4W 0B5 No. 2 Wanhong West St.
CANADA Chaoyang District
100015 BEIJING
P.R. CHINA
Attention is drawn to the possibility that some of the elements of this document 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.
viii © ISO/IEC 2018 – All rights reserved

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.
Annexes A, B and D are normative elements; Annexes C, E, F, G and H are for information.
© ISO/IEC 2018 – All rights reserved ix

INTERNATIONAL STANDARD ISO/IEC 14888-3:2018(E)
IT Security techniques — Digital signatures with
appendix —
Part 3:
Discrete logarithm based mechanisms
1 Scope
This document specifies digital signature mechanisms with appendix whose security is based on the
discrete logarithm problem.
This document 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 document specifies
— the process of generating a pair of keys,
— the process of producing signatures, and
— the process of verifying signatures.
Annex A defines object identifiers assigned to the digital signature mechanisms specified in this
document, and defines algorithm parameter structures.
Annex B defines conversion functions of FE2I, I2FE, FE2BS, BS2I, I2BS, I2OS and OS2I used in this
document.
Annex D defines how to generate DSA domain parameters.
2 Normative references
The following documents are referred to in the text in such a way that some or all of their content
constitutes requirements 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 10118-3, IT Security techniques — Hash-functions — Part 3: Dedicated hash-functions
ISO/IEC 14888-1, 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.
ISO and IEC maintain terminological databases for use in standardization at the following addresses:
— ISO Online browsing platform: available at https: //www .iso .org/obp
— IEC Electropedia: available at http: //www .electropedia .org/
© ISO/IEC 2018 – All rights reserved 1

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;
— 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 either r is an odd prime, p, or r is
m
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 m 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 q, for
1 2
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
2 © ISO/IEC 2018 – All rights reserved

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
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.
D a parameter which specifies the relationship between the signature key and the verifi-
cation 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 group of elliptic curve
p
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 is p − 1;
p
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
E
infinity)]
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 over GF(r)
1 1
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
© ISO/IEC 2018 – All rights reserved 3

ID a data string containing an identifier of the signer, used in Mechanisms SM2, IBS-1,
IBS-2 and Chinese IBS
m an embedding degree (or extension degree)
[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 point at
E
infinity), and [−n]P = [n](−P)
P a generator of G which is used in Mechanisms IBS-1, IBS-2 and Chinese IBS
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 points,
m
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, IBS-2 and Chinese IBS
V the KGC's master public key, an element of G , which is used in mechanisms IBS-1, IBS-2
and Chinese IBS
*
Z the set of integers i with 0 < i < N and gcd (i, N) = 1, with arithmetic defined modulo N
N
*
Z the set of integers i with 0 < i < p and p a prime number, which is a multiplicative group
p
α 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 X Y
Π y-coordinate of Π in which Π = (Π , Π ) is an elliptic curve point
Y X Y
Π first element of Π in which Π = (Π , Π ) is an element of an extension field of degree 2
a a b
Π second element of Π in which Π = (Π , Π ) is an element of an extension field of degree 2
b a b
0 the point at infinity on the elliptic curve E
E
< > a bilinear and non-degenerate pairing
|| X || Y is used to mean the
...