ANSI ASC X9 X9.82-1-2006 Random Number Generation Part 1 Overview and Basic Principles.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 (R2013)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

4、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 Cryptographic 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 Flippin

5、g 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 Neumann 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.

6、4 Types of Random Bit Generators 20 7.4.1 Non-deterministic Random Bit Generator (NRBG) 21 7.4.2 Deterministic Random Bit Generator (DRBG) 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 Stre

7、ngths 23 8.3 Entropy and Min-Entropy . 24 8.4 Backtracking Resistance and Prediction Resistance 25 8.5 Indistinguishability Versus Unpredictability. 26 8.6 Prediction Resistance and Backtracking Resistance Considerations . 27 8.7 Desired RBG Output Properties. 28 8.8 Desired RBG Operational Properti

8、es. 29 ASC X9, Inc. 2006 All rights reservedii 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 Complex Discard Method. 31 9.2.3 The Simp

9、le 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 Considerations 36 A.1 Attack Model . 36

10、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 41 Annex B (Informative) Bibliograph

11、y . 43 Figures Figure 1: Random Bit Generation Functional Model 18 Figure 2: Sequence of DRGB States 26ASC X9, Inc. 2006 All rights reserved iiiANS X9.82, Part 1-2006 Foreword The Accredited Standards Committee on Financial Services (ANSI X9) has developed several cryptographic standards to protect

12、financial information. Many of these standards require the use of Random Number Generators to 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 wh

13、en other ASC standards require the use of random numbers for cryptographic purposes. While the 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 institut

14、ion to put an overall process in place with the necessary controls to ensure that the process 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 Standar

15、d requires verification by ASC that the requirements for due process, consensus, and other criteria 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 mater

16、ially affected interests. Substantial agreement means much more than a simple majority, but not 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 vol

17、untary; their existence does not in any respect preclude anyone, whether he has approved the standards 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 a

18、nd will in no circumstances give an interpretation of any American National Standard. Moreover, 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 add

19、ressed to the secretariat or sponsor whose name appears on the title page of this Standard. CAUTION 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 withdr

20、aw this Standard no later than five years from the date of approval. ASC X9, Inc. 2006 All rights reservediv ANS X9.82, Part 1-2006 Published by Accredited Standards Committee X9 Incorporated Financial Industry standards 1212 West Street, Suite 200 Annapolis, MD 21401 USA X9 Online http:/www.x9.org

21、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 United States of America. ASC X9, Inc. 2006 All rights reserved vANS X9.82,

22、Part 1-2006 Introduction NOTE The users attention is 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 conn

23、ection therewith. The patent holder has, however, filed 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

24、 improvement or revision of this Standard are welcome. 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 t

25、he Accredited Standards Committee on Financial Services, 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,

26、Executive Director Organization Represented RepresentativeACI 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 B

27、rown Citigroup, Inc. Mike Halpern Clarke American Checks, 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

28、Technology Consortium Daniel Schutzer Hewlett Packard Larry Hines Hypercom Scott Spiker ASC X9, Inc. 2006 All rights reservedvi ANS X9.82, Part 1-2006 iStream Imaging Ken Biel IBM Corporation Todd Arnold Identrus Mack Hicks Ingenico John Spence Intuit, Inc. Jana Hocker J.P. Morgan Chase a set of rul

29、es 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 formatting, and health check functions. 4.3 Approved An X9 Approved resource is one that is either: specified as (or with

30、in) 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 an ideal random sequence even to an adversary who compromises the RBG in the future, up to the claimed security streng

31、th 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 complementary assurance is called Prediction Resistance. 4.5 Basic NRBG A Basic NRBG relies only upon the Entropy Source, entropy

32、 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 sample space if one bitstring (or a number) is more likely than another bitstring (or number) to be chosen. Contrast with un

33、biased. 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 of the string. 4.8 Block Cipher A symmetric key cryptographic algorithm that transforms a block of information at a time

34、 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 3ANS X9.82, Part 1-2006 4.9 Conditioning A method for removing bias. 4.10 Consuming Application An application that uses random numbers or ran

35、dom bits obtained 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

36、input that 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 p

37、lain text 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 atta

38、ck by an adversary 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 o

39、utputs. ANS X9.92, Part 1-2006 4 ANS X9.82, Part 1-2006 4.16 Deterministic Processing Processing that can be performed by one or more deterministic algorithms. 4.17 Deterministic Random Bit Generator (DRBG) An RBG that uses a deterministic algorithm to produce a pseudorandom sequence of bits from a

40、secret initial value called a seed, along with other possible inputs. A DRBG is also called a Pseudorandom Number (or Bit) Generator. 4.18 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 Signa

41、ture A cryptographic transformation of data, which, when associated with a data unit, may provide the services of: (a) Origin authentication, (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; co

42、ntrast with a Basic NRBG. 4.21 Entropy The entropy of a random variable X is a mathematical measure of the amount of information provided by 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 Assessm

43、ent Component The component of an Entropy Source that produces a conservative estimate of the amount of entropy present in Entropy Source outputs. 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

44、 is assessed. For an NRBG, this is obtained from an ANS X9.82, Part 1-2006 5ANS 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 containing an assessed

45、 amount of entropy from an Entropy Source divided by the total number of bits produced. This will be a value between zero (no entropy) and one (full entropy). 4.25 Entropy Source A major component of the RBG functional model that contains a source of randomness such as thermal noise or hard drive se

46、ek times, along with digitization, entropy assessment, optional conditioning, and health tests. 4.26 Equivalent Process Two processes are equivalent if, when the same values are input to each process, the same output is produced. 4.27 Full entropy Each bit of a bitstring with full entropy is unpredi

47、ctable (with a uniform distribution) and independent of every other bit of that bitstring. 4.28 Hash Function A (mathematical) function that maps values from a large (possibly very large) domain into a smaller range. See the definition for a cryptographic hash function for a special type of hash fun

48、ction. 4.29 Health Tests The parts of an RBG that monitor the RBG components to ensure they are continuing to function properly. 4.30 Ideal (Binary) Random Sequence A sequence of binary random numbers from an idealized Entropy Source with two possible output values, such that each output is unpredic

49、table, unbiased and independent. 4.31 Implementation An implementation of an RBG is a cryptographic device or portion of a cryptographic device that is a physical embodiment of the RBG design, for example, some code running on a computing platform. ANS X9.92, Part 1-2006 6 ANS X9.82, Part 1-2006 4.32 Implementation Testing Testing to help ensure that an implementation of a standard conforms to the specifications of that standard. See Validation Testing for a specific type of Implementation Testing. 4.33 Initialization Vector (IV) A number used as a starting point for the c