# CryptoRand
Fast and efficient cryptographically strong versions of several [Enum](https://hexdocs.pm/elixir/Enum.html) functions that rely on [`:rand`](http://www.erlang.org/doc/man/rand.html) __uniform__ functions for randomness.
By default, the [`:rand`](http://www.erlang.org/doc/man/rand.html) 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`](http://www.erlang.org/doc/man/crypto.html#rand_seed-0) can be used to force [`:rand`](http://www.erlang.org/doc/man/rand.html) 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.
[](https://travis-ci.org/CryptoRand/Elixir) [](https://hex.pm/packages/crypto_rand) []()
### <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:
```elixir
def deps, do:
[ {:crypto_rand, "~> 1.0.0"} ]
```
[TOC](#TOC)
## <a name="Efficiency"></a>Efficiency
The source code for the [`:rand`](http://www.erlang.org/doc/man/rand.html) module indicates that at least 55 random bits are required to generate values using [`:rand`](http://www.erlang.org/doc/man/rand.html) 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.
[TOC](#TOC)
## <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.
[TOC](#TOC)
## <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`.
[TOC](#TOC)
## <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:
```bash
> 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:
```bash
> 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:
```bash
> 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:
```bash
> 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:
```bash
> 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
[TOC](#TOC)
## <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()`.
[TOC](#TOC)
## <a name="Caveat_Emptor"></a>Caveat Emptor
The development of `CryptoRand` was initially in support of functionality needed for the [Puid](https://hex.pm/packages/puid) and [RandomPassword](https://hex.pm/packages/random_password) 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.
