ISO/IEC 14888-3:1998

INTERNATIONAL ISO/IEC
STANDARD 14888-3
First edition
1998-12-15
Corrected and reprinted
1999-12-15
Information technology — Security
techniques — Digital signatures with
appendix —
Part 3:
Certificate-based mechanisms
Technologies de l'information — Techniques de sécurité — Signatures
digitales avec appendice —
Partie 3: Mécanismes fondés sur certificat
Reference number
Foreword
ISO (the International Organization for Standardization) and the 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.
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.
International Standard ISO/IEC 14888-3 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information
technology, Subcommittee SC 27, IT Security techniques.
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: Identity-based mechanisms
— Part 3: Certificate-based mechanisms
Further parts may follow.
Annexes A and B form an integral part of this part of ISO/IEC 14888. Annexes C to G are for information only.
©  ISO/IEC 1998
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 the publisher.
ISO/IEC Copyright Office • Case postale 56 • CH-1211 Genève 20 • Switzerland
Printed in Switzerland
ii
©
INTERNATIONAL STANDARD  ISO/IEC ISO/IEC 14888-3:1998(E)
Information technology — Security techniques — Digital
signatures with appendix —
Part 3:
Certificate-based mechanisms
ISO/IEC 9796:1991, Information technology —
1  Scope
Security techniques — Digital signature scheme
ISO/IEC 14888 specifies digital signature
giving message recovery.
mechanisms with appendix for messages of
arbitrary length and is applicable for providing data
Information technology —
ISO/IEC 9796-2:1997,
origin authentication, non-repudiation, and integrity
Security techniques — Digital signature schemes
of data.
giving message recovery — Part 2: Mechanisms
using a hash-function.
This part of ISO/IEC 14888 specifies certificate-
based digital signature mechanisms with appendix.
ISO/IEC 10118-3:1998, Information technology —
In particular, this part of ISO/IEC 14888 provides 1)
Security techniques — Hash-functions — Part 3:
a general description of certificate-based digital
Dedicated hash-functions
.
signature mechanisms whose security is based on
the difficulty of the discrete logarithm problem in
Information technology —
ISO/IEC 10118-4:1998,
the underlying commutative group (see Clause 6),
Security techniques — Hash-functions — Part 4:
2) a general description of certificate-based digital
Hash-functions using modular arithmetic
.
signature mechanisms whose security is based on
the difficulty of factoring (see Clause 7), and 3) a
3  General
variety of normative digital signature mechanisms
with appendix using certificate-based mechanisms
This part of ISO/IEC 14888 makes use of the
for messages of arbitrary length (see Annex A
definitions, symbols, legend for figures, and
and B).
notation given in ISO/IEC 14888-1.
The verification of a digital signature requires the
2  Normative references
signing entity's verification key. It is thus essential
The following standards contain provisions which,
for a verifier to be able to associate the correct
through reference in this text, constitute provisions
verification key with the signing entity. For
of this part of ISO/IEC 14888. At the time of
certificate-based mechanisms, this association
publication, the editions indicated were valid. All
must be provided by some certifying measure, for
standards are subject to revision, and parties to
example, the verification key is retrieved from a
agreements based on this part of ISO/IEC 14888
certificate.
are encouraged to investigate the possibility of
applying the most recent editions of the standards
The goal of this part of ISO/IEC 14888 is to specify
indicated below. Members of IEC and ISO maintain
the following processes and functions within the
registers of currently valid International Standards.
general model described in ISO/IEC 14888-1:
ISO/IEC 14888-1:1998, Information technology —
- the process of generating keys
Security techniques — Digital signatures with
- generating domain parameters
appendix — Part 1: General.
- generating signature and verification keys
ISO/IEC 14888-2:1999, Information technology —
Security techniques — Digital signatures with
- the process of producing signatures
appendix — Part 2: Identity-based mechanisms
.
- (optional) producing pre-signatures
- preparing the message for signature
©
- computing witnesses
6  Digital signature mechanisms based
- computing the signature
on discrete logarithms
- the process of verification
6.1 Key generation process
- preparing message for verification
6.1.1 Generating domain parameters
- retrieving the witness
For digital signature mechanisms based on
- computing the verification function
discrete logarithms, the set Z of domain
- verifying the witness
parameters determines the following parameters:
4  Definitions
- a finite commutative group E
For the purpose of this part of ISO/IEC 14888, the
- one or more divisors Q of #E
definitions of ISO/IEC 14888-1 apply. Additional
- one or more elements G of order Q in E
definitions which are required are as follows.
In the group E, multiplicative notation is used. The
4.1 Finite commutative group: A finite set J with
signature mechanism will use one element G in E.
the binary operation «∗« such that:
It is worthwhile to note that the particular signature
mechanism chosen may place additional
- For all a, b, c∈J, (a∗b) ∗ c = a ∗ (b∗c)
constraints on the choice of E, Q, and G.
- There exists e∈J with e∗a = a for all a∈J
6.1.2 Generation of signature key and
- For all a∈J there exists b∈J with b∗a = e
verification key
- For all a, b∈J, a∗b = b∗a
A signature key of a signing entity is a secretly
generated random or pseudo-random integer X
4.2 Order of an element in a finite commutative
such that 0 < X < Q and gcd(X, Q) = 1. The
0 n+1 n
∗ ≥
group: If a =e, and a =a a (for n 0), is corresponding public verification key Y is an
element of E and is computed as
∈
defined recursively, the order of a J is the least
n
positive integer n such that a = e.
X
Y = G .
5  Symbols and notation
Note: It is allowed to exclude a few integers from consideration
Throughout this part of ISO/IEC 14888 the
as possible X values.
following symbols and notations are used in
addition to those given in ISO/IEC 14888-1.
In some instances, validation of domain
parameters and keys may be required. However, it
E a finite commutative group
is outside the scope of this standard.
#E the cardinality of E
6.2 Signature process
a||b concatenation of b to a
In this clause the signature process for a class of
signature mechanisms is described. Within this
Q a divisor of #E
class the signature function for the mechanism to
G an element of order Q in E
be used is specified by a permutation (A, B, C) of
(S,T ,T ) which determines the coefficients of the
1 2
gcd(U, N) the greatest common divisor of
signature equation.
integers U and N
T1 first part of assignment
K X ≡ Q
A + B + C 0 (mod ).
T second part of assignment
This permutation will be specified or agreed upon
Z U ≤ U < N
the set of integers with 0
N when setting up the signature system.
*
Z U U N
the set of integers with 0 < <
N
The signature process and the formation of a
and gcd (U, N) = 1
signed message consists of eight stages (See
Figure 1):
a the greatest integer equal to or less
than a
- producing the randomizer
- producing the pre-signature
- preparing the message for signing
©
ISO/IEC ISO/IEC 14888-3:1998(E)
- computing the witness (the first part of the from 6.2.5, the permutation (A, B, C) of (S,T ,T )
1 2
signature) and domain parameter Q as specified in 6.1.1. The
- computing the assignment
signing entity forms the signature equation
- computing the second part of the signature
- constructing the appendix
(AK + BX + C) ≡ 0 (mod Q)
- constructing the signed message
S
and solves the signature equation for , the
In this process, the signing entity makes use of its
second part of the signature, where 0 X
private signature key , and the domain
pair (R, S) will be called the signature, Σ.
E G Q.
parameters , , and
6.2.7 Constructing the appendix
6.2.1 Producing the randomizer
The appendix is constructed from the signature
The signing entity generates a secret randomizer
text R S text
and an optional text field, , as (( , ), ). The
which is an integer K with 0 < K < Q and satisfying
text field could include a certificate which
gcd (K, Q) = 1. The output of this stage is K, which
cryptographically ties the public verification key to
the signing entity keeps secret.
the identification data of the signing entity.
Note: It is allowable to exclude a few integers from
Note: As indicated in ISO/IEC 14888-1, depending on the
consideration as possible K values.
application, there are different ways of forming the appendix
and appending it to the message. The general requirement is
that the verifier is able to relate the correct signature to the
6.2.2 Producing the pre-signature
message. For successful verification, it is also essential that
K
The input to this stage is the randomizer , with
prior to the verification process, the verifier is able to associate
the correct verification key with the signature.
which the signing entity computes
K
6.2.8 Constructing the signed message
Π = G
The signed message is obtained by the
in E. The output of this stage is the pre-signature,
concatenation of message M and appendix,
M R S text
Π. || (( , ), )
6.2.3 Preparing the message for signing
The message is split into two parts which will be
called data inputs M and M . One of these parts
1 2
may be empty and the two parts need not be
distinct (See ISO/IEC 14888-1 for further details.)
6.2.4 Computing the witness (the first part of
the signature)
The variables to this stage are the pre-signature Π
M
from 6.2.2 and from 6.2.3. The values of these
variables are taken as inputs to the witness
function. The output of the witness function is
witness R.
6.2.5 Computing the assignment
The inputs to the assignment function are the first
R
part of the signature, which is the witness from
M
6.2.4, and from 6.2.3. The output of the
assignment function is assignment T = (T ,T )
1 2
where T and T are integers such that
1 2
0 < |T | < Q , 0 < |T | < Q.
1 2
6.2.6 Computing the second part of the
signature
The inputs to this stage are randomizer K from
X, T T T
6.2.1, the signature key assignment = ( , )
1 2
©
Signature Key, X
Message, M
X
M
Producing
Pre-Signature
text
Preparing
�
message
M
2 M
Computing Witness
K
R
Computing
Assignment
T
Computing Second Part of Signature
S
Signature
(R,S)
Constructing Appendix ((R,S ), text)
Constructing Signed Message
M||((R,S), text)
Signed Message
Figure 1 — Signature process with randomized witness
©
ISO/IEC ISO/IEC 14888-3:1998(E)
6.3 Verification process 6.3.4 Verifying the witness
The verification process consists of four stages The signature is verified if the recomputed witness,
(See Figure 2).
R from 6.3.3.3 is equal to R from 6.3.2. Additional
checks may be required (See A.1.2.4.6 for other
- Preparing message for verification
example checks.)
- Retrieving the witness
- Computing the verification function
- retrieving the assignment
- recomputing the pre-signature
- recomputing the witness
- Verifying the witness.
In this process, the verifier makes use of the
signer’s verification key Y and the domain
parameters: finite group E, element G in E and its
order Q.
6.3.1 Preparing message for verification
The verifier retrieves M from the signed message
and divides the message into two parts M and M .
1 2
6.3.2 Retrieving the witness
The verifier retrieves the signature (R, S) from the
appendix, and divides it into witness R and the
second part of the signature S.
6.3.3 Computing the verification function
6.3.3.1 Retrieving the assignment
This stage is identical to 6.2.5. The inputs to the
assignment function consist of the witness R from
M
6.3.2 and from 6.3.1. The assignment
T T T
= ( , ) is recomputed as the output from the
1 2
assignment function.
6.3.3.2 Recomputing the pre-signature
Z
The inputs to this stage are the set of domain
Y
parameters, the verification key , the assignment
T = (T ,T ) from 6.3.3.1 and the second part of the
1 2
signature S from 6.3.2. The verifier assigns to the
coefficients (A, B, C) the values (S,T ,T ) according
1 2
to the order specified by the signature function, and
∏ E
computes the element in as
m n
∏ = Y G
-1 -1
where m = -A B mod Q and n = -A C mod Q.
6.3.3.3 Recomputing the witness
The computations at this stage are the same as in
6.2.4. The verifier executes the witness function.
The inputs are ∏ from 6.3.3.2 and M from 6.3.1.
The output is the recomputed witness, R .
©
Message, M Verification Key, Y
Signature,�
S R
Y
M
Preparing
Message
M M
1 2
Retrieving
Assignment
T
Recomputing
Pre-Signature
��
Recomputing
Witness
�R
Verifying
Witness
yes/no
Figure 2 — Verification process with a randomized witness
©
ISO/IEC ISO/IEC 14888-3:1998(E)
7.2.1.2 Computing the pre-signature
7  Digital signature mechanisms based
The pre-signature is a function of the randomizer
on factoring
and independent of the message. The input to this
Digital signature mechanisms based on factoring
stage is the randomizer K and the signature key.
utilize a deterministic witness and produce a one-
The output of this stage is the pre-signature,
part signature, but can be randomized or
denoted Π.
deterministic (Reference ISO/IEC 14888-1,
Figures 2 and 4). In either case, such a
7.2.2 Preparing of message for signing
mechanism employs an integer N as a component
of the verification key whose factorization is part of
M
The message is used to construct data inputs
the signature key. It is assumed that it is
M M
and . The second part, , might be empty and
2 2
computationally infeasible to factor N into its prime
the two inputs need not be distinct.
factors. Constraints should be imposed on the
generation of the signature key to make the
7.2.3 Computing the witness
factorization sufficiently difficult.
The input to this stage is the data input M . The
H
output is the hash token, , determined by the data
7.1 Key generation process
M
input . Note that the hash token is interpreted
7.1.1 Generation of domain parameters
as an integer mod N chosen so that 0 < H < N.
For digital signature mechanisms based on
factoring, the set Z of domain parameters 7.2.4 Computing the signature
optionally contains an integer v used as a system
The inputs to this stage are the witness computed
wide portion of the verification key, subject to the
in 7.2.3, the signature key from 7.1.2.1 and
conditions specified in 7.1.2.
optional data input M (See ISO/IEC 14888-1,
Figure 2). For a randomized mechanism, the
7.1.2 Generation of signature key and
randomizer K and the pre-signature Π are also
verification key
valid inputs. The output is a one-part signature
7.1.2.1 Generation of signature key Σ = S.
A signature key of a signing entity is a secretly
7.2.5 Constructing the appendix
generated collection X = ({P ,P , …, P }, s),
1 2 r
consisting of a set of randomly or pseudo-randomly
The appendix is constructed from the signature, Σ
chosen, but not necessarily distinct prime integers
and an optional text field, text. The text field could
P , and an integer s. The minimum number of
i
include a certificate which cryptographically ties the
distinct primes to be used is two.
public verification key to the identification data of
the signing entity.
7.1.2.2 Generation of verification key
Y N v
The verification key is a pair of integers ( , )
7.2.6 Constructing the signed message
where N is the product, Π P of all primes P and v
The signed message is obtained by concatenating
i i
the message M with the appendix from 7.2.5,
is an integer which satisfies a condition depending
on the signature key.
v
If is specified as a domain parameter, additional M || (Σ , text ).

constraints might be imposed on the signature key
so that v satisfies the appropriate condition.
7.3 Verification process
7.3.1 Preparing message for verification
7.2 Signature process
The verifier retrieves M from the signed message
7.2.1 Producing the pre-signature (optional)
and determines the two data input parts M and M
1 2
A randomized signature mechanism employs a
as specified in 7.2.2.
pre-signature, which depends only on a randomizer
and a signature key. The pre-signature is
7.3.2 Retrieving the witness
computed in two steps.
The verifier retrieves the value of the witness H as
a function of the data input M according to the
7.2.1.1 Producing the randomizer
witness function specified in 7.2.3.
The signing entity secretly generates a randomizer
K N
which is an integer mod , possibly subject to
7.3.3 Computing the verification function
additional constraints. The output of this stage is
Using the integer v obtained either from the
K, which the signing entity keeps secret.
domain parameter set Z or the verification key Y,
©
the verifier uses the verification function to obtain a
recomputed witness, H .
7.3.4 Verifying the witness
The signature is valid if the value of the retrieved
witness H agrees with the value from the
verification function of the recomputed witness, H .
©
ISO/IEC ISO/IEC 14888-3:1998(E)
Annex A
(normative)
Examples of certificate-based digital signatures with appendix based on discrete
logarithms
Examples of such signature mechanisms are the Secure Hash Algorithm is also described in
Digital Signature Algorithm (DSA) of the U.S. NIST, ISO/IEC DIS 10118-3. (Note that no control field
Pointcheval/Vaudenay, and elliptic curve with a hash-function identifier is required for DSA,
signatures. These schemes are described below. thus the hash token is simply h(M). See ISO/IEC
14888-1).
The groups used for the signature mechanisms
The coefficients (A, B, C) of the DSA signature
*
include a multiplicative group Z             , where P is a
P
equation are set as follows
prime (i.e., DSA and Pointcheval/Vaudenay) and
an additive group formed by the points of an elliptic
(A, B, C) = (S,T ,T ).
1 2
curve over a finite field (i.e., Elliptic Curve DSA).
Thus the signature equation becomes
A.1 Non-Elliptic curve based examples
A.1.0 Symbols and notation (SK - RX - H) ≡ 0 (mod Q).
P prime integer
A.1.1.1 DSA Parameters
Z ≤
set of integers U with 0 U < P
P
* L I l ≤ I
512 + 64 , for an integer 0  < 8
Z
set of integers U with 0 < U < P
P L-1 L
P a prime, where 2 < P < 2
Q P Q
a prime divisor of -1, where 2 <
A.1.1 The U.S. Digital Signature Algorithm 160
< 2
(DSA)
F an integer such that 1 < F < P-1 and F
(P - 1)
/
This example is taken from the U.S. National
Q
mod P >1
Institute of Standards and Technology (NIST)
(P -1)
/
Q
GF mod P, an element of order Q
Federal Information Processing Standards
*
E Z
Publication 186 (FIPS PUB 186), 19 May 1994. in =
P
The general parameters defined in clause 6 shall
have the following forms. The notation here has P Q G
The integers , , and can be public and can be
been changed slightly from FIPS PUB 186 to
common to a group of users.
conform with notation used elsewhere in this part
To achieve FIPS compliance, parameters P and Q
of ISO/IEC 14888.
are generated as specified in FIPS PUB 186,
* Appendix 2 (Details can be found in Annex C of
The DSA is a signature mechanism with E Z P
=  ,
P
this part of ISO/IEC 14888).
a prime, and Q a prime dividing P - 1. The
M M M
message is split such that is empty and = .
1 2
Note 1: The size of the prime P in this normative example is as
The witness function is defined by the formula specified by the Digital Signature Algorithm (DSA). Note that
P
the size of is restricted to be at most 1024 bits. As of 19 May
P
1994, the size of provides a sufficient security margin. It is
R = Π mod Q
acknowledged that future advances in number theoretic
algorithms may possibly render the size of P of 1024 bits as
and the assignment function by the formula insufficient.
Note 2: It is recommended that all users check the proper
(T ,T ) = (-R,-H)
1 2
generation of the DSA public parameters.
Note 3: It is recognized that DSA possesses an unfavourable
where H = h(M) is the hash-token of message M,
property in which an attack can be mounted where collisions on
the underlying hash function can be found with a complexity of
converted to an integer according to the
74 80
2 as compared to 2 in the most secure case. This attack
conversion rule given in Annex C. The hash-
though is easily detectable. For users who may still wish to
function h is the Secure Hash Algorithm (SHA) as
avoid this property, it can be prevented by using the
adopted in the U.S. NIST Secure Hash Standard
mechanism of A.1.2.
(SHS), FIPS PUB 180-1, 17 April 1995. The
©
be generated and the signature should be
A.1.1.2 DSA generation of signature key and
recalculated. (It is extremely unlikely that R = 0 or
verification key
S
= 0 if signatures are generated properly).
The signature key of a signing entity is a secretly
generated random or pseudo-random integer X
A.1.1.3.7 Constructing the appendix
X Q
such that 0 < < . The corresponding public
Y
verification key is The appendix will be the concatenation of (R, S)
and an optional text field, text, (R, S)||text.
X
Y =G .
A.1.1.3.8 Constructing the signed message
A user's secret signature key X and public
A signed message is the concatenation of a
verification key Y are normally fixed for a period of
message, M, and the appendix.
time. The signature key X must be kept secret.
M||(R, S)||text
A.1.1.3 DSA signature process
A.1.1.3.1 Producing the randomizer
A.1.1.4 DSA verification process
The signing entity computes a random or pseudo-
Prior to verifying the signature of a signed
K K Q K
random integer such that 0< < . Parameter
message, it is necessary that the verifier has
must be generated for each signature and must be
trusted copies of P, Q and G.
kept secret.
The verifier also acquires the necessary data items
A.1.1.3.2 Producing the pre-signature for the verification process. For example, the
verification key (see ISO/IEC 14888-1, clause 9 for
The input to this stage is the randomizer K and the
additional required data items).
signing entity computes
K
A.1.1.4.1 Preparing the message for
Π = G mod P
verification
The verifier retrieves M = M from the signed
A.1.1.3.3 Preparing the message for signing 2
M
message. is empty.
The message is split such that M is empty and M
1 2
is the message, M = M.
A.1.1.4.2 Retrieving the witness
The verifier retrieves the witness R and the second
A.1.1.3.4 Computing the witness
part of the signature S from the appendix.
The signing entity computes R = Π mod Q where
the witness is simply a function of the pre-
A.1.1.4.3 Retrieving the assignment
signature. Thus,
This stage is identical to A.1.1.3.5. The inputs to
K
the assignment function consist of the witness R
R = (G mod P) mod Q
from A.1.1.4.2 and M from A.1.1.4.1. The
assignment T = (T ,T ) is recomputed as output
1 2
A.1.1.3.5 Computing the assignment
from the assignment function, A.1.1.3.5.
T T
The signing entity computes the assignment ( , )
1 2
= (-R,-H) where H = h(M) is the hash-token of
A.1.1.4.4 Recomputing the pre-signature
message M and M = M .
The inputs to this stage are domain parameters,
verification key Y, assignment T = (T ,T ) from
1 2
A.1.1.3.6 Computing the second part of the
A.1.1.4.3 and second part of the signature S from
signature
A.1.1.4.2. The verifier assigns the coefficients
The signature is (R, S). Thus,
S T T
(A, B, C) the values ( , , ) as determined by the
1 2
signature function, and obtains a recomputed value
K
R = (G mod P) mod Q
-1
Π of the pre-signature using the formula
S K h M XR Q
= ( ( ( ) + )) mod
-1 -1
-A B Q -A C Q
mod mod
Π = Y G mod P in E.
The value of h(M) is a 160-bit string output of the
Secure Hash Algorithm. For use in computing S,
this string must be converted to an integer. The A.1.1.4.5 Recomputing the witness
conversion rule is given in Annex C.
The computations at this stage are the same as in
A.1.1.3.4. The verifier executes the witness
As an option, one may wish to check if R = 0 or S =
function. The input is Π from A.1.1.4.4. Note that
0. If either R = 0 or S = 0, a new value of K should
©
ISO/IEC ISO/IEC 14888-3:1998(E)
M is empty. The output is the recomputed witness
A.1.2.2 Pointcheval/Vaudenay generation of
signature key and verification key
R.
The signature key of a signing entity is a secretly
generated random or pseudo-random integer X
A.1.1.4.6 Verifying the witness
X Q
such that 0 < < . The corresponding public
Let M be the value from A.1.1.4.1, and R and S
Y
verification key is
the values from A.1.1.4.2. Let Y be the public
verification key of the signing entity. To verify the
X
Y =G .
signature, the verifier first checks to see that
R Q S Q
0 < < and 0 < < . If either condition is
A user's secret signature key X and public
violated the signature shall be rejected. If these two
verification key Y are normally fixed for a period of
conditions are satisfied, the verifier compares the
time. The signature key X must be kept secret.
R
recomputed witness, from A.1.1.4.5 to the value
of R from A.1.1.4.2. If R = R, then the signature is
A.1.2.3 Pointcheval/Vaudenay signature
valid.
process
A.1.2.3.1 Producing the randomizer
A.1.2 Pointcheval/Vaudenay signatures
The signing entity computes a random or pseudo-
The method of Pointcheval/Vaudenay is a variant
random integer K such that 0 *
E
of the DSA algorithm, with = Z , P a prime, and
P
1.
Q P
a prime divisor of -1. The message is split
such that M is empty and M = M. The witness is
1 2
A.1.2.3.2 Producing the pre-signature
defined by the formula
The input to this stage is the randomizer K and the
signing entity computes
R = Π mod Q
K
Π = G mod P.
and the assignment function by the formula
(T ,T ) = (-R,-H) A.1.2.3.3 Preparing message for signing
1 2
M M
The message is split such that is empty and
1 2
where H = h(R ||M) is the hash token of the
M M
is the message, = .
R
concatenation of the witness and the message
M
. The hash-function h is the Secure Hash
A.1.2.3.4 Computing the witness
Algorithm (SHA-1). Note that the computation of
R Π Q
The signing entity computes = mod where
T above requires the conversion of the hash code
the witness is simply a function of the pre-
to an integer. Some agreed upon method for this
signature. Thus,
conversion is required for this step (see for
example ISO/IEC DIS 10118-4) .
K
R G P Q
= ( mod ) mod
The coefficients (A, B, C) of the
A.1.2.3.5 Computing the assignment
Pointcheval/Vaudenay signature equation are set
as follows
The signing entity computes the assignment (T ,T )
1 2
= (-R,-H), where H = h(R||M) is the hash token of
(A, B, C) = (S, T , T ).
M
1 2 the concatenation of the witness and message
M M
(and = ).
Thus the signature equation becomes
A.1.2.3.6 Computing the signature
SK - RX - H ≡ 0 (mod Q).
The signature is (R, S). Thus,
K
A.1.2.1 Pointcheval/Vaudenay parameters
R G P Q
= ( mod ) mod
-1
P prime number S K R M XR Q
= (h( || ) + ) mod .
Q prime divisor of P-1
F integer such that 1 < F < P-1 and
A.1.2.3.7 Constructing the appendix
(P -1)
/
Q
F P
mod >1 The appendix will be the concatenation of (R, S)
P
( -1)
/Q
text R S text
and an optional text field, , ( , )|| .
GF mod P
P Q
Note: Special care should be taken to the generation of , ,
and F. For example, the procedures of A.1.1.1 may be used.
©
If these two conditions are satisfied, the verifier
A.1.2.3.8 Constructing the signed message
compares the recomputed witness, R from
A signed message is the concatenation of a
message, M, and the appendix.
A.1.2.4.5 to the value of R from A.1.2.4.2. If R =
R
, then the signature is valid.
M||(R, S)||text
A.2 Elliptic curve based example
A.1.2.4 Pointcheval/Vaudenay verification
A.2.1 Elliptic curve DSA
process
The following scheme is an elliptic curve analogue
Prior to verifying the signature of a signed
of the DSA algorithm. [See Annex D for additional
message, it is necessary that the verifier has
elliptic curve mathematical background
trusted copies of P, Q and G and the other
information.] Thus it is a signature mechanism with
necessary data items.
E being a cyclic group of points on an elliptic curve.
We take
A.1.2.4.1 Preparing the message for
verification
(A, B, C) = (S, T , T )
1 2
M M
The verifier retrieves = from the signed
M
message. is empty.
where (T ,T ) = (-R,H) and H is the hash token of
1 2
the message M.
A.1.2.4.2 Retrieving the witness
The verifier retrieves the witness R and the second Thus the signature equation becomes
S
part of the signature from the appendix.
SK - RX + H ≡ 0 (mod Q).
A.1.2.4.3 Retrieving the assignment
A.2.1.1 Elliptic curve DSA parameters
This stage is identical to A.1.2.3.5. The inputs to
the assignment function consist of the witness R
F  a finite field
from A.1.2.4.2 and M from A.1.2.4.1. The
2 E  Elliptic curve group over field F
T T T
assignment = ( , ) is recomputed as output
1 2  # E    the cardinality of E
from the assignment function, A.1.2.3.5.
Q E
a prime divisor of #
G Q
a point on the elliptic curve of order
A.1.2.4.4 Recomputing the pre-signature
Note: Although it is standard in the literature to write the
The inputs to this stage are domain parameters,
arithmetic of elliptic curve groups additively, we will be
verification key Y, assignment T = (T ,T ) from
1 2
consistent with the general description above and use
S
A.1.2.4.3 and second part of the signature from
multiplicative notation.
A.1.2.4.2. The verifier assigns the coefficients
S T T
(A, B, C) the values ( , , ) as determined by
1 2
A.2.1.2 Elliptic curve DSA generation of
the signature function, and obtains a recomputed
signature key and verification key
value Π of the pre-signature by computing it using
The signature key of a signing entity is a secretly
the formula
X
generated random or pseudo-random integer
X Q
such that 0 < < . The corresponding public
-1 -1
-A B mod Q -A C mod Q
Π = Y G mod P verification key Y is
X
in E. Y =G .
A user's secret signature key X and public
A.1.2.4.5 Recomputing the witness
Y
verification key are normally fixed for a period of
The computations at this stage are the same as in
X
time. The signature key must be kept secret.
A.1.2.3.4. The verifier executes the witness
function. The inputs are Π from A.1.2.4.4 and M
A.2.1.3 Elliptic curve DSA signature process
from A.1.2.4.1. The output is the recomputed
A.2.1.3.1 Producing the randomizer
witness R.
The random secret integer K is generated,
0 < K < Q.
A.1.2.4.6 Verifying the witness
M R S
Let  be the value from A.1.2.4.1, and and
A.2.1.3.2 Producing the pre-signature
the values from A.1.2.4.2. The verifier checks to
K
The input to this stage is the randomizer and the
see that 0 < R < Q and 0 < S < Q. If either
signing entity computes
condition is violated the signature shall be rejected.
K
Π = G .
©
ISO/IEC ISO/IEC 14888-3:1998(E)
A.2.1.3.3 Preparing message for signing A.2.1.4.1 Preparing message for verification
The message is split such that M is empty and M The verifier retrieves M from the signed message
1 2
is the message, M = M. and divides the message into two parts M and M .
2 1 2
M will be empty and M = M.
1 2
A.2.1.3.4 Computing the witness
A.2.1.4.2 Retrieving the witness
The signing entity computes R = Π mod Q where
x
The verifier retrieves the witness R and the second
Π is the x coordinate of the point Π, interpreted
x
part of the signature S from the appendix.
Q
as an integer in the range [1, -1] (See
ISO/IEC 14888-1, subclause 5.2).
A.2.1.4.3 Retrieving the assignment
A.2.1.3.5 Computing the assignment This stage is identical to A.2.1.3.5. The inputs to
R
the assignment function consist of the witness
The signing entity computes the assignment (T ,T )
1 2
from A.2.1.4.2 and M from A.2.1.4.1. The
= (-R, H) where H is the hash-token of the
assignment T = (T ,T ) is recomputed as output
1 2
M
message .
from the assignment function, A.2.1.3.5.
A.2.1.3.6 Computing the second part of the
A.2.1.4.4 Recomputing the pre-signature
signature
The inputs to this stage are system parameters,
The signature is (R, S). Thus,
Y T T T
verification key , assignment = ( , ) from
1 2
A.2.1.4.3 and second part of the signature S from
R = Π mod Q
x
A.2.1.4.2. The verifier assigns the coefficients
-1
S = (K (XR - H)) mod Q
(A, B, C) the values (S,T ,T ) as determined by the
1 2
So that
signature function, and obtains a recomputed value
-1
Π of the pre-signature by computing it using the
(R, S) = ((Π ) mod Q , (K (XR - H)) mod Q )
x
formula
-1 -1
A.2.1.3.7 Constructing the appendix
-A C mod Q A B mod Q
Π = G Y
R S
The appendix will be the concatenation of ( , )
text R S text
and an optional text field, , ( , )|| .
A.2.1.4.5 Recomputing the witness
The computations at this stage are the same as in
A.2.1.3.8 Constructing the signed message
A.2.1.3.4. The verifier executes the witness
A signed message is the concatenation of the
function. The input is Π from A.2.1.4.4. The output
message, M, and the appendix.
is the recomputed witness R.
M R S text
||( , )||
A.2.1.4.6 Verifying the witness
A.2.1.4 Elliptic curve DSA verification process
Let M, R, and S be the values retrieved from the
signed message, and let Y be the public
The verifying entity acquires the necessary data
verification key of the signer. To verify the
items required for the verification process.
signature, the verifier first checks to see that
0 < R < Q and 0 < S < Q; if either condition is
violated the signature shall be rejected. If these two
conditions are satisfied, the verifier compares the
R
recomputed witness, from A.2.1.4.5 to the
R
retrieved version of from A.2.1.4.2.
R R
If = , then the signature is verified.
©
Annex B
(normative)
Example of certificate-based digital signatures with appendix based on factoring
Examples of such signature mechanisms are
sv ≡ P P v
1  mod ½ lcm ( - 1, - 1) if is even.
1 2
digital signatures with hashing based on ISO/IEC
The signature key X is the set ({P , P },s).
1 2
9796 (deterministic) and ESIGN (randomized).
These schemes are described below.
B.1.2.3 Generation of verification key
The verification key Y is the set (N, v).
B.1 Digital signatures with hashing
based on ISO/IEC 9796
B.1.3 Signature process
The digital signature mechanism given in ISO/IEC
The signature process is that of a deterministic
9796 is a deterministic signature mechanism
signature mechanism, and as such does not
based on factoring. As such, it does not employ a
produce a pre-signature.
randomizer or pre-signature. There are exactly two
secret prime factors P , P in the signature key
1 2
B.1.3.1 Preparing the message for signing
defined in clause 7.
The data input M = M is the message; M is
1 2
empty.
B.1.1 Generation of the domain parameters
The domain parameters Z optionally contain a
B.1.3.2 Computing the witness
specification for a system wide verification
exponent v. Other system parameters such as a
The deterministic witness is an integer H Mod N,
hash function are optionally specified in the domain
determined by the hash token of the message.
parameters. The hash token is formed from a padded hash
code as defined in ISO/IEC 10118 concatenated
with an optional control field containing hash
B.1.2 Generation of the signature key and
function identification. If the hash function is not
verification key
uniquely specified by the domain parameter, the
B.1.2.1 Public Verification Exponent
control field is mandatory. If the verification key is
If not specified in the domain parameter set, the
even, the resulting hash token is forced to have
signing entity selects a positive integer v,
Jacobi symbol 1 mod N
by dividing by 2 if
where v < N (modulus).
necessary.
B.1.2.2 Generation of signature key
B.1.3.3 Computing the signature
s
The signing entity secretly generates a collection
The signature is S = H mod N.
{P , P} of two randomly or pseudo-randomly
1 2
chosen and distinct prime integers P, subject to
i
B.1.3.4 Constructing the appendix
the following conditions
The appendix is constructed from the signature
and an optional text field, text. The text field could
- if v is odd, then P -1 shall be coprime to v
i
include a certificate which cryptographically ties the
public verification key to the identification data of
v P v
- if is even, then ( - 1)/2 shall be coprime to
i
the signing entity.
P P
and - shall not be divisible by 8.
1 2
B.1.3.5 Constructing the signed message
Additional constraints on the P to ensure that the
i
The signed message is obtained by the
factorization of N = PP is computationally
1 2
M
concatenation of message and the appendix,
infeasible are optional.
M || (S, text).
The signing entity computes public modulus N =
P P and the signature exponent, s, an integer
1 2
N s N
mod with 0 < < so that
sv ≡ 1  mod lcm(P - 1, P - 1) if v is odd,
1 2
©
ISO/IEC ISO/IEC 14888-3:1998(E)
B.1.4 Verification process B.2.2.2 Generation of verification key
The verifying entity acquires the necessary data The verification key is a pair of integers Y = (N, v),
items required for the verification process (see where N is the product N = P P P = P Q and v is
1 2 3
ISO/IEC 14888-1, clause 9).
an integer which satisfies the condition v = s ≥ 4.
B.1.4.1 Preparing the message for verification
B.2.3 Signature process
The verifier retrieves M = M from the signed
The signature process of ESIGN follows the
M
message.  is empty.
general model described in Clause 8 of ISO/IEC
14888-1. It is a randomized signature mechanism
B.1.4.2 Retrieving the witness
which uses a deterministic witness and produces a
one-part signature.
The witness H is reconstructed from the data input
M according to B.1.3.2.
B.2.3.1 Producing pre-signature
B.1.4.3 Computing the verification function The pre-signature is computed in two steps.
Using the integer v obtained either from the
B.2.3.1.1 Producing the randomizer
Z Y
domain parameters or the verification key , and
N Y
the integer from the verification key , the
The signing entity generates secretly a randomizer
verifier computes
which is a random or pseudo-random positive
integer K Mod PQ such that 0 < K < PQ. The
v
output of this stage is K, which the signing entity
H = S mod N.
keeps secret.
If the verification exponent is even, H is modified
B.2.3.1.2 Producing the pre-signature
according to its congruence modulo 8.
The input to this stage is the randomizer K and the
signature key X. The signing entity computes the
B.1.4.4 Verifying the witness
s
pre-signature Π = (U, V), where U = K mod N and
The signature is valid only if the value of the
s-1 -1
V = (sK ) mod P. The second part V of the pre-
H
retrieved witness agrees with the value of the
signature shall be kept secret.
recomputed witness H .
B.2.3.2 Preparing the message for signing
B.2 ESIGN
The entire message M is taken as input M to the
B.2.1 Generation of domain parameters
computation of witness, M = M is the message;
M is empty, see 8.2 of ISO/IEC 14888-1.
ESIGN is a digital signature mechanism which 2
uses as a modulus an integer N = P Q where P>Q
are prime integers and a signature exponent s B.2.3.3 Computing the witness
v
equal to the verification exponent , an integer
The deterministic witness is the hash token of the
greater than or equal to 4. This common exponent
message, denoted H where H should be less than
n-1
can be included in the domain parameters or
2 .
derived from a certificate in the optional text of the
appendix. Also specified (optionally) in the domain
B.2.3.4 Computing the signature
parameters is an integer n which specifies the size
P Q
The inputs to this stage are and from the
of the integer primes in bits. Nominally, n is 1/3 the
X K
signature key , the randomizer computed in
number of bits used to represent N. The size of
B.2.3.1.1, the pre-signature Π = (U, V) computed in
the hash token is restricted to n-1 bits (i.e., 0 < H <
n-1
B.2.3.1.2 and the witness H computed in B.2.3.3.
2 ).
The signature S is computed using the formula:
B.2.2 Generation of signature key and
2n
S = K + ( (2 H - U)/PQV mod P )PQ mod N.
verification key
B.2.2.1 Generation of signature key
The output of this step is the signature Σ = S.
The signature key of a signing entity is a secretly
generated collection X = ({P, P, P}, s),
1 2 3
B.2.3.5 Constructing the appendix
determined by two distinct randomly or pseudo-
randomly chosen prime integers P = P = P and The appendix is constructed from the signature
1 2
text
P = Q with P>Q and the signature exponent s with and an optional text field, . The text field could
include a certificate which cryptographically ties the
s ≥ P Q
4. The factors and shall be kept secret.
©
public verification key to the identification data of
the signing entity.
B.2.3.6 Constructing the signed message
The signed message is obtained by the
concatenation of message M and appendix, M ||(S,
text).
B.2.4 Verification process
The verifying entity acquires the necessary data
items required for the verification process.
B.2.4.1 Preparing message for verification
The verifier retrieves M = M from the signed
M
message.  is empty.
B.2.4.2 Retrieving the witness
The witness H is reconstructed from the data input
M .
B.2.4.3 Computing the verification function
Using the integer v obtained either from the
domain parameters Z or the verification key Y, the
H
verifier computes , the high n bits of
v
S N
mod .
B.2.4.4 Verifying the witness
The signature is valid only if the value of the
reconstructed witness H agrees with value of the
recomputed witness H .
©
ISO/IEC ISO/IEC 14888-3:1998(E)
Annex C
(informative)
FIPS PUB 186 Generation of Primes P and Q
The prime generation scheme starts by using the Step 6. Let counter = 0 and offset = 2.
SHA-1 and a user supplied SEED to construct a
159 160
prime Q, in the range 2 < Q < 2 . Once this is Step 7. For k = 0, … , n let
g
V = SHA[(SEED + offset + k) mod 2 ].
accomplished, the same SEED value is used to
k
L-1 L
X X
construct an in the range 2 < < 2 . The
prime P is then formed by rounding X to a number Step 8. Let W be the integer W = V + V *
0 1
160 (n-1)*160 b n*160
2 + … + V * 2 + (V mod 2 ) * 2
congruent to 1 mod 2Q as described below. n-
...