ISO/IEC 14888-3:2016

Information technology — Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms

ISO/IEC 14888-3:2016 specifies digital signature mechanisms with appendix whose security is based on the discrete logarithm problem. ISO/IEC 14888-3:2016 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.

Technologies de l'information — Techniques de sécurité — Signatures numériques avec appendice — Partie 3: Mécanismes basés sur un logarithme discret

General Information

• Status: Withdrawn
• Publication Date: 16-Mar-2016
• Withdrawal Date: 16-Mar-2016
• ICS: 35.030 - IT Security
• ICS: 35.040 - Information coding
• Technical Committee: ISO/IEC JTC 1/SC 27 - Information security, cybersecurity and privacy protection
• Drafting Committee: ISO/IEC JTC 1/SC 27/WG 2 - Cryptography and security mechanisms
• Current Stage: 9599 - Withdrawal of International Standard
• Completion Date: 12-Nov-2018

Relations

• Revised: ISO/IEC 14888-3:2018 - IT Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms
• Effective Date: 30-Jun-2018
• Revises: ISO/IEC 14888-3:2006/Amd 2:2012 - Information technology — Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms — Amendment 2: Optimizing hash inputs
• Effective Date: 06-Jul-2013
• Revises: ISO/IEC 14888-3:2006 - Information technology — Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms
• Effective Date: 06-Jul-2013
• Revises: ISO/IEC 14888-3:2006/Amd 1:2010 - Information technology — Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms — Amendment 1: Elliptic Curve Russian Digital Signature Algorithm, Schnorr Digital Signature Algorithm, Elliptic Curve Schnorr Digital Signature Algorithm, and Elliptic Curve Full Schnorr Digital Signature Algorithm
• Effective Date: 06-Jul-2013

Standards Content (Sample)

© ISO/IEC 2015 – All rights reserved
ISO/IEC JTC 1/SC 27 N15619 Style Definition
... [1]
Field Code Changed
... [2]
Date: 2017‐08‐10
Formatted
... [3]
Field Code Changed
ISO/IEC 14888-3
Formatted
... [4]
ISO/IEC JTC 1/SC 27/WG 2
Field Code Changed
Formatted
... [5]
Secretariat: DIN
Deleted: 2015‐11‐11
Information technology — Security techniques — Digital signatures with Formatted: French (Switzerland)
appendix — Part 3: Discrete logarithm based mechanisms Field Code Changed
Formatted
... [6]
Technologies de l'information — Techniques de sécurité — Signatures numériques avec appendice — Partie 3:
Field Code Changed
Méchanismes basés sur un logarithme discréte
Formatted
... [7]
Field Code Changed
Formatted
... [8]
Field Code Changed
Formatted
... [9]
Field Code Changed
Formatted
... [10]
Field Code Changed
Formatted
... [11]
Field Code Changed
Formatted
... [12]
Document type: International Standard

---------------------- Page: 1 ----------------------
ISO/IEC 14888-3:2017(E)
Deleted: 2016
Contents Page
Foreword . 10
Introduction . 11
1  Scope . 14
2  Normative references . 14
3  Terms and definitions . 14
4  Symbols and abbreviated terms . 16
5  General model . 18
5.1  Parameter generation process . 18
5.2  Signature process . 20
5.3  Verification process . 23
6  Certificate-based mechanisms . 25
6.1  General . 25
6.2  DSA . 26
6.3  KCDSA . 29
6.4  Pointcheval/Vaudenay algorithm . 32
6.5  SDSA . 34
6.6  EC-DSA . 37
6.7  EC-KCDSA . 40
6.8  EC-GDSA . 43
6.9  EC-RDSA . 45
6.10  EC-SDSA . 47
6.11  EC-FSDSA . 50
7  Identity-based mechanisms . 52
7.1  General . 52
7.2  IBS-1 . 53
7.3  IBS-2 . 56
Annex A (normative) Object identifier . 59
Annex B (normative) Conversion functions (I) . 62
B.1  Conversion from a field element to an integer: FE2I(r, x) . 62
B.2  Conversion from an integer to a field element: I2FE(r, x) . 63
B.3  Conversion from a field element to a binary string: FE2BS(r, x) . 64
B.4  Conversion from a binary string to an integer: BS2I (g, x) . 65
B.5  Conversion from an integer to a binary string: I2BS(g, x) . 65
B.6  Conversion between an integer and an octet string: I2OS(h, x) & OS2I(h, M). 65
Annex C (informative) Conversion functions (II) . 67
Annex D (normative) Generation of DSA domain parameters . 69
D.1  Generation of the prime p and q . 69
D.2  Generation of the generator G . 70
D.2.1  Unverifiable generation of G . 70
D.2.2  Verifiable generation of G . 70
ii © ISO/IEC 2015 – All rights reserved

---------------------- Page: 2 ----------------------
ISO/IEC 14888-3:2017(E)
Deleted: 2016
Annex E (informative) The Weil and Tate pairings . 71
E.1  General . 71
E.2  The functions f, g and d . 71
E.3  The Weil pairing . 72
E.4  The Tate pairing . 72
E.5  The reduced Tate pairing . 73
Annex F (informative) Numerical examples . 74
F.1  General . 74
F.2  DSA mechanism . 74
F.2.1  Example 1: 2048-bit Prime P, SHA-224 . 74
F.2.1.1 General . 74
F.2.1.2  Parameters . 74
F.2.1.3 Signature key and verification key . 75
F.2.1.4 Per message data . 75
F.2.1.5  Signature . 75
F.2.1.6 Verification . 75
F.2.2  Example 2: 3072-bit Prime P, SHA-256 . 75
F.2.2.1 General . 75
F.2.2.2  Parameters . 76
F.2.2.3 Signature key and verification key . 77
F.2.2.4 Per message data . 78
F.2.2.5  Signature . 78
F.2.2.6 Verification . 78
F.3  KCDSA mechanism . 78
F.3.1  Example 1: 2048-bit Prime P, 224-bit Prime Q, SHA-224 . 78
F.3.1.1 General . 78
F.3.1.2  Parameters . 78
F.3.1.3 Signature key and verification key . 79
F.3.1.4 Per message data . 80
F.3.1.5  Signature . 80
F.3.1.6 Verification . 80
F.3.2  Example 2: 3072-bit Prime P, 256-bit Prime Q, SHA-256 . 80
F.3.2.1 General . 80
F.3.2.2  Parameters . 80
F.3.2.3 Signature key and verification key . 81
F.3.2.4 Per message data . 82
F.3.2.5  Signature . 82
© ISO/IEC 2015 – All rights reserved iii

---------------------- Page: 3 ----------------------
ISO/IEC 14888-3:2017(E)
Deleted: 2016
F.3.2.6 Verification . 83
F.3.3  Example 3: 2048-bit Prime P, 224-bit Prime Q, SHA-256 . 83
F.3.3.1 General . 83
F.3.3.2 Parameters . 83
F.3.3.3 Signature key and verification key . 84
F.3.3.4 Per message data . 84
F.3.3.5 Signature . 84
F.3.3.6 Verification . 85
F.4  Pointcheval-Vaudenay mechanism . 85
F.4.1  Example 1: 2048-bit Prime P, SHA-224 . 85
F.4.1.1 General . 85
F.4.1.2 Parameters . 85
F.4.1.3 Signature key and verification key . 86
F.4.1.4 Per message data . 86
F.4.1.5 Signature . 86
F.4.1.6 Verification . 87
F.5  SDSA mechanism . 87
F.5.1  Example 1: 2048-bit Prime P, SHA-224 . 87
F.5.1.1 General . 87
F.5.1.2 Parameters . 87
F.5.1.3 Signature key and verification key . 88
F.5.1.4 Per message data . 88
F.5.1.5 Signature . 89
F.5.1.6 Verification . 89
F.5.2  Example 2: 2048-bit Prime P, SHA-256 . 90
F.5.2.1 General . 90
F.5.2.2 Parameters . 90
F.5.2.3 Signature key and verification key . 90
F.5.2.4 Per message data . 91
F.5.2.5 Signature . 91
F.5.2.6 Verification . 92
F.6  EC-DSA mechanism . 92
F.6.1  General . 92
m
F.6.2  Example 1: Field F2 , m =191, SHA-1 . 92
F.6.2.1 Parameters . 92
F.6.2.2 Signature key and verification key . 93
F.6.2.3 Per message data . 93
iv © ISO/IEC 2015 – All rights reserved

---------------------- Page: 4 ----------------------
ISO/IEC 14888-3:2017(E)
Deleted: 2016
F.6.2.4  Signature . 93
F.6.2.5 Verification . 93
F.6.3  Example 2: Field F , 192-bit Prime P, SHA-1 . 93
P
F.6.3.1  Parameters . 93
F.6.3.2 Signature key and verification key . 94
F.6.3.3 Per message data . 94
F.6.3.4  Signature . 94
F.6.3.5 Verification . 95
m
F.6.4  Example 3: Field F , m =283, SHA-256 . 95
2
F.6.4.1  Parameters . 95
F.6.4.2 Signature key and verification key . 95
F.6.4.3 Per message data . 96
F.6.4.4  Signature . 96
F.6.4.5 Verification . 96
F.6.5  Example 4: Field F , 256-bit Prime P, SHA-256 . 96
p
F.6.5.1  Parameters . 96
F.6.5.2 Signature key and verification key . 97
F.6.5.3 Per message data . 97
F.6.5.4  Signature . 97
F.6.5.5 Verification . 97
F.7  EC-KCDSA mechanism . 98
F.7.1  Example 1: Field FP, 224-bit Prime P, SHA-224 . 98
F.7.1.1 General . 98
F.7.1.2  Parameters . 98
F.7.1.3 Signature key and verification key . 98
F.7.1.4 Per message data . 99
F.7.1.5  Signature . 99
F.7.1.6 Verification . 99
F.7.2  Example 2: Field F , 256-bit Prime P, SHA-256 . 99
P
F.7.2.1 General . 99
F.7.2.2  Parameters . 99
F.7.2.3 Signature key and verification key . 100
F.7.2.4 Per message data . 100
F.7.2.5  Signature . 101
F.7.2.6 Verification . 101
m
F.7.3  Example 3: Field F , m=233, SHA-224 . 101
2
F.7.3.1 General . 101
© ISO/IEC 2015 – All rights reserved v

---------------------- Page: 5 ----------------------
ISO/IEC 14888-3:2017(E)
Deleted: 2016
F.7.3.2 Parameters . 101
F.7.3.3 Signature key and verification key . 101
F.7.3.4 Per message data . 102
F.7.3.5 Signature . 102
F.7.3.6 Verification . 102
m
F.7.4  Example 4: Field F , m=233 (Koblitz Curve), SHA-224 . 103
2
F.7.4.1 General . 103
F.7.4.2 Parameters . 103
F.7.4.3 Signature key and verification key . 104
F.7.4.4 Per message data . 104
F.7.4.5 Signature . 104
F.7.4.6 Verification . 104
m
F.7.5  Example 5: Field F , m=283, SHA-256 . 105
2
F.7.5.1 General . 105
F.7.5.2 Parameters . 105
F.7.5.3 Signature key and verification key . 105
F.7.5.4 Per message data . 105
F.7.5.5 Signature . 106
F.7.5.6 Verification . 106
m
F.7.6  Example 6: Field F , m=283 (Koblitz Curve), SHA-256 . 106
2
F.7.6.1 General . 106
F.7.6.2 Parameters . 106
F.7.6.3 Signature key and verification key .
...

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 14888-3:2016(E)
©
ISO/IEC 2016

---------------------- Page: 1 ----------------------
ISO/IEC 14888-3:2016(E)

COPYRIGHT PROTECTED DOCUMENT
© 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. [phone]
Fax [phone]
[e-mail]
www.iso.org
ii © ISO/IEC 2016 – All rights reserved

---------------------- Page: 2 ----------------------
ISO/IEC 14888-3:2016(E)

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

---------------------- Page: 3 ----------------------
ISO/IEC 14888-3:2016(E)

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

---------------------- Page: 4 ----------------------
ISO/IEC 14888-3:2016(E)

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

---------------------- Page: 5 ----------------------
ISO/IEC 14888-3:2016(E)

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

---------------------- Page: 6 ----------------------
ISO/IEC 14888-3:2016(E)

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

---------------------- Page: 7 ----------------------
ISO/IEC 14888-3:2016(E)

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 certifi
...