ISO/IEC 14888-3:2006

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

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

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

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

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

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

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 cited applies. For undated references, the latest edition of the referenced
document (including any amendments) applies.
ISO/IEC 10118 (all parts), Information technology — Security techniques — Hash-functions
ISO/IEC 14888-1:1998, Information technology — Security techniques — Digital signatures with appendix —
Part 1: General
© ISO/IEC 2006 – All rights reserved 1

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 a, b, c ∈ E, (a ∗ b) ∗ c = a ∗ (b ∗ c);
- there exists e ∈ E with e ∗ a = a for all a ∈ E;
- for all a ∈ E there exists b ∈ E with b ∗ a = e;
- for all a, b ∈ E, a ∗ b = b ∗ a;
- for all a, b ∈ E, a ∗ b ∈ E.
0 n+1 n
NOTE 1 – If a = e, and a = a ∗ a (for n ≥ 0) is defined recursively, the order of a ∈ E is the least positive integer n such
n
that a = e.
NOTE 2 – 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
group E of n elements that contains an element a ∈ E, called the generator, of order n
3.3
pairing
function which takes two elements, P and Q, from an elliptic curve cyclic group over a finite field, G , as input,
and produces an element from another cyclic group over a finite field, G , as output, and which has the
following two properties (where we assume that the cyclic groups G and G have order q, for some prime q,
1 2
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.4
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
a||b concatenation of a and b, in the order specified
a⊕b bitwise exclusive OR of a and b
a , a elliptic curve coefficients
1 2
(A, B, C) a permutation of (S, T , T ), which specifies the functionality of the signature mechanisms
1 2
D  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
2 © ISO/IEC 2006 – All rights reserved

E a finite commutative group; in the mechanisms based on a multiplicative group, elements of E
*
are in Z ; in the mechanisms based on an additive group of elliptic curve points, elements of E
p
are the points on the elliptic curve E over GF(r)
#E the cardinality of E; in the mechanisms based on a multiplicative group, #E is p - 1; in the
mechanisms based on an additive group of elliptic curve points, #E is the number of points on
the elliptic curve E over GF(r)
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 Galois field of cardinality r
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 (first express the data string as
1 1
an integer and then convert the integer into a point on E over GF(r) by using the I2P function,
see Annex C for details)
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)
[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 infinity), and [-n]P = [n](-P)
E
P a generator of G which is used in Mechanisms IBS-1 and IBS-2
p  a prime number or a prime power
q  a divisor of #E and the order of G and G , which is a prime number
1 2
r the size of GF(r); in the mechanisms based on an additive group of elliptic curve points, r is a
m
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 KGC's master private key, which is a randomly chosen integer used in Mechanisms IBS-1 and
IBS-2
V KGC's master public key, which is an element of G used in Mechanisms IBS-1 and IBS-2
*
Z the set of integers U with 0 < U < N and gcd (U, N) = 1, with arithmetic defined modulo N
N
α the bit-length of a prime number (or prime power) p
β the bit-length of a prime number q
γ the output bit-length of hash-functions h and H
Π x-coordinate of Π
x
0  the point at infinity on the elliptic curve E
E
< >  a bilinear and non-degenerate pairing
© ISO/IEC 2006 – All rights reserved 3

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
Y = G ,
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. As a result we use additive group notation here and throughout clause 7.
5.1.2.2 Generation of domain parameters
For the identity-based digital signature mechanisms based on discrete logarithms, the set of domain
parameters includes the following parameters:
- 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
5.1.2.3 Generation of master key
A master private key of a KGC is a secretly generated random or pseudo-random integer U such that
0 < U < q. The corresponding master public key V is an element of G and is computed as
V = [U]P.
4 © ISO/IEC 2006 – All rights reserved

5.1.2.4 Generation of signature key and verification key
A signature key of a signing entity is an element of G and is computed by the KGC as
X = [U]Y,
where U is the KGC's master private key and Y is the public verification key generated from an identity string
ID and a hash-function H , i.e., Y = H (ID).
1 1
5.1.3 Parameter selection
5.1.3.1 Selecting parameter size
The bit-lengths of parameters for typical security levels are shown in Table 1. The minimum recommended
security level is 2 .
NOTE – Security level means the number of steps in the best known attack on a cryptographic primitive. If 2 steps are
required in the best known attack on a hash-function, the security level of the hash-function is 2 . For a comprehensive
analysis of parameter sizes, see Silverman [27], and Lenstra and Verheul [22].
It is not necessary to select α, β, and γ having same security level; the security level of an implemented
signature scheme is the lowest among security levels of parameters.
Table 1 — Parameter sizes according to the security level
80 112 128 192 256
Security level 2 2 2 2 2
1024 2048 3072 7680 15360
α
β 160 224 256 384 512
γ 160 224 256 384 512
5.1.3.2 Selecting hash-function
Selection of hash-functions should be based on those standardized in ISO/IEC 10118-3. That is, h and H are
one of the mechanisms specified in ISO/IEC 10118-3 and H converts a data string obtained by using one of
the mechanisms specified in ISO/IEC 10118-3 into an element in G (see Annex B for details).
NOTE 1 – The hash-functions used in this part of ISO/IEC 14888 should be collision-resistant.
NOTE 2 – The security strength for the selected hash-function must meet or exceed the security strength of the
parameters in key generation. The relation between the security levels of a hash-function and parameters is shown in the
above clause.
Furthermore, implementations that verify digital signatures shall have a way of securely determining which
hash-function was used by the signer. Otherwise an attacker might be able to convince a verifier to use a
different weaker, hash-function and thus bypass the intended security level.
5.1.4 Validity of domain parameters and verification key
The signature verifier may require assurance that the domain parameters and public verification key are valid,
otherwise there is no assurance of meeting the intended security even if the signature verifies, and an
adversary may be able to generate signatures that verify.
© ISO/IEC 2006 – All rights reserved 5

Assurance of the validity of domain parameters can be provided by one of the following:
- Selection of valid domain parameters from a trusted published source, such as a standard;
- Generation of valid domain parameters by a trusted third party, such as a CA or a KGC;
- Validation of candidate domain parameters by a trusted third party, such as a CA or a KGC;
- For the signer, generation of valid domain parameters by the signer using a trusted system; and
- Validation of candidate domain parameters by the user (i.e., the signer or verifier).
Assurance of validity of a public verification key can be provided by one of the following:
- For the signer, generation of the public verification/private signature key pair using a trusted system;
- For the signer or verifier, validation of the public verification key by a trusted third party, such as a CA or
a KGC; and
- Validation of the public verification key by the user (i.e., the signer or verifier).
NOTE 1 – Validation of domain parameters and keys is required. However, how to achieve this is outside the scope of this
document.
NOTE 2 – The method of authenticating the signer is dependent on the real applications, which is out of the scope of this
document.
5.2 Signature process
All of the signature mechanisms in this part of ISO/IEC 14888 make use of a randomizing value K, which is
used (along with the message) to produce a witness R (the first part of the signature) and an assignment (T ,
T ). The signature for the message is the pair (R, S) where S (the second part of the signature) is computed
as the solution of a signature equation.
In the certificate-based mechanisms, specified in Clause 6, the signature equation is
D
AK + BX + C ≡ 0 (mod q),
given that (A, B, C) is a permutation of (S, T , T ), X is the private signature key and D is a parameter
1 2
depending on the particular mechanism.
In the identity-based mechanisms, specified in Clause 7, the signature equation is
D
[K]A + [U ]B + C ≡ 0 (in G ).
E 1
Given that (A, B, C) is a permutation of (S, T , T ), U is the master private key and D is a parameter
1 2
depending on the particular mechanism.
The permutation will be specified or agreed upon when setting up the signature system.
The signature process and the formation of a signed message consist of eight stages (See Figure 1):
- Producing the randomizer
- Producing the pre-signature
- Preparing the message for signing
- Computing the witness
6 © ISO/IEC 2006 – All rights reserved

- Computing the assignment (it is not necessary to compute the assignment in the identity-based
mechanisms)
- Computing the second part of the signature
- Constructing the appendix
- Constructing the signed message.
In this process, the signing entity makes use of its private signature key, its public verification key (optional)
and the domain parameters.
5.2.1 Producing the randomizer
For each signature, the signing entity freshly generates a secret randomizer which is an integer K with
0 < K < q. The output of this stage is K, which shall be kept secret and destroyed safely after use.
NOTE 1 – The randomizer K can be considered as an ephemeral key.
NOTE 2 – For the same rationale of 5.1.1.2, an implementation is still considered compliant if it excludes a few integers
from consideration as possible K values.
5.2.2 Producing the pre-signature
The inputs to this stage are the randomizer K and optionally signature key X, with which the signing entity
computes the pre-signature, Π, by using K and public parameters as input. In the certificate-based
mechanisms specified in Clause 6, it is computed as
K
Π = G
in E. In the identity-based mechanisms specified in Clause 7, it is individually specified in the mechanisms.
The output of this stage is the pre-signature, Π.
5.2.3 Preparing the message for signing
In the process of preparing the message, one of M and M becomes message M, the other becomes empty.
1 2
5.2.4 Computing the witness (the first part of the signature)
The variables to this stage are the pre-signature Π from 5.2.2 and M from 5.2.3. The values of these
variables are taken as inputs to the witness function. The output of the witness function is the witness R. The
witness function is specified in the mechanisms.
5.2.5 Computing the assignment
The inputs to the assignment function are the first part of the signature, which is the witness R from 5.2.4, M
from 5.2.3, and, optionally, the verification key Y. The output of the assignment function is assignment T = (T ,
T ). In the certificate-based mechanisms specified in Clause 6, T and T are integers such tha
...