ANSI INCITS ISO IEC 18031-2005 Information technology Security techniques Random bit generation.pdf

1、INCITS/ISO/IEC 18031:20052008 (ISO/IEC 18031:2005, IDT) Information technology Security techniques Random bit generationINCITS/ISO/IEC 18031:20052008(ISO/IEC 18031:2005, IDT)INCITS/ISO/IEC 18031:20052008 ii ITIC 2008 All rights reserved PDF disclaimer This PDF file may contain embedded typefaces. In

2、 accordance with Adobes 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 Ado

3、bes 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

4、 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. Adopted by INCITS (InterNational Committee for Information Technology

5、 Standards) as an American National Standard. Date of ANSI Approval: 7/1/2008 Published by American National Standards Institute, 25 West 43rd Street, New York, New York 10036 Copyright 2008 by Information Technology Industry Council (ITI). All rights reserved. These materials are subject to copyrig

6、ht claims of International Standardization Organization (ISO), International Electrotechnical Commission (IEC), American National Standards Institute (ANSI), and Information Technology Industry Council (ITI). Not for resale. No part of this publication may be reproduced in any form, including an ele

7、ctronic retrieval system, without the 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 States of America INCITS/ISO/IEC 18031:20052008 ITIC 2008 All rights reserved iii Contents Page

8、Foreword vi Introduction . vii 1 Scope 1 2 Normative references .1 3 Terms and definitions 2 4 Symbols 5 5 Overarching objectives and requirements of a random bit generator .5 5.1 Required properties of randomness 6 5.2 Backward and forward secrecy .6 5.3 Top-level objectives and requirements for a

9、random bit generator (RBG) output 7 5.4 Top-level objectives and requirements for RBG operation 7 5.5 Random bit generator functional requirements 8 6 General functional model for random bit generation8 6.1 Basic components 8 6.1.1 Entropy source .9 6.1.2 Additional inputs 10 6.1.3 Internal state .

10、10 6.1.4 Internal state transition functions . 11 6.1.5 Output generation function 12 6.1.6 Support functions. 13 7 Types of random bit generators 14 7.1 Non-deterministic random bit generators (NRBGs) 14 7.2 Deterministic random bit generators (DRBGs) . 15 7.3 The RBG spectrum . 15 8 Overview and r

11、equirements for a non-deterministic random bit generator 16 8.1 Overview . 16 8.2 Functional model of a non-deterministic random bit generator . 16 8.2.1 Overview of the model . 16 8.3 Entropy sources . 18 8.3.1 Primary entropy source . 18 8.3.2 Physical entropy sources 20 8.3.3 Non-physical entropy

12、 sources . 21 8.3.4 Additional entropy sources 21 8.3.5 Hybrid non-deterministic random bit generators 22 8.4 Additional inputs 23 8.4.1 Overview . 23 8.4.2 Mandatory requirements 23 8.5 Internal state . 23 8.5.1 Overview . 23 8.5.2 Mandatory requirements 24 8.5.3 Optional requirements . 24 8.6 Inte

13、rnal state transition functions . 25 8.6.1 Overview . 25 8.6.2 Mandatory requirements 26 8.6.3 Optional requirements . 26 8.7 Output generation function 26 8.7.1 Overview . 26 8.7.2 Mandatory requirements 26 INCITS/ISO/IEC 18031:20052008 iv ITIC 2008 All rights reserved 8.7.3 Optional requirement .

14、27 8.8 Health tests. 27 8.8.1 Overview . 27 8.8.2 General health test requirements 27 8.8.3 Health test on deterministic components . 28 8.8.4 Health tests on entropy sources . 28 8.8.5 Health tests on random output 29 8.9 Component interaction 31 8.9.1 Overview . 31 8.9.2 Mandatory requirements 31

15、8.9.3 Optional requirements . 32 9 Overview and requirements for a deterministic random bit generator 32 9.1 Overview . 32 9.2 Functional model of DRBG 33 9.2.1 Overview of the model . 33 9.3 Entropy source . 35 9.3.1 Primary entropy source . 35 9.3.2 Generating seed values . 37 9.3.3 Additional ent

16、ropy sources . 37 9.3.4 Hybrid deterministic random bit generator . 38 9.4 Additional inputs 38 9.5 Internal state . 38 9.6 Internal state transition function . 39 9.7 Output generation function . 40 9.7.1 Overview . 40 9.8 Support functions 40 9.8.1 Overview . 40 9.8.2 Self test . 40 9.8.3 Determin

17、istic algorithm test 41 9.8.4 Software/Firmware integrity test . 41 9.8.5 Critical functions test . 41 9.8.6 Software/Firmware load test 41 9.8.7 Manual key entry test . 41 9.8.8 Continuous random bit generator test 42 9.9 Additional DRBG functional requirements 42 9.9.1 Keys 42 Annex A (normative)

18、Combining random bit generators 44 Annex B (normative) Conversion methods 45 B.1 Random number generation 45 B.1.1 The simple discard method . 45 B.1.2 The complex discard method 45 B.1.3 The simple modular method 46 B.1.4 The complex modular method . 46 B.2 Extracting bits in the Dual_EC_DRBG 47 B.

19、2.1 Potential bias in an elliptic curve over a prime field Fp 47 B.2.2 Adjusting for the missing bit(s) of entropy in the x coordinates . 48 B.2.3 Values for E 49 B.2.4 Observations 51 Annex C (normative) Deterministic random bit generators 52 C.1 Introduction 52 C.2 Deterministic RBGs based on a ha

20、sh-function . 52 C.2.1 Hash-function DRBG (Hash_DRBG) 52 C.3 DRBG based on block ciphers 60 C.3.1 CTR_DRBG . 61 C.3.2 OFB_DRBG () 70 C.4 Deterministic RBGs based on number theoretic problems 72 C.4.1 Dual Elliptic Curve DRBG (Dual_EC_DRBG) . 72 C.4.2 Micali Schnorr DRBG (MS_DRBG) 81 INCITS/ISO/IEC 1

21、8031:20052008 ITIC 2008 All rights reserved v Annex D (normative) Application specific constants 91 D.1 Constants for the Dual_EC_DRBG 91 D.1.1 Curves over Prime Fields . 91 D.1.2 Curves over binary fields . 94 D.2 Default moduli for the MS_DRBG () 103 D.2.1 Default modulus n of size 1024 bits . 103

22、 D.2.2 Default modulus n of size 2048 bits . 103 D.2.3 Default modulus n of size 3072 bits . 104 D.2.4 Default modulus n of size 7680 bits . 104 D.2.5 Default modulus n of size 15360 bits . 105 Annex E (informative) Non-deterministic random bit generator examples . 107 E.1 Canonical coin tossing exa

23、mple 107 E.1.1 Overview . 107 E.1.2 Description of basic process . 107 E.1.3 Relation to standard NRBG components 107 E.1.4 Optional variations . 108 E.1.5 Peres unbiasing procedure 108 E.2 Hypothetical noisy diode example. 109 E.2.1 Overview . 109 E.2.2 General structure 109 E.2.3 Details of operat

24、ion 110 E.2.4 Failsafe design consequences 114 E.2.5 Modified example . 114 E.3 Mouse movement example 115 Annex F (informative) Security considerations 116 F.1 Attack model . 116 F.2 The security of hash-functions 116 F.3 Algorithm and key size selection . 116 F.3.1 Equivalent algorithm strengths .

25、 117 F.3.2 Selection of appropriate DRBGs 118 F.4 The security of block cipher DRBGS . 119 F.5 Conditioned entropy sources and the derivation function . 119 Annex G (informative) Discussion on the estimation of entropy 120 Annex H (informative) Random bit generator assurance 121 Annex I (informative

26、) Random bit generator boundaries 122 Bibliography 124 INCITS/ISO/IEC 18031:20052008 vi ITIC 2008 All rights reserved Foreword ISO (the International Organization for Standardization) and IEC (International Electrotechnical Commission) form the specialized system for worldwide standardization. Natio

27、nal bodies that are members of ISO and 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

28、. 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

29、 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 technical committees are circulated to the member bodies for voting. Publication as an International Standard requires ap

30、proval by at least 75 % of the member 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 shall not be held responsible for identifying any or all such patent rights. ISO/IEC 18031 was prepared by Joint Tech

31、nical Committee ISO/IEC JTC 1, Information technology, Subcommittee SC 27, IT Security techniques. INCITS/ISO/IEC 18031:20052008 ITIC 2008 All rights reserved vii Introduction This International Standard sets out specific requirements that when met will result in the development of a random bit gene

32、rator that may be applicable to cryptographic applications. Numerous cryptographic applications require the use of random bits. These cryptographic applications include the following: random keys and initialisation values (IVs) for encryption; random keys for keyed MAC algorithms; random private key

33、s for digital signature algorithms; random values to be used in entity authentication mechanisms; random values to be used in key establishment protocols; random PIN and password generation; nonces. The purpose of this International Standard is to establish a conceptual model, terminology, and requi

34、rements related to the building blocks and properties of systems used for random bit generation in or for cryptographic applications. In general terms, it is possible to categorize random bit generators into two types depending on whether their source of entropy varies or is fixed. This Internationa

35、l Standard identifies the two types as non-deterministic and deterministic random bit generators. A non-deterministic random bit generator can be defined as a random bit generating mechanism that uses a source of entropy to generate a random bit stream. A deterministic random bit generator can be de

36、fined as a bit generating mechanism that uses deterministic mechanisms, such as cryptographic algorithms on a source of entropy, to generate a random bit stream. In this type of bit stream generation, there is a specific input (normally called a seed) and perhaps some optional input, which, dependin

37、g on its application may or may not be publicly available. The seed is processed by a function which provides an output. AMERICAN NATIONAL STANDARD INCITS/ISO/IEC 18031:20052008 ITIC 2008 All rights reserved 1 Information technology Security techniques Random bit generation 1 Scope This Internationa

38、l Standard specifies a conceptual model for a random bit generator for cryptographic purposes, together with the elements of this model. This International Standard also includes the following: the description of the main elements required for a non-deterministic random bit generator; the descriptio

39、n of the main elements required for a deterministic random bit generator; their characteristics; their security requirements. Where there is a requirement to produce sequences of random numbers from random bit strings, Annex B provides guidance on how this can be performed. Techniques for statistica

40、l testing of random bit generators for the purposes of independent verification or validation, and detailed designs for such generators, are outside the scope of this International Standard. 2 Normative references The following referenced documents are indispensable for the application of this docum

41、ent. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies. ISO/IEC 10116, Information technology Security techniques Modes of operation for an n-bit block cipher ISO/IEC 10118-3:2004, Informatio

42、n technology Security techniques Hash-functions Part 3: Dedicated hash-functions ISO/IEC 18032:2004, Information technology Security techniques Prime number generation ISO/IEC 18033-3:2005, Information technology Security techniques Encryption algorithms Part 3: Block ciphers ISO/IEC 19790, Informat

43、ion technology Security techniques Security requirements for cryptographic modules1) 1) To be published. INCITS/ISO/IEC 18031:20052008 2 ITIC 2008 All rights reserved 3 Terms and definitions For the purposes of this document, the following terms and definitions apply. 3.1 algorithm clearly specified

44、 mathematical process for computation; a set of rules that, if followed, will give a prescribed result. 3.2 backward secrecy assurance that previous values cannot be determined from the current value or subsequent values. 3.3 biased source source of bit strings (or numbers) from a sample space is sa

45、id to be biased if some bit string(s) (or number(s) are more likely than some other bit string(s) (or number(s) to be chosen. Equivalently, if the sample space consists of r elements, some elements will occur with probability different from 1/r. cf. unbiased source 3.4 bit stream continuous output o

46、f bits from a device or mechanism 3.5 bit string finite sequence of ones and zeros. 3.6 black box idealized mechanism that accepts inputs and produces outputs, but is designed such that an observer cannot see inside the box or determine exactly what is happening inside that box. cf. glass box 3.7 bl

47、ock cipher symmetric encipherment system with the property that the encryption operates on a block of plaintext, i.e., a string of bits of a defined length, to yield a block of ciphertext. ISO/IEC 18033-1 3.8 cryptographic boundary explicitly defined continuous perimeter that establishes the physica

48、l bounds of a cryptographic module and contains all the hardware, software and/or firmware components of a cryptographic module. ISO/IEC 19790 3.9 deterministic algorithm characteristic of an algorithm that states that given the same input, the same output is always produced. 3.10 deterministic rand

49、om bit generator DRBG random bit generator that produces a random-appearing sequence of bits by applying a deterministic algorithm to a suitably random initial value called a seed and, possibly, some secondary inputs upon which the security of the random bit generator does not depend. In particular, non-deterministic sources may also form part of these secondary inputs. INCITS/ISO/IEC 18031:20052008 ITIC 2008 All rights reserved 3 3.11 entropy measure of the disorder, random