# CryptoRand

Fast and efficient cryptographically strong versions of several [Enum]( functions that rely on [`:rand`]( __uniform__ functions for randomness.

By default, the [`:rand`]( functions operate in pseudo-random number generator (PRNG) mode, and hence are not cryptographically secure. To achieve cryptographically strong pseudo-random number generation (CSPRNG) versions, [`:crypto.rand_seed`]( can be used to force [`:rand`]( functions into a CSPRNG mode; however, the performance of the `Enum` functions under CSPRNG is approximately _10 times slower_ than under PRNG. This module provides functions that are faster than corresponding `Enum` functions when operating in CSPRNG mode.

[![Build Status](](   [![Hex Version]( "Hex Version")](   [![License: MIT](]()

### <a name="TOC"></a>TOC
 - [Installation](#Installation)
 - [Efficiency](#Efficiency)
 - [Random Bytes](#Random_Bytes)
 - [Process Dictionary](#Process_Dictionary)
 - [Tests](#Tests)
 - [Speed](#Speed)
 - [String Processing](#String_Processing)
 - [Caveat Emptor](#Caveat_Emptor)

## <a name="Installation"></a>Installation

Add `crypto_rand` to `mix.exs` dependencies:

  def deps, do:
    [ {:crypto_rand, "~> 1.0.0"} ]


## <a name="Efficiency"></a>Efficiency

The source code for the [`:rand`]( module indicates that at least 55 random bits are required to generate values using [`:rand`]( functions. So, for example, the call `:rand.uniform(2)`, which returns a value of either `1` or `2`, consumes 55 bits of randomness, even though only 1 bit is actually needed to chose between two values.

PRNG methods are sufficiently fast that this inefficient use of randomness is negligible. CSPRNG methods, however, are much slower, and the inefficiency is easily detected. For example, the time (in seconds) required to generate 1 million random integers using `:rand.uniform(8)` with PRNG vs CSPRNG yields:

      PRNG:   0.218
      CSPRNG: 2.566

The timing is, of course, system dependent. But it's the relative timing that is of interest. Running `:rand.uniform/1` under CSPRNG is much slower than PRNG.

Consider the inefficient use of randomness in the above example. At least 53.8 MB of randomness was used to generate the one million integers in the range **1..8**; yet since each integer in theory only needs 3 bits to be determined, only 2.9 MB of randomness was actually needed. The remaining 50.9 MB were effectively wasted. That's a usage efficiency ratio of around 5%.

`CryptoRand` implements a strategy that maximizes the effective use of CSRPNG generated bytes. For example, to generate random integers in the range **1..8**, the function `CryptoRand.uniform(8)` uses 3 bits of randomness per call. The time (in seconds) required to generate 1 million CSPRNG random integers as above is:

      CryptoRand: 0.647

Though slower than `:rand.uniform/1` under PRNG, `CryptoRand.uniform/1` is significantly faster than the equivalent use of `:rand.uniform/1` under CSPRNG.


## <a name="Random_Bytes"></a>Random Bytes

All `CryptoRand` functions take a final, `rand_bytes` argument to specify a function of the form `(non_negative_integer) -> binary()` that returns an input integer number of bytes as a `binary`. The optional argument defaults to `:cryto.strong_rand_bytes/1` and can omitted. However, any suitable function can be substituted for generating bytes, allowing for deterministic testings as well as substituting any random byte generating function of choice.


## <a name="Process_Dictionary"></a>Process Dictionary

For efficiency, `CryptoRand` stores values in the process dictionary. This is consistent with the default behavior of `:rand`. `CryptoRand` stores unprocessed bytes generated using `rand_bytes` under the key `:crypto_rand_bytes` and parameters needed for generating uniform values in the range `1..max` under the key `:crypto_rand_max`. These entries can be removed using `CryptoRand.clear/0`.


## <a name="Tests"></a>Tests

The test suite contains deterministic tests of correctness, non-deterministic histogram tests for validating `CryptoRand` implementation in the face of randomness, and timing tests for rough comparison to existing solutions.

#### Deterministic

To run the deterministic tests:
> mix test --trace

#### Non-Deterministic

The non-deterministic tests use `CryptoRand` functions to create histograms which should exhibit uniform behaviour. The histograms are validated using a simple chi-square test. However, the very nature of chi-square testing means these tests are subject to potential failure even if the underlying implementation is correct. So an occasional failure of a histogram chi-square tests does not mean the implementation is necessarily wrong. For this reason, these tests are put in a separate file that does not automatically get run with the standard `mix test` command.

To run the histogram tests:
> mix test --trace test/histogram.exs

The histogram tests include module tags for testing particular `CryptoRand` functions. The tags are `random`, `shuffle`, `take_random`, and `uniform`. For example, to run the `CryptoRand.shuffle/1` histogram tests:

> mix test --trace test/histogram.exs --only shuffle

#### Timing

The timing tests compare `CryptoRand` implementation to various existing implementations. These tests are, of course, system dependent; but it is the resulting relative timings that are of interest. Also note these timing tests do not assert expected behavior, and as such don't either pass or fail. For this reason, these tests are put in a separate file that does not automatically get run with the standard mix test command.

To run the timing tests:

> mix test test/timing.exs

The timing tests include module tags for timing particular `CryptoRand` functions. The tags are `random`, `shuffle`, `take_random`, `uniform` and `uniform_list`. For example, to run the `CryptoRand.shuffle/1` timing tests:

> mix test test/timing.exs --only shuffle

The following provides example timings.

#### Select random element: `CryptoRand.random/1` vs `:Enum.random/1`:

    250000 random elements from enumerable 1..12
      rand.uniform   (PRNG) : 0.111963
      rand.uniform (CSPRNG) : 0.735606
      CryptoRand            : 0.34594

    250000 random elements from list len 12
      rand.uniform   (PRNG) : 0.736724
      rand.uniform (CSPRNG) : 7.786567
      CryptoRand            : 0.297439

#### Shuffle enumerable: `CryptoRand.shuffle/1` vs `:Enum.shuffle/1`:

    250000 shuffles of enumerable 1..12
      rand.uniform   (PRNG) : 0.827411
      rand.uniform (CSPRNG) : 9.516535
      CryptoRand            : 2.285146

    250000 shuffles of list len 12
      rand.uniform   (PRNG) : 0.796975
      rand.uniform (CSPRNG) : 9.318896
      CryptoRand            : 2.121225

#### Take random elements: `CryptoRand.take_random/2` vs `:Enum.take_random/2`:

    100000 trials of take_random 5 elements from enumerable 1..26
      rand.uniform   (PRNG) : 0.711783
      rand.uniform (CSPRNG) : 7.060916
      CryptoRand            : 0.680446

    100000 trials of take_random 5 elements from list len 26
      rand.uniform   (PRNG) : 0.734776
      rand.uniform (CSPRNG) : 7.020736
      CryptoRand            : 0.572719

#### `CryptoRand.uniform/1` vs `:rand.uniform/1`:

    1000000 uniform ints in range 1..25
      rand.uniform   (PRNG) : 0.22094
      rand.uniform (CSPRNG) : 2.583177
      CryptoRand            : 1.056496
#### Generate uniform int lists: `:rand.uniform/1` vs `CryptoRand.uniform_list/1`:

    100000 lists of size 20 with uniform ints from 1..21
      rand.uniform   (PRNG) : 0.384218
      rand.uniform (CSPRNG) : 5.614058
      CryptoRand            : 1.026913


## <a name="String_Processing"></a>String Processing

Unlike `Enum`, `CryptoRand` isn't contextually constrained to enumerables. Each of the functions `CryptoRand.random/1`, `CryptoRand.shuffle/1` and `CryptoRand.take_random/1` operate on Elixir `String.t()`.


## <a name="Caveat_Emptor"></a>Caveat Emptor

The development of `CryptoRand` was initially in support of functionality needed for the [Puid]( and [RandomPassword]( libraries. Neither of these libraries required operating on enumerables with a large number of elements. Ensure suitability for your needs before adopting `CryptoRand` into your projects.