ISO/IEC 9796-2:2010
(Main)Information technology — Security techniques — Digital signature schemes giving message recovery — Part 2: Integer factorization based mechanisms
Information technology — Security techniques — Digital signature schemes giving message recovery — Part 2: Integer factorization based mechanisms
ISO/IEC 9796-2:2010 specifies three digital signature schemes giving message recovery, two of which are deterministic (non-randomized) and one of which is randomized. The security of all three schemes is based on the difficulty of factorizing large numbers. All three schemes can provide either total or partial message recovery. ISO/IEC 9796-2:2010 specifies the method for key production for the three signature schemes. However, techniques for key management and for random number generation (as required for the randomized signature scheme), are outside the scope of ISO/IEC 9796-2:2010. The first mechanism specified in ISO/IEC 9796-2:2010 is only applicable for existing implementations, and is retained for reasons of backward compatibility.
Technologies de l'information — Techniques de sécurité — Schémas de signature numérique rétablissant le message — Partie 2: Mécanismes basés sur une factorisation entière
General Information
Relations
Standards Content (Sample)
INTERNATIONAL ISO/IEC
STANDARD 9796-2
Third edition
2010-12-15
Information technology — Security
techniques — Digital signature schemes
giving message recovery —
Part 2:
Integer factorization based mechanisms
Technologies de l'information — Techniques de sécurité — Schémas
de signature numérique rétablissant le message —
Partie 2: Mécanismes basés sur une factorisation entière
Reference number
ISO/IEC 9796-2:2010(E)
©
ISO/IEC 2010
---------------------- Page: 1 ----------------------
ISO/IEC 9796-2:2010(E)
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.
COPYRIGHT PROTECTED DOCUMENT
© ISO/IEC 2010
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2010 – All rights reserved
---------------------- Page: 2 ----------------------
ISO/IEC 9796-2:2010(E)
Contents Page
Foreword .v
Introduction.vi
1 Scope.1
2 Normative references.1
3 Terms and definitions .1
4 Symbols and abbreviated terms .3
5 Converting between bit strings and integers .5
6 Requirements.5
7 Model for signature and verification processes .7
7.1 General .7
7.2 Signing a message.7
7.2.1 Overview.7
7.2.2 Message allocation.7
7.2.3 Message representative production.8
7.2.4 Signature production .8
7.3 Verifying a signature.8
7.3.1 Overview.8
7.3.2 Signature opening.8
7.3.3 Message recovery .8
7.3.4 Message assembly.9
7.4 Specifying a signature scheme.9
8 Digital signature scheme 1.9
8.1 General .9
8.2 Parameters .9
8.2.1 Modulus length.9
8.2.2 Trailer field options .10
8.2.3 Capacity.10
8.3 Message representative production.10
8.3.1 Hashing the message.10
8.3.2 Formatting.10
8.4 Message recovery .11
9 Digital signature scheme 2.12
9.1 General .12
9.2 Parameters .12
9.2.1 Modulus length.12
9.2.2 Salt length .12
9.2.3 Trailer field options .12
9.2.4 Capacity.13
9.3 Message representative production.13
9.3.1 Hashing the message.13
9.3.2 Formatting.13
9.4 Message recovery .13
10 Digital signature scheme 3.14
Annex A (normative) ASN.1 module .15
A.1 General.15
A.2 Use of subsequent object identifiers .17
© ISO/IEC 2010 – All rights reserved iii
---------------------- Page: 3 ----------------------
ISO/IEC 9796-2:2010(E)
Annex B (normative) Public key system for digital signature. 18
B.1 Terms and definitions . 18
B.2 Symbols and abbreviations . 18
B.3 Key production. 19
B.3.1 Public verification exponent. 19
B.3.2 Secret prime factors and public modulus. 19
B.3.3 Private signature exponent. 20
B.4 Signature production function . 20
B.5 Signature opening function. 20
B.6 Alternative signature production function. 21
B.7 Alternative signature opening function. 21
Annex C (normative) Mask generation function . 22
C.1 Symbols and abbreviations . 22
C.2 Requirements. 22
C.3 Specification. 22
C.3.1 Parameters . 22
C.3.2 Mask generation. 22
Annex D (informative) On hash-function identifiers and the choice of the recoverable length of the
message. 23
Annex E (informative) Examples. 24
E.1 Examples with public exponent 3 . 24
E.1.1 Example of key production process. 24
E.1.2 Examples with total recovery . 25
E.1.3 Examples with partial recovery. 31
E.2 Examples with public exponent 2 . 38
E.2.1 Example of key production process. 38
E.2.2 Examples with total recovery . 38
E.2.3 Examples with partial recovery. 44
Bibliography. 53
iv © ISO/IEC 2010 – All rights reserved
---------------------- Page: 4 ----------------------
ISO/IEC 9796-2:2010(E)
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are members of
ISO or IEC participate in the development of International Standards through technical committees
established by the respective organization to deal with particular fields of technical activity. ISO and IEC
technical committees collaborate in fields of mutual interest. Other international organizations, governmental
and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information
technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft International
Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as
an International Standard requires approval by at least 75 % of the national bodies casting a vote.
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights.
ISO/IEC 9796-2 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 9796-2:2002), which has been technically
revised. It also incorporates the Amendment ISO/IEC 9796-2:2002/Amd.1:2008.
Implementations which comply with ISO/IEC 9796-2 (1st edition) and which use a hash-code of at least
160 bits in length will be compliant with ISO/IEC 9796-2 (3rd edition). Note, however, that implementations
complying with ISO/IEC 9796-2 (1st edition) that use a hash-code of less than 160 bits in length will not be
compliant with ISO/IEC 9796-2 (3rd edition). Implementations which comply with ISO/IEC 9796-2 (2nd edition)
will be compliant with ISO/IEC 9796-2 (3rd edition).
ISO/IEC 9796 consists of the following parts, under the general title Information technology ― Security
techniques — Digital signature schemes giving message recovery:
⎯ Part 2: Integer factorization based mechanisms
⎯ Part 3: Discrete logarithm based mechanisms
Further parts may follow.
© ISO/IEC 2010 – All rights reserved v
---------------------- Page: 5 ----------------------
ISO/IEC 9796-2:2010(E)
Introduction
Digital signature mechanisms can be used to provide services such as entity authentication, data origin
authentication, non-repudiation, and integrity of data. A digital signature mechanism satisfies the following
requirements.
⎯ Given the verification key but not the signature key it shall be computationally infeasible to produce a
valid signature for any message.
⎯ Given the signatures produced by a signer, it shall be computationally infeasible to produce a valid
signature on a new message or to recover the signature key.
⎯ It shall be computationally infeasible, even for the signer, to find two different messages with the same
signature.
NOTE 1 Computational feasibility depends on the specific security requirements and environment.
Most digital signature mechanisms are based on asymmetric cryptographic techniques and involve three basic
operations:
⎯ a process for generating pairs of keys, where each pair consists of a private signature key and the
corresponding public verification key;
⎯ a process that uses the signature key, called the signature process;
⎯ a process that uses the verification key, called the verification process.
There are two types of digital signature mechanism.
⎯ When, for a given signature key, two signatures produced for the same message are identical, the
mechanism is said to be non-randomized (or deterministic); see ISO/IEC 14888-1.
⎯ When, for a given message and signature key, each application of the signature process produces a
different signature, the mechanism is said to be randomized.
The first and third of the three mechanisms specified in this part of ISO/IEC 9796 are deterministic (non-
randomized), whereas the second of the three mechanisms specified is randomized.
Digital signature mechanisms can also be divided into the following two categories:
⎯ When the whole message has to be stored and/or transmitted along with the signature, the mechanism is
named a “signature mechanism with appendix” (see ISO/IEC 14888).
⎯ When the whole message, or part of it, can be recovered from the signature, the mechanism is named a
“signature mechanism giving message recovery” [see ISO/IEC 9796 (all parts)].
NOTE 2 Any signature mechanism giving message recovery, for example the mechanisms specified in ISO/IEC 9796
(all parts), can be converted to give a digital signature with appendix. This can be achieved by applying the signature
mechanism to a hash-code derived as a function of the message. If this approach is employed, then all parties generating
and verifying signatures must agree on this approach, and must also have a means of unambiguously identifying the
hash-function to be used to generate the hash-code from the message.
The mechanisms specified in ISO/IEC 9796 (all parts) give either total or partial recovery, with the objective of
reducing storage and transmission overhead. If the message is short enough, then the entire message can be
vi © ISO/IEC 2010 – All rights reserved
---------------------- Page: 6 ----------------------
ISO/IEC 9796-2:2010(E)
included in the signature, and recovered from the signature in the verification process. Otherwise, a part of the
message can be included in the signature, and the remainder stored and/or transmitted along with the
signature.
The mechanisms specified in this part of ISO/IEC 9796 use a hash-function for hashing the entire message
(possibly in more than one part). ISO/IEC 10118 specifies hash-functions for digital signatures.
© ISO/IEC 2010 – All rights reserved vii
---------------------- Page: 7 ----------------------
INTERNATIONAL STANDARD ISO/IEC 9796-2:2010(E)
Information technology — Security techniques — Digital
signature schemes giving message recovery —
Part 2:
Integer factorization based mechanisms
1 Scope
This part of ISO/IEC 9796 specifies three digital signature schemes giving message recovery, two of which
are deterministic (non-randomized) and one of which is randomized. The security of all three schemes is
based on the difficulty of factorizing large numbers. All three schemes can provide either total or partial
message recovery.
This part of ISO/IEC 9796 specifies the method for key production for the three signature schemes. However,
techniques for key management and for random number generation (as required for the randomized signature
scheme) are outside the scope of this part of ISO/IEC 9796.
The first mechanism specified in this part of ISO/IEC 9796 is only applicable for existing implementations, and
is retained for reasons of backward compatibility.
2 Normative references
The following referenced documents are indispensable for the application of this document. For dated
references, only the edition cited applies. For undated references, the latest edition of the referenced
document (including any amendments) applies.
ISO/IEC 10118 (all parts), Information technology — Security techniques — Hash-functions
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
capacity
positive integer indicating the number of bits available within the signature for the recoverable part of the
message
3.2
certificate domain
collection of entities using public key certificates created by a single Certification Authority (CA) or a collection
of CAs operating under a single security policy
3.3
certificate domain parameters
cryptographic parameters specific to a certificate domain and which are known and agreed by all members of
the certificate domain
© ISO/IEC 2010 – All rights reserved 1
---------------------- Page: 8 ----------------------
ISO/IEC 9796-2:2010(E)
3.4
collision-resistant hash-function
hash-function satisfying the following property:
⎯ it is computationally infeasible to find any two distinct inputs which map to the same output
[ISO/IEC 10118-1]
3.5
hash-code
string of bits which is the output of a hash-function
[ISO/IEC 10118-1]
3.6
hash-function
function which 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 which maps to this output;
⎯ for a given input, it is computationally infeasible to find a second input which maps to the same output
[ISO/IEC 9797-2]
3.7
mask generation function
function which maps strings of bits to strings of bits of arbitrary specified length, satisfying the following
property:
⎯ it is computationally infeasible to predict, given one part of an output but not the input, another part of the
output
3.8
message
string of bits of any length
[ISO/IEC 14888-1]
3.9
message representative
bit string derived as a function of the message and which is combined with the private signature key to yield
the signature
3.10
nibble
block of four consecutive bits (half an octet)
3.11
non-recoverable part
part of the message stored or transmitted along with the signature; empty when message recovery is total
3.12
octet
string of eight bits
3.13
private key
key of an entity's asymmetric key pair which should only be used by that entity
[ISO/IEC 9798-1]
2 © ISO/IEC 2010 – All rights reserved
---------------------- Page: 9 ----------------------
ISO/IEC 9796-2:2010(E)
3.14
private signature key
private key which defines the private signature transformation
[ISO/IEC 9798-1]
3.15
public key
key of an entity's asymmetric key pair which can be made public
[ISO/IEC 9798-1]
3.16
public key system
〈digital signature〉 cryptographic scheme consisting of three functions:
⎯ key production, a method for generating a key pair made up of a private signature key and a public
verification key;
Σ from a message representative F and a
⎯ signature production, a method for generating a signature
private signature key;
⎯ signature opening, a method for obtaining the recovered message representative F* from a signature Σ
and a public verification key
NOTE The output of this function also contains an indication as to whether the signature opening procedure
succeeded or failed.
3.17
public verification key
public key which defines the public verification transformation
[ISO/IEC 9798-1]
3.18
recoverable part
part of the message conveyed in the signature
3.19
salt
random data item produced by the signing entity during the generation of the message representative in
Signature scheme 2
3.20
signature
string of bits resulting from the signature process
[ISO/IEC 14888-1]
3.21
trailer
string of bits of length one or two octets, concatenated to the end of the recoverable part of the message
during message representative production
4 Symbols and abbreviated terms
For the purposes of this document, the following symbols and abbreviations apply.
NOTE In most cases upper case letters are used to represent bit strings and octet strings, whereas lower case letters
are used to represent functions.
© ISO/IEC 2010 – All rights reserved 3
---------------------- Page: 10 ----------------------
ISO/IEC 9796-2:2010(E)
C Octet string encoding the bit length of the recoverable part of the message (used in message
representative production in Signature schemes 2 and 3).
c The capacity of the signature scheme, i.e. the maximum number of bits available for the recoverable
part of the message.
c* The recoverable message length, i.e. the length in bits of the recoverable part of the message
(c ≥ c*).
D, D′ Bit strings constructed during message representative production in Signature schemes 2 and 3.
D*, D′* Bit strings constructed during message recovery in Signature schemes 2 and 3.
F Message representative (a bit string).
F* Recovered message representative (as output from the Signature opening step).
g Mask generation function.
H Hash-code computed as a function of the message M (a bit string).
H* Recovered hash-code as derived during the Message recovery step.
h Collision-resistant hash-function.
k The bit length of the modulus of the private signature key and public verification key (see Annex A).
L The bit length of hash-codes produced by the hash-function h.
h
L The bit length of the salt S.
S
M Message to be signed (a bit string).
M* Message recovered from a signature as a result of the verification process.
M Recoverable part of the message M, i.e. M = M ||M .
1 1 2
M * Recovered recoverable part of the message (as generated during message recovery).
1
M Non-recoverable part of the message M, i.e. M = M ||M .
2 1 2
M * Non-recoverable part of the message, as input to the verification process.
2
N Bit string constructed during message representative production in Signature schemes 2 and 3.
N* Bit string generated during message recovery in Signature schemes 2 and 3.
P A string of zero bits constructed during message representative production in Signature schemes 2
and 3.
S Salt (a bit string).
S* Recovered salt (a bit string).
t The number of octets in the Trailer field (t = 1 or 2).
T The Trailer field (a string of 8t bits used during message representative production).
Δ Integer in the range 0 to 7 used in the specification of message allocation.
4 © ISO/IEC 2010 – All rights reserved
---------------------- Page: 11 ----------------------
ISO/IEC 9796-2:2010(E)
δ Integer in the range 0 to 7 used in the specification of Signature schemes 2 and 3.
Σ Signature (a bit string containing k-1 or k bits).
|A| The bit length of the bit-string A, i.e. the number of bits in A.
A || B Concatenation of bit strings A and B (in that order).
⎡a⎤ for a real number a, the smallest integer not less than a.
a mod n for integers a and n, (a mod n) denotes the (non-negative) remainder obtained when a is divided
by n. Еquivalently if b = a mod n, then b is the unique integer satisfying:
(i) 0 ≤ b < n, and
(ii) (b-a) is an integer multiple of n.
⊕ The bit-wise exclusive-or operator, as used to combine two binary strings of the same length.
5 Converting between bit strings and integers
l
To represent a non-negative integer x as a bit string of length l (l has to be such that 2 > x), the integer shall
be written in its unique binary representation:
l–1 l–2
x = 2 x + 2 x + … + 2x + x
l–1 l–2 1 0
l–1
where 0 ≤ x < 2 (note that one or more leading digits will be zero if x < 2 ). The bit string shall be
i
x x … x .
l-1 l-2 0
To represent a bit string x x … x (of length l) as an integer x, the inverse process shall be followed, i.e. x
l-1 l-2 0
shall be the integer defined by
l–1 l–2
x = 2 x + 2 x + … + 2x + x .
l–1 l–2 1 0
6 Requirements
Users of this part of ISO/IEC 9796 are, wherever possible, recommended to adopt the second mechanism
(Digital signature scheme 2). However, in environments where generation of random variables by the signer is
deemed infeasible, then Digital signature scheme 3 is recommended.
Users who wish to employ a digital signature mechanism compliant with this part of ISO/IEC 9796 shall
ensure that the following properties hold.
a) The message M to be signed shall be a binary string of any length, possibly empty.
b) The signature function uses a private signature key, while the verification function uses the corresponding
public verification key.
– Each signing entity shall use and keep secret its private signature key corresponding to its public
verification key.
– Each verifying entity should know the public verification key of the signing entity.
c) Use of the signature schemes specified in this part of ISO/IEC 9796 requires the selection of a collision-
resistant hash-function h. Hash-functions are standardised in ISO/IEC 10118. There shall be a binding
between the signature m
...
Questions, Comments and Discussion
Ask us and Technical Secretary will try to provide an answer. You can facilitate discussion about the standard in here.