Format-Preserving Encryption

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 $r$ (called the radix) and an arbitrary message length $m$? That is the algorithmic puzzle at the heart of FPE.

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.

<!-- {{c_html_comment}} -->
<div class="fpe-wrap">
  <div class="field-row">
    <label for="alphabet">{{lbl_alphabet}}</label>
    <input id="alphabet" type="text" value="0123456789" maxlength="64" spellcheck="false" placeholder="{{ph_alphabet}}" title="{{title_alphabet}}" aria-label="{{aria_alphabet}}">
  </div>
  <div class="field-row">
    <label for="key-input">{{lbl_key}}</label>
    <input id="key-input" type="number" value="42" min="1" max="9999" title="{{title_key}}" aria-label="{{aria_key}}">
  </div>
  <div class="field-row">
    <label for="plaintext">{{lbl_plaintext}}</label>
    <input id="plaintext" type="text" value="4532015112830366" spellcheck="false" placeholder="{{ph_plaintext}}" title="{{title_plaintext}}" aria-label="{{aria_plaintext}}">
  </div>
  <div class="btns">
    <button id="btn-enc" type="button">{{btn_encrypt}}</button>
    <button id="btn-dec" type="button">{{btn_decrypt}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div class="output-grid">
    <div class="out-box">
      <div class="out-label">{{lbl_ciphertext}}</div>
      <div class="out-value" id="ct-value">&#8212;</div>
    </div>
    <div class="out-box">
      <div class="out-label">{{lbl_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>

/* {{c_css_comment}} */
* { 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; }

// Code not found

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.

Why not just map each plaintext to a random ciphertext and store the lookup table? Because the domain has size $r^{m}$, which for a 16-digit number ($r = 10$, $m = 16$) is $10^{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 $A$ and $B$ of lengths $\lfloor m/2 \rfloor$ and $\lceil m/2 \rceil$.
• For each round $i$, compute $F_{i}(B)$ — a round function built on AES — and add it modulo the half-domain size to $A$, then swap.
• After enough rounds the composed permutation is indistinguishable from a random permutation on the full domain $r^{m}$.

The challenge is that when $m$ is odd the two halves have different sizes, so addition must be performed in two different modular rings ($r^{\lfloor m/2 \rfloor}$ and $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 $r^{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.

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.

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 $r$ and length $m$ shows that a provably secure permutation can be built on any domain of size $r^{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.