Introduction

Your credit card number is 16 digits. The database that stores it is also 16 digits wide. A classic cipher like AES would turn those 16 digits into a 16-byte binary blob — the schema would break, the legacy validation rules would reject it, and every system downstream would need updating.

Format-preserving encryption (FPE) solves this with a neat trick: it encrypts a string and returns a ciphertext in the exact same format — same alphabet, same length. Encrypt a 16-digit number and you get back a 16-digit number. Encrypt a 9-character uppercase string and you get back a 9-character uppercase string.

This is not just cosmetic convenience. Entire payment, healthcare, and government pipelines handle fixed-width fields. FPE lets you bolt encryption onto those pipelines without touching the schema, the application code, or the downstream validators.

The key question is: how do you build a provably secure block cipher over an arbitrary alphabet of size rr (called the radix) and an arbitrary message length mm? That is the algorithmic puzzle at the heart of FPE.

Try It

Type any message using only the letters in the alphabet box. Pick a numeric key and press Encrypt. The output uses the same characters, same length — completely different sequence.

<!-- FPE demo: encrypt/decrypt within a custom alphabet using a toy Feistel network -->
<div class="fpe-wrap">
  <div class="field-row">
    <label for="alphabet">Alphabet (radix)</label>
    <input id="alphabet" type="text" value="0123456789" maxlength="64" spellcheck="false" placeholder="e.g. 0123456789" title="Characters to use in plaintext and ciphertext" aria-label="Alphabet for encryption">
  </div>
  <div class="field-row">
    <label for="key-input">Key (numeric)</label>
    <input id="key-input" type="number" value="42" min="1" max="9999" title="Numeric key for the Feistel round function" aria-label="Numeric key">
  </div>
  <div class="field-row">
    <label for="plaintext">Plaintext</label>
    <input id="plaintext" type="text" value="4532015112830366" spellcheck="false" placeholder="Enter text using the alphabet above" title="Text to encrypt — must only use characters from the alphabet" aria-label="Plaintext input">
  </div>
  <div class="btns">
    <button id="btn-enc" type="button">Encrypt</button>
    <button id="btn-dec" type="button">Decrypt</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="output-grid">
    <div class="out-box">
      <div class="out-label">Ciphertext</div>
      <div class="out-value" id="ct-value">&#8212;</div>
    </div>
    <div class="out-box">
      <div class="out-label">Decrypted</div>
      <div class="out-value" id="dec-value">&#8212;</div>
    </div>
  </div>
  <div class="status" id="status"></div>
  <div class="explainer" id="explainer"></div>
</div>

/* FPE demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .4rem; }
.fpe-wrap { max-width: 480px; }
.field-row { display: flex; flex-direction: column; margin-bottom: .7rem; }
label { font-size: .8rem; font-weight: 600; color: #555; margin-bottom: .25rem; text-transform: uppercase; letter-spacing: .04em; }
input[type=text], input[type=number] {
  font: 500 15px ui-monospace, monospace; padding: .4rem .6rem;
  border: 1px solid #c0c8d2; border-radius: 8px; outline: none;
  transition: border-color .15s; background: #f8f9fa; }
input:focus { border-color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .9rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.output-grid { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; margin-bottom: .7rem; }
.out-box { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px; padding: .6rem .8rem; }
.out-label { font-size: .75rem; font-weight: 600; color: #5a7088; text-transform: uppercase; letter-spacing: .04em; margin-bottom: .3rem; }
.out-value { font: 700 15px ui-monospace, monospace; color: #1d3557; word-break: break-all; min-height: 1.4em; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; margin-bottom: .4rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.explainer { font-size: .82rem; color: #555; line-height: 1.5; background: #f0f4f8; border-radius: 8px; padding: .6rem .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Toy Format-Preserving Encryption demo using a Feistel network.
// The Feistel structure guarantees a bijection (permutation) over the domain r^m,
// so ciphertext length and alphabet always match plaintext.

// Read and deduplicate the alphabet from the input.
function getAlphabet() {
  const raw = document.getElementById('alphabet').value;
  // Remove duplicate characters so the radix is exactly alpha.length.
  return [...new Set(raw)].join('');
}

// Interpret a string as a base-r number (left digit is most significant).
function strToNum(s, alpha) {
  const r = alpha.length;
  let n = 0n;
  for (const ch of s) {
    n = n * BigInt(r) + BigInt(alpha.indexOf(ch));
  }
  return n;
}

// Convert a big integer back to a fixed-length base-r string.
function numToStr(n, len, alpha) {
  const r = BigInt(alpha.length);
  const out = [];
  for (let i = 0; i < len; i++) {
    out.push(alpha[Number(n % r)]);
    n /= r;
  }
  return out.reverse().join('');
}

// Toy round function: a deterministic hash of (value, round, key) reduced mod m.
// In real FF1/FF3 the round function is AES in CBC or ECB mode.
function roundFn(val, round, key, mod) {
  // Multiply-xor-shift mixing (Murmur3-inspired), no crypto security claimed.
  let h = (val * 2654435761n + BigInt(round) * 1234567891n + BigInt(key)) % 4294967296n;
  h = (h ^ (h >> 16n)) * 2246822519n % 4294967296n;
  h = (h ^ (h >> 13n)) * 3266489917n % 4294967296n;
  h = h ^ (h >> 16n);
  return h % mod;
}

const ROUNDS = 8;

// Encrypt: 8-round Feistel over two halves A (length u) and B (length v=m-u).
function feistelEncrypt(s, alpha, key) {
  const r = BigInt(alpha.length);
  const m = s.length;
  const u = Math.floor(m / 2);
  const v = m - u;
  let modA = r ** BigInt(u);
  let modB = r ** BigInt(v);
  let A = strToNum(s.slice(0, u), alpha);
  let B = strToNum(s.slice(u), alpha);
  for (let i = 0; i < ROUNDS; i++) {
    // Add F(B) mod domain_A to A, then swap A and B.
    const F = roundFn(B, i, key, modA);
    const newA = (A + F) % modA;
    A = B;
    B = newA;
    // Swap the moduli so each half alternates between domain_u and domain_v.
    const tmp = modA; modA = modB; modB = tmp;
  }
  // After an even number of rounds A is still the left half; odd flips them.
  if (ROUNDS % 2 === 0) {
    return numToStr(A, u, alpha) + numToStr(B, v, alpha);
  }
  return numToStr(A, v, alpha) + numToStr(B, u, alpha);
}

// Decrypt: reverse the Feistel rounds by running them backwards.
function feistelDecrypt(s, alpha, key) {
  const r = BigInt(alpha.length);
  const m = s.length;
  const u = Math.floor(m / 2);
  const v = m - u;
  let modA = r ** BigInt(u);
  let modB = r ** BigInt(v);
  // Split ciphertext respecting the parity-dependent half ordering.
  let A, B;
  if (ROUNDS % 2 === 0) {
    A = strToNum(s.slice(0, u), alpha);
    B = strToNum(s.slice(u), alpha);
  } else {
    A = strToNum(s.slice(0, v), alpha);
    B = strToNum(s.slice(v), alpha);
  }
  // If ROUNDS is odd the moduli are swapped at the end of encrypt.
  if (ROUNDS % 2 !== 0) { const tmp = modA; modA = modB; modB = tmp; }
  // Undo each round in reverse: swap mods back, invert A = B, B = (A-F) mod modB.
  for (let i = ROUNDS - 1; i >= 0; i--) {
    // Undo the mod swap that happened at the end of this forward round.
    const tmp = modA; modA = modB; modB = tmp;
    // After restoring modA, invert: old_B=A (current), old_A=(B-F(A,modA))%modA.
    const F = roundFn(A, i, key, modA);
    const prevOldA = ((B - F) % modA + modA) % modA;
    const prevOldB = A;
    A = prevOldA;
    B = prevOldB;
  }
  return numToStr(A, u, alpha) + numToStr(B, v, alpha);
}

function validate(text, alpha) {
  for (const ch of text) {
    if (!alpha.includes(ch)) return ch;
  }
  return null;
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg;
  s.className = 'status ' + (cls || '');
}

function setExplainer(msg) {
  document.getElementById('explainer').innerHTML = msg;
}

function domainStr(r, m) {
  try {
    const v = Math.pow(r, m);
    if (!isFinite(v)) return r + '^' + m;
    return v.toLocaleString();
  } catch(e) { return r + '^' + m; }
}

function doEncrypt() {
  const alpha = getAlphabet();
  const key = parseInt(document.getElementById('key-input').value) || 1;
  const pt = document.getElementById('plaintext').value;
  document.getElementById('dec-value').textContent = '—';
  if (alpha.length < 2) { setStatus('Alphabet must have at least 2 characters.', 'bad'); return; }
  if (pt.length < 2) { setStatus('Plaintext must be at least 2 characters.', 'bad'); return; }
  const bad = validate(pt, alpha);
  if (bad !== null) {
    setStatus(fmt('Character '%bad%' is not in the alphabet.', { bad: bad }), 'bad');
    return;
  }
  const ct = feistelEncrypt(pt, alpha, key);
  document.getElementById('ct-value').textContent = ct;
  setStatus('Encrypted — same alphabet, same length.', 'ok');
  setExplainer(fmt('Radix r = %length%, length m = %length2%. Domain size r^m = %domainStr% possible strings — the Feistel permutes all of them.', { length: alpha.length, length2: pt.length, domainStr: domainStr(alpha.length, pt.length) }));
}

function doDecrypt() {
  const alpha = getAlphabet();
  const key = parseInt(document.getElementById('key-input').value) || 1;
  const ct = document.getElementById('ct-value').textContent;
  if (ct === '—' || ct === '') { setStatus('Encrypt first, then decrypt.', 'bad'); return; }
  const pt2 = feistelDecrypt(ct, alpha, key);
  document.getElementById('dec-value').textContent = pt2;
  const original = document.getElementById('plaintext').value;
  if (pt2 === original) {
    setStatus('Decrypted — matches original plaintext perfectly.', 'ok');
  } else {
    setStatus('Mismatch — key or alphabet changed?', 'bad');
  }
}

function doReset() {
  document.getElementById('alphabet').value = '0123456789';
  document.getElementById('key-input').value = '42';
  document.getElementById('plaintext').value = '4532015112830366';
  document.getElementById('ct-value').textContent = '—';
  document.getElementById('dec-value').textContent = '—';
  setStatus('', '');
  setExplainer('');
}

document.getElementById('btn-enc').addEventListener('click', doEncrypt);
document.getElementById('btn-dec').addEventListener('click', doDecrypt);
document.getElementById('btn-reset').addEventListener('click', doReset);
Result
Console

Notice that Decrypt perfectly recovers the original. The cipher is a bijection on the set of all strings of that length over that alphabet — every plaintext maps to a unique ciphertext and back. The toy Feistel here uses simple arithmetic modular operations, which is exactly the strategy behind the real FF1 and FF3 standards.

The Real Complexity

Why not just map each plaintext to a random ciphertext and store the lookup table? Because the domain has size rmr^{m}, which for a 16-digit number (r=10r = 10, m=16m = 16) is 101610^{16} entries — storing that table is impossible.

The elegant solution is a Feistel network adapted for an arbitrary radix:

  • Split the string into two halves AA and BB of lengths ⌊m/2⌋\lfloor m/2 \rfloor and ⌈m/2⌉\lceil m/2 \rceil.
  • For each round ii, compute Fi(B)F_{i}(B) — a round function built on AES — and add it modulo the half-domain size to AA, then swap.
  • After enough rounds the composed permutation is indistinguishable from a random permutation on the full domain rmr^{m}.

The challenge is that when mm is odd the two halves have different sizes, so addition must be performed in two different modular rings (r⌊m/2⌋r^{\lfloor m/2 \rfloor} and r⌈m/2⌉r^{\lceil m/2 \rceil}). The NIST-standardized FF1 and FF3 algorithms (NIST SP 800-38G, 2016) handle exactly this with careful number encoding.

Security is proven in the ideal-cipher model: if AES behaves like a random permutation (which cryptographers assume), then after enough Feistel rounds the output is computationally indistinguishable from a truly random permutation on rmr^{m}. This is a standard PRF-to-PRP reduction, the same backbone behind ordinary AES modes.

Like factoring or discrete logarithms, the security of FPE ultimately rests on hardness assumptions — no polynomial-time algorithm is known to break it, but no proof exists that one cannot.

Where It Matters

Format constraints appear everywhere sensitive data meets legacy infrastructure:

  • Payment tokenization (PCI-DSS): replace a 16-digit Primary Account Number (PAN) with a 16-digit token that passes Luhn-check validators and fits existing database columns — zero schema migration.
  • Healthcare (HIPAA): social security numbers and date-of-birth fields are fixed-width; FPE encrypts them in place, keeping all downstream parsers intact.
  • Government and national IDs: national identity numbers, tax identifiers, and passport numbers all have rigid formats that cannot change across systems.
  • Database-level encryption: FPE allows column-level encryption without altering the table schema, making it invisible to the application layer.
  • Tokenization vs. encryption: FPE is deterministic encryption — the same plaintext with the same key always produces the same ciphertext, which enables equality queries on encrypted columns (at the cost of leaking that two records share a value).

The tension between format-preserving and pattern matching is instructive: FPE guarantees the output format, but it cannot hide the structure of the domain (an attacker still knows the ciphertext is a 16-digit number). Semantic security in the full sense requires padding and randomness — FPE trades that for deployability.

Conclusion

Format-preserving encryption is a beautiful example of cryptography engineered around a constraint: the world cannot change its data formats, so the cipher must adapt to them.

The Feistel construction over an arbitrary radix rr and length mm shows that a provably secure permutation can be built on any domain of size rmr^{m} — no lookup table, no schema change, no downstream disruption. FF1 and FF3, standardized by NIST in 2016, are now the backbone of PCI-DSS tokenization worldwide.

But the tradeoff is worth understanding: FPE is deterministic, so equal plaintexts always yield equal ciphertexts. For fields with high entropy — a full credit card number — this is fine. For low-entropy fields — a two-digit age — it leaks information. Like every tool in the cryptographer's kit, FPE is powerful precisely within its intended domain, and dangerous outside it.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/format-preserving-encryption/Content licensed under CC BY-NC 4.0.