Difference between revisions of "Pseudorandom number generators"
| Line 9: | Line 9: | ||
First of all let’s start with pseudorandom functions. A pseudorandom function is any function defined over <math>{{\textnormal(K, X, Y)}}</math> : | First of all let’s start with pseudorandom functions. A pseudorandom function is any function defined over <math>{{\textnormal(K, X, Y)}}</math> : | ||
| − | <math>{{ | + | <math>{{F:K \times X \rightarrow Y}}</math> |
| + | |||
| + | where: | ||
| + | |||
| + | # <math>{{K}}</math> is key space | ||
| + | # <math>{{X}}</math> is input space | ||
| + | # <math>{{Y}}</math> is output space | ||
such that exists efficient algorithm to evaluate <math>{{\textnormal F(k,x)}}</math>.<ref name=crypto>[https://class.coursera.org/crypto/class/index Boneh, D. (2012); Lecture 3 - Block ciphers, Introduction to Cryptography. Stanford, USA.]</ref> | such that exists efficient algorithm to evaluate <math>{{\textnormal F(k,x)}}</math>.<ref name=crypto>[https://class.coursera.org/crypto/class/index Boneh, D. (2012); Lecture 3 - Block ciphers, Introduction to Cryptography. Stanford, USA.]</ref> | ||
| − | On the other hand pseudorandom permutation is any function defined over <math>{{\textnormal(K, X)}}</math | + | |
| + | On the other hand pseudorandom permutation is any function defined over <math>{{\textnormal(K, X)}}</math>: | ||
<math>{{E:K \times X \rightarrow X}}</math> | <math>{{E:K \times X \rightarrow X}}</math> | ||
| − | such that: | + | such that<ref name=crypto/>: |
# Exists efficient deterministic algorithm to evaluate <math>{{\textnormal E(k,x)}}</math> | # Exists efficient deterministic algorithm to evaluate <math>{{\textnormal E(k,x)}}</math> | ||
| Line 24: | Line 31: | ||
| − | + | Any pseudorandom permutation is also pseudorandom function given | |
| + | # <math>{{X=Y}} | ||
| + | # Function is efficiently invertible | ||
Revision as of 18:52, 1 December 2012
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.
Contents
Definition
First of all let’s start with pseudorandom functions. A pseudorandom function 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:
- 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
- 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
- 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)}}} .[1]
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[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)}}}
- 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
- 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 is also pseudorandom function given
- <math>Template:X=Y
- Function is efficiently invertible
