Difference between revisions of "Pseudorandom number generators"

From Simulace.info
Jump to: navigation, search
(→‎Solution)
 
(19 intermediate revisions by one other user not shown)
Line 25: Line 25:
  
 
'''Unbiased - Uniform distribution'''<br/>
 
'''Unbiased - Uniform distribution'''<br/>
−
By definition of the word unbiased this property states that PRG is showing no prejudice for or against something. In PRG language this means that all values of whatever sample size is collected are equiprobable.
+
By definition of the word unbiased this property states that PRG is showing no prejudice for or against something. In PRG language this means that all values of whatever sample size is collected are equiprobable. This property ensures the independence of the generator and its stability against certain types of attacks.
−
<br/>'''What happens when this property is not guaranteed:'''<br/>
 
−
One of the measures of how successfully can adversary attack
 
  
  
 
'''Unpredictable - Independence'''<br/>
 
'''Unpredictable - Independence'''<br/>
−
It is impossible to predict what the next output will be, given all the previous outputs, but not the internal state
+
It is impossible to predict what the next output will be, given all the previous outputs, but not the internal state. If this is not guaranteed then basically anyone can pose as a generator. This is used for example in the man in the middle attack.
−
<br/>'''What happens when this property is not guaranteed:'''<br/>
 
−
<TODO>
 
  
  
 
'''Unreproducible'''<br/>
 
'''Unreproducible'''<br/>
−
Two of the same generators, given the same starting conditions, will produce different outputs
+
Two of the same generators, given the same starting conditions, will produce different outputs. Certain types of spoofing attacks try to reproduce subset of real production environment in order to exploit the lack of security in respect with this condition.
−
<br/>'''What happens when this property is not guaranteed:'''<br/>
 
−
<TODO>
 
  
  
 
'''Long period'''<br/>
 
'''Long period'''<br/>
−
The generator should be of long period
+
The generator should be of long period because this property directly influences the randomness of generated outputs. This is crucial for example for simulations since they are conducted in order to simulate dynamic behavior and states of an environment not only the cyclic stages of an environment.
−
<br/>'''What happens when this property is not guaranteed:'''<br/>
 
−
<TODO>
 
  
  
 
'''Fast computation'''<br/>
 
'''Fast computation'''<br/>
−
The generator should be reasonably fast
+
The generator should be reasonably fast. It is always a good idea to take care about the users of the generator since they might be in a quite constrained environment either by hardware specifications or by expected time performance.
−
<br/>'''What happens when this property is not guaranteed:'''<br/>
 
−
<TODO>
 
  
  
 
'''Security'''<br/>
 
'''Security'''<br/>
−
The generator should be secured
+
The generator should be secured. Basically, security of the generator ensures that no one can break the generator in reasonable time either by the brute-force approach or by more clever ones. If there is no polynomial-time algorithm that on the first <math>m</math> output sequence can predict the <math>{m + 1}^{th}</math> bit with probability greater than 0.5 we consider the generator to be secured.
−
<br/>'''What happens when this property is not guaranteed:'''<br/>
 
−
<TODO>
 
  
 
== Construction of simple PRG ==
 
== Construction of simple PRG ==
Line 169: Line 157:
  
 
'''Example:'''<br/>
 
'''Example:'''<br/>
−
<todo>
+
Following example shows how to compute first five output values for specified LCG:
 +
 
 +
* <math>m = 7902</math>
 +
* <math>a = 4331</math>
 +
* <math>c = 3492</math>
 +
* <math>x_0 = 1477</math>.
 +
 
 +
{| class="wikitable"
 +
|+
 +
! <math>X_1</math> || <math>\equiv</math> || <math>4331 * X_0 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>4331 * 1477 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 7661
 +
|-
 +
! <math>X_2</math> || <math>\equiv</math> || <math>4331 * X_1 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>4331 * 7661 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 2785
 +
|-
 +
! <math>X_3</math> || <math>\equiv</math> || <math>4331 * X_2 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>4331 * 2785 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 6875
 +
|-
 +
! <math>X_4</math> || <math>\equiv</math> || <math>4331 * X_3 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>4331 * 6875 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 4381
 +
|-
 +
! <math>X_5</math> || <math>\equiv</math> || <math>4331 * X_4 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>4331 * 4381 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 4901
 +
|}
  
 
=== Multiplicative Congruential Generator ===
 
=== Multiplicative Congruential Generator ===
Line 192: Line 198:
  
 
'''Example:'''<br/>
 
'''Example:'''<br/>
−
<todo>
+
Following example shows how to compute first five output values for specified MCG:
  
−
=== Lagged Fibonacci generator ===
+
* <math>m = 5037</math>
 +
* <math>a = 3414</math>
 +
* <math>x_0 = 1739</math>.
 +
 
 +
{| class="wikitable"
 +
|+
 +
! <math>X_1</math> || <math>\equiv</math> || <math>X_0 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>1739 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 3360
 +
|-
 +
! <math>X_2</math> || <math>\equiv</math> || <math>X_1 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>3360 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 1791
 +
|-
 +
! <math>X_3</math> || <math>\equiv</math> || <math>X_2 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>1791 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 4593
 +
|-
 +
! <math>X_4</math> || <math>\equiv</math> || <math>X_3 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>4593 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 0321
 +
|-
 +
! <math>X_5</math> || <math>\equiv</math> || <math>X_4 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math> || <math>\equiv</math>  || <math>0321 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)</math>  || <math>\equiv</math> || 2865
 +
|}
 +
 
 +
=== Lagged Fibonacci Generator ===
 
{| class=infobox width=250px
 
{| class=infobox width=250px
 
|style="background:#33CC33;color:#FFFFFF"|<center>'''Advantages'''</center>
 
|style="background:#33CC33;color:#FFFFFF"|<center>'''Advantages'''</center>
Line 243: Line 266:
 
[[File:LFG_example.gif]]
 
[[File:LFG_example.gif]]
  
−
'''Example:'''<br/>
+
=== Mersenne Twister ===
−
<todo>
 
−
 
 
−
=== Mersenne twister ===
 
 
{| class=infobox width=250px
 
{| class=infobox width=250px
 
|style="background:#33CC33;color:#FFFFFF"|<center>'''Advantages'''</center>
 
|style="background:#33CC33;color:#FFFFFF"|<center>'''Advantages'''</center>
Line 273: Line 293:
  
 
[[File:MT_example.png]]
 
[[File:MT_example.png]]
−
 
−
'''Example:'''<br/>
 
−
<todo>
 
  
 
==Nonlinear methods==
 
==Nonlinear methods==
Line 313: Line 330:
  
 
[[File:BBS_example.gif]]
 
[[File:BBS_example.gif]]
−
 
−
'''Example:'''<br/>
 
−
<todo>
 
  
 
==Testing==
 
==Testing==
−
Very important contcept to ensure reliability and determine possible areas of use is testing PRGs. There are many tests for PRGs. First of all let's take a look at bacis catogories of tests.
+
Very important concept to ensure reliability and determine possible areas of use is testing PRGs. There are many tests for PRGs. First of all let's take a look at bacis catogories of tests.
  
 
=== Theoretic tests ===
 
=== Theoretic tests ===
Line 336: Line 350:
 
** This test detects periodical aspects of produced sequences. Nice application of these test on LCGs is demonstrated [http://random.mat.sbg.ac.at/tests/theory/spectral/ here]
 
** This test detects periodical aspects of produced sequences. Nice application of these test on LCGs is demonstrated [http://random.mat.sbg.ac.at/tests/theory/spectral/ here]
  
−
=== Balckbox testing ===
+
=== Blackbox testing ===
 
Sometimes adversary does not have an access to the used PRG or simply cannot determine what kind of PRG (if any) is used. In these cases adversary uses another approach and tries to determine the PRG by supplying certain groups of parameters and analysing and testing provided result sequences. Result analysis is based on finding similarities and patterns in result sets. In case of less secured PRG the adversary is able to determine just by doing that, whether they are interacting with PRG or truly random function. An adversary might be able to determine a kind of PRG or even the concrete implementation based on the randomness of gathered outputs.
 
Sometimes adversary does not have an access to the used PRG or simply cannot determine what kind of PRG (if any) is used. In these cases adversary uses another approach and tries to determine the PRG by supplying certain groups of parameters and analysing and testing provided result sequences. Result analysis is based on finding similarities and patterns in result sets. In case of less secured PRG the adversary is able to determine just by doing that, whether they are interacting with PRG or truly random function. An adversary might be able to determine a kind of PRG or even the concrete implementation based on the randomness of gathered outputs.
  
Line 380: Line 394:
 
! Ciphertext    || 13 || 36
 
! Ciphertext    || 13 || 36
 
|}
 
|}
 +
----
 +
2. Let <math>F:K \times X \rightarrow \{0, 1\}^{128}</math> be a secure PRF. I following generator G a secure PRF?
 +
 +
<math>G(k, x) = {
 +
\begin{cases}
 +
0^{128} {\hskip 1cm} \text{if  } x = 0\\
 +
F(k, x) {\hskip 0.5cm} \text{otherwise}\\
 +
\end{cases}
 +
</math>
 +
 +
* a) No, it is easy to distinguish G from a random function
 +
* b) Yes, an attack on G would also break F
 +
* c) It depends on F
 +
----
 +
3. Which required property of PRG is not fulfilled based on the following output from a generator:
 +
{| class="wikitable"
 +
|+
 +
! Input  || 235 || 803 || 186 || 597 || 931 || 235 || 274 || 727
 +
|-
 +
! Output || 345812 || 971486 || 207319 || 349183 || 729460 || 345812 || 367428 || 319708
 +
|-
 +
|}
 +
 +
* a) unbiased
 +
* b) unpredictable
 +
* c) unreproducible
 +
* d) none of the above
 +
----
 +
4. What is value of <math>X_8</math> for MCG defined as follows: <math>m = 6478</math>, <math>a = 5620</math>, and <math>x_0 = 3671</math>.
 +
 +
* a) 4572
 +
* b) 3649
 +
* c) 2892
 +
* d) 6217
 +
----
 +
5. Categorize test based on its description.
 +
 +
Birthday spacings: Choose random points on a large interval. The spacings between the points should be asymptotically exponentially distributed. The name is based on the birthday paradox.
  
 +
* a) theoretic test
 +
* b) blackbox testing
 +
----
 
=== Solution ===
 
=== Solution ===
−
# Answer: LCGINACTION
+
* '''1. Answer:''' LCGINACTION
−
* First determine first 6 outputs of the generator. Get letter codes by reversed modulo 10 addition and translate the ciphertext.
+
** First determine first 6 outputs of the generator. Get letter codes by reversed modulo 10 addition and translate the ciphertext.
 +
* '''2. Answer:''' a
 +
** When the adversary queries G at x = 0 they always get 0 and they know they are interacting with PRF and not truly random function.
 +
* '''3. Answer:''' c
 +
** Generator produced same output for two identical inputs
 +
* '''4. Answer:''' c
 +
* '''5. Answer:''' a

Latest revision as of 11:31, 19 January 2016

Random numbers are useful for a variety of purposes, such as generating data encryption keys, simulating and modeling complex phenomena and for selecting random samples from larger data sets. They have also been used aesthetically, for example in literature and music, and are of course ever popular for games and gambling. When discussing single numbers, a random number is one that is drawn from a set of possible values, each of which is equally probable, i.e., a uniform distribution. When discussing a sequence of random numbers, each number drawn must be statistically independent of the others.[1]

This chapter aims at explaining why it's hard and very important (besides interesting) to understand how to get a computer to generate proper random numbers. Since most of currently used security and encryption standards depend on random numbers, it is easy to imagine that by selecting not secured algorithms causes many aspects of our digital lives to become exposed to clever programmers and companies interested in data analysis or less legal practices (identity theft, surveillance, bank fraud and so on). One must realize that the privacy of for example all their banking activities, email communication, social networking and so on heavily depends on randomness in applied security mechanisms.

In cryptography, a pseudorandom generator (or PSG) is procedure that outputs a sequence computationally indistinguishable from truly random sequence with uniformly distributed random sequence. The prefix pseudo (from Greek ψευδής "lying, false") is used to mark something as false, fraudulent, or pretending to be something it is not. Pseudo random generators find application in many fields besides cryptography such as applied mathematics, physics and simulations. Simulations often require mechanisms producing sequences of random values. These procedures are certainly non-trivial and often require significant amounts of computational time.


Definition

A pseudorandom generator (or PRG) is a (deterministic) map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G:\{0, 1\}^l \rightarrow \{0, 1\}^n}}} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n \geq l}}} . Here Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{l}}} is the 'seed length' and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n - l \geq 0}}} is the 'stretch'. We typically think that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n \gg l}}} and that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G}}} is efficiently computable in some model. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f:\{0, 1\}^n \rightarrow \{0, 1\}}}} is any 'statistical test', we say that G 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -fools' Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f}}} is


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{|Pr[f({U_n} = 1)] - Pr[f(G({U_l})) = 1)]| \leq \epsilon}}}


where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {U_m}} denotes a uniformly random string in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\{0, 1\}^m}}} . Here the string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{U_l}}} is called the 'seed'. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{C}}} is a class of tests, we say that G 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -fools Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{C}}} ' or is an 'Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -PRG against Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{C}}} ' if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G}}} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\epsilon}}} -fools Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f}}} for every Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f \in C}}} .[2]


In other words we are trying to convince any outside party (let's call them an adversary) that sequences returned from PRG are being produced chosen at random. Adversary may use statistical test algorithms to check simultaneously outputs from PRG and uniformly random sequnces. PRGs ensure that both outputs look the same to the adversary..

Required properties

Reliable PRG should have all these properties[3]:

Unbiased - Uniform distribution
By definition of the word unbiased this property states that PRG is showing no prejudice for or against something. In PRG language this means that all values of whatever sample size is collected are equiprobable. This property ensures the independence of the generator and its stability against certain types of attacks.


Unpredictable - Independence
It is impossible to predict what the next output will be, given all the previous outputs, but not the internal state. If this is not guaranteed then basically anyone can pose as a generator. This is used for example in the man in the middle attack.


Unreproducible
Two of the same generators, given the same starting conditions, will produce different outputs. Certain types of spoofing attacks try to reproduce subset of real production environment in order to exploit the lack of security in respect with this condition.


Long period
The generator should be of long period because this property directly influences the randomness of generated outputs. This is crucial for example for simulations since they are conducted in order to simulate dynamic behavior and states of an environment not only the cyclic stages of an environment.


Fast computation
The generator should be reasonably fast. It is always a good idea to take care about the users of the generator since they might be in a quite constrained environment either by hardware specifications or by expected time performance.


Security
The generator should be secured. Basically, security of the generator ensures that no one can break the generator in reasonable time either by the brute-force approach or by more clever ones. If there is no polynomial-time algorithm that on the first Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} output sequence can predict the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {m + 1}^{th}} bit with probability greater than 0.5 we consider the generator to be secured.

Construction of simple PRG

There are many ways how to construct PRGs and one of the simplest ones is to use pseudorandom functions and expand the key. A pseudorandom function (or PRF) is any function defined over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal(K, X, Y)}}}  :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{F:K \times X \rightarrow Y}}}

where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{K}}} is key space
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{X}}} is input space
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{Y}}} is output space

such that exists efficient algorithm to evaluate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal F(k,x)}}} .[4]


On the other hand pseudorandom permutation is any function defined over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal(K, X)}}} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{E:K \times X \rightarrow X}}}

such that[4]:

  1. Exists efficient deterministic algorithm to evaluate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal E(k,x)}}}
  2. The function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal F(k,\cdot)}}} is one-to-one
  3. Exists efficient inversion algorithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{\textnormal D(k,y)}}}


Any pseudorandom permutation (or PRP) is also pseudorandom function given

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{X=Y}}}
  2. Function is efficiently invertible


So let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{F: K \times \{0, 1\}^n \rightarrow \{0, 1\}^n}}} be a PRF


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{ \begin{cases} Functions[X, Y]: \text{ all functions from X to Y}\\ S_F = {F(k, \cdot) st. k \in K} \subseteq Functions[X, Y] \end{cases} }


For PRF to be suitable for use in PRG it must be secure and therefore computationally indistinguishable from random function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f(\cdot)}}} . This situation is depicted below:


Secure prf.png


The adversary can not distinguish whether output came from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{S_F}}} or some random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f(\cdot)}}} .


If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{F}}} is secure PRF we can use key expantion to construct secure PRG defined as


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G: K \times \{0, 1\}^{nt}}}} where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{n}}} number of bits in each block
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{t}}} number of generated blocks


We get return value by using key expansion. Great advantage of using this approach is ability to employ multiple CPU cores and take advantage of parallelization (for example odd values are computed by core 1; even values are computed by core 2). Security of PRG is provided by fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{F(k, \cdot)}}} is indistinguishable from random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{f(\cdot)}}} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {{G(k) = F(k, 0) || F(k, 1) || ... || F(k, t-1)}}}

Linear methods

Linear Congruential Generator

Advantages
  • fast computation time
  • small memery requirements
  • suitable for embedded systems
  • suitable for gaming consoles (high order bits)
Disadvantages
  • low quality of randomness
  • selection from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} -dimensional space produces points positioned on lines
  • weak against the spectral test
  • big differences in the length of the period for low and high order bits

Linear Congruential Generator (or LCG) is one of the best known PRGs in the world. This generator is defined as follows

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_{n+1} \equiv \left( a X_n + c \right)~~\pmod{m}}

where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_{n}} is the sequence of pseudorandom values
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_0,\,0 \le X_0 < m} is the seed
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,\,0 < a < m} is the multiplier
  4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c,\,0 \le c < m} is the increment
  5. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m,\, 0<m } is the modulo

are integer constants that specify the generator.[5]

The range of output values is restricted since after at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} values the period starts to repeat itself (in the terms of repeating the same pattern). The most significant element in terms of the length of the period is the multiplier. Best outputs from generator with regard to the length of the period are provided given values:

  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a - 1} is divisable by all the primes that divide the multiplier
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a - 1} is multiple of number 4, when the multiplier is multiple of number 4
  • the multiplier and the increment do not have common divisor (except from 1)

An example of output exported from WolframAplha application[6]:

LCG example.png

Example:
Following example shows how to compute first five output values for specified LCG:

  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 7902}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a = 4331}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c = 3492}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_0 = 1477} .
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * X_0 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * 1477 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 7661
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_2} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * X_1 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * 7661 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 2785
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_3} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * X_2 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * 2785 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 6875
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_4} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * X_3 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * 6875 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 4381
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_5} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * X_4 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4331 * 4381 + 3492 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 4901

Multiplicative Congruential Generator

Choice of m:
Most natural choice for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} is one that equals to the capacity of a computer word.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 2^b} (binary machine), where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} is the number of bits in the computer word.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 10^d} (decimal machine), where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d} is the number of digits in the computer word.

Multiplicative Congruent Generator (or MCG) is simplified version of LCG since if c = 0 in LCG we get the MCG[5]. This generator is defined as follows:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_{n+1} \equiv a X_n ~~\pmod{m}}

where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_{n}} is the sequence of pseudorandom values
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_0,\,0 \le X_0 < m} is the seed
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a,\,0 < a < m} is the multiplier
  4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m,\, 0<m } is the modulo

An example of output (of 59-bit multiplicative congruential generator) exported from WolframAplha application[7]:

MCG59 example.png

Example:
Following example shows how to compute first five output values for specified MCG:

  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 5037}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a = 3414}
  • Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_0 = 1739} .
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_0 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1739 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 3360
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_2} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_1 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3360 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 1791
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_3} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_2 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1791 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 4593
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_4} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_3 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 4593 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 0321
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_5} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_4 * 3414 {\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0321 * 3414{\hskip 0.5cm} (mod{\hskip 0.15cm}7902)} Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \equiv} 2865

Lagged Fibonacci Generator

Advantages
  • fast computation time
  • efficient implementation
  • long period
  • acceptable performance on standard statistical tests for randomness
  • a large number of independent streams of numbers can be generated from the same initial values
Disadvantages
  • poor behavior with R(24,55) and smaller generators
  • weak against birthday spacing and generalized triple tests
  • complexity of the initialization of LFGs
  • outputs are very sensitive to initial conditions

Lagged Fibonacci generator (or LFG) is one of the fastest PRGs providing long period. LFG is defined as follows

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle LFG(p, q, \bigoplus)}

where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} is coeficient of lag, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p > q}
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} is coeficient of lag, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p > q}
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \bigoplus} binary operation such as adding or subtracting in modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} , multiplication in modulo Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} or bitwise exclusive Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle OR} (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle XOR} )

and the sequence is defined by

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_n = x_{n-p} \bigoplus x_{n-q}}


For generator to work, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} must be odd numbers. Generator stores used Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} values in a lag table. In order to achieve the maximum length of the period and fair degree of randomness parameters need to be set in the following way:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 2^b}
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} have values of powers of primitive polynomials

producing the length of the period for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle XOR} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle P = 2^p - 1} [8]


An example of an output[9]:

LFG example.gif

Mersenne Twister

Advantages
  • long period
  • passes number of tests for statistical randomness
  • passes most of the strict tests from TestU01 crush randomness tests
Disadvantages
  • not suitable for cryptography (in its native form)
  • after certain number of observations one is able to predict outputs of the future iterations
  • it takes quite long time to turn non-random initial state into sufficiently random output that passes randomness tests
  • may require LFG or LCG to do the initial seeding

Mersenne twister (or MT) is one of the modern implementations of PRGs and it provides very high quality of peudorandom numbers. It was developed by Makoto Matsumoto and Takuji Nishimura in 1997 with the aim of replacement of some known faults of older PRGs. MT is founded on a matrix linear recurrence over a finite binary field. Nowadays, the most used versions are MT with 32 and 64 bit word length. Due to optimizations applied to MT it is optimized to be used in Monte Carlo method simulaions in many fields of science.

Since the description of algorithm is quite , I would like to point the readers to this paper from George Mason University where the internal mechanics of MT are explained in detail.

An example of output (of Mersenne twister shift register generator) exported from WolframAplha application[7]:

MT example.png

Nonlinear methods

Blum Blum Shub

Advantages
  • unpredictable (passes next-bit test)
  • security is based on difficulty of factoring Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle N}
  • suitable for key generation
Disadvantages
  • slow computation times
  • uses very large numbers
  • not suitable for cipher use

Blum Blum Shub (or BBS) is PRG developed by Lenore Blum, Manuel Blum and Michael Shub in 1986. It is defined as follows:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_{n+1} = x_n^2 \hspace{0.5cm} mod M}

where:

  1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} random large prime
  2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q} random large prime
  3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} is th eproduct of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q}
  4. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_0} is the seed; usually an integer that is co-prime to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} [10]


BBS does not find application in simulations due to its running time. On the other hand due to it's security properties it is appropriate for use in cryptography.

An example of output constructed in Maple 14 (seed=10, range=1000):

BBS example.gif

Testing

Very important concept to ensure reliability and determine possible areas of use is testing PRGs. There are many tests for PRGs. First of all let's take a look at bacis catogories of tests.

Theoretic tests

These tests aim at detailed study of internal structure of a PRG, its parameters and inner workings. They are typically used when theoretical concepts of PRG are publicly known. From cryptography we know that best way to test any security concept is to assume that adversary already knows the structure and inner workings of tested concept so we rely on complexity of the math backing this concept.


These tests aim at:

  • finding logical gaps in proposed solutions
  • short comings in the ways parameters are processed
  • detail analysis and possible test covarage (in terms of the software development testing)


Examples:

  • Autocorrelation test
    • Analysis serial correlation of the members of the sequence. Very nice example and tutorial how to approach this problem is described here with simple applet for computing the autocorrelation test
  • Spectral test
    • This test detects periodical aspects of produced sequences. Nice application of these test on LCGs is demonstrated here

Blackbox testing

Sometimes adversary does not have an access to the used PRG or simply cannot determine what kind of PRG (if any) is used. In these cases adversary uses another approach and tries to determine the PRG by supplying certain groups of parameters and analysing and testing provided result sequences. Result analysis is based on finding similarities and patterns in result sets. In case of less secured PRG the adversary is able to determine just by doing that, whether they are interacting with PRG or truly random function. An adversary might be able to determine a kind of PRG or even the concrete implementation based on the randomness of gathered outputs.


These tests aim at:

  • faults in PRG inner workings
  • repeating sequences and patterns in result sequences
  • outputs of certain combination of entry parameters

References

  1. ↑ Introduction to Randomness and Random Numbers, 2012, Random.org
  2. ↑ Lecture 16: Nisan's PRG for small space, 15-855: Intensive Intro to Complexity Theory. Spring 2009, Carnegie Mellon University, USA.: page 1
  3. ↑ Xiang-Yang Li, Pseudo-random Number - Cryptography and Network Security. Illinois Institute of Technology, USA
  4. ↑ 4.0 4.1 Boneh, D. (2012); Lecture 3 - Block ciphers, Introduction to Cryptography. Stanford, USA.
  5. ↑ 5.0 5.1 Knuth, D. E. (1997). The Art of Computer Programming, volume 2. Addison Wesley, third edition.
  6. ↑ WolframAlpha - Linear Congruential Generators (2012)
  7. ↑ 7.0 7.1 WolframAlpha - Mersenne Twister and Friends (2012)
  8. ↑ Mikulka Z., (2008); Random Number Generators - Bachelor’s thesis. University of technology - Faculty of electrical engeneering and communication, Department of telecomunications, Brno.: page 14
  9. ↑ SPRNG Libraries Documentation
  10. ↑ Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.

Extarnal links

  1. WolframAlpha - Linear Congruential Generator
  2. WolframAlpha - Mersenne Twister simulator
  3. Mersenne Twister – A Pseudo Random Number Generator and its Variants
  4. Autocorrelation test
  5. Spectral test
  6. Web dedicated to the 'randomness'

Self test

1. What is the plaintext for cipher text "33 63 66 15 41 79 85 15 65 58 85" with following encryption properties:

Lets assume that a secret message has been prepared by converting the letters into digits following the rule:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Letter code 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Then the successive digits are added, modulo 10 to the successive digits of the output of a LCG with following properties: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 8397} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a = 4381} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle c = 7364} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_0 = 2134} .

If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_1 = 1234} , then cipher for plaintext AB is:

Plaintext A B
Plaintext code 01 02
Key digits 12 34
Ciphertext 13 36

2. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle F:K \times X \rightarrow \{0, 1\}^{128}} be a secure PRF. I following generator G a secure PRF?

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle G(k, x) = { \begin{cases} 0^{128} {\hskip 1cm} \text{if } x = 0\\ F(k, x) {\hskip 0.5cm} \text{otherwise}\\ \end{cases} }

  • a) No, it is easy to distinguish G from a random function
  • b) Yes, an attack on G would also break F
  • c) It depends on F

3. Which required property of PRG is not fulfilled based on the following output from a generator:

Input 235 803 186 597 931 235 274 727
Output 345812 971486 207319 349183 729460 345812 367428 319708
  • a) unbiased
  • b) unpredictable
  • c) unreproducible
  • d) none of the above

4. What is value of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle X_8} for MCG defined as follows: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m = 6478} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a = 5620} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_0 = 3671} .

  • a) 4572
  • b) 3649
  • c) 2892
  • d) 6217

5. Categorize test based on its description.

Birthday spacings: Choose random points on a large interval. The spacings between the points should be asymptotically exponentially distributed. The name is based on the birthday paradox.

  • a) theoretic test
  • b) blackbox testing

Solution

  • 1. Answer: LCGINACTION
    • First determine first 6 outputs of the generator. Get letter codes by reversed modulo 10 addition and translate the ciphertext.
  • 2. Answer: a
    • When the adversary queries G at x = 0 they always get 0 and they know they are interacting with PRF and not truly random function.
  • 3. Answer: c
    • Generator produced same output for two identical inputs
  • 4. Answer: c
  • 5. Answer: a
Retrieved from "http://www.simulace.info/index.php?title=Pseudorandom_number_generators&oldid=10708"