|
|
Home | Switchboard | Unix Administration | Red Hat | TCP/IP Networks | Neoliberalism | Toxic Managers |
| (slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and bastardization of classic Unix | |||||||
| See Also | Recommended Books | Recommended Links | Tutorials | Reference and FAQs | Recommended Papers | |
| Symmetric Crypto | Public Crypto | Digital signatures | Certificates | Compression and security | Digital Code Signing | |
| Usenet | Magazines | eBooks | University Courses | History | Humor | Etc |
|
|
Random generator which is one of the classic themes in algorithms (see Volume 2 of TAOCP) is also useful cryptographic device. Generally pseudorandom generation is a rather boring chapter in Algorithms Theory and even with a very interesting discussion of the subject in TAOCP its difficult to keep students attention on the subject. This connection with crypto makes the subject more fascinating and suggests a lot of projects that students might find interesting.
|
|
Pseudorandom generator is a function that deterministically expands a short random seed to a longer, "random looking'' string. Random looking means that no probabilistic polynomial time algorithm can distinguish between true random bits and the output of the generator. Basically, the best such an algorithm can do is to "guess" the source of it's given input.
That means that any "high-quality" pseudorandom generator can probably be used as a one time pad. In this case the key consists of pair (seed, offset), where seed is the initialization value for the pseudorandom generator and offset is the number of values one need to skip before starting using the sequence as a proxy to one time pad (you need to keep the initial state of the random generator secret.). I am wondering if using DES as a pseudorandom generator and then encoding the stream using DEC in a regular way (but with the second key) will be as secure as Triple DES or not.
But the key word here is "high quality" that simply means "cryptographically secure". Here is relevant quote from The Laws of Cryptography Pseudo-random Number Generation :
However, even generators of high quality are mostly not usable in cryptography. For example, given several successive numbers of a linear congruence generator, it is possible to compute the modulus and the multiplier with reasonable efficiency. One could make the generator more complex in order to resist this attack, but there would still be no proof or assurance of the difficulty of ``reverse engineering'' the generator. Instead, if generators are needed in cryptographic applications, one is usually created using a conventional cipher such as the Advanced Encryption Standard or using a public key cipher such as RSA or one of its variants. The AES-based generator will be efficient and will satisfy most practical requirements, but the RSA-based systems, while extremely slow compared to the others, have a very strong property of being cryptographically secure, a term that means the generator will pass all possible efficient statistical tests. These matters will be defined and discussed in the next chapter.
It might be that "cryptographically secure" pseudorandom generators are preferable in other applications too.
|
|
Switchboard | ||||
| Latest | |||||
| Past week | |||||
| Past month | |||||
Contents Fundamentals of Computing Leonid A. Levin
The above definition of randomness is very robust, if not practical. True random generators are rarely used in computing. The problem is not that making a true random generator is impossible: we just saw efficient ways to perfect the distributions of biased random sources. The reason lies in many extra benefits provided by pseudorandom generators. E.g., when experimenting with, debugging, or using a program one often needs to repeat the exact same sequence. With a truly random generator, one actually has to record all its outcomes: long and costly. The alternative is to generate pseudo-random strings from a short seed. Such methods were justified in [Blum Micali], [Yao]:
First, take any one-way permutation
(see sec. 5.5) with a hard-core bit (see below)
which is easy to compute from x,p, but infeasible to guess from
with any noticeable correlation.
Then take a random seedand Repeat: (
).
We will see how distinguishing outputs S of this generator from strings of coin flips would imply a fast inverting of F (believed impossible).
But if P=NP (a famous open problem), no one-way F, and no pseudorandom generators could exist.
By Kolmogorov's standards, pseudo-random strings are not random: let G be the generator; s be the seed,
, and
. Then
, so this violates Kolmogorov's definition. We can distinguish between truly and pseudo- random strings by simply trying all short seeds. However this takes time exponential in the seed length. Realistically, a pseudo-random string will be as good as a truly random one if they can't be distinguished in feasible time. Such generators we call perfect.
Pseudo-Random Generators, a High-Level Survey-in-Progress
This internet document contains miscellaneous thoughts on pseudo-random number generation. It is a "survey-in-progress" of the field. Indeed, there isn't a single field of science attached to pseudo-random generators, and this document originality might be to shed light on this topic from various angles in a single communication.
For genuine survey articles, see [6] and [15], which are respectively from the computer simulation field and cryptography. Interesting Internet resources on this topic includes the PLab project, a server on the theory and practice of random number generation, maintained by a team of mathematicians and computer scientists from the University of Salzburg.
[PDF]Two-Stage
Random Generator (TSRG); Attack-Oriented Design and ...
File Format: PDF/Adobe Acrobat
-
View as HTML septembre 2002 S ´Ecurit´e des Communications sur Internet
SECI02 Two-Stage Random Generator (TSRG); Attack-Oriented
Design and Implementation Gamal ...
www.lsv.ens-cachan.fr/~goubault/SECI-02/ Final/actes-seci02/pdf/003-ghussein.pdf
-
Similar pages
Abstract: There are many natural examples of conjectured one-way functions, whereas pseudorandom generators have a number of important applications, including the construction of a private key cryptosystem that is provably secure. We show how to construct a pseudo-random generator from any one-way function. Our constructions make extensive use of hashing to extract and smooth entropy from a one-way function. 1 Introduction One of the basic primitives in cryptography and other areas of computer science... (Update)
This page lists online resources for collecting and processing crypto-strength randomness. See this paper for a motivating example of why this is important to get right.
Randomness, Pseudorandomness, and its Applications to Cryptography (ResearchIndex)
Abstract: Introduction What does it mean for something to be random? What is a random number? Is 2 a random number? If one has a truly random number, and then proceeds to show it to everyone in the world and use it in every application, does it remain a random number? Intuitively, we all have a feel for performing some sort of action "at random". It is natural to think of choosing something "randomly " by selecting it out of a set of objects without any indication as to which object is chosen. As a... (Update)
Google matched content |
Project Cryptography, TCS, Nada, KTH Random Generators in Cryptography
One of the most useful cryptographic primitives is the pseudo-random generator. This is a function that deterministically expands a short random seed to a longer, random ``looking'' string. Random looking means that no probabilistic polynomial time algorithm can distinguish between true random bits and the output of the generator. Basically, the best such an algorithm can do is to "guess" the source of it's given input.
There are several known simple constructions of such generators, based on the existence of so called one-way functions with certain additional properties. For instance if the one-way function in addition is a permutation, the construction is very simple. (A one-way function is intuitively a function easy to compute, but hard to invert.)
In fact, it is known from papers by Imagliazzo, Levin, and Luby and by Håstad (see below) that we can remove all assumptions on the one-way function used (except for the one-wayness of course). However removing these assumptions greatly increases the complexity of the construction, or equivalently, lowers the provable "randomness" of the generator for a given length of the seed. Hence, the main goal of the research is to give a more efficient construction of a pseudo-random generator based on any one-way function.
Bit Security
In constructing pseudo-random generators one needs to extract extra "random" bits since the output of the generator must be longer than the seed. For this purpose, one can use a so called hard core predicate. In analogy to the above definition of a pseudo random generator, we say that a set of boolean functions, H, is a hard-core predicate for the function f, if no probabilistic polynomial time algorithm can distinguish between (f(x),h(x)) and (f(x),b) where b is a true random bit, say produced by an unbiased coin-flip. Note that this implies that f must be a one-way function. There are a few examples of such hard core predicates, see e.g. the papers by Näslund below.
A related problem is to study the security of individual bits in an encrypted message. Although an encryption scheme (hopefully) has the property that it is hard to retrieve the entire message, the system may still leak partial information. For instance, the enemy might be able to deduce that "the encrypted message is an odd integer", and this may be bad enough. There are several results of this type, e.g. see Håstad, Schrift, and Shamir below.
Digital Cash Systems
The objective here is to replace existing payment mechanisms; cash and credit cards, by a system that preserves the anonymity of a cash payment and has flexibility and simplicity of the credit card. Of course, the security for all parties (banks, credit card companies, shops and users) should also be preserved to avoid frauds, counterfeiting etc. Also, the system should preferably be open, i.e. no secret algorithms or special hard-ware should be needed.
Recent publications
- On the complexity of interactive proof with bounded communication
- O. Goldreich, J. Håstad,
- Information processing letters, Vol.~67 (4), 1998, pp 205--214.
- postscript
- A Pseudorandom Generator from any one-way function
- J. Håstad, R. Imagliazzo, L. Levin, and M. Luby
- SIAM Journal on Computing, Vol 28, 1999, pp 1364--1396.
- postscript
- The Security of Individual RSA Bits
- J. Håstad and M. Näslund
- Proceedings, FOCS '98, pp 510-519, IEEE.
- A more complete version of this is contained in Mats Näslund's thesis found below.
- Bit Extraction, Hard-Core Predicates, and the Bit Security of RSA
- M. Näslund
- Ph.D. Thesis, Nada, October, 1998
- PDF.
- The Complexity of Computing Hard Core Predicates
- M. Goldmann and M. Näslund
- Proceedings, CRYPT0 '97. LNCS 1294, pp 1-15, Springer Verlag.
- Pseudo-Random Generators under Uniform Assumptions
- J. Håstad
- Proceedings, 22nd STOC, 1990, pp 395-404.
- The Discrete Logarithm Modulo a Composite Hides O(n) Bits
- J. Håstad, A. W. Schrift, and A. Shamir
- JCSS 47 1993, pp. 376-403
- Universal Hash Functions & Hard Core Bits
- M. Näslund
- Proceedings, EUROCRYPT '95, LNCS 921, pp 356-366, Springer Verlag
- All Bits in ax+b mod p are Hard
- M. Näslund
- Proceedings, CRYPT0 '96. LNCS 1109, pp 114-128, Springer Verlag.
RFC 1750: randomness recommendations
Terry Ritter's very extensive archive of Usenet posts on true randomness
RSA Faq:
|
2.5.2 What
is random number generation?
Random number generation is used in a wide variety of cryptographic operations, such as key generation and challenge/response protocols. A random number generator is a function that outputs a sequence of 0s and 1s such that at any point, the next bit cannot be predicted based on the previous bits. However, true random number generation is difficult to do on a computer, since computers are deterministic devices. Thus, if the same random generator is run twice, identical results are received. True random number generators are in use, but they can be difficult to build. They typically take input from something in the physical world, such as the rate of neutron emission from a radioactive substance or a user's idle mouse movements. Because of these difficulties, random number generation on a computer is usually only pseudo-random number generation. A pseudo-random number generator produces a sequence of bits that has a random looking distribution. With each different seed (a typically random stream of bits used to generate a usually longer pseudo-random stream), the pseudo-random number generator generates a different pseudo-random sequence. With a relatively small random seed a pseudo-random number generator can produce a long apparently random string. Pseudo-random number generators are often based on cryptographic functions like block ciphers or stream ciphers. For instance, iterated DES encryption starting with a 56-bit seed produces a pseudo-random sequence. |
|
4.1.2.2 How does one find random numbers for keys? Whether using a secret-key cryptosystem or a public-key cryptosystem, one needs a good source of random numbers for key generation. The main features of a good source are that it produces numbers that are unknown and unpredictable by potential adversaries. Random numbers obtained from a physical process are in principle the best, since many physical processes appear truly random. One could use a hardware device, such as a noisy diode; some are sold commercially on computer add-in boards for this purpose. Another idea is to use physical movements of the computer user, such as inter-key stroke timings measured in microseconds. Techniques using the spinning of disks to generate random data are not truly random, as the movement of the disk platter cannot be considered truly random. A negligible-cost alternative is available; Davis et al. designed a random number generator based on the variation of a disk drive motor's speed [DIP94]. This variation is caused by air turbulence, which has been shown to be unpredictable. By whichever method they are generated, the random numbers may still contain some correlation, thus preventing sufficient statistical randomness. Therefore, it is best to run them through a good hash function (see Question 2.1.6) before actually using them [ECS94]. Another approach is to use a pseudo-random number generator fed by a random seed. The primary difference between random and pseudo-random numbers is that pseudo-random numbers are necessarily periodic whereas truly random numbers are not. Since pseudo-random number generators are deterministic algorithms, it is important to find one that is cryptographically secure and also to use a good random seed; the generator effectively acts as an "expander" from the seed to a larger amount of pseudo-random data. The seed must be sufficiently variable to deter attacks based on trying all possible seeds. It is not sufficient for a pseudo-random number generator just to pass a variety of statistical tests, as described in Knuth [Knu81] and elsewhere, because the output of such generators may still be predictable. Rather, it must be computationally infeasible for an attacker to determine any bit of the output sequence, even if all the others are known, with probability better than 1/2. Blum and Micali's generator based on the discrete logarithm problem [BM84] satisfies this stronger definition, assuming that computing discrete logarithm is difficult (see Question 2.3.7). Other generators perhaps based on DES (see Section 3.2) or a hash function (see Question 2.1.6) can also be considered to satisfy this definition, under reasonable assumptions. A summary of methods for generating random numbers in software can be found in [Mat96]. Note that one does not need random numbers to determine the public and private exponents in RSA. After generating the primes, and hence the modulus (see Question 3.1.1), one can simply choose an arbitrary value (subject to the standard constraints) for the public exponent, which then determines the private exponent. |
The Laws of Cryptography Pseudo-random Number Generation Copyright © 2002 by Neal R. Wagner. All rights reserved.
... ... ...
Law RNG3: One should not use a random method to generate random numbers. [Donald Knuth]
An early suggested source of pseudo-random numbers was an equation which was much later to become a part of modern ``chaos'' theory. A later chapter describes a generator derived from this equation.
Another early idea for a source of random numbers was to use the bits or digits in the exapnsion of a transcendental number such as pi, the ratio of the circumference of a circle to its diameter.
3.14159 26535 89793 23846 26433 83279 50288 41972 ... (in decimal) 3.11037 55242 10264 30215 14230 63050 56006 70163 21122 ... (in octal)
It has long been conjectured that this is a very good source of pseudo-random numbers, a conjecture that has still not been proved. In 1852 an English mathematician named William Shanks published 527 digits of pi, and then in 1873 another 180 digits for a total of 707. These numbers were studied statistically, and an interesting excess of the number 7 was observed in the last 180 digits. In 1945 von Neumann wanted to study statistical properties of the sequence of digits and used one of the early computers to calculate several thousand. Fortunately for Shanks his triumph was not spoiled during his lifetime, but his last 180 digits were in error and his last 20 years of effort were wasted. Also there was no ``excess of 7s''. The number pi has now been calculated to many billions of places, although the calculation of its digits or bits is too hard to provide a good source of random numbers. The later digits are harder to calculate than earlier ones, although a recent clever algorithm allows calculation of the nth binary (or hexadecimal) digit without calculating the previous ones.
Later work focused on a particularly simple approach using a congruence equation.
Linear Congruence Generators.
This approach uses a linear congruence equation of the form:
xn+1 = (k*xn + a) mod m
where all terms are integers, k is the multiplier, a (often taken to be 0) is the increment, and m is the modulus. An initial seed is s = x0. Each successive term is transformed into the next. The pseudo-random terms are in the range from 1 to m-1. To get (more-or-less) uniformly distributed floating point numbers between 0 and 1, just do a floating point division by m. Assuming that a = 0, the quality of the numbers produced depends heavily on k and m.
This type of generator can produce at most m-1 different numbers before it starts to repeat. To get this behavior, one can start with a prime number for m and use a generator for k so that all m-1 numbers will be produced in a repeating cycle, starting with whatever the seed s is.
The old generator provided by the C standard library uses 16-bit integers, and so has a maximum possible cycle length of 216 = 65237 -- a ridiculously small cycle, making the generator usless except for toy applications. By far the most common generator of the past was implemented on hardware with 32-bit integers and used the fact that 231-1 is a prime. The multiplier commonly used (starting in 1969) was 75 = 16807 and the constant a was taken to be zero. This generator is quite efficient, and has a cycle length of 231 - 2. The multiplier was chosen so that various statistical properties of the sequence would be similar to the results for a true random sequence. In the 1970s when I first started using this sequence the cycle length seemed quite long -- now it seems quite short since I frequently run experiments with hundreds of billions of trials.
Knuth in his chapter on conventional random number generators approves the values m = 231 - 1 and k = 16807 above as ``adequate'', but he has suggestions for better values, such as:
| m | k |
|---|---|
| 231-249 | 40692 |
| 231-1 | 48271 |
| 231-1 | 62089911 |
| 232 | 69069 |
| 248 | 31167285 |
| 264-1 | 6364136223846793005 |
Knuth suggests various generators, including one that combines the first two table entries above:
xn+1 = 48271*xn mod (231 - 1), yn+1 = 40692*yn mod (231 - 249), zn = (xn - yn) mod (231 - 1),
where independent seeds are needed for x0 and y0, and the sequence of the zn make up the output random numbers. The period is nearly the square of the component generators. Knuth also recommends:
xn = (271828183*xn-1 - 314159269*xn-2) mod (231 - 1),
which has very good performance and whose period is the square of m. Of course two independent seeds x0 and x1 are needed to start the sequence off with x2.
Commentary.
Knuth has other suggestions for efficient random number generators of high quality, where ``quality'' is measured by a variety of statistical tests that compare the output of the pseudo-random generator with true random numbers. If for a given test the comparison says the two sets of numbers look the same, then one says the generator ``passes'' this particular test. A generator that passes all the popular tests that people can devise is of high quality.
However, even generators of high quality are mostly not usable in cryptography. For example, given several successive numbers of a linear congruence generator, it is possible to compute the modulus and the multiplier with reasonable efficiency. One could make the generator more complex in order to resist this attack, but there would still be no proof or assurance of the difficulty of ``reverse engineering'' the generator. Instead, if generators are needed in cryptographic applications, one is usually created using a conventional cipher such as the Advanced Encryption Standard or using a public key cipher such as RSA or one of its variants. The AES-based generator will be efficient and will satisfy most practical requirements, but the RSA-based systems, while extremely slow compared to the others, have a very strong property of being cryptographically secure, a term that means the generator will pass all possible efficient statistical tests. These matters will be defined and discussed in the next chapter.
Society
Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers : Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism : The Iron Law of Oligarchy : Libertarian Philosophy
Quotes
War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda : SE quotes : Language Design and Programming Quotes : Random IT-related quotes : Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Bernard Shaw : Mark Twain Quotes
Bulletin:
Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 : Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law
History:
Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds : Larry Wall : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS : Programming Languages History : PL/1 : Simula 67 : C : History of GCC development : Scripting Languages : Perl history : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history
Classic books:
The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month : How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite
Most popular humor pages:
Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor
The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D
Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.
This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...
|
|
You can use PayPal to to buy a cup of coffee for authors of this site |
Disclaimer:
The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.
Last modified: March 12, 2019
