Softpanorama 

Contents  Bulletin  Scripting in shell and Perl  Network troubleshooting  History  Humor 
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 "highquality" 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 Pseudorandom 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 AESbased generator will be efficient and will satisfy most practical requirements, but the RSAbased 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.
 
Bulletin  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 pseudorandom strings from a short seed. Such methods were justified in [Blum Micali], [Yao]:
First, take any oneway permutation (see sec. 5.5) with a hardcore bit (see below) which is easy to compute from x,p, but infeasible to guess from with any noticeable correlation.
Then take a random seed and 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 oneway F, and no pseudorandom generators could exist.
By Kolmogorov's standards, pseudorandom 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 pseudorandom string will be as good as a truly random one if they can't be distinguished in feasible time. Such generators we call perfect.
PseudoRandom Generators, a HighLevel SurveyinProgress
This internet document contains miscellaneous thoughts on pseudorandom number generation. It is a "surveyinprogress" of the field. Indeed, there isn't a single field of science attached to pseudorandom 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]TwoStage
Random Generator (TSRG); AttackOriented Design and ...
File Format: PDF/Adobe Acrobat

View as HTML septembre 2002 S ´Ecurit´e des Communications sur Internet
SECI02 TwoStage Random Generator (TSRG); AttackOriented
Design and Implementation Gamal ...
www.lsv.enscachan.fr/~goubault/SECI02/ Final/actesseci02/pdf/003ghussein.pdf

Similar pages
Abstract: There are many natural examples of conjectured oneway 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 pseudorandom generator from any oneway function. Our constructions make extensive use of hashing to extract and smooth entropy from a oneway 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 cryptostrength 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)
Softpanorama Top Visited 
Project Cryptography, TCS, Nada, KTH Random Generators in Cryptography
One of the most useful cryptographic primitives is the pseudorandom 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 oneway functions with certain additional properties. For instance if the oneway function in addition is a permutation, the construction is very simple. (A oneway 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 oneway function used (except for the onewayness 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 pseudorandom generator based on any oneway function.
Bit Security
In constructing pseudorandom 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 hardcore 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 coinflip. Note that this implies that f must be a oneway 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 hardware 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 205214.
 postscript
 A Pseudorandom Generator from any oneway function
 J. Håstad, R. Imagliazzo, L. Levin, and M. Luby
 SIAM Journal on Computing, Vol 28, 1999, pp 13641396.
 postscript
 The Security of Individual RSA Bits
 J. Håstad and M. Näslund
 Proceedings, FOCS '98, pp 510519, IEEE.
 A more complete version of this is contained in Mats Näslund's thesis found below.
 Bit Extraction, HardCore 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 115, Springer Verlag.
 PseudoRandom Generators under Uniform Assumptions
 J. Håstad
 Proceedings, 22nd STOC, 1990, pp 395404.
 The Discrete Logarithm Modulo a Composite Hides O(n) Bits
 J. Håstad, A. W. Schrift, and A. Shamir
 JCSS 47 1993, pp. 376403
 Universal Hash Functions & Hard Core Bits
 M. Näslund
 Proceedings, EUROCRYPT '95, LNCS 921, pp 356366, Springer Verlag
 All Bits in ax+b mod p are Hard
 M. Näslund
 Proceedings, CRYPT0 '96. LNCS 1109, pp 114128, 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 pseudorandom number generation. A pseudorandom 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 pseudorandom stream), the pseudorandom number generator generates a different pseudorandom sequence. With a relatively small random seed a pseudorandom number generator can produce a long apparently random string. Pseudorandom number generators are often based on cryptographic functions like block ciphers or stream ciphers. For instance, iterated DES encryption starting with a 56bit seed produces a pseudorandom sequence. 
4.1.2.2 How does one find random numbers for keys? Whether using a secretkey cryptosystem or a publickey 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 addin boards for this purpose. Another idea is to use physical movements of the computer user, such as interkey 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 negligiblecost 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 pseudorandom number generator fed by a random seed. The primary difference between random and pseudorandom numbers is that pseudorandom numbers are necessarily periodic whereas truly random numbers are not. Since pseudorandom 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 pseudorandom data. The seed must be sufficiently variable to deter attacks based on trying all possible seeds. It is not sufficient for a pseudorandom 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 Pseudorandom 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 pseudorandom 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 pseudorandom 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:
x_{n+1} = (k*x_{n} + 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 = x_{0}. Each successive term is transformed into the next. The pseudorandom terms are in the range from 1 to m1. To get (moreorless) 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 m1 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 m1 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 16bit integers, and so has a maximum possible cycle length of 2^{16} = 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 32bit integers and used the fact that 2^{31}1 is a prime. The multiplier commonly used (starting in 1969) was 7^{5} = 16807 and the constant a was taken to be zero. This generator is quite efficient, and has a cycle length of 2^{31}  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 = 2^{31}  1 and k = 16807 above as ``adequate'', but he has suggestions for better values, such as:
m  k 

2^{31}249  40692 
2^{31}1  48271 
2^{31}1  62089911 
2^{32}  69069 
2^{48}  31167285 
2^{64}1  6364136223846793005 
Knuth suggests various generators, including one that combines the first two table entries above:
x_{n+1} = 48271*x_{n} mod (2^{31}  1), y_{n+1} = 40692*y_{n} mod (2^{31}  249), z_{n} = (x_{n}  y_{n}) mod (2^{31}  1),
where independent seeds are needed for x_{0} and y_{0}, and the sequence of the z_{n} make up the output random numbers. The period is nearly the square of the component generators. Knuth also recommends:
x_{n} = (271828183*x_{n1}  314159269*x_{n2}) mod (2^{31}  1),
which has very good performance and whose period is the square of m. Of course two independent seeds x_{0} and x_{1} are needed to start the sequence off with x_{2}.
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 pseudorandom 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 AESbased generator will be efficient and will satisfy most practical requirements, but the RSAbased 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 ITrelated 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) ObjectOriented 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 (19502000): 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 19872006 : 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 ManMonth : 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 Editorrelated Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPLrelated 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 : Perlrelated 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 : Assemblerrelated Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor
Copyright © 19962014 by Dr. Nikolai Bezroukov. www.softpanorama.org was created as a service to the UN Sustainable Development Networking Programme (SDNP) in the author free time. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Site uses AdSense so you need to be aware of Google privacy policy. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine. 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 make a contribution, supporting hosting of this site with different providers to distribute and speed up access. Currently there are two functional mirrors: softpanorama.info (the fastest) and softpanorama.net. 
Disclaimer:
The statements, views and opinions presented on this web page are those of the author and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.
Last modified: August 05, 2013