ISO/IEC 9798-5:2009

Information technology — Security techniques — Entity authentication — Part 5: Mechanisms using zero-knowledge techniques

ISO/IEC 9798-5:2009 specifies entity authentication mechanisms using zero-knowledge techniques: mechanisms based on identities and providing unilateral authentication; mechanisms based on integer factorization and providing unilateral authentication; mechanisms based on discrete logarithms with respect to numbers that are either prime or composite, and providing unilateral authentication; mechanisms based on asymmetric encryption systems and providing either unilateral authentication, or mutual authentication; mechanisms based on discrete logarithms on elliptic curves and providing unilateral authentication. These mechanisms are constructed using the principles of zero-knowledge techniques, but they are not necessarily zero-knowledge according to the strict definition for every choice of parameters.

Technologies de l'information — Techniques de sécurité — Authentification d'entité — Partie 5: Mécanismes utilisant des techniques à divulgation nulle

General Information

• Status: Published
• Publication Date: 10-Dec-2009
• ICS: 35.030 - IT Security
• ICS: 35.040 - Information coding
• Technical Committee: ISO/IEC JTC 1/SC 27 - Information security, cybersecurity and privacy protection
• Drafting Committee: ISO/IEC JTC 1/SC 27/WG 2 - Cryptography and security mechanisms
• Current Stage: 9092 - International Standard to be revised
• Start Date: 03-May-2024
• Completion Date: 12-Feb-2026

Relations

• Revises: ISO/IEC 9798-5:2004 - Information technology — Security techniques — Entity authentication — Part 5: Mechanisms using zero-knowledge techniques
• Effective Date: 15-Apr-2008

Overview

ISO/IEC 9798-5:2009 - part of the ISO/IEC 9798 series - specifies entity authentication mechanisms using zero-knowledge techniques. Published as the third edition in 2009, it defines a family of authentication exchanges between a claimant and a verifier built on zero-knowledge principles. The standard covers mechanisms based on identities, integer factorization, discrete logarithms (prime and composite moduli), asymmetric encryption systems (supporting unilateral or mutual authentication), and elliptic-curve discrete logarithms. It also provides normative and informative annexes with object identifiers, zero-knowledge principles, parameter guidance, and numerical examples.

Key topics and technical requirements

• Mechanism families: identity-based, integer-factorization-based, discrete-logarithm-based (prime/composite), asymmetric-encryption-based (unilateral/mutual), and elliptic-curve discrete logarithm mechanisms.
• Authentication flows: definitions and formats for witness, challenge, response, and the exchange multiplicity of messages in an authentication instance.
• Key production and management: procedures and requirements for generating private/public keys, accreditation exponents, adaptation parameters, and domain parameters.
• Security environment requirements: prerequisites for safe deployment of each mechanism family (e.g., randomness, parameter selection, and computational assumptions).
• Operational concepts: unilateral vs mutual authentication, coupon strategy (pre-computation to reduce runtime work for constrained claimants or verifiers), and token/claimant parameter handling.
• Parameter guidance: Annex C provides guidance on choosing parameters and comparing mechanisms; Annex D includes numerical examples to aid implementation.
• Terminology: clear definitions of claimant, verifier, private/public key, secret/response, token, and other cryptographic terms used in entity authentication.
• Caveat: mechanisms follow zero-knowledge principles but “may not be strictly zero-knowledge” for every parameter choice - implementers must heed parameter guidance.

Applications and who uses it

ISO/IEC 9798-5 is targeted at professionals designing and implementing strong authentication for systems that require cryptographic assurance of identity:

• Security architects and protocol designers building authentication schemes
• PKI and certificate authorities integrating authentication primitives
• Cryptographers and researchers comparing zero-knowledge-based schemes
• Embedded and IoT device manufacturers using coupon strategies to offload compute
• Auditors, compliance teams and vendors assessing cryptographic authentication mechanisms

Practical uses include secure login, device pairing, firmware/authentication tokens, challenge–response APIs, and protocols where private keys must be proven without disclosure.

Related standards

• ISO/IEC 9798 (other parts): Part 1 (General), Part 2 (symmetric algorithms), Part 3 (digital signatures), Part 4 (cryptographic check function), Part 6 (manual data transfer).
• Annexes in ISO/IEC 9798-5: principles of zero-knowledge (B), parameter guidance (C), numerical examples (D).

Keywords: ISO/IEC 9798-5:2009, entity authentication, zero-knowledge techniques, discrete logarithm, elliptic curve, integer factorization, asymmetric encryption, authentication mechanisms.

Standards Content (Sample)

INTERNATIONAL ISO/IEC
STANDARD 9798-5
Third edition
2009-12-15
Information technology — Security
techniques — Entity authentication —
Part 5:
Mechanisms using zero-knowledge
techniques
Technologies de l'information — Techniques de sécurité —
Authentification d'entité —
Partie 5: Mécanismes utilisant des techniques à divulgation nulle

Reference number
©
ISO/IEC 2009
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 2009
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 [e-mail]
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2009 – All rights reserved

Contents Page
Foreword .iv
Introduction.v
1 Scope.1
2 Terms and definitions .1
3 Notation, symbols and abbreviated terms.4
4 Mechanisms based on identities .7
4.1 Security requirements for the environment.7
4.2 Key production .8
4.3 Unilateral authentication exchange.10
5 Mechanisms based on integer factorization.12
5.1 Security requirements for the environment.12
5.2 Key production .12
5.3 Unilateral authentication exchange.13
6 Mechanisms based on discrete logarithms with respect to prime numbers .15
6.1 Security requirements for the environment.15
6.2 Key production .15
6.3 Unilateral authentication exchange.16
7 Mechanisms based on discrete logarithms with respect to composite numbers.17
7.1 Security requirements for the environment.17
7.2 Key production .18
7.3 Unilateral authentication exchange.19
8 Mechanisms based on asymmetric encryption systems.20
8.1 Security requirements for the environment.20
8.2 Unilateral authentication exchange.21
8.3 Mutual authentication exchange.22
9 Mechanism based on discrete logarithms with respect to elliptic curves .23
9.1 Security requirements for the environment.23
9.2 Key production .24
9.3 Unilateral authentication exchange.24
Annex A (normative) Object identifiers .26
Annex B (informative) Principles of zero-knowledge techniques.28
Annex C (informative) Guidance on parameter choice and comparison of the mechanisms .31
Annex D (informative) Numerical examples.41
Bibliography.52

© ISO/IEC 2009 – All rights reserved iii

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 9798-5 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
This third edition cancels and replaces the second edition (ISO/IEC 9798-5:2004), which has been technically
revised. This edition adds a new mechanism based on elliptic curve discrete logarithm.
ISO/IEC 9798 consists of the following parts, under the general title Information technology — Security
techniques — Entity authentication:
⎯ Part 1: General
⎯ Part 2: Mechanisms using symmetric encipherment algorithms
⎯ Part 3: Mechanisms using digital signature techniques
⎯ Part 4: Mechanisms using a cryptographic check function
⎯ Part 5: Mechanisms using zero-knowledge techniques
⎯ Part 6: Mechanisms using manual data transfer

iv © ISO/IEC 2009 – All rights reserved

Introduction
This part of ISO/IEC 9798 specifies authentication mechanisms that involve exchanges of information
between a claimant and a verifier.
In accordance with the types of calculations that need to be performed by the claimant and the verifier, the
mechanisms can be classified into the following four main groups (see Annex C).
⎯ The first group (see Clauses 4 and 5) is characterized by the performance of short modular
exponentiations. The challenge size needs to be optimized since it has a proportional impact on
workloads.
⎯ The second group (see Clauses 6 and 7 and 8) is characterized by the possibility of a “coupon strategy”
for the claimant. A verifier can authenticate a claimant with very limited computational power. The
challenge size has no practical impact on workloads.
⎯ The third group (see 9.2) is characterized by the possibility of a coupon strategy for the verifier. A verifier
with very limited computational power can authenticate a claimant. The challenge size has no impact on
workloads.
⎯ The fourth group (see 9.3) has no possibility of a coupon strategy.
ISO and IEC draw attention to the fact that it is claimed that compliance with this part of ISO/IEC 9798 may
involve the use of the following patents and their counterparts in other countries.
US 4 995 082 issued 1991-02-19, Inventor: C.P. Schnorr,
US 5 140 634 issued 1992-08-18, Inventors: L.C. Guillou and J-J. Quisquater,
EP 0 311 470 issued 1992-12-16, Inventors: L.C. Guillou and J-J. Quisquater,
EP 0 666 664 issued 1995-02-02, Inventor: M. Girault,
ISO and IEC take no position concerning the evidence, validity and scope of these patent rights.
The holders of these patent rights have assured ISO and IEC that they are willing to negotiate licenses under
reasonable and non-discriminatory terms and conditions with applications throughout the world. In this respect,
the statements of the holders of these patent rights are registered with ISO and IEC. Information may be
obtained from the companies listed overleaf.
RSA Security Inc. US 4 995 082
Attention General Counsel
174 Middlesex Turnpike
Bedford, MA 01730, USA
France Telecom R&D
US 5 140 634, EP 0 311 470, EP 0 666 664
Service PIV
38-40 Rue du Général Leclerc
F 92794 Issy les Moulineaux Cedex 9, France
Philips International B.V. US 5 140 634, EP 0 311 470
Corporate Patents and Trademarks
P.O. Box 220
5600 AE Eindhoven, The Netherlands
France Telecom claims that Patent Applications are pending in relation to Clauses 6 (GQ2) and 8 (GPS2). The Patent
numbers will be provided when available. ISO/IEC will then request the appropriate statement.

© ISO/IEC 2009 – All rights reserved v

INTERNATIONAL STANDARD ISO/IEC 9798-5:2009(E)

Information technology — Security techniques — Entity
authentication —
Part 5:
Mechanisms using zero-knowledge techniques
1 Scope
This part of ISO/IEC 9798 specifies entity authentication mechanisms using zero-knowledge techniques:
⎯ mechanisms based on identities and providing unilateral authentication;
⎯ mechanisms based on integer factorization and providing unilateral authentication;
⎯ mechanisms based on discrete logarithms with respect to numbers that are either prime or composite,
and providing unilateral authentication;
⎯ mechanisms based on asymmetric encryption systems and providing either unilateral authentication, or
mutual authentication;
⎯ mechanisms based on discrete logarithms on elliptic curves and providing unilateral authentication.
These mechanisms are constructed using the principles of zero-knowledge techniques, but they are not
necessarily zero-knowledge according to the strict definition for every choice of parameters.
2 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
2.1
accreditation exponent
secret number related to the verification exponent and used in the production of private keys
2.2
adaptation parameter
public key specific to the modulus and used in the definition of public keys in the GQ2 mechanisms
2.3
asymmetric cryptographic technique
cryptographic technique that uses two related operations: a public operation defined by a public data item, and
a private operation defined by a private data item (the two operations have the property that, given the public
operation, it is computationally infeasible to derive the private operation)
2.4
asymmetric encryption system
system based on asymmetric cryptographic techniques whose public operation is used for encryption and
whose private operation is used for decryption
© ISO/IEC 2009 – All rights reserved 1

2.5
asymmetric pair
two related data items where the private data item defines a private operation and the public data item defines
a public operation
2.6
challenge
procedure parameter used in conjunction with secret parameters to produce a response
2.7
claimant
entity whose identity can be authenticated, including the functions and the private data necessary to engage in
authentication exchanges on behalf of a principal
2.8
coupon
pair of pre-computed numbers to be used only once; one is kept secret and the other remains secret until its
use by an entity
2.9
claimant parameter
public data item, number or bit string, specific to a given claimant within the domain
2.10
decryption
reversal of a corresponding encryption
[30] [24]
NOTE Decryption and decipherment are equivalent terms.
2.11
domain
collection of entities operating under a single security policy
NOTE For example, public key certificates created either by a single certification authority, or by a collection of
certification authorities using the same security policy.
2.12
domain parameter
public key, or function, agreed and used by all entities within the domain
2.13
encryption
reversible operation by a cryptographic algorithm converting data into ciphertext, so as to hide the information
content of the data
[30] [24]
NOTE Encryption and encipherment are equivalent terms.
2.14
entity authentication
corroboration that an entity is the one claimed
[ISO/IEC 9798-1:1997, definition 3.3.11]
2.15
exchange multiplicity parameter
number of exchanges of information involved in one instance of an authentication mechanism
2 © ISO/IEC 2009 – All rights reserved

2.16
hash-function
function that maps strings of bits to fixed-length strings of bits, satisfying the following two properties:
⎯ for a given output, it is computationally infeasible to find an input that maps to this output;
⎯ it is computationally infeasible to find two distinct inputs that map to the same output
[ISO/IEC 10118-1:2000, definition 3.5]
2.17
identification data
set of public data items (an account number, an expiry date and time, a serial number, etc.) assigned to an
entity and used to identify it
2.18
mutual authentication
entity authentication that provides both entities with assurance of each other's identity
[ISO/IEC 9798-1:1997, definition 3.3.14]
2.19
number
natural number, i.e. a non-negative integer
2.20
pair multiplicity parameter
number of asymmetric pairs of numbers involved in one instance of an authentication mechanism
2.21
private key
data item of an asymmetric pair, that shall be kept secret and should only be used by a claimant in
accordance with an appropriate response formula, thereby establishing its identity
2.22
procedure parameter
transient public data item used in an instance of an authentication mechanism such as a witness, challenge or
response
2.23
public key
data item of an asymmetric pair, that can be made public and shall be used by every verifier for establishing
the claimant's identity
2.24
random number
time variant parameter whose value is unpredictable
[ISO/IEC 9798-1:1997, definition 3.3.24]
2.25
response
procedure parameter produced by the claimant, and processed by the verifier for checking the identity of the
claimant
2.26
secret parameter
number or bit string that does not appear in the public domain and is only used by a claimant, e.g. a private
key
© ISO/IEC 2009 – All rights reserved 3

2.27
token
message consisting of data fields relevant to a particular communication and which contains information that
has been produced using a cryptographic technique
2.28
unilateral authentication
entity authentication that provides one entity with assurance of the other's identity but not vice versa
[ISO/IEC 9798-1:1997, definition 3.3.33]
2.29
verification exponent
public key used as exponent by the claimant and the verifier
2.30
verifier
entity including the functions necessary for engaging in authentication exchanges on behalf of an entity
requiring an entity authentication
2.31
witness
procedure parameter that provides evidence of the claimant's identity to the verifier
3 Notation, symbols and abbreviated terms
For the purposes of this document, the following notation, symbols and abbreviated terms apply.
(a ⏐ n) Jacobi symbol of a positive integer a with respect to an odd composite integer n
NOTE 1 By definition, the Jacobi symbol of any positive integer a with respect to any odd positive composite integer n
is the product of the Legendre symbols of a with respect to each prime factor of n (repeating the Legendre symbols for the
[13][16]
repeated prime factors). The Jacobi symbol can be efficiently computed without knowledge of the prime factors of n.
(a ⏐ p) Legendre symbol of a positive integer a with respect to an odd prime integer p
NOTE 2 By definition, the Legendre symbol of any positive integer a with respect to any odd positive prime integer p is
(p–1)/2
equal to a mod p. This means that (a ⏐ p) is zero if a is a multiple of p, and either +1 or –1 otherwise, depending on
whether or not a is a square modulo p.
i–1 i
⏐A⏐ bit size of the number A if A is a number (i.e. the unique integer i so that 2 ≤ A < 2 if A > 0, or
0 if A = 0, e.g. ⏐65 537 = 2 +1⏐ = 17), or bit length of the bit string A if A is a bit string
NOTE 3 The binary representation of a number A as a string of ⏐A⏐ bits is straightforward. To represent a number A as
a string of α bits with α >⏐A⏐, α –⏐A⏐ bits set to 0 are appended to the left of the ⏐A⏐ bits.
⎣A⎦ the greatest integer that is less than or equal to the real number A
B || C bit string resulting from the concatenation of data items B and C in the order specified. In cases
where the result of concatenating two or more data items is input to a cryptographic algorithm as
part of an authentication mechanism, this result shall be composed so that it can be uniquely
resolved into its constituent data strings, i.e. so that there is no possibility of ambiguity in
interpretation. This latter property could be achieved in a variety of different ways, depending on
the application. For example, it could be guaranteed by
(a) fixing the length of each of the substrings throughout the domain of use of the mechanism,
or
(b) encoding the sequence of concatenated strings using a method that guarantees unique
[23]
decoding, e.g. using the distinguished encoding rules defined in ISO/IEC 8825-1
4 © ISO/IEC 2009 – All rights reserved

CRT Chinese remainder theorem
d challenge (procedure parameter)
D response (procedure parameter)
f number of prime factors
gcd(a, b) the greatest common divisor of the two integers a and b
G, G public key (domain parameter)
i
G(A), G(A) public key (claimant parameter)
i
h hash-function
⏐h⏐ bit length of the hash-code produced by the hash-function h
H, HH hash-codes
Id(A) identification data (claimant parameter)
Id (A) part of the identification data (claimant parameter)
i
j mod n the unique integer i from {0, 1, … n–1} such that n divides j – i
j mod* n the unique integer i from {0, 1, … (n–1)/2} such that n divides either j – i or j + i
lcm(a, b) the least common multiple of the two integers a and b
m pair multiplicity parameter (domain parameter)
n composite modulus (domain parameter)
n(A) composite modulus (claimant parameter)
p , p … prime factors of the modulus in ascending order, i.e. p < p < … (secret parameters)
1 2 1 2
Q, Q private key (secret parameter)
i
r fresh random number or fresh string of random bits (secret parameter)
v verification exponent (domain parameter)
W witness (procedure parameter)
'X X ' number whose hexadecimal representation is X X …, where each X is equal to one of 0-9 and
1 2… 1 2 i
A-F
–1
α α
α modulus size in bits, i.e. 2 ≤ modulus < 2 , also denoted ⏐modulus⏐ (domain parameter)
δ length of fresh strings of random bits for representing challenges (domain parameter)
ρ length of fresh strings of random bits for representing random numbers (domain parameter)
{a, b, c, …} set containing the elements a, b, c, …
© ISO/IEC 2009 – All rights reserved 5

For the purposes of Clause 5 (identity-based mechanisms), the following symbols and abbreviated terms
apply.
F bit string
t exchange multiplicity parameter (domain parameter)
u accreditation exponent with respect to the modulus (secret parameter)
u accreditation exponent with respect to the prime factor p (secret parameter)
j j
For the purposes of Clause 6 (integer factorization based mechanisms), the following symbols and
abbreviated terms apply.
b adaptation parameter (specific to the modulus)
D response component with respect to the prime factor p (secret parameter)
j j
g basic number (domain parameter)
i
g(A) basic number (claimant parameter)
i
k security parameter (domain parameter)
Q private component with respect to the basic number g and the prime factor p (secret parameter)
i,j i j
r fresh random number with respect to the prime factor p (secret parameter)
j j
u accreditation exponent with respect to the prime factor p (secret parameter)
j j
W witness component with respect to the prime factor p (secret parameter)
j j
For the purposes of Clause 7 (mechanisms based on discrete logarithms with respect to prime numbers), the
following symbols and abbreviated terms apply.
g base of the discrete logarithms (domain parameter)
p modulus (domain parameter)
q prime number (domain parameter)
For the purposes of Clause 8 (mechanisms based on discrete logarithms with respect to composite numbers),
the following symbols and abbreviated terms apply.
g base of the discrete logarithms (domain parameter)
g(A) base of the discrete logarithms (claimant parameter)
σ number of bits for private keys in the first mode (domain parameter)
For the purposes of Clause 9 (mechanisms based on asymmetric encryption systems), the following symbols
and abbreviated terms apply.
P public operation, i.e. encryption (claimant parameter)
A
S private operation, i.e. decryption (secret parameter)
A
6 © ISO/IEC 2009 – All rights reserved

For the purposes of Clause 10 (mechanisms based on discrete logarithms on elliptic curves), the following
symbols and abbreviated terms apply.
[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 is the sum
of n occurrences of P. The operation satisfies [0]P = 0E (the point at infinity), and [-n]P = [n](-P)
4 Mechanisms based on identities
4.1 Security requirements for the environment
These mechanisms enable a verifier to check that a claimant knows private key(s) that are related to
identification data by a verification key.
[4]
NOTE These mechanisms implement schemes due either to Fiat and Shamir and denoted FS, or to Guillou and
[11]
Quisquater and denoted GQ1.
Within a given domain, the following requirements shall be satisfied.
1) Domain parameters shall be selected, which will govern the operation of the mechanism. They include a
[25]
hash-function, e.g. one of the functions specified in ISO/IEC 10118-3 . The selected parameters shall
be made known in a reliable manner to all entities within the domain.
2) Every claimant shall be equipped with a modulus that is either a domain parameter or a claimant parameter.
Each number used as modulus is set equal to the product of two or more distinct prime factors so that
knowledge of its value shall not feasibly enable any entity to deduce its prime factors, where feasibility is
defined by the context of use of the mechanism.
⎯ If the modulus is a domain parameter, then it is denoted n. A trusted authority has selected it and only
this authority can use the corresponding prime factors. The authority guarantees the identities of every
claimant within the domain.
NOTE 1 For example, a card issuer has a modulus. A delegated entity signs identification data for issuing
smart cards; it uses the issuer's prime factors. In each card, the delegated entity stores appropriate identification
data and private key(s). During its life, the card uses its private key(s) in accordance with an identity-based
mechanism.
⎯ If the modulus is a claimant parameter, then it is denoted n(A). A principal has selected it and the
corresponding prime factors are the principal's long-term secret. For each session, the principal
creates a claimant. The claimant uses private key(s) as a short-term secret.
NOTE 2 For example, in a local area network, an authority supervises each login operation within the domain
and manages a directory where every verifier can obtain a trusted copy of a modulus for each principal.
⎯ During each login operation, i.e. when a computer opens a session, it uses a principal's prime factors for a
"single-sign-on" of session identification data including identifier, expiry date and time, rights, etc.
⎯ During the session, the computer cannot use the prime factors because it does not know them any more. It
uses the private key(s) in accordance with an identity-based mechanism. The private keys only last for a few
hours: their utility disappears after the session.
3) Every claimant shall be provided with identification data and with one or more private keys by some
means. In this context, the identification data is a string of bits, not all equal, that uniquely and
meaningfully identifies the claimant in accordance with an agreed convention.
NOTE The presence of an expiry date and time in the identification data enforces their expiry; the presence of a
serial number simplifies their revocation.
4) Every verifier shall obtain a trusted copy of the correct modulus of the claimant.
NOTE The exact means by which the verifier obtains a trusted copy of the correct modulus is beyond the scope of
this part of ISO/IEC 9798. his may, for example, be achieved by the use of public-key certificates or by some other
environment-dependent means.
5) Every claimant and every verifier shall have the means to produce random numbers.
© ISO/IEC 2009 – All rights reserved 7

4.2 Key production
4.2.1 Asymmetric key pair
A verification exponent, a pair multiplicity parameter and an exchange multiplicity parameter shall be selected.
Unless otherwise specified, they are domain parameters respectively denoted v, m and t.
16 32 36 13 40
⎯ Certain values of v, such as the prime numbers 2, 257, 2 +1, 2 +15, 2 +2 +1 and 2 +15, have some
practical advantages.
⎯ The value of m shall be at most eight if v = 2 and set equal to one if v is an odd prime.
–m × t –8 –40
⎯ The value of v fixes a mechanism security level (see C.1.4). A value from 2 to 2 is appropriate
for most applications.
α –1 α
A number, denoted α, fixes the modulus size in bits, i.e. 2 < modulus < 2 , in accordance with the context
of use of the mechanism (for further details, see C.1.1). It is a domain parameter.
The authority or the principal shall keep secret two or more distinct large prime factors denoted p , p … in
1 2
ascending order, the product of which is the modulus.
• If v = 2 (the Rabin scheme), there shall be only two prime factors (i.e. f = 2), both congruent to 3 mod 4,
but not congruent to each other mod 8.
• If v is an odd prime (the RSA scheme), there may be more than two prime factors. For each prime
factor p , p –1 shall be co-prime to v.
j j
If α is a multiple of the number of prime factors, denoted f, then the bit size of each prime factor shall be α / f
(for further details, see C.1.2). The modulus is set equal to either p × p if v = 2, or p × . × p if v is odd. In
1 2 1 f
accordance with the second requirement in 5.1, the modulus is either a domain parameter denoted n, or a
claimant parameter denoted n(A).
With respect to each prime factor p, an accreditation exponent, denoted u, is set equal to the least positive
j j
integer so that u × v +1 is a multiple of either (p –1)/2 if v = 2, or p –1 if v is an odd prime.
j j j
With respect to the modulus, an accreditation exponent, denoted u, is set equal to the least positive integer so
that u × v +1 is a multiple of either lcm(p –1, p –1)/2 if v = 2, or lcm(p –1, … p –1) if v is an odd prime.
1 2 1 f
4.2.2 Asymmetric pair(s) of numbers
4.2.2.1 Case where v = 2
The identification data Id(A) shall be converted into m parts by appending sixteen bits representing the
numbers 1 to m, namely '0001', '0002', and so on, in turn to the string Id(A).
Id (A) = Id(A) || '000X'
x
[27]
NOTE The mechanism below derives from the first format mechanism specified in ISO/IEC 14888-2 , known as
[1]
PSS (PSS reads Probabilistic Signature Scheme) and due to Bellare and Rogaway .
For converting each part, from Id (A) to Id (A), into a string of α bits, denoted F to F , the following
1 m 1 m
computational steps are performed.
1) The string Id (A) shall be hashed to obtain a hash-code denoted H .
x x
H = h(Id (A))
x x
2) A string of (64+⏐h⏐) bits is constructed from left to right by concatenating 8 octets set to '00' and the hash-
code H . This string shall be hashed to obtain a hash-code denoted HH .
x x
HH = h('00000000 00000000' || H )
x x
8 © ISO/IEC 2009 – All rights reserved

3) A mask comprising a string of (α –⏐h⏐– 8) bits is constructed from the hash-code HH . The procedure
x
makes use of two variables: a bit string of variable length, denoted String, and a 32-bit counter, denoted
Counter.
a) Set String to the empty string.
b) Set Counter to 0.
c) Replace String by String || h(HH || Counter).
x
d) Replace Counter by Counter + 1.
e) If ⏐h⏐× Counter < α –⏐h⏐– 8, then go to step c.
Mask equals the leftmost (α –⏐h⏐– 8) bits of String where the leftmost bit has been forced to 0.
x
4) A string denoted F is constructed from left to right by concatenating the (α –⏐h⏐– 8) bits of the mask
x
where the rightmost bit has been reversed, the ⏐h⏐ bits of the hash-code HH and one octet set to 'BC'.
x
F = Format(Id (A)) = (Mask ⊕ (000 … 000 || 1)) || HH || 'BC'
x x x x
A public key denoted G (A) is derived from the number represented by the bit string F (also denoted F , this
x x x
number is even, non-zero and less than the modulus), as follows.
⎯ If the Jacobi symbol (F I n) is +1, then G (A) = F .
x x x
⎯ If the Jacobi symbol (F I n) is –1, then G (A) = F / 2.
x x x
The authority or the principal shall provide claimant A with m private keys denoted Q to Q . The private key
1 m
denoted Q is set equal to the u-th modular power of the public key G (A).
x x
u
Q = G (A) (mod* either n or n(A))
x x
NOTE 1 The CRT technique (see C.2.3) may be used for converting each public key into a private key.
uj
⎯ For each prime factor p , a component Z is set equal to G (A) mod p .
j j x j
⎯ A CRT composition converts the set of components {Z , Z …} into a number Z.
1 2
Q = Z (mod* either n or n(A))
x
NOTE 2 Each asymmetric pair of numbers verifies a relationship governed by the verification key.
G (A) × Q ≡ 1 (mod* either n or n(A))
x x
NOTE 3 Consequently, any number G (A) or Q may be replaced by the modulus minus the number.
x x
4.2.2.2 Case where v is an odd prime
[27]
NOTE The mechanism below derives from the first format mechanism specified in ISO/IEC 14888-2 , known as
[1]
PSS (PSS reads Probabilistic Signature Scheme) and due to Bellare and Rogaway .
For converting the identification data Id(A) into a string of α bits, denoted F, the following computational steps
are performed.
1) The string Id(A) shall be hashed to obtain a hash-code denoted H.
H = h(Id(A))
2) A string of (64+⏐h⏐) bits is constructed from left to right by concatenating 8 octets set to '00' and the hash-
code H. This string shall be hashed to obtain a hash-code denoted HH.
HH = h('00000000 00000000' || H)
3) A mask comprising a string of (α –⏐h⏐) bits is constructed from the hash-code HH. The procedure makes
use of two variables: a bit string of variable length, denoted String, and a 32-bit counter, denoted Counter.
a) Set String to the empty string.
b) Set Counter to 0.
c) Replace String by String || h(HH || Counter).
© ISO/IEC 2009 – All rights reserved 9

d) Replace Counter by Counter + 1.
e) If ⏐h⏐× Counter < α –⏐h⏐, then go to step c.
The mask equals the leftmost (α –⏐h⏐) bits of String where the leftmost bit has been forced to 0.
4) A string denoted F is constructed from left to right by concatenating the (α –⏐h⏐) bits of the mask where
the rightmost bit has been reversed and the ⏐h⏐ bits of the hash-code HH.
F = Format(Id(A)) = (Mask ⊕ (000 … 000 || 1)) || HH
A public key, denoted G(A), is set equal to the number represented by the bit string F (also denoted F, this
number is non-zero and less than the modulus).
G(A) = F
The authority or the principal shall provide claimant A with a private key, denoted Q, set equal to the u-th
modular power of the public key G(A).
u
Q = G(A) (mod either n or n(A))
NOTE 1 The CRT technique (see C.2.3) may be used for converting the public key into the private key.
uj
⎯ For each prime factor p , a component Q is set equal to G(A) mod p .
j j j
⎯ A CRT composition converts the set of components {Q , Q …} into the number Q.
1 2
NOTE 2 The asymmetric pair of numbers (the private key is the modular inverse of the RSA signature, see
[27]
ISO/IEC 14888-2 ) verifies a relationship governed by the verification key.
v
G(A) × Q ≡ 1 (mod either n or n(A))
4.3 Unilateral authentication exchange
The bracketed numbers in Figure 1 correspond to the steps of the mechanism, including the exchanges of
information, described in detail below. The claimant is denoted A. The verifier is denoted B.
(2) TokenAB
A B
(4) Challenge
(1), (5) (3), (7)
(6) TokenAB
Figure 1 ⎯ Identity-based mechanism
In addition to identification data Id(A), a verification exponent v (a prime number), a pair multiplicity parameter
m and an exchange multiplicity parameter t, the claimant shall store a modulus n or n(A) and either
• m private keys Q to Q if v = 2, or
1 m
• a single private key Q if v is an odd prime.
In addition to identification data Id(A), a verification exponent v (a prime number), a pair multiplicity parameter
m and an exchange multiplicity parameter t, the verifier shall be provided with a trusted copy of a modulus n or
n(A). If not already known by B, a copy of Id(A), v, m and t shall be sent along with TokenAB ; however, such
a copy needs not be trusted.
For each application of the mechanism, the following procedure shall be performed t times. The verifier B shall
only accept the claimant A as valid if all t iterations of the procedure complete successfully.
1) For each iteration of the procedure, a fresh number shall be uniformly selected at random, so that it is
non-zero and less than the modulus. Denoted r, it shall be kept secret.
10 © ISO/IEC 2009 – All rights reserved

The fresh random number r shall be converted into a witness, denoted W, as the v-th modular power.
• Witness formula if v = 2:   W = r (mod* either n or n(A))
v
• Witness formula if v is an odd prime: W = r (mod either n or n(A))
The number W is represented by a string of α bits, also denoted W.
2) A sends TokenAB to B. TokenAB is either witness W or a hash-code of W and Text, one of the following
1 1
four hash variants.
The four hash variants are h(W || Text), h(W || h(Text)), h(h(W) || Text), and h(h(W) || h(Text), where h is a
hash-function and Text is an optional text field (it may be empty). If the text field is non-empty, then B shall
have the means to recover the value of Text; this may require A to send all or part of the text field at this
point. The text field is available for use in applications outside the scope of this part of ISO/IEC 9798.

[24]
Annex A of ISO/IEC 9798-1 gives information on the use of text fields. The hash variant is a domain
parameter.
3) On receipt of TokenAB , the following computational steps are performed.
m t 40
×
a) If the value of v is less than 2 and/or if m > 8 when v = 2, and/or if m > 1 when v is an odd prime,
then the procedure fails.
b) If the identification data Id(A) is invalid (e.g. expired or revoked), then the procedure fails.
c) A fresh string of δ bits shall be uniformly selected at random.
• If v = 2, then δ = m and the string consists of m bits, denoted d to d .
1 m
• If v is an odd prime, then δ = ⏐v⏐–1 and the string represents a number less than v, possibly zero,
denoted d.
NOTE The total number of possible challenges per iteration of the procedure should be limited to 2 . If this
recommendation is not followed, then special care should be taken to prevent the verifier using the claimant as a
signing oracle.
4) B sends the fresh string as a challenge to A.
NOTE Optimizations may induce constraints on the Hamming weight of the challenges, with an impact on
the total number of possible challenges and on the mechanism security level.
5) On receipt of the challenge, the following computational steps are performed.
a) If the challenge is not a string of δ bits, then the procedure fails.
b) A response denoted D shall be computed from the random number r and
• the m private keys Q , Q , … Q and the m challenge bits d , d , … d if v = 2.
m m
1 2 1 2
m
d
i
Response formula if v = 2:  D = r × Q (mod* either n or n(A))
∏ i
i =1
• the single private key Q and the challenge number d if v is an odd prime.
d
Response formula if v is an odd prime: D = r × Q (mod either n or n(A))
6) A sends TokenAB to B. TokenAB is the response D computed from step 5)b).
2 2
7) On receipt of TokenAB , the following computational steps are performed.
a) If the response D is zero or equal to or more than the modulus, then the procedure fails.
b) The identification data Id(A) shall be converted into
• m public keys (see 5.2.2.1), denoted G (A), G (A), … G (A), if v = 2.
1 2 m
• a single public key (see 5.2.2.2), denoted G(A), if v is an odd prime.
© ISO/IEC 2009 – All rights reserved 11

c) Denoted W*, a witness shall be computed.
m
2 d
i
• Verification formula if v = 2:   W* =
D × G (A) (mod* either n or n(A))
∏ i
i =1
v d
• Verification formula if v is an odd prime: W* = D × G(A) (mod either n or n(A))
d) If either witness W* or a hash-code of W* and Text, one of the four hash variants, is identical to
TokenAB received in step (2), then the iteration of the procedure is successful. Otherwise the
procedure fails.
NOTE 1 Other information may be sent with any exchange of the procedure. B might use such information to help
compute the value of the optional text field.
NOTE 2 B can compute the public key(s) for A at any stage, i.e. B need not wait until the receipt of response D before
computing them. If B verifies A frequently, then B may cache the public key(s).
NOTE 3 The t iterations of the procedure can be performed in parallel, i.e. in the first step, A may choose t random
numbers r , r , … r, compute t witnesses W , W , … W, send them simultaneously to B, and so on. If this parallel
1 2 t 1 2 t
implementation is adopted, the total number of message exchanges will be equal to three, regardless of the value of t.
NOTE 4 The use of a hash-code instead of witness W in the first exchange of the procedure can achieve efficiency
gains by reducing the number of bits in TokenAB .
5 Mechanisms based on integer factorization
5.1 Security requirements for the environment
These mechanisms enable a verifier to check that a claimant knows a decomposition of a claimed modulus.
[12]
NOTE These mechanisms implement schemes due to Guillou and Quisquater and denoted GQ2.
Within a given domain, the following requirements shall be satisfied.
1) Domain parameters shall be selected, which will govern the operation of the mechanism. The selected
parameters shall be made known in a reliable manner to all entities within the domain.
2) Every claimant shall be equipped with distinct prime factors so that knowledge of their product, i.e. the
modulus (a claimant parameter), shall not feasibly enable any entity to deduce them, where feasibility is
defined by the context of use of the mechanism.
NOTE When opening a session (see 5.1), a computer may randomly select two prime factors to be used during the
session (a few hours). Using the principal's long-term secret in a "single-sign-on" of session identification data, the
computer signs an "ephemeral" certificate covering an "ephemeral" modulus, product of the "ephemeral" prime factors.
3) Every verifier shall obtain a trusted copy of the modulus specific to the claimant.
NOTE The exact means by which the verifier obtains a trusted copy of the modulus specific to the claimant is
beyond the scope of this part of ISO/IEC 9798. This may, for example, be achieved by the use of public-key
certificates or by some other environment-dependent means.
4) Every claimant and every verifier shall have the means to produce random numbers.
5) If the mechanism makes use of a hash-function, then all entities within the domain shall agree on a hash-
[25]
function, e.g. one of the functions specified in ISO/IEC 10118-3 .
5.2 Key production
–1
α α
A number, denoted α, fixes the modulus size in bits, i.e. 2 < modulus < 2 , in accordance with the context
of use of the mechanism (for further details, see C.1.1). It is a domain parameter.
A security parameter and a pair multiplicity parameter, denoted k and m, together fix a mechanism security
–k m
×
level set to the value of 2 in accordance with the needs of the application (see C.1.4). They are domain
parameters. A value of k × m from 8 to 40 is appropriate for most applications.
12 © ISO/IEC 2009 – All rights reserved

NOTE 1 The total number of possible challenges should be limited to 2 . If this recommendation is not followed, then
special care should be taken to prevent the verifier using the claimant as a signing oracle.
Claimant A shall keep secret two or more distinct large prime factors denoted p , p … in ascending order. If α
1 2
is a multiple of the number of prime factors, denoted f, then the bit size of each prime
...