ANSI INCITS ISO IEC 10118-4-1998 Information technology - Security techniques Hash-functions Part 4 Hash-functions using modular arithmetic (Adopted by INCITS).pdf

1、B CReference numberISO/IEC 10118-4:1998(E)INTERNATIONALSTANDARDISO/IEC10118-4First edition1998-12-15Information technology Securitytechniques Hash-functions Part 4:Hash-functions using modular arithmeticTechnologies de linformation Techniques de scurit Fonctionsde brouillage Partie 4: Fonctions de h

2、achage utilisant larithmtique modulaireAdopted by INCITS (InterNational Committee for Information Technology Standards) as an American National Standard.Date of ANSI Approval: 7/7/200Published by American National Standards Institute,25 West 43rd Street, New York, New York 10036Copyright 2003 by Inf

3、ormation 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 Institute (ANSI), and Information Technology Industry Counci

4、l(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 Street NW,Washington, DC 20005.Printed in the United

5、States of AmericaISO/IEC 10118-4:1998(E) ISO/IEC 1998All rights reserved. Unless otherwise specified, no part of this publication may be reproducedor utilized in any form or by any means, electronic or mechanical, including photocopying andmicrofilm, without permission in writing from the publisher.

6、ISO/IEC Copyright Office Case postale 56 CH-1211 Genve 20 SwitzerlandPrinted in SwitzerlandiiContents1 Scope .12 Normative reference .13 Terms and definitions.13.1 From ISO/IEC 10118-1.13.2 Unique to this part of ISO/IEC 10118.13.3 Conventions 24 Symbols and abbreviated terms24.1 From ISO/IEC 10118-

7、1.24.2 Unique to this part of ISO/IEC 10118.35 Requirements 46 Variables and values needed for the hash operation46.1 The length of the hash-code and of the modulus46.2 The modulus of the round-function 46.3 Initializing value 56.4 Exponent56.5 Reduction-function prime number57 Hashing procedure .57

8、.1 Preparation of the data string57.1.1 Padding the data string 57.1.2 Appending the length .57.1.3 Splitting the data string57.1.4 Expansion 57.2 Application of the round-function.5ISO/IECISO/IEC 10118-4:1998(E)iii7.3 The Reduction-function 67.3.1 Splitting the block Hq. 67.3.2 Extending the data s

9、tring. 67.3.3 Processing the half-blocks 67.3.4 Reduction 68 Hash-functions 68.1 MASH-1 68.2 MASH-2 7Annex A (informative) Examples . 9Annex B (informative) Additional Information 22Annex C (informative) Bibliography 23ISO/IEC 10118-4:1998(E)ISO/IECivForewordISO (the International Organization for S

10、tandardization) 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 therespective organiza

11、tion 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.In the field of information technology, IS

12、O 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.

13、International Standard ISO/IEC 10118-4 was prepared by Joint Technical Committee ISO/IEC JTC 1, Informationtechnology, Subcommittee SC27, IT Security techniques.ISO/IEC 10118 consists of the following parts, under the general title Information technology Security techniques Hash-functions: Part 1: G

14、eneral Part 2: Hash-functions using an n-bit block cipher algorithm Part 3: Dedicated hash-functions Part 4: Hash-functions using modular arithmeticAnnexes A, B and C of this part of ISO/IEC 10118 are for information only.INTERNATIONAL STANDARD ISO/IEC ISO/IEC 10118-4:1998(E)1Information technology

15、Security techniques Hashfunctions Part 4:Hash-functions using modular arithmetic1 ScopeThis part of ISO/IEC 10118 specifies two hash-functions which make use of modular arithmetic. These hash-func-tions, which are believed to be collision-resistant, compress messages of arbitrary but limited length

16、to a hash-codewhose length is determined by the length of the prime number used in the reduction-function defined in 7.3. Thus,the hash-code is easily scaled to the input length of any mechanism (e.g., signature algorithm, identificationscheme).The hash-functions specified in this part of ISO/IEC 10

17、118, known as MASH-1 and MASH-2 (Modular ArithmeticSecure Hash) are particularly suitable for environments in which implementations of modular arithmetic of sufficientlength are already available. The two hash-functions differ only in the exponent used in the round-function.2 Normative referenceThe

18、following standard contains provisions which, through reference in this text, constitute provisions of this part ofISO/IEC 10118. At the time of publication, the edition indicated was valid. All standards are subject to revision andparties to agreements based on this part of ISO/IEC 10118 are encour

19、aged to investigate the possibility of applyingthe most recent edition of the standard indicated below. Members of IEC and ISO maintain registers of currentlyvalid International Standards.ISO/IEC 10118-1: 1994, Information technology Security techniques Hash-functions Part 1: General.3 Terms and def

20、initionsFor the purposes of this part of ISO/IEC 10118, the following definitions apply.3.1 From ISO/IEC 10118-1 collision-resistant hash-function data string (data) hash-code hash-function initializing value padding.3.2 Unique to this part of ISO/IEC 101183.2.1blocka string of bits of length L, whi

21、ch shall be an integer multiple of 16 (see also clause 6.1)EXAMPLE The length of the output Hjof the round-function.ISO/IEC 10118-4:1998(E)ISO/IEC23.2.2half-blocka string of bits of length L /2EXAMPLE Half the length of the block Hj.3.2.3hash-function identifiera byte identifying a specific hash-fun

22、ction3.2.4modulusa parameter which is a positive integer and a product of two distinct prime numbers3.2.5reduction-functiona function RED that is applied to the block Hqof length L to generate the hash-code H of length Lp3.2.6round-functiona function (.,.) that transforms two binary strings of lengt

23、h L to a binary string of length LNOTE It is used iteratively as part of a hash-function, where it combines an expanded data block of length L with theprevious output of length L .3.3 Conventions3.3.1 Bit orderingBit ordering in this part of ISO/IEC 10118 is as described in clause 3 of ISO/IEC 10118

24、-1.3.3.2 Converting a number to a stringDuring computation of the round-function, integers need to be converted to strings of L bits. Where this is required,the string of bits shall be made equal to the binary representation of the integer, with the left-most bit of the stringcorresponding to the mo

25、st significant bit of the binary representation. If the resulting string of bits has less than Lbits, then the string shall be left-padded with the appropriate number of zeros to make it of length L.3.3.3 Converting a string to a numberDuring computation of the round-function, strings of bits need t

26、o be converted into integers. Where this is required,the integer shall be made equal to the number having binary representation equal to the binary string, where theleft-most bit of the string is considered as the most significant bit of the binary representation.3.4 Hash-function identifierIdentifi

27、ers are defined for each of the two MASH hash-functions specified in this standard. The hash-functionidentifiers for the hash-functions specified in clause 8.1 and 8.2 are equal to 41 and 42 (hexadecimal) respectively.The range of values from 43 to 4f (hexadecimal) are reserved for future use as has

28、h-function identifiers by this partof ISO/IEC 10118.4 Symbols and abbreviated termsThroughout this part of ISO/IEC 10118, the following symbols and abbreviations apply.4.1 From ISO/IEC 10118-1D DataH Hash-codeIV Initializing valueXY Exclusive-or of strings of bits X and YISO/IECISO/IEC 10118-4:1998(

29、E)34.2 Unique to this part of ISO/IEC 10118BjThe jth block derived from the data string D after the padding, splitting, and expansion process.DjThe jth half-block derived from the data string D after the padding and the splitting process. Dq+1throughDq+8are additional data blocks computed in the red

30、uction-function.e The exponent used in the round-function.E A constant blockequal to four ones (in the left-most position) followed by L 4 zeros.HjThe output of the round-function in the jth round. Hjhas length L.LDThe length of the input string D in bits.LThe length of the output Hjof the round-fun

31、ction . It shall be an integer multiple of 16.LNThe length of the modulus N used in the round-function.Lp The length of the prime number p used in the reduction-function.mod If Z1is an integer and Z2is a positive integer, then Z1mod Z2denotes the unique integer Z3which satisfiesa) 0 Z3 Z2, andb) Z1

32、- Z3 is an integer multiple of Z2.N A composite integer, used as the modulus in the round-function.NOTE For the determination of the value of N, see clause 5.p A prime number used in the reduction-function.NOTE For the determination of the value of p, see clause 5.q The number of half-blocks in the

33、data string D after the padding and splitting processes, also the number ofblocks after the padding, splitting, and expansion process.RED The reduction-function, that is applied as the last operation of the hashing procedure to reduce the block Hqof length Lto the hash-code H of length Lp.YjThe jth

34、sub-string of length L/4 bits used in the reduction-function. A round-function. If X and Y denote strings of Lbits, then (X,Y) denotes a string of Lbits obtained byapplying to X and Y. The bit-wise inclusive OR operation on strings of bits, i.e., if X and Y are strings of the same length, thenXY den

35、otes the string obtained as the bit-wise inclusive OR of X and Y. A symbol denoting the truncate operation. If X is a bitstring then Xj denotes the bitstring obtained by takingthe right-most j bits of X.:= A symbol denoting the set equal to operation. It is used in the procedural specification of th

36、e round-functionand of the reduction-function, where it indicates that the block on the left side of the symbol shall bechanged to equal the value of the expression on the right side of the symbol.X | Y Concatenation of bit-strings X and Y in the indicated order.ISO/IEC 10118-4:1998(E)ISO/IEC45 Requ

37、irements5.1 To employ either of the hash-functions specified in this part of ISO/IEC 10118, two integers shall be selected:the modulus N used in the round-function and the prime p used in the reduction-function.Both integers, N and p, are determined by the security requirements of the application fo

38、r which these hash-func-tions are used.5.1.1 The modulus N shall be chosen so that factoring it is computationally infeasible.5.1.2 The modulus N shall be generated in a way that the factors remain secret. This can be accomplished by atrusted third party or by a secure multiparty computation.NOTE 1

39、Generating a modulus N with the property that its factors remain secret can be accomplished by using a trustedthird party, trusted hardware, and/or a secure multiparty computation. Examples can be found in Boneh 1, Cocks 2, andFrankel 3.NOTE 2 If the factors of the modulus are kept secret, and if th

40、e size of the prime p is sufficiently large, then the best knownalgorithm to find a collision takes approximately 2Lp/2evaluations of the round-function, and the best known algorithm to find a(2nd) pre-image requires approximately 2Lpevaluations of the round-function. Thus in these circumstances MAS

41、H-1 andMASH-2 are believed to be collision-free hash-functions.5.1.3 The reduction-function prime p shall not be a factor of the modulus N of the round-function.5.1.4 The length Lp of the prime p shall be at most half of the length of the modulus N, Lp L/2.5.1.5 The three high order bits of prime p

42、shall consist of ones.5.2 To employ one of the hash-functions, MASH-1 or MASH-2, the user has to select one of the two exponents eused in the round-function .5.3 MASH-1 and MASH-2 can be applied to all data strings D containing at most 2L/2-1 bits.6 Variables and values needed for the hash operation

43、6.1 The length of the hash-code and of the modulusThe length of the modulus N and the length of the blocks Hj are related in the following manner:L+1 LN L+16The length L of the block Hqshall be an integer multiple of 16.NOTE 1 If the length Lis chosen, then the length LNis constrained by the inequal

44、ities above. If the length LNis chosen,then the length Lwill be the largest multiple of 16 less than LN.NOTE 2 Knowledge of N is sufficient to determine LN, and consequently L.6.2 The modulus of the round-functionThe modulus N used in the round-function is a composite integer generated as a product

45、of two prime numbers ofabout the same length such that it is computationally infeasible to factorize N.NOTE 1 In addition to the infeasibility of the factorization of the modulus, the security of the MASH hash-functions is based inpart on the difficulty of extracting modular roots.NOTE 2 The choice

46、of a specific modulus N of appropriate length is outside the scope of this part of ISO/IEC 10118.ISO/IECISO/IEC 10118-4:1998(E)56.3 Initializing valueThe initializing value IV is defined to be the string of Lbinary zeros.6.4 ExponentFor MASH-1 the value of the exponent e in the round-function equals

47、 2. For MASH-2 the value of the exponent e inthe round-function equals 257.6.5 Reduction-function prime numberThe reduction-function specified in 7.3 requires a prime p. The length Lp of prime p is determined by the securityrequirements, and by the input length of any mechanism using the hash-code.

48、The length Lp shall be at most half ofthe length of the modulus N, Lp L/2.NOTE 1 The choice of a specific prime p of appropriate length is outside the scope of this part of ISO/IEC 10118.NOTE 2 To avoid unbalanced results by the reduction modulo p, the prime number p shall be selected with the three

49、 highorder bits equal to ones.7 Hashing procedureThe hash-code H of the data string D shall be calculated using the following steps (see Figure 1):7.1 Preparation of the data stringThe data string D is transformed into a sequence of blocks for input to the round-function . The preparationconsists of padding, splitting, and expanding as detailed in the following sub-clauses.7.1.1 Padding the data stringIf the length LDof the data string D is not an integer multiple of L/2,