# Vitamin C Permutation
[](https://crates.io/crates/vitaminc-permutation)
[](https://github.com/cipherstash/vitaminc/actions/workflows/test.yml)
A library for permuting data in a secure and efficient manner.
This crate is part of the [Vitamin C](https://github.com/cipherstash/vitaminc) framework to make cryptography code healthy.
## Warning
This library is a low-level primitive designed to be used in cryptographic applications.
It is not recommended to use this library directly unless you are familiar with the underlying
cryptographic principles.
### Relationship to `vitaminc-protected`
This library is designed to work with the `vitaminc-protected` library.
## Example: Permuting an array
```rust
use vitaminc_permutation::{Permute, PermutationKey};
use vitaminc_random::{Generatable, SafeRand, SeedableRng};
use vitaminc_protected::{Controlled, Protected};
let mut rng = SafeRand::from_seed([0; 32]);
let key = PermutationKey::random(&mut rng).expect("Random error");
let input: [u8; 8] = [1, 2, 3, 4, 5, 6, 7, 8];
assert_eq!(key.permute(input), [5, 3, 6, 2, 4, 8, 1, 7]);
```
## Bitwise Permutations
The `BitwisePermute` trait is a low-level trait that allows for bitwise permutations.
This is useful for when you need to permute a single byte or a small number of bytes.
```rust
use vitaminc_permutation::{BitwisePermute, PermutationKey};
use vitaminc_protected::{Controlled, Protected};
use vitaminc_random::{Generatable, SafeRand, SeedableRng};
let mut rng = SafeRand::from_seed([0; 32]);
let key = PermutationKey::random(&mut rng).expect("Random error");
let input: u32 = 1000;
assert_eq!(key.bitwise_permute(input), 1082155265);
```
## Permutations and Security
As a quick primer (or refresher), a permutation is an array of numbers which “shuffles” an input.
Each element of the permutation says which element of the input should be output in that position.
For example:
```plaintext
// Input array
X = [6, 7, 8, 9]
// Permutation
P = [2, 0, 3, 1]
// Permuted output
Y = [8, 6, 9, 7]
```
Because the first element of P is 2, we take the 2nd element (counting from 0) from X and place it in the output.
The next element, 6, comes from the 0th position and so on.
This operation is often written as Y=P(X).
Permutations like this are useful because there is a _super-exponential_ relationship between the size of the
permutation and the number of possible inputs that could have been processed by a given key.
For example, a 3-element input X was permuted by a permutation P.
We don’t know X or P but we do know the output.
Let’s say `Y=[2, 1, 0]`, the input could have been:
```plaintext
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0] // A permutation that does nothing
```
A permutation of N elements will have `N!` (factorial) possible values.
For N=16, the number of permutations is ~20 trillion.
For N=32, about 2x10^35. This number can be represented by about 117 bits (compare that to AES-128 which is 128-bits).
A permutation is loosely analogous to an XOR operation.
In fact, XOR can be thought of a 1-bit (2-element) permutation operating on a 1-bit (2-element) input.
If the key is 1, the input bit is flipped, otherwise it isn’t.
```plaintext
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
```
The XOR of a key with a plaintext has perfect security but if an attacker knows both the input and the output,
the key is trivial to recover (k=input^output).
Despite this, XOR features heavily in modern cryptography and forms the basis of virtually all block-cipher modes.
These modes are designed to take advantage of the secret properties of XOR without creating a situation where
an input and output to an XOR is accessible to an attacker without a key.
In a sense, permutations are the generalised version of XOR.
They too have perfect secrecy but, like XOR, if an attacker knows the input and output to a permutation,
the permutation itself is trivially recoverable.
## CipherStash
Vitamin C is brought to you by the team at [CipherStash](https://cipherstash.com).
License: MIT