ANSI X9.82 Part 1-2006 Random Number Generation Part 1 Overview and Basic Principles《随机数生成.第1部分 综述和基本原则》.pdf

1、 American National Standard for Financial Services ANSI X9.82: Part 12006 Random Number Generation Part 1: Overview and Basic Principles Accredited Standards Committee X9, Incorporated Financial Industry Standards Date Approved: July 26, 2006 American National Standards Institute American National S

2、tandards, Technical Reports and Guides developed through the Accredited Standards Committee X9, Inc., are copyrighted. Copying these documents for personal or commercial use outside X9 membership agreements is prohibited without express written permission of the Accredited Standards Committee X9, In

3、c. For additional information please contact ASC X9, Inc., 1212 West Street, Suite 200, Annapolis, Maryland 21401.ASC X9, Inc. 2006 All rights reserved Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted withou

4、t license from IHS-,-,-ANS X9.82, Part 1-2006 Contents Foreword. iv Introduction vi 1 Scope 1 2 Conformance 2 3 Normative references. 2 4 Terms and definitions 2 5 Symbols and Abbreviations 10 6 General Discussion 11 6.1 Overview of Document . 11 6.2 The Need for Random Numbers. 12 6.3 Examples of C

5、ryptographic Use of Random Numbers 13 7 Overview of Random Bit Generators 15 7.1 Secure RBG . 15 7.2 Idealized Coin Flipping The Canonical RBG 15 7.2.1 Coin Flipping Preliminaries. 15 7.2.2 Properties of Idealized Coin Flipping . 15 7.2.3 Possible Problems with Actual Coin Flipping . 16 7.2.4 von Ne

6、umann Unbiasing . 17 7.3 Random Bit Generation Functional Model 17 7.3.1 Entropy Source. 19 7.3.2 Algorithmic Processing . 19 7.3.3 Interfacing with the RBG . 20 7.4 Types of Random Bit Generators 20 7.4.1 Non-deterministic Random Bit Generator (NRBG) 21 7.4.2 Deterministic Random Bit Generator (DRB

7、G) 21 7.4.3 The RBG Spectrum 22 7.4.4 Summary of an Approved RBG. 23 8 Security Properties of a Random Bit Generator 23 8.1 General Discussion. 23 8.2 Security Strengths 23 8.3 Entropy and Min-Entropy . 24 8.4 Backtracking Resistance and Prediction Resistance 25 8.5 Indistinguishability Versus Unpre

8、dictability. 26 8.6 Prediction Resistance and Backtracking Resistance Considerations . 27 8.7 Desired RBG Output Properties. 28 8.8 Desired RBG Operational Properties. 29 ASC X9, Inc. 2006 All rights reservedii Copyright American National Standards Institute Provided by IHS under license with ANSI N

9、ot for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 9 Converting Random Bits to/from Random Numbers 30 9.1 The Need for Conversion Routines . 30 9.2 Converting Random Bits into a Random Number 30 9.2.1 The Simple Discard Method 31 9.2.2 The Comple

10、x Discard Method. 31 9.2.3 The Simple Modular Method 32 9.2.4 The Complex Modular Method 32 9.3 Converting a Random Number into Random Bits 33 9.3.1 The No Skew (Variable Length Extraction) Method. 33 9.3.2 The Negligible Skew (Fixed Length Extraction) Method. 34 Annex A (Informative) Security Consi

11、derations 36 A.1 Attack Model . 36 A.2 RBG Security Analysis. 36 A.3 Computationally-Indistinguishable Randomness Theorems 37 A.4 Min-Entropy as the Measure of Entropy . 38 A.4.1 Why Shannon Entropy Is Not Appropriate 39 A.4.2 Why Guessing Entropy Is Not Appropriate . 40 A.4.3 Min-Entropy Tutorial 4

12、1 Annex B (Informative) Bibliography . 43 Figures Figure 1: Random Bit Generation Functional Model 18 Figure 2: Sequence of DRGB States 26ASC X9, Inc. 2006 All rights reserved iiiCopyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or

13、networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 Foreword The Accredited Standards Committee on Financial Services (ANSI X9) has developed several cryptographic standards to protect financial information. Many of these standards require the use of Random Number Generators to

14、generate random and unpredictable cryptographic keys and other critical security parameters. This Standard, Random Number Generation, defines techniques for the generation of random numbers that are used when other ASC standards require the use of random numbers for cryptographic purposes. While the

15、 techniques specified in this Standard are designed to generate random numbers, the Standard does not guarantee that a particular implementation is secure. It is the responsibility of the financial institution to put an overall process in place with the necessary controls to ensure that the process

16、is securely implemented. Furthermore, the controls should include the application with appropriate validation tests in order to verify compliance with this Standard. Approval of an American National Standard requires verification by ASC that the requirements for due process, consensus, and other cri

17、teria for approval have been met by the standards developer. Consensus is established when, in the judgment of the ASC Board of Standards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but no

18、t necessarily unanimity. Consensus requires that all views and objections be considered, and that a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their existence does not in any respect preclude anyone, whether he has approved the s

19、tandards or not from manufacturing, marketing, purchasing, or using products, processes, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover

20、, no person shall have the right or authority to issue an interpretation of an American National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this Standard. CA

21、UTION NOTICE: This American National Standard may be revised or withdrawn at any time. The procedures of the American National Standards Institute require that action be taken to reaffirm, revise, or withdraw this Standard no later than five years from the date of approval. ASC X9, Inc. 2006 All rig

22、hts reservediv Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 Published by Accredited Standards Committee X9 Incorporated Financial Industry standards 12

23、12 West Street, Suite 200 Annapolis, MD 21401 USA X9 Online http:/www.x9.org Copyright 2004 ASC X9, Inc. All rights reserved. No part of this publication may be reproduced in any form, in an electronic retrieval system or otherwise, without prior written permission of the publisher. Published in the

24、 United States of America. ASC X9, Inc. 2006 All rights reserved vCopyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 Introduction NOTE The users attention is

25、 called to the possibility that compliance with this Standard may require use of an invention covered by patent rights. By publication of this Standard, no position is taken with respect to the validity of this claim or of any patent rights in connection therewith. The patent holder has, however, fi

26、led a statement of willingness to grant a license under these rights on reasonable and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Details may be obtained from the standards developer. Suggestions for the improvement or revision of this Standard are welcom

27、e. They should be sent to the X9 Committee Secretariat, Accredited Standards Committee X9, Inc., Financial Industry Standards, 1212 West Street, Suite 200, Annapolis, MD 21401 USA. This Standard was processed and approved for submittal to ANSI by the Accredited Standards Committee on Financial Servi

28、ces, X9. Committee approval of the Standard does not necessarily imply that all the committee members voted for its approval. The X9 committee had the following members: James Shaffer, X9 Chairman Vincent DeSantis, X9 Vice-Chairman Cynthia Fuller, Executive Director Organization Represented Represen

29、tativeACI Worldwide Jim Shaffer American Bankers Association C. Diane Poole American Express Company John Allen American Financial Services Association Mark Zalewski Bank of America Daniel Welch Capital One Scott Sykes Certicom Corporation Daniel Brown Citigroup, Inc. Mike Halpern Clarke American Ch

30、ecks, Inc. John W. McCleary Deluxe Corporation John Fitzpatrick Diebold, Inc. R. David Nein Discover Financial Services Katie Howser Federal Reserve Bank Dexter Holt First Data Corporation Connie Spurgeon Fiserv Skip Smith FSTC, Financial Services Technology Consortium Daniel Schutzer Hewlett Packar

31、d Larry Hines Hypercom Scott Spiker ASC X9, Inc. 2006 All rights reservedvi Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 iStream Imaging Ken Biel IBM C

32、orporation Todd Arnold Identrus Mack Hicks Ingenico John Spence Intuit, Inc. Jana Hocker J.P. Morgan Chase a set of rules that, if followed, will give a prescribed result. 4.2 Algorithmic Processing (AP) A major component of the RBG functional model that performs deterministic cryptographic, data fo

33、rmatting, and health check functions. 4.3 Approved An X9 Approved resource is one that is either: specified as (or within) a current X9 standard, or listed in the X9 Registry. 4.4 Backtracking Resistance The assurance that the pre-compromise output sequence from an RBG remains indistinguishable from

34、 an ideal random sequence even to an adversary who compromises the RBG in the future, up to the claimed security strength of the RBG. For example, an RBG that allowed an adversary to “backtrack“ from the current state to compute prior outputs would not provide backtracking resistance. The complement

35、ary assurance is called Prediction Resistance. 4.5 Basic NRBG A Basic NRBG relies only upon the Entropy Source, entropy conditioning function and health tests for its security. Contrast with an Enhanced NRBG, which also relies on a DRBG. 4.6 Biased A random bitstring or number is biased over a sampl

36、e space if one bitstring (or a number) is more likely than another bitstring (or number) to be chosen. Contrast with unbiased. 4.7 Bitstring A bitstring is an ordered sequence of 0s and 1s. The left-most bit is the most significant bit in the string. The right-most bit is the least significant bit o

37、f the string. 4.8 Block Cipher A symmetric key cryptographic algorithm that transforms a block of information at a time using a cryptographic key. For a block cipher algorithm, the length of the input block is the same as the length of the output block. ANS X9.82, Part 1-2006 3Copyright American Nat

38、ional Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 4.9 Conditioning A method for removing bias. 4.10 Consuming Application An application that uses random numbers or random bits o

39、btained from an Approved random number generator. 4.11 Cryptographic Hash Function A (mathematical) function that maps values from a large (possibly very large) domain into a smaller range, which satisfies the following properties: 1. (One-way) It is computationally infeasible to find any input that

40、 maps to any pre-specified output; 2. (Collision-resistant) It is computationally infeasible to find any two distinct inputs that map to the same output. 4.12 Cryptographic Key (Key) A parameter that determines the operation of a cryptographic function, such as 1. The transformation from plain text

41、to cipher text and/or vice versa, 2. The generation of keying material, 3. A digital signature computation or validation, 4. The agreement upon a shared secret. 4.13 Cryptographically-strong A mechanism is said to be cryptographically strong when it has an assessed strength against an attack by an a

42、dversary that provides at least one ASC X9 Approved security strength. 4.14 Cycle A single complete execution of a periodically repeated phenomenon; a periodically repeated sequence of events. 4.15 Deterministic Algorithm An algorithm that, given the same inputs, always produces the same outputs. AN

43、S X9.92, Part 1-2006 4 Copyright American National Standards Institute Provided by IHS under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 4.16 Deterministic Processing Processing that can be performed by one or more deter

44、ministic algorithms. 4.17 Deterministic Random Bit Generator (DRBG) An RBG that uses a deterministic algorithm to produce a pseudorandom sequence of bits from a secret initial value called a seed, along with other possible inputs. A DRBG is also called a Pseudorandom Number (or Bit) Generator. 4.18

45、DRBG Boundary A conceptual boundary that is used to explain the operations of a DRBG and its interaction with and relation to other processes. 4.19 Digital Signature A cryptographic transformation of data, which, when associated with a data unit, may provide the services of: (a) Origin authenticatio

46、n, (b) Data integrity, and (c) Signer non-repudiation. 4.20 Enhanced NRBG An Enhanced NRBG relies on the Entropy Source and an Approved DRBG for its security; contrast with a Basic NRBG. 4.21 Entropy The entropy of a random variable X is a mathematical measure of the amount of information provided b

47、y an observation of X. As such, entropy is always relative to an observer and his or her knowledge prior to an observation. See min-entropy. 4.22 Entropy Assessment Component The component of an Entropy Source that produces a conservative estimate of the amount of entropy present in Entropy Source o

48、utputs. 4.23 Entropy Input Process The input to an RBG of a string of bits that contains a certain amount of entropy; that is, the entropy input is digitized and is assessed. For an NRBG, this is obtained from an ANS X9.82, Part 1-2006 5Copyright American National Standards Institute Provided by IHS

49、 under license with ANSI Not for ResaleNo reproduction or networking permitted without license from IHS-,-,-ANS X9.82, Part 1-2006 Entropy Source. For a DRBG, this is included in the seed material, some of which is (ultimately) obtained from an Entropy Source. 4.24 Entropy Rate The rate of production of bits containi