ISO/IEC 14888-3:2006
(Main)Information technology — Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms
Information technology — Security techniques — Digital signatures with appendix — Part 3: Discrete logarithm based mechanisms
ISO/IEC 14888-3:2006 specifies digital signature mechanisms with appendix whose security is based on the discrete logarithm problem. It 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, ISO/IEC 14888-3:2006 specifies the process of generating keys, the process of producing signatures, and the process of verifying signatures. The verification of a digital signature requires 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 precisely, with (parts of) the signing entity's identification data. This association may be provided by another means that is not covered in ISO/IEC 14888-3:2006. Whatever the nature of such means, the scheme is then said to be 'certificate-based'. If not, the association between the correct verification key and the signing entity's identification data is somehow inherent in the verification key itself. In such a case, the scheme is said to be 'identity-based'. Depending on the two different ways of checking the correctness of the verification keys, the digital signature mechanisms specified in ISO/IEC 14888-3:2006 are categorized in two groups: certificate-based and identity-based.
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
Relations
Standards Content (Sample)
INTERNATIONAL ISO/IEC
STANDARD 14888-3
Second edition
2006-11-15
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:2006(E)
©
ISO/IEC 2006
---------------------- Page: 1 ----------------------
ISO/IEC 14888-3:2006(E)
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
---------------------- Page: 2 ----------------------
ISO/IEC 14888-3:2006(E)
Contents Page
Foreword. vi
Introduction . vii
1 Scope .1
2 Normative references .1
3 Terms and definitions .2
4 Symbols .2
5 General model.4
5.1 Parameter generation process .4
5.1.1 Certificate-based mechanisms.4
5.1.2 Identity-based mechanisms.4
5.1.3 Parameter selection.5
5.1.4 Validity of domain parameters and verification key.5
5.2 Signature process.6
5.2.1 Producing the randomizer .7
5.2.2 Producing the pre-signature.7
5.2.3 Preparing the message for signing.7
5.2.4 Computing the witness (the first part of the signature).7
5.2.5 Computing the assignment .7
5.2.6 Computing the second part of the signature.8
5.2.7 Constructing the appendix .8
5.2.8 Constructing the signed message.8
5.3 Verification process .9
5.3.1 Retrieving the witness.10
5.3.2 Preparing message for verification.10
5.3.3 Retrieving the assignment.10
5.3.4 Recomputing the pre-signature .10
5.3.5 Recomputing the witness .10
5.3.6 Verifying the witness.10
6 Certificate-based mechanisms.11
6.1 DSA .11
6.1.1 Parameters .12
6.1.2 Generation of signature key and verification key .12
6.1.3 Signature process.12
6.1.4 Verification process .13
6.2 KCDSA .14
6.2.1 Parameters .15
6.2.2 Generation of signature key and verification key .15
6.2.3 Signature process.15
6.2.4 Verification process .16
6.3 Pointcheval/Vaudenay algorithm .17
6.3.1 Parameters .17
6.3.2 Generation of signature key and verification key .18
6.3.3 Signature process.18
6.3.4 Verification process .19
6.4 EC-DSA .19
6.4.1 Parameters .20
6.4.2 Generation of signature key and verification key .20
6.4.3 Signature process.20
6.4.4 Verification process .21
© ISO/IEC 2006 – All rights reserved iii
---------------------- Page: 3 ----------------------
ISO/IEC 14888-3:2006(E)
6.5 EC-KCDSA . 22
6.5.1 Parameters. 22
6.5.2 Generation of signature key and verification key. 23
6.5.3 Signature process. 23
6.5.4 Verification process. 24
6.6 EC-GDSA. 24
6.6.1 Parameters. 25
6.6.2 Generation of signature key and verification key. 25
6.6.3 Signature process. 25
6.6.4 Verification process. 26
7 Identity-based mechanisms. 27
7.1 IBS-1 . 27
7.1.1 Parameters. 28
7.1.2 Generation of master key and signature/verification key. 28
7.1.3 Signature process. 28
7.1.4 Verification process. 29
7.2 IBS-2 . 30
7.2.1 Parameters. 30
7.2.2 Generation of master key and signature/verification key. 30
7.2.3 Signature process. 30
7.2.4 Verification process. 31
Annex A (normative) ASN.1 module. 33
Annex B (normative) Conversion functions (I). 36
B.1 Conversion from a field element to an integer (FE2I). 36
B.2 Conversion from an integer to a field element (I2FE) . 36
B.3 Conversion from a field element to a bit sequence (FE2BS). 36
B.4 Conversion from a bit sequence to an integer (BS2I) . 36
B.5 Conversion from an integer to a bit sequence (I2BS) . 37
B.6 Conversion between an integer and an octet string (I2OS & OS2I). 37
Annex C (informative) Conversion functions (II). 38
C.1 Conversion from an integer to a point (I2P) . 38
Annex D (normative) Generation of DSA domain parameters. 40
D.1 Generation of the prime p and q. 40
D.2 Generation of the generator G. 41
D.2.1 Unverifiable generation of G. 41
D.2.2 Verifiable generation of G . 41
Annex E (informative) The Weil and Tate pairings. 42
E.1 The functions f, g and d. 42
E.2 The Weil pairing . 43
E.3 The Tate pairing . 43
Annex F (informative) Numerical examples . 45
F.1 DSA mechanism. 45
F.1.1 Example 1. 45
F.1.2 Example 2. 46
F.2 KCDSA mechanism. 48
F.2.1 Parameters. 48
iv © ISO/IEC 2006 – All rights reserved
---------------------- Page: 4 ----------------------
ISO/IEC 14888-3:2006(E)
F.2.2 Signature key and verification key.49
F.2.3 Per message data .49
F.2.4 Signature .49
F.2.5 Verification .49
F.3 Pointcheval-Vaudenay mechanism.49
F.3.1 Parameters .49
F.3.2 Signature key and verification key.49
F.3.3 Per message data .50
F.3.4 Signature .50
F.3.5 Verification .50
F.4 EC-DSA mechanism .50
m
F.4.1 Example 1: Field F , m =191 .50
2
F.4.2 Example 2: Field F , 192-bit Prime P.51
P
F.5 EC-KCDSA mechanism .52
m
F.5.1 Example 1: Field F , m =163 .52
2
F.5.2 Example 2: Field F , 192-bit Prime P.53
P
m
F.5.3 Example 2: Field F , 32-bit P and m = 5 .54
P
F.6 EC-GDSA mechanism .55
F.6.1 Domain and User Parameters.55
F.6.2 Example 1: Field F , 192-bit Prime P.55
P
F.7 IBS-1 mechanism.56
F.7.1 Example 1: Field F , 512-bit Prime p .56
p
F.7.2 Example 2: Field F , 512-bit Prime p .58
p
F.8 IBS-2 mechanism.60
F.8.1 Example 1: Field F , 512-bit Prime p .60
p
Annex G (informative) Comparison of the signature schemes .64
G.1 Symbols and abbreviated terms for comparing the signature schemes.64
G.2 Comparison of the signature schemes .64
Annex H (informative) Claimed features for choosing a mechanism .66
Bibliography .67
© ISO/IEC 2006 – All rights reserved v
---------------------- Page: 5 ----------------------
ISO/IEC 14888-3:2006(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.
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 14888-3 was prepared by Joint Technical Committee ISO/IEC JTC 1, Subcommittee SC 27,
IT Security techniques.
This second edition cancels and replaces the first edition (ISO/IEC 14888-3:1998), which has been technically
revised. It also incorporates Technical Corrigendum ISO/IEC 14888-3:1998/Cor.1:2001. New mechanisms
and object identifiers have been specified.
ISO/IEC 14888 consists of the following parts, under the general title Information technology — Security
techniques — Digital signatures with appendix:
⎯ Part 1: General
⎯ Part 2: Integer factorization based mechanisms
⎯ Part 3: Discrete logarithm based mechanisms
vi © ISO/IEC 2006 – All rights reserved
---------------------- Page: 6 ----------------------
ISO/IEC 14888-3:2006(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:
o the verification key but not the signature key,
o a set of signatures on a sequence of messages that an attacker has adaptively chosen,
it should be computationally infeasible for the attacker:
o to produce a valid signature on a new message,
o to produce a new signature on a previously signed message, or
o to recover the signature key.
• It should be computationally infeasible, even for the signer, to find two different messages with the
same signature.
NOTE – Computational feasibility depends on the specific security requirements and environment.
Digital signature mechanisms are based on asymmetric cryptographic techniques and involve 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.
There are 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 non-randomized (or deterministic); see ISO/IEC 14888-1.
• When, for a given message and signature key, each application of the signature process produces a
different signature, the mechanism is said to be randomized.
The eight 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" (which is 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" (see ISO/IEC 9796).
Security of the digital signature mechanisms is based on unsolvable problems, i.e. problems for which, given
current knowledge, finding a solution is computationally infeasible, such as the factorization problem and the
discrete logarithm problem. ISO/IEC 14888-3 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 – The previous version of ISO/IEC 14888 grouped identity-based mechanisms into Part 2 and certificate-based
mechanisms into Part 3, with each of the two parts covering mechanisms based on both the discrete logarithm and the
factorisation problems. This revision re-organizes the grouping, so that Part 2 contains integer factoring based
mechanisms and Part 3 discrete logarithm based mechanisms.
This part of ISO/IEC 14888 includes eight mechanisms, two of which were in ISO/IEC 14888-3:1998, and
three of which are in ISO/IEC 15946-2:2002. The Korean Certificate-based Digital Signature Algorithm
(KCDSA) and two mechanisms based on pairing technology are newly added.
© ISO/IEC 2006 – All rights reserved vii
---------------------- Page: 7 ----------------------
ISO/IEC 14888-3:2006(E)
The mechanisms specified in this part of ISO/IEC 14888 use a collision resistant hash-function for hashing the
entire message (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 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 (SD 8) "Patent Information". SD 8 is publicly available at:
http://www.ni.din.de/sc27
Further information is available from the identified patent-holders.
Area Inventors Patent Issue date Contact address
DSA Kravitz US 5 231 668 1993-07-27 [no licence required]
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 2006 – All rights reserved
---------------------- Page: 8 ----------------------
INTERNATIONAL STANDARD ISO/IEC 14888-3:2006(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;
- 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;
- the process of verifying signatures.
The verification of a digital signature requires 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 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 derive 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 – For certificate-based mechanisms, various PKI standards can be used for key management. For further
information, see ISO/IEC 11770-3, ISO/IEC 9594-8 (also known as X.509) and ISO/IEC 15945.
2 Normative references
The following referenced documents are indispensable for the application of this document. For dated
references, only the edition
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.