Softpanorama
May the source be with you, but remember the KISS principle ;-)

Contents Bulletin Scripting in shell and Perl Network troubleshooting History Humor

Random Generators

News

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.

Top updates

Shop Amazon Cyber Monday Deals Week
Google Search

Old News ;-)

Contents Fundamentals of Computing Leonid A. Levin

5.4 Pseudo-randomness.

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 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 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

Construction of a pseudo-random generator from any one-way function - Hastad, Impagliazzo, Levin, Luby (ResearchIndex)

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)

Randomness for crypto

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)


Recommended Links

Softpanorama Top Visited

Softpanorama Recommended

Hardware

Source code for generating randomness

Source code for testing randomness

Hardware for generating randomness

Source code to other useful crypto modules

Miscellaneous

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.

Referrence and FAQs

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.

 

Tutorials

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]

Linear Congruence Generators.




Etc

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 in our efforts to advance understanding of environmental, political, human rights, economic, democracy, scientific, and social justice issues, etc. We believe this constitutes a 'fair use' of any such copyrighted material as provided for in section 107 of the US Copyright Law. In accordance with Title 17 U.S.C. Section 107, the material on this site is distributed without profit exclusivly for research and educational purposes.   If you wish to use copyrighted material from this site for purposes of your own that go beyond 'fair use', you must obtain permission from the copyright owner.

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 quotesSomerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose BierceBernard 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 DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting 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-MonthHow 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


Copyright © 1996-2014 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.

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 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