Difference between revisions of "Random numbers, Encryption and Hashing"

From Organic Design wiki
(found the source online (actually I emailed the author who gave me the link))
(See also: Myths about /dev/urandom)
(12 intermediate revisions by 3 users not shown)
Line 7: Line 7:
 
'''2. Definition:''' A random sequence is one in which each number in the sequence is [[W:Statistical independence|independent]] and equally [[W:Probability|probable]].
 
'''2. Definition:''' A random sequence is one in which each number in the sequence is [[W:Statistical independence|independent]] and equally [[W:Probability|probable]].
  
'''3. Definition:''' A random sequence is one in which all finite sub-sequences of numbers are ∞-distributed.
+
'''3. Definition:''' A random sequence is one in which all finite sub-sequences of numbers are ∞-distributed (∞-distributed is an [[W:Independent and identically-distributed random variables|iid]] process chacterized as a sequence of numbers).
 
 
∞-distributed is an [[W:Independent and identically-distributed random variables|iid]] process chacterized as a sequence of numbers
 
  
 
A [[W:Pseudorandom number generator|pseudo random number generator]] is a generator that produces a series of numbers that pass a reasonable set of statistical tests.
 
A [[W:Pseudorandom number generator|pseudo random number generator]] is a generator that produces a series of numbers that pass a reasonable set of statistical tests.
Line 20: Line 18:
  
 
== Encryption ==
 
== Encryption ==
[[W:Encryption|Encryption]] is the idea of locaking away information so that the only a person with a key can unock and read it. The simplest example of a code is the alphabetic substitution cipher. This is easily crackable due to inherent structure in languages, for example spaces between words, and repeated letters.
+
[[W:Encryption|Encryption]] is the idea of locking away information so that the only a person with a key can unock and read it. The simplest example of a code is the alphabetic substitution cipher. This is easily crackable due to inherent structure in languages, for example spaces between words, and repeated letters.
  
 
See also;
 
See also;
Line 34: Line 32:
  
 
== Hashing ==
 
== Hashing ==
Hasing is the name given to a function that chops up, scrambles and compresses or expands its argument until it is unrecognisable. Encrpytion performs the same function as hashing, with hashing one gets a fixed number of ''random bits'', where as encryption produces ''random bits'' that are the same length as the input data. both hashing and encryption consistently produce the same random bits given the same input data.
+
[[Hash]]ing is the name given to a function that chops up, scrambles and compresses or expands its argument until it is unrecognisable. Encrpytion performs the same function as hashing, with hashing one gets a fixed number of ''random bits'', where as encryption produces ''random bits'' that are the same length as the input data. both hashing and encryption consistently produce the same random bits given the same input data.
  
See also;
+
As the input is variable in size and the output is of fixed length, it is possible for two different input keys to have the same output. This is known as a [[W:Hash collision|Hash collision]].
*[[W:Hash function|Hash function]]
 
*[[W:Associative array|Associative array]]
 
*[[W:Hash table|Hash table]]
 
*[[W:Hash collision|Hash collision]]
 
  
 
== See also ==
 
== See also ==
 
*[http://www.serve.net/buz/Notes.1st.year/HTML/1.year.html Robert Uzgalis' Lecture Notes] ''- the notes containing the text from which these notes are derived''
 
*[http://www.serve.net/buz/Notes.1st.year/HTML/1.year.html Robert Uzgalis' Lecture Notes] ''- the notes containing the text from which these notes are derived''
 +
*[[Hash]]
 +
*[http://keccak.noekeon.org/ The Keccak sponge function family] ''- NIST selects Keccak for SHA-3''
 +
*[http://sponge.noekeon.org/ The Sponge Functions Corner]
 +
*[https://www.2uo.de/myths-about-urandom/ Myths about /dev/urandom]
 +
[[Category:Maths]]__NOTOC__

Revision as of 17:29, 19 September 2018

Random numbers

1. Definition: A random sequence must be generated as if they were independent draws from a well mixed urn where each number is represented once in the urn.

Mathematicians prefer abstract specifications not descriptions of processes.

2. Definition: A random sequence is one in which each number in the sequence is independent and equally probable.

3. Definition: A random sequence is one in which all finite sub-sequences of numbers are ∞-distributed (∞-distributed is an iid process chacterized as a sequence of numbers).

A pseudo random number generator is a generator that produces a series of numbers that pass a reasonable set of statistical tests.

In the 1950's Linear congruential random number generators (LCG's) were used to generate pseudo-random numbersbased on the computation;

[math] r_i = (c_1 \times r_{i-1} + c_2 ) \mbox{MOD} c_3[/math]

where [math]c_1, c_2, c_3[/math] are constants, and [math]r_{i-1}[/math] is the last pseudo-randomly generated number. All LCG's eventually repeat, and have many non random properties based on prior observations.

Encryption

Encryption is the idea of locking away information so that the only a person with a key can unock and read it. The simplest example of a code is the alphabetic substitution cipher. This is easily crackable due to inherent structure in languages, for example spaces between words, and repeated letters.

See also;

Encryption is used in User Authentication. The idea is rather than encrypting an entire file of passwords once, encrypt each users password via an encryption process used to generate a standard message phrase. Then only the result of the encryption is required to be stored for validation, not the actual password that generates the result. e.g.

buz:wYdB]eaWLpD[tz[b]z: Robert Uzgalis

Here, buz is the username, but the password is never stored only the result of the encryption process for validation - wYdB]eaWLpD[tz[b]z.

Hashing

Hashing is the name given to a function that chops up, scrambles and compresses or expands its argument until it is unrecognisable. Encrpytion performs the same function as hashing, with hashing one gets a fixed number of random bits, where as encryption produces random bits that are the same length as the input data. both hashing and encryption consistently produce the same random bits given the same input data.

As the input is variable in size and the output is of fixed length, it is possible for two different input keys to have the same output. This is known as a Hash collision.

See also