Skip to content

Pseudorandom Permutations in O(1)

What if you wanted to enumerate all 32-bit integers in a random order, without repetition? In other words, how would you create a random permutation of the entire 32-bit space?

For just 32-bit integers, perhaps we could enumerate all of them—that would just take \(2^{32} \times 32\) bits \(= 16\) Gibibytes of RAM. Possible on today’s laptops and desktops.

But what about all 64-bit integers (you’d need \(128\) Exbibytes)? Not possible even with the huge RAM of cloud servers! And don’t even think about it for 128-bit integers (you’d need \(4.5 \times 10^{15}\) Yobibytes).

What if I told you there is a method of doing this in O(1) space? Essentially, just the size of two integers. Worst case two 128-bit (so, a total of 256 bits) integers.

First, I’ll show off a quick and dirty way of doing this. In follow-up articles, I’ll showcase more advanced methods.

Try it out

Below is a live Feistel Finite Set Encryption Mode (FFSEM) demo compiled from Zig to a 12 KB standalone WebAssembly module running locally in your browser. Pick one of the worked-out examples or enter any arbitrary input, domain size \(M \in [2, 2^{128})\), round count, and key to inspect every Feistel round and cycle-walking pass.

Examples:

Worked-out Examples to Notice

  1. 10-bit Balanced Feistel ([0, 1023), x = 42): With \(M = 1023\), FFSEM uses a 10-bit Feistel block split into two 5-bit halves \((L, R)\). Over 6 rounds of AES-256, 42 maps to 999 in a single pass. Click Decrypt Result to watch the exact same 6 rounds run in reverse (5 → 0) and recover 42.
  2. Cycle Walking ([0, 1000), x = 4): The smallest even bit-width covering [0, 1000) is still 10 bits ([0, 1024)). On Pass 1, encrypting 4 lands in the out-of-range tail [1000, 1023], so FFSEM feeds that intermediate output right back into the Feistel network until it lands below 1000 (530). Because every pass is a bijection, decrypting 530 walks back through the exact same out-of-range value to 4.
  3. 16-Digit FPE ([0, 10^16)) & 128-Bit Space ([0, 10^27)): Demonstrates preserving a 16-digit card-number shape (54-bit Feistel) and operating natively above 64 bits (90-bit Feistel) using Zig’s built-in u128.

What is a Pseudorandom Permutation (PRP)?

Our requirement is to be able to enumerate all values without repetition, and in random orders. If we kept doing it, it should be possible to enumerate all possible permutations as well. This means we can’t just use a simple counter. We also can’t use typical random number generators, as they allow repetitions to occur—which is also critical for their randomness properties.

What can we do? It turns out there is something called a pseudorandom permutation. Remember, a permutation is an ordering of values. If, for example, our domain was \([1,3]\), then a valid permutation would be:

\[\begin{equation} (1, 2, 3) \end{equation}\]

Other valid permutations include:

\[\begin{eqnarray} (1, 3, 2) \\ (2, 1, 3) \\ (2, 3, 1) \\ (3, 1, 2) \\ (3, 2, 1) \end{eqnarray}\]

If you remember how to count permutations, we are picking 3 values out of 3 possible values, thus there are \(P(3, 3) = \frac{3!}{(3-3)!} = \frac{3!}{0!} = \frac{1 \times 2 \times 3}{1} = 6\) valid choices.

A PRP would just give us a permutation from the list above with uniform probability. In other words, all six permutations would appear from a PRP generator with equal likelihood (⅙ of the time).

Bijective Functions and Block Ciphers

It turns out that there are encryption schemes designed to do just this. At its most basic level, a block cipher is a bijective function mapping \(n\)-bit values into other \(n\)-bit values. Because it is bijective, if you feed a counter (\(0, 1, 2, \dots\)) and a key into a block cipher, each distinct counter value produces a distinct output—enumerating the entire space in pseudorandom order without repetition. The counter is necessary because feeding each output back into the cipher only walks one of its disjoint cycles and can repeat early (for AES specifically, every encryption is an even permutation in \(A_{2^{128}}\), so a single full-length cycle is mathematically impossible).

To refresh ourselves, the definition of a bijective function \(f\colon X \to Y\) is:

  1. each element of \(X\) must be paired with at least one element of \(Y\),
  2. no element of \(X\) may be paired with more than one element of \(Y\),
  3. each element of \(Y\) must be paired with at least one element of \(X\), and
  4. no element of \(Y\) may be paired with more than one element of \(X\).

In other words, every input maps to one and only one output, and the number of elements in the input equals the number of elements in the output.

Such a mapping is a valid permutation! It just so happens that in the 128-bit space, a cipher like AES-256 is a bijective function defined as: \(\textsf{AES-}256\colon 128\textsf{-bit} \to 128\textsf{-bit}\).

AES-256 is a 128-bit block cipher, meaning it maps all 128-bit strings into all 128-bit strings without repetition—otherwise we couldn’t encrypt all possible values. If you were wondering why it is called AES-256 and not AES-128, the 256 in its abbreviated name refers to the key size—not the block size.

To generate a random permutation over an arbitrary range \([0, M)\) up to the 128-bit space, we can wrap AES-256 in a balanced Feistel network with cycle walking (FFSEM).

Implementation Note

I originally wrote this implementation in Golang, but redid it with Gemini 4 Neon in Zig because Zig has native 128-bit integer support (u128) and is a simple systems programming language with an easier learning curve compared to Rust. It also compiles directly to a tiny 12 KB standalone WebAssembly module with no runtime overhead. The source code below is released under the MIT License.

// MIT License
//
// Copyright (c) 2021 - 2026 Wolfgang Richter
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

const std = @import("std");
const Aes256 = std.crypto.core.aes.Aes256;

/// Smallest even bit-width (2..128) that can represent 0..max-1.
pub fn evenBitWidth(max: u128) u8 {
    std.debug.assert(max >= 2);
    const bits: u8 = @intCast(128 - @clz(max - 1));
    return (bits + 1) & ~@as(u8, 1);
}

/// Pseudorandom function F(right, round) using AES-256, masked to `half` bits.
pub fn prf(aes: std.crypto.core.aes.AesEncryptCtx(Aes256), right: u128, half: u7, r: u8) u128 {
    var block: [16]u8 = @splat(0);
    std.mem.writeInt(u64, block[0..8], @truncate(right), .little);
    std.mem.writeInt(u64, block[8..16], r, .little);

    var out: [16]u8 = undefined;
    aes.encrypt(&out, &block);

    const mask = (@as(u128, 1) << half) - 1;
    return @as(u128, std.mem.readInt(u64, out[8..16], .little)) & mask;
}

/// Balanced Feistel network over a (2 * half)-bit block.
fn feistel(
    aes: std.crypto.core.aes.AesEncryptCtx(Aes256),
    x: u128,
    half: u7,
    rounds: u8,
    comptime inverse: bool,
) u128 {
    const mask = (@as(u128, 1) << half) - 1;
    var left = (x >> half) & mask;
    var right = x & mask;

    for (0..rounds) |i| {
        const r: u8 = if (inverse) rounds - 1 - @as(u8, @intCast(i)) else @intCast(i);
        if (inverse) {
            const prev_left = right ^ prf(aes, left, half, r);
            right = left;
            left = prev_left;
        } else {
            const next_right = left ^ prf(aes, right, half, r);
            left = right;
            right = next_right;
        }
    }

    return (left << half) | right;
}

/// Encrypts `x` in [0, max) into a pseudorandom permutation over [0, max).
pub fn encrypt(x: u128, max: u128, key: [32]u8, rounds: u8) u128 {
    std.debug.assert(x < max);
    const aes = Aes256.initEnc(key);
    const half: u7 = @intCast(evenBitWidth(max) / 2);

    var y = feistel(aes, x, half, rounds, false);
    while (y >= max) y = feistel(aes, y, half, rounds, false); // cycle walking
    return y;
}

/// Inverts `encrypt`, mapping any `y` in [0, max) back to its original `x`.
pub fn decrypt(y: u128, max: u128, key: [32]u8, rounds: u8) u128 {
    std.debug.assert(y < max);
    const aes = Aes256.initEnc(key);
    const half: u7 = @intCast(evenBitWidth(max) / 2);

    var x = feistel(aes, y, half, rounds, true);
    while (x >= max) x = feistel(aes, x, half, rounds, true); // cycle walking
    return x;
}

test "FFSEM is a bijection over [0, 1023)" {
    const max = 1023;
    const key: [32]u8 = @splat(0);
    var seen: [max]bool = @splat(false);

    for (0..max) |i| {
        const c = encrypt(i, max, key, 6);
        try std.testing.expect(c < max);
        try std.testing.expect(!seen[@intCast(c)]); // no collisions
        seen[@intCast(c)] = true;
        try std.testing.expectEqual(@as(u128, i), decrypt(c, max, key, 6));
    }
}

test "FFSEM works on a 128-bit domain" {
    const max: u128 = 1_000_000_000_000_000_000_000_000_000; // 10^27 (> 64 bits)
    const key: [32]u8 = @splat(0x42);
    const x: u128 = 123_456_789_012_345_678_901_234_567;
    const c = encrypt(x, max, key, 6);
    try std.testing.expect(c < max);
    try std.testing.expectEqual(x, decrypt(c, max, key, 6));
}

Format-preserving Encryption (FPE) and NIST Standardization

In a follow-up article, I’ll extend this idea to arbitrary bit-length strings, and give an overview of new standardization efforts by NIST and the NSA to formalize algorithms implementing FPE.

FPE is useful to mask things like credit card numbers, SSNs, zip codes, phone numbers, really data where it is useful to retain the shape of the data, but not the precise value. In fact, preserving the precise value may violate compliance in scenarios such as HIPAA/HITRUST and PCI-DSS or PA-DSS.