# Random numbers, Encryption and Hashing

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

- Enigma machine
- Vernam cypher -
*Uses XOR bit function* - Vigenère cipher

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

- Robert Uzgalis' Lecture Notes
*- the notes containing the text from which these notes are derived* - Hash
- The Keccak sponge function family
*- NIST selects Keccak for SHA-3* - The Sponge Functions Corner
- Myths about /dev/urandom