ANSI INCITS ISO IEC 9796-3-2000 Information technology Security techniques Digital signature schemes giving message recovery Part 3 Discrete logarithm based mechanisms.pdf

1、Reference numberISO/IEC 9796-3:2000(E)ISO/IEC 2000INTERNATIONALSTANDARDISO/IEC9796-3First edition2000-04-15Information technology Securitytechniques Digital signature schemesgiving message recovery Part 3:Discrete logarithm based mechanismsTechnologies de linformation Techniques de scurit Schma desi

2、gnature numrique rtablissant le message Partie 3: Mcanismes bass sur les logarithmes discretsAdopted by INCITS (InterNational Committee for Information Technology Standards) as an American National Standard.Date of ANSI Approval: 11/1/00Published by American National Standards Institute,25 West 43rd

3、 Street, New York, New York 10036Copyright 2002 by Information Technology Industry Council (ITI).All rights reserved.These materials are subject to copyright claims of International Standardization Organization (ISO), InternationalElectrotechnical Commission (IEC), American National Standards Instit

4、ute (ANSI), and Information Technology Industry Council(ITI). Not for resale. No part of this publication may be reproduced in any form, including an electronic retrieval system, withoutthe prior written permission of ITI. All requests pertaining to this standard should be submitted to ITI, 1250 Eye

5、 Street NW,Washington, DC 20005.Printed in the United States of AmericaISO/IEC 9796-3:2000(E)PDF disclaimerThis PDF file may contain embedded typefaces. In accordance with Adobes licensing policy, this file may be printed or viewed but shall notbe edited unless the typefaces which are embedded are l

6、icensed to and installed on the computer performing the editing. In downloading thisfile, parties accept therein the responsibility of not infringing Adobes licensing policy. The ISO Central Secretariat accepts no liability in thisarea.Adobe is a trademark of Adobe Systems Incorporated.Details of th

7、e software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation parameterswere optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In the unlikely eventthat a problem relating to

8、it is found, please inform the Central Secretariat at the address given below. ISO/IEC 2000All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means, electronicor mechanical, including photocopying and microfilm, without pe

9、rmission in writing from either ISO at the address below or ISOs member bodyin the country of the requester.ISO copyright officeCase postale 56 Gb7 CH-1211 Geneva 20Tel. + 41 22 749 01 11Fax + 41 22 734 10 79E-mail copyrightiso.chWeb www.iso.chPrinted in Switzerlandii ISO/IEC 2000 All rights reserve

10、dISO/IEC 9796-3:2000(E) ISO/IEC 2000 All rights reserved iiiContents Page1 Scope12 Normative references13 Terms and definitions .14 Symbols, conventions, and legend for figures.34.1 Symbols and notation.34.2 Coding convention, length and size of the field.44.3 Legend for figures.55 Requirements.55.1

11、 Options for binding signature mechanism and hash-function.56 Signature process66.1 Producing the pre-signature.66.2 Producing the hash-token 66.3 Formatting the data input .76.4 Computing the signature76.5 Formatting the signed message.87 Verification process 87.1 Opening the signed message.87.2 Re

12、covering the pre-signature and the data input.107.3 Recovering the message and the (truncated) hash-token107.4 Recomputing the hash-token.107.5 Comparing the recovered and the recomputed (truncated) hash-tokens.108 Signature schemes giving message recovery109 Signature scheme on a prime field119.1 D

13、omain parameters.119.2 Signature and verification key119.3 Randomizer and pre-signature.119.4 The first part of the signature.119.5 Signature function.129.6 Verification function129.7 Recovering the data input.1210 Signature scheme on an elliptic curve1210.1 Domain parameters.1210.1.1 Equation and g

14、roup law for a field over a prime1210.1.2 Equation and group law for a field over a power of two1310.2 Signature and verification key1310.3 Randomizer and pre-signature.1310.4 Computing the first part of the signature1310.5 Signature function.1310.6 Verification function1310.7 Recovering the data in

15、put.13Annex A (normative) Validation of domain parameters and public keys14A.1 Signature scheme on a prime field14A.1.1 Domain parameter validation .14A.1.2 Verification key validation 14A.2 Signature scheme on an elliptic curve14A.2.1 Domain parameter validation .14A.2.2 Verification key validation

16、 16ISO/IEC 9796-3:2000(E)iv ISO/IEC 2000 All rights reservedAnnex B (informative) Numerical examples I Signature mechanisms on finite fields.17B.1 Examples with partial recovery17B.1.1 Example with hash-function SHA-1 18B.1.2 Example with hash-function RIPEMD-160 18B.1.3 Example with hash-function R

17、IPEMD-128 19B.2 Example with total recovery.19B.2.1 Example with hash-function RIPEMD-128 20Annex C (informative) Numerical examples II Elliptic curve mechanisms.21C.1 Elliptic curve over a prime field21C.1.1 Example with hash-function RIPEMD-160 22C.1.2 Example with hash-function RIPEMD-128 22C.2 E

18、lliptic curve over an extension field GF(2n).22C.2.1 Example with hash-function RIPEMD-160 23C.2.2 Example with hash-function RIPEMD-128 23Annex D (informative) Information about patents24Bibliography .25ISO/IEC 9796-3:2000(E) ISO/IEC 2000 All rights reserved vForewordISO (the International Organiza

19、tion for Standardization) and IEC (the International Electrotechnical Commission)form the specialized system for worldwide standardization. National bodies that are members of ISO or IECparticipate in the development of International Standards through technical committees established by therespectiv

20、e organization to deal with particular fields of technical activity. ISO and IEC technical committeescollaborate in fields of mutual interest. Other international organizations, governmental and non-governmental, inliaison with ISO and IEC, also take part in the work.International Standards are draf

21、ted in accordance with the rules given in the ISO/IEC Directives, Part 3.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

22、.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 part of ISO/IEC 9796 may be the subject ofpatent rights. ISO and IEC shall not be held responsible for identifyin

23、g any or all such patent rights.International Standard ISO/IEC 9796-3 was prepared by Joint Technical Committee ISO/IEC JTC 1, Informationtechnology, Subcommittee SC 27, IT Security techniques.This first edition cancels and replaces ISO/IEC 9796:1991, which has been technically revised.ISO/IEC 9796

24、consists of the following parts, under the general title Information technology Securitytechniques Digital signature schemes giving message recovery:Gbe Part 2: Mechanisms using a hash-functionGbe Part 3: Discrete logarithm based mechanismsAnnex A forms a normative part of this part of ISO/IEC 9796.

25、 Annexes B to D are for information only.ISO/IEC 9796-3:2000(E)vi ISO/IEC 2000 All rights reservedIntroductionDigital signature mechanisms can be used to provide services such as entity authentication, data originauthentication, non-repudiation, and integrity of data.A digital signature mechanism sa

26、tisfies the following requirements:Gbe Given only the verification key and not the signature key it is computationally infeasible to produce anymessage and a valid signature for this message.Gbe The signatures produced by a signer can neither be used for producing any new message and a validsignatur

27、e for this message nor for recovering the signature key.Gbe It is computationally infeasible, even for the signer, to find two different messages with the same signature.NOTE Computational feasibility depends on the specific security requirements and environment.Most digital signature mechanisms are

28、 based on asymmetric cryptographic techniques and involve three basicoperations:Gbe A process of generating pairs of keys, where each pair consists of a private signature key and thecorresponding public verification key.Gbe A process using the signature key; called the signature process.Gbe A proces

29、s using the verification key; called the verification process.There are two types of digital signature mechanisms:Gbe When, for each given signature key, the signatures produced for the same message are the same, themechanism is said to be non-randomized (or deterministic, see ISO/IEC 14888-1).Gbe W

30、hen, for a given message and a given signature key, each application of the signature process produces adifferent signature, the mechanism is said to be randomized.Digital signature schemes can also be divided into the following two categories:Gbe When the whole message has to be stored and/or trans

31、mitted along with the signature, the mechanism isnamed a ”signature mechanism with appendix” (see ISO/IEC 14888).Gbe When the whole message or a part of it is recovered from the signature, the mechanism is named a ”signaturemechanism giving message recovery” (see ISO/IEC 9796).NOTE Any signature mec

32、hanism giving message recovery, for example, the mechanisms specified in ISO/IEC 9796, canbe converted for provision of digital signatures with appendix. In this case, the signature is produced by application of thesignature mechanism to a hash-token of the message.The mechanisms specified in ISO/IE

33、C 9796 give either total or partial recovery, aiming at reducing storage andtransmission overhead.The mechanisms specified in this part of ISO/IEC 9796 use a hash-function for hashing the entire message.ISO/IEC 10118 specifies hash-functions for digital signatures. If the message is short enough, th

34、en the entiremessage can be 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 rest of it is stored and/or transmitted along with thesignature.INTERNATIONAL STANDARD ISO/IEC 9796-3:2000(E)

35、ISO/IEC 2000 All rights reserved 1Information technology Security techniques Digital signatureschemes giving message recovery Part 3:Discrete logarithm based mechanisms1 ScopeThis part of ISO/IEC 9796 specifies two randomized digital signature schemes giving message recovery. Thesecurity of both sch

36、emes is based on the difficulty of the discrete logarithm problem. The first scheme is defined ona prime field and the second one on an elliptic curve.This part of ISO/IEC 9796 also defines a redundancy scheme using hash-codes and specifies how the basicsignature schemes are to be combined with the

37、redundancy scheme.This part of ISO/IEC 9796 also defines an optional control field in the hash-token, which can provide added securityto the signature.2 Normative referencesThe following normative documents contain provisions which, through reference in this text, constitute provisions ofthis part o

38、f ISO/IEC 9796. For dated references, subsequent amendments to, or revisions of, any of thesepublications do not apply. However, parties to agreements based on this part of ISO/IEC 9796 are encouraged toinvestigate the possibility of applying the most recent editions of the normative documents indic

39、ated below. Forundated references, the latest edition of the normative document referred to applies. Members of ISO and IECmaintain registers of currently valid International Standards.ISO/IEC 10118 (all parts), Information technology Security techniques Hash-functions.ISO/IEC 11770-3:1999, Informat

40、ion technology Security techniques Key management Part 3: Mechanismsusing asymmetric techniques.ISO/IEC 14888-1:1998, Information technology Security techniques Digital signatures with appendix Part 1:General.ISO/IEC 15946 (parts 1 and 2, to be published), Information technology Security techniques

41、Cryptographictechniques based on elliptic curves Part 1: General and Part 2: Digital signatures.3 Terms and definitionsFor the purposes of this part of ISO/IEC 9796, the following definitions apply.3.1 assignmentISO/IEC 14888-1 A data item which is a function of the witness and possibly of a part of

42、 the message, and formspart of the input to the signature function.3.2 certification authorityISO/IEC 11770-3 A centre trusted to create and assign public key certificates. Optionally, the certification authoritymay create and assign keys to the entities.ISO/IEC 9796-3:2000(E)2 ISO/IEC 2000 All righ

43、ts reserved3.3 collision-resistant hash-functionISO/IEC 10118-1 A hash-function satisfying the following property:Gbe it is computationally infeasible to find any two distinct inputs which map to the same output.NOTE Computational feasibility depends on the specific security requirements and environ

44、ment.3.4 data inputA data item which depends on the entire message and forms a part of the input to the signature function.3.5 domain parameterISO/IEC14888-1 A data item which is common to and known by or accessible to all entities within the domain.NOTE The set of domain parameters may contain data

45、 items such as hash-function identifier, length of the hash-token,length of the recoverable part of the message, finite field parameters, elliptic curve parameters, or other parameters specifyingthe security policy in the domain.3.6 hash-codeISO/IEC 10118-1 The string of bits which is the output of

46、a hash-function.3.7 hash-functionISO/IEC 10118-1 A function which maps strings of bits to fixed-length strings of bits, satisfying the following twoproperties:Gbe for a given output, it is computationally infeasible to find an input which maps to this output; andGbe for a given input, it is computat

47、ionally infeasible to find a second input which maps to the same output.NOTE Computational feasibility depends on the specific security requirements and environment.3.8 hash-tokenISO/IEC 14888-1 A concatenation of a hash-code and an optional control field, which can be used to identify thehash-funct

48、ion and the padding method.NOTE The control field with hash-function identifier is mandatory unless the hash-function is uniquely determined by thesignature mechanism or by the domain parameters.3.9 messageA string of bits of any length.3.10 pre-signatureISO/IEC 14888-1 A value computed in the signa

49、ture process which is a function of the randomizer but isindependent of the message.3.11 public key certificateISO/IEC 11770-3 The public key information of an entity signed by the certification authority and thereby renderedunforgeable.NOTE In the context of this part of ISO/IEC 9796 the public key information contains the information about the verificationkey and the domain parameters.3.12 randomizedISO/IEC 14888-1 Dependent on a randomizer.3.13 randomizerISO/IEC 14888-1 A secret data it