ISO/IEC 14888-3:1998
(Main)Information technology — Security techniques — Digital signatures with appendix — Part 3: Certificate-based mechanisms
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
General Information
Relations
Standards Content (Sample)
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
ISO/IEC 14888-3:1998(E)
---------------------- Page: 1 ----------------------
ISO/IEC 14888-3:1998(E)
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
---------------------- Page: 2 ----------------------
©
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
1
---------------------- Page: 3 ----------------------
©
ISO/IEC 14888-3:1998(E) ISO/IEC
- 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
2
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
2
---------------------- Page: 4 ----------------------
©
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
1
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
2
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
3
---------------------- Page: 5 ----------------------
©
ISO/IEC 14888-3:1998(E) ISO/IEC
Signature Key, X
Message, M
X
M
Producing
Pre-Signature
text
Preparing
�
message
M
2 M
1
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
4
---------------------- Page: 6 ----------------------
©
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
2
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.
1
The output is the recomputed witness, R .
5
---------------------- Page: 7 ----------------------
©
ISO/IEC 14888-3:1998(E) ISO/IEC
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
6
---------------------- Page: 8 ----------------------
©
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
1
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
1
H
output is the hash token, , determined by the data
7.1 Key generation process
M
input . Note that the hash token is interpreted
1
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,
2
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
1
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,
7
---------------------- Page: 9 ----------------------
©
ISO/IEC 14888-3:1998(E) ISO/IEC
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 .
8
---------------------- Page: 10 ----------------------
©
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
159
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
9
---------------------- Page: 11 ----------------------
©
ISO/IEC 14888-3:1998(E) ISO/IEC
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.
1
The message is split such that M is empty and M
1 2
is the message, M = M.
2
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
2
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 .
2
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
10
---------------------- Page: 12 ----------------------
©
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
1
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
2
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, = .
2
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
2
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 = ).
2
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.
11
---------------------- Page: 13 ----------------------
©
ISO/IEC 14888-3:1998(E) ISO/IEC
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
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.