MappedSequenceGenerator - turn boring database sequences into random-looking IDs

README.md

MappedSequenceGenerator: turn boring database sequences into random-looking IDs

The problem

Most systems hand out IDs from a database sequence or auto-increment column: 1, 2, 3, 4, …. They're perfect internally (compact, ordered, collision-free), but the moment they appear in a URL, an invoice number, an API response, or a QR code, they leak information:

• Enumeration. /orders/1042 tells anyone they can probably fetch /orders/1041 and /orders/1043.
• Business intelligence. A competitor who signs up twice a week can read your growth rate straight off their own user IDs.
• Guessability. Sequential IDs are trivially predictable.

The usual "fixes" each have a cost: random UUIDs are large and unordered, hashing isn't reversible, and encryption is heavyweight and changes the value's length.

The idea

MappedSequenceGenerator keeps your clean internal sequence (1, 2, 3, …) and maps it to a shuffled, random-looking, fixed-width number, reversibly, with zero collisions, and with no lookup table.

It relies on a small piece of number theory (multiplicative inverses): if you multiply each value by a constant that is coprime with the size of your ID space and take the result modulo that size, you get a bijection: every input maps to exactly one distinct output, and the whole thing is reversible. No duplicates are even possible, by construction.

offset     = sequence - 1
obfuscated = lowerLimit + (offset * multiplier) mod count

Why it's nice

• Reversible. Obfuscate on the way out, de-obfuscate on the way in. No mapping table to store.
• No collisions, ever. The coprime multiplier guarantees a 1-to-1 mapping; a built-in exhaustive check can prove it for a given configuration.
• Fixed width. Choose the exact range, e.g. always-10-digit IDs that never start with zero.
• Tiny and stateless. Two numbers (a range and a multiplier) fully describe the mapping.
• Reproducible. Persist those keys and rebuild the identical generator on the next run.
• Fast. Plain integer arithmetic; no hashing, no encryption, no I/O.

Note: this is obfuscation, not encryption. It stops casual enumeration and hides ordering, but a determined attacker with enough samples could recover the multiplier. Don't use it as a security boundary. Use it to keep public identifiers tidy and non-sequential.

Usage

1. Pick an ID shape

// Default 0-based space: input 1..100_000_000 -> output [0, 99_999_999]
MappedSequenceGenerator gen = MappedSequenceGenerator.forDigits(8);

// Custom output range: 10-digit IDs that always start with 1
MappedSequenceGenerator gen = MappedSequenceGenerator.forRange(1_000_000_000L, 1_999_999_999L);

The input is always your natural sequence 1..count; the limits bound only the output.

2. Obfuscate and reverse

long publicId  = gen.obfuscate(dbSequence);    // e.g. 1 -> 1000000000, 2 -> 1490431497, ...
long dbSequence = gen.deobfuscate(publicId);    // exact inverse

Consecutive inputs produce scattered, non-sequential outputs, so the next/previous ID can't be guessed.

3. Prove it's collision-free (optional)

boolean unique = gen.verifyNoDuplicates();      // exhaustive scan for feasible ranges

4. Reproduce it on the next run

The randomness only happens when the generator is created. Once you have one, save its keys and rebuild it deterministically in three equivalent ways:

// A) serialize to a token, store it, reload later
String token = gen.serialize();                 // "1000000000:1999999999:490431497"
MappedSequenceGenerator same = MappedSequenceGenerator.deserialize(token);

// B) store the keys individually
MappedSequenceGenerator same =
        MappedSequenceGenerator.fromKeys(lowerLimit, upperLimit, multiplier);

// C) store only a seed and let a seeded Random pick the same multiplier
MappedSequenceGenerator same =
        MappedSequenceGenerator.forRange(1_000_000_000L, 1_999_999_999L, new Random(seed));

A typical flow with a database sequence

// One-time setup: create a generator and persist its keys (e.g. in config or a settings table).
MappedSequenceGenerator gen = MappedSequenceGenerator.forRange(1_000_000_000L, 1_999_999_999L);
config.save("order-id.keys", gen.serialize());

// On write: store the raw sequence internally, expose the obfuscated value.
long seq = db.nextval("order_seq");             // 1, 2, 3, ...
long publicOrderId = gen.obfuscate(seq);        // random-looking 10-digit ID for the customer

// On read: turn a public ID back into the internal sequence.
long seq = gen.deobfuscate(publicOrderId);

Internally your data stays sequential (great for indexes and ordering); externally every identifier looks random and reveals nothing about volume or order.

MappedSequenceGenerator.java

package io.fouad;

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.BitSet;
import java.util.Random;

/**
 * Obfuscates sequential ids into seemingly-random numbers that land inside a chosen
 * inclusive output range {@code [lowerLimit, upperLimit]}, using a multiplicative-inverse
 * (modular multiplication) mapping.
 *
 * <p>Reference: <a href="https://ericlippert.com/2013/11/14/a-practical-use-of-multiplicative-inverses/">
 * Eric Lippert &mdash; A practical use of multiplicative inverses</a>.
 *
 * <p>Let {@code count = upperLimit - lowerLimit + 1} be the total number of sequences. The
 * input is always {@code 1..count}; the limits bound only the output. For an input
 * {@code sequence} in {@code [1, count]} the mapping is:
 * <pre>
 *   offset     = sequence - 1                          // 0-based position, in [0, count)
 *   obfuscated = lowerLimit + (offset * multiplier) mod count
 * </pre>
 * where {@code multiplier} is any value coprime with {@code count}.
 *
 * <p>Because {@code gcd(multiplier, count) == 1}, the mapping is a bijection from the input
 * domain {@code [1, count]} onto the output range {@code [lowerLimit, upperLimit]}: every
 * input maps to a distinct output inside the range, with no collisions, and it can be
 * reversed via the modular inverse.
 *
 * <p>Examples:
 * <ul>
 *   <li>{@code forDigits(8)} &rarr; input {@code 1..100_000_000}, output {@code [0, 99_999_999]}.</li>
 *   <li>{@code forRange(1_000_000_000L, 1_999_999_999L)} &rarr; input {@code 1..1_000_000_000},
 *       output 10-digit ids that all start with 1.</li>
 * </ul>
 */
public final class MappedSequenceGenerator {

    /**
     * Smallest value the obfuscated output can take, inclusive.
     */
    private final long lowerLimit;

    /**
     * Largest value the obfuscated output can take, inclusive.
     */
    private final long upperLimit;

    /**
     * Total number of sequences, equal to {@code upperLimit - lowerLimit + 1}.
     */
    private final long count;

    /**
     * Multiplier coprime with {@link #count}, which guarantees a collision-free bijection.
     */
    private final long multiplier;

    /**
     * Modular inverse of {@link #multiplier} modulo {@link #count}, used to reverse the mapping.
     */
    private final long inverse;

    /**
     * @param lowerLimit smallest value in the output range, inclusive (must be {@code >= 0})
     * @param upperLimit largest value in the output range, inclusive (must be {@code > lowerLimit})
     * @param multiplier value coprime with {@code count = upperLimit - lowerLimit + 1}
     * @throws IllegalArgumentException if the limits are invalid or the multiplier is not coprime
     */
    public MappedSequenceGenerator(long lowerLimit, long upperLimit, long multiplier) {
        if (lowerLimit < 0) {
            throw new IllegalArgumentException("lowerLimit must be >= 0, was " + lowerLimit);
        }
        if (upperLimit <= lowerLimit) {
            throw new IllegalArgumentException(
                    "upperLimit (" + upperLimit + ") must be greater than lowerLimit (" + lowerLimit + ")");
        }
        long size = upperLimit - lowerLimit + 1;
        if (size <= 0) { // overflowed: the span exceeds Long.MAX_VALUE
            throw new IllegalArgumentException(
                    "range [" + lowerLimit + ", " + upperLimit + "] is too large to represent");
        }
        long normalizedMultiplier = Math.floorMod(multiplier, size);
        if (gcd(normalizedMultiplier, size) != 1) {
            throw new IllegalArgumentException(
                    "multiplier " + multiplier + " is not coprime with count " + size + " (gcd must be 1)");
        }
        this.lowerLimit = lowerLimit;
        this.upperLimit = upperLimit;
        this.count = size;
        this.multiplier = normalizedMultiplier;
        this.inverse = BigInteger.valueOf(normalizedMultiplier)
                .modInverse(BigInteger.valueOf(size))
                .longValueExact();
    }

    /**
     * Builds a generator over the default 0-based output space for ids of the given width,
     * i.e. range {@code [0, 10^numberOfDigits - 1]}, picking a random coprime multiplier.
     *
     * @param numberOfDigits number of decimal digits (1..18)
     */
    public static MappedSequenceGenerator forDigits(int numberOfDigits) {
        return forDigits(numberOfDigits, new SecureRandom());
    }

    /**
     * Same as {@link #forDigits(int)} but with a caller-supplied source of randomness
     * (useful for reproducible tests).
     */
    public static MappedSequenceGenerator forDigits(int numberOfDigits, Random random) {
        if (numberOfDigits < 1 || numberOfDigits > 18) {
            // 10^19 overflows a long, so cap at 18 digits.
            throw new IllegalArgumentException("numberOfDigits must be in 1..18, was " + numberOfDigits);
        }
        return forRange(0, pow10(numberOfDigits) - 1, random);
    }

    /**
     * Builds a generator over the inclusive output range {@code [lowerLimit, upperLimit]},
     * picking a random multiplier coprime with the range size.
     */
    public static MappedSequenceGenerator forRange(long lowerLimit, long upperLimit) {
        return forRange(lowerLimit, upperLimit, new SecureRandom());
    }

    /**
     * Same as {@link #forRange(long, long)} but with a caller-supplied source of randomness.
     *
     * <p>Passing a seeded {@link Random} (e.g. {@code new Random(42)}) makes the chosen
     * multiplier reproducible: the same {@code (lowerLimit, upperLimit, seed)} rebuilds the
     * same generator on later runs, so only the seed need be stored. The no-argument
     * {@link #forDigits(int)} and {@link #forRange(long, long)} factories use a
     * {@link SecureRandom}, which is not reproducible.
     */
    public static MappedSequenceGenerator forRange(long lowerLimit, long upperLimit, Random random) {
        if (upperLimit <= lowerLimit) {
            throw new IllegalArgumentException(
                    "upperLimit (" + upperLimit + ") must be greater than lowerLimit (" + lowerLimit + ")");
        }
        long size = upperLimit - lowerLimit + 1;
        if (size <= 0) {
            throw new IllegalArgumentException(
                    "range [" + lowerLimit + ", " + upperLimit + "] is too large to represent");
        }
        long multiplier = randomCoprimeMultiplier(size, random);
        return new MappedSequenceGenerator(lowerLimit, upperLimit, multiplier);
    }

    /**
     * Reconstructs a generator from previously-saved keys so it reproduces the exact same
     * mapping on later runs. Store {@link #getLowerLimit()}, {@link #getUpperLimit()} and
     * {@link #getMultiplier()}, then pass them back here.
     *
     * <p>Behaves exactly like {@link #MappedSequenceGenerator(long, long, long)}; it exists
     * to make the intent of rebuilding from saved keys explicit at the call site.
     */
    public static MappedSequenceGenerator fromKeys(long lowerLimit, long upperLimit, long multiplier) {
        return new MappedSequenceGenerator(lowerLimit, upperLimit, multiplier);
    }

    /**
     * Parses the {@code "lowerLimit:upperLimit:multiplier"} token produced by
     * {@link #serialize()} and rebuilds the corresponding generator.
     *
     * @throws IllegalArgumentException if the token is malformed or the keys are invalid
     */
    public static MappedSequenceGenerator deserialize(String token) {
        if (token == null) {
            throw new IllegalArgumentException("token must not be null");
        }
        String[] parts = token.trim().split(":");
        if (parts.length != 3) {
            throw new IllegalArgumentException(
                    "expected \"lowerLimit:upperLimit:multiplier\", was \"" + token + "\"");
        }
        try {
            return new MappedSequenceGenerator(
                    Long.parseLong(parts[0].trim()),
                    Long.parseLong(parts[1].trim()),
                    Long.parseLong(parts[2].trim()));
        } catch (NumberFormatException e) {
            throw new IllegalArgumentException("token contains a non-numeric field: \"" + token + "\"", e);
        }
    }

    /**
     * Obfuscates a sequence number into an id inside the output range {@code [lowerLimit, upperLimit]}.
     *
     * @param sequence original sequence number, must be within {@code [1, count]}
     */
    public long obfuscate(long sequence) {
        if (sequence < 1 || sequence > count) {
            throw new IllegalArgumentException(
                    "sequence must be in [1, " + count + "], was " + sequence);
        }
        long offset = sequence - 1;
        return lowerLimit + modMultiply(offset, multiplier, count);
    }

    /**
     * Reverses {@link #obfuscate(long)}, recovering the original sequence number in {@code [1, count]}.
     */
    public long deobfuscate(long obfuscated) {
        if (obfuscated < lowerLimit || obfuscated > upperLimit) {
            throw new IllegalArgumentException(
                    "value must be in [" + lowerLimit + ", " + upperLimit + "], was " + obfuscated);
        }
        long offset = obfuscated - lowerLimit;
        return modMultiply(offset, inverse, count) + 1;
    }

    /**
     * Exhaustively verifies that obfuscating every sequence number in {@code [1, count]}
     * yields only in-range outputs and no duplicates, confirming the mapping is a bijection
     * onto {@code [lowerLimit, upperLimit]}. Since {@code lowerLimit >= 0}, an in-range output
     * is also guaranteed to be non-negative.
     *
     * <p>This is an O(count) scan and is only feasible while the whole range fits a
     * {@link BitSet}, whose index is an int, i.e. {@code count <= Integer.MAX_VALUE}. For
     * larger ranges the coprimality enforced in the constructor already guarantees the
     * bijection, so an exhaustive scan is unnecessary.
     *
     * @return {@code true} if every output is within the range and unique
     * @throws IllegalStateException if the range is too large to scan exhaustively
     */
    public boolean verifyNoDuplicates() {
        if (count > Integer.MAX_VALUE) {
            throw new IllegalStateException(
                    "count " + count + " is too large to brute-force verify; "
                            + "coprimality already guarantees a bijection");
        }
        BitSet seen = new BitSet((int) count);
        for (long sequence = 1; sequence <= count; sequence++) {
            long out = obfuscate(sequence);
            if (out < lowerLimit || out > upperLimit) {
                // Out of range, which (since lowerLimit >= 0) also catches any negative value.
                return false;
            }
            int index = (int) (out - lowerLimit);
            if (seen.get(index)) {
                return false; // collision found
            }
            seen.set(index);
        }
        // Every input produced a distinct in-range output, so full coverage is confirmed too.
        return seen.cardinality() == count;
    }

    /**
     * Returns the smallest value the obfuscated output can take, inclusive.
     */
    public long getLowerLimit() {
        return lowerLimit;
    }

    /**
     * Returns the largest value the obfuscated output can take, inclusive.
     */
    public long getUpperLimit() {
        return upperLimit;
    }

    /**
     * Returns the total number of sequences, equal to {@code upperLimit - lowerLimit + 1}.
     */
    public long getCount() {
        return count;
    }

    /**
     * Returns the multiplier used by the mapping, which is coprime with {@link #getCount()}.
     */
    public long getMultiplier() {
        return multiplier;
    }

    /**
     * Returns a compact token holding everything needed to rebuild this exact generator,
     * formatted as {@code "lowerLimit:upperLimit:multiplier"}. Store it and reload with
     * {@link #deserialize(String)}.
     */
    public String serialize() {
        return lowerLimit + ":" + upperLimit + ":" + multiplier;
    }

    /**
     * Returns a human-readable description of the output range, count and multiplier.
     */
    @Override
    public String toString() {
        return "MappedSequenceGenerator{range=[" + lowerLimit + ", " + upperLimit + "]"
                + ", count=" + count + ", multiplier=" + multiplier + '}';
    }

    // --- helpers -----------------------------------------------------------------

    /**
     * Computes {@code (a * b) mod modulus} without overflowing, falling back to
     * {@link BigInteger} for large moduli.
     */
    private static long modMultiply(long a, long b, long modulus) {
        // a and b are both < modulus. If modulus^2 fits in a long (modulus <= ~3.03e9),
        // the plain product is exact.
        if (modulus <= 3_037_000_499L) {
            return (a * b) % modulus;
        }
        return BigInteger.valueOf(a)
                .multiply(BigInteger.valueOf(b))
                .mod(BigInteger.valueOf(modulus))
                .longValueExact();
    }

    /**
     * Picks a random multiplier coprime with {@code count}, avoiding the identity (1) when possible.
     */
    private static long randomCoprimeMultiplier(long count, Random random) {
        if (count <= 2) {
            return 1; // too few elements for a non-trivial multiplier
        }
        while (true) {
            // Uniform in [1, count - 1].
            long candidate = 1 + Math.floorMod(random.nextLong(), count - 1);
            // Skip 1: it would be the identity map (no obfuscation at all).
            if (candidate != 1 && gcd(candidate, count) == 1) {
                return candidate;
            }
        }
    }

    /**
     * Returns the greatest common divisor of {@code a} and {@code b} using the Euclidean algorithm.
     */
    private static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    /**
     * Returns {@code 10^n} as a long. The caller must ensure {@code n <= 18} to avoid overflow.
     */
    private static long pow10(int n) {
        long result = 1;
        for (int i = 0; i < n; i++) {
            result *= 10;
        }
        return result;
    }
}