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

From Organic Design wiki
(Hashing)
m (Random numbers)
 
(15 intermediate revisions by 3 users not shown)
Line 1: Line 1:
==Random numbers==
+
== Random numbers ==
  
 
'''1. Definition:''' A random [[W:Sequence|sequence]] must be generated as if they were [[W:Statistical independence|independent]] draws from a well mixed urn where each number is represented once in the urn.
 
'''1. Definition:''' A random [[W:Sequence|sequence]] must be generated as if they were [[W:Statistical independence|independent]] draws from a well mixed urn where each number is represented once in the urn.
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.
  
In the 1950's Linear congruential random number generators (LCG's) were used to generate pseudo-random numbersbased on the computation;
+
In the 1950's Linear congruential random number generators (LCG's) were used to generate pseudo-random numbers based on the computation;
  
 
<math> r_i = (c_1 \times r_{i-1} + c_2 ) \mbox{MOD} c_3</math>  
 
<math> r_i = (c_1 \times r_{i-1} + c_2 ) \mbox{MOD} c_3</math>  
Line 19: Line 17:
 
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.
 
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 ==
[[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;
 
 
*[[W:Enigma machine|Enigma machine]]
 
*[[W:Enigma machine|Enigma machine]]
 
*[[W:Gilbert Vernam|Vernam cypher]] - ''Uses [[W:Exclusive or|XOR]] bit function''
 
*[[W:Gilbert Vernam|Vernam cypher]] - ''Uses [[W:Exclusive or|XOR]] bit function''
Line 34: Line 31:
 
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''.
 
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 ==
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.
 +
 
 +
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]].
  
See also;
+
== See also ==
*[[W:Hash function|Hash function]]
+
*[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''
*[[W:Associative array|Associative array]]
+
*[[Hash]]
*[[W:Hash table|Hash table]]
+
*[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__

Latest revision as of 01:37, 8 October 2020

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