<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Format Preserving Encryption — Botan</title>
<link rel="stylesheet" href="_static/agogo.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: './',
VERSION: '1.10.17',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="top" title="Botan" href="contents.html" />
<link rel="next" title="Python Binding" href="python.html" />
<link rel="prev" title="Random Number Generators" href="rng.html" />
</head>
<body role="document">
<div class="header-wrapper">
<div class="header">
<h1>Botan</h1>
</div>
</div>
<div class="content-wrapper">
<div class="content">
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="format-preserving-encryption">
<h1>Format Preserving Encryption<a class="headerlink" href="#format-preserving-encryption" title="Permalink to this headline">¶</a></h1>
<div class="versionadded">
<p><span class="versionmodified">New in version 1.9.17.</span></p>
</div>
<p>Format preserving encryption (FPE) refers to a set of techniques for
encrypting data such that the ciphertext has the same format as the
plaintext. For instance, you can use FPE to encrypt credit card
numbers with valid checksums such that the ciphertext is also an
credit card number with a valid checksum, or similiarly for bank
account numbers, US Social Security numbers, or even more general
mappings like English words onto other English words.</p>
<p>The scheme currently implemented in botan is called FE1, and described
in the paper <a class="reference external" href="http://eprint.iacr.org/2009/251">Format Preserving Encryption</a> by Mihir Bellare, Thomas
Ristenpart, Phillip Rogaway, and Till Stegers. FPE is an area of
ongoing standardization and it is likely that other schemes will be
included in the future.</p>
<p>To use FE1, use these functions, from <code class="docutils literal"><span class="pre">fpe_fe1.h</span></code>:</p>
<dl class="function">
<dt id="_CPPv2N3FPE11fe1_encryptERK6BigIntRK6BigIntRK12SymmetricKeyRK12MemoryRegionI4byteE">
<span id="FPE::fe1_encrypt__BigIntCR.BigIntCR.SymmetricKeyCR.MemoryRegion:byte:CR"></span>BigInt <code class="descclassname">FPE::</code><code class="descname">fe1_encrypt</code><span class="sig-paren">(</span><em class="property">const</em> BigInt &<em>n</em>, <em class="property">const</em> BigInt &<em>X</em>, <em class="property">const</em> SymmetricKey &<em>key</em>, <em class="property">const</em> MemoryRegion<byte> &<em>tweak</em><span class="sig-paren">)</span><a class="headerlink" href="#_CPPv2N3FPE11fe1_encryptERK6BigIntRK6BigIntRK12SymmetricKeyRK12MemoryRegionI4byteE" title="Permalink to this definition">¶</a></dt>
<dd><p>Encrypts the value <em>X</em> modulo the value <em>n</em> using the <em>key</em> and
<em>tweak</em> specified. Returns an integer less than <em>n</em>. The <em>tweak</em> is
a value that does not need to be secret that parameterizes the
encryption function. For instance, if you were encrypting a
database column with a single key, you could use a per-row-unique
integer index value as the tweak.</p>
<p>To encrypt an arbitrary value using FE1, you need to use a ranking
method. Basically, the idea is to assign an integer to every value
you might encrypt. For instance, a 16 digit credit card number
consists of a 15 digit code plus a 1 digit checksum. So to encrypt
a credit card number, you first remove the checksum, encrypt the 15
digit value modulo 10<sup>15</sup>, and then calculate what the
checksum is for the new (ciphertext) number.</p>
</dd></dl>
<dl class="function">
<dt id="_CPPv2N3FPE11fe1_decryptERK6BigIntRK6BigIntRK12SymmetricKeyRK12MemoryRegionI4byteE">
<span id="FPE::fe1_decrypt__BigIntCR.BigIntCR.SymmetricKeyCR.MemoryRegion:byte:CR"></span>BigInt <code class="descclassname">FPE::</code><code class="descname">fe1_decrypt</code><span class="sig-paren">(</span><em class="property">const</em> BigInt &<em>n</em>, <em class="property">const</em> BigInt &<em>X</em>, <em class="property">const</em> SymmetricKey &<em>key</em>, <em class="property">const</em> MemoryRegion<byte> &<em>tweak</em><span class="sig-paren">)</span><a class="headerlink" href="#_CPPv2N3FPE11fe1_decryptERK6BigIntRK6BigIntRK12SymmetricKeyRK12MemoryRegionI4byteE" title="Permalink to this definition">¶</a></dt>
<dd><p>Decrypts an FE1 ciphertext produced by <a class="reference internal" href="#_CPPv2N3FPE11fe1_encryptERK6BigIntRK6BigIntRK12SymmetricKeyRK12MemoryRegionI4byteE" title="FPE::fe1_encrypt"><code class="xref cpp cpp-func docutils literal"><span class="pre">fe1_encrypt</span></code></a>; the
<em>n</em>, <em>key</em> and <em>tweak</em> should be the same as that provided to the
encryption function. Returns the plaintext.</p>
<p>Note that there is not any implicit authentication or checking of
data, so if you provide an incorrect key or tweak the result is
simply a random integer.</p>
</dd></dl>
<p>This example encrypts a credit card number with a valid
<a class="reference external" href="http://en.wikipedia.org/wiki/Luhn_algorithm">Luhn checksum</a> to
another number with the same format, including a correct checksum.</p>
<div class="highlight-cpp"><div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf"><botan/botan.h></span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf"><botan/fpe_fe1.h></span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf"><botan/sha160.h></span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">Botan</span><span class="p">;</span>
<span class="cp">#include</span> <span class="cpf"><iostream></span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf"><stdexcept></span><span class="cp"></span>
<span class="k">namespace</span> <span class="p">{</span>
<span class="n">byte</span> <span class="n">luhn_checksum</span><span class="p">(</span><span class="n">u64bit</span> <span class="n">cc_number</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">byte</span> <span class="n">sum</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="kt">bool</span> <span class="n">alt</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
<span class="k">while</span><span class="p">(</span><span class="n">cc_number</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">byte</span> <span class="n">digit</span> <span class="o">=</span> <span class="n">cc_number</span> <span class="o">%</span> <span class="mi">10</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">alt</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">digit</span> <span class="o">*=</span> <span class="mi">2</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">digit</span> <span class="o">></span> <span class="mi">9</span><span class="p">)</span>
<span class="n">digit</span> <span class="o">-=</span> <span class="mi">9</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">sum</span> <span class="o">+=</span> <span class="n">digit</span><span class="p">;</span>
<span class="n">cc_number</span> <span class="o">/=</span> <span class="mi">10</span><span class="p">;</span>
<span class="n">alt</span> <span class="o">=</span> <span class="o">!</span><span class="n">alt</span><span class="p">;</span>
<span class="p">}</span>
<span class="k">return</span> <span class="p">(</span><span class="n">sum</span> <span class="o">%</span> <span class="mi">10</span><span class="p">);</span>
<span class="p">}</span>
<span class="kt">bool</span> <span class="n">luhn_check</span><span class="p">(</span><span class="n">u64bit</span> <span class="n">cc_number</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">return</span> <span class="p">(</span><span class="n">luhn_checksum</span><span class="p">(</span><span class="n">cc_number</span><span class="p">)</span> <span class="o">==</span> <span class="mi">0</span><span class="p">);</span>
<span class="p">}</span>
<span class="n">u64bit</span> <span class="n">cc_rank</span><span class="p">(</span><span class="n">u64bit</span> <span class="n">cc_number</span><span class="p">)</span>
<span class="p">{</span>
<span class="c1">// Remove Luhn checksum</span>
<span class="k">return</span> <span class="n">cc_number</span> <span class="o">/</span> <span class="mi">10</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">u64bit</span> <span class="n">cc_derank</span><span class="p">(</span><span class="n">u64bit</span> <span class="n">cc_number</span><span class="p">)</span>
<span class="p">{</span>
<span class="k">for</span><span class="p">(</span><span class="n">u32bit</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">!=</span> <span class="mi">10</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
<span class="k">if</span><span class="p">(</span><span class="n">luhn_check</span><span class="p">(</span><span class="n">cc_number</span> <span class="o">*</span> <span class="mi">10</span> <span class="o">+</span> <span class="n">i</span><span class="p">))</span>
<span class="k">return</span> <span class="p">(</span><span class="n">cc_number</span> <span class="o">*</span> <span class="mi">10</span> <span class="o">+</span> <span class="n">i</span><span class="p">);</span>
<span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
<span class="cm">/*</span>
<span class="cm">* Use the SHA-1 hash of the account name or ID as a tweak</span>
<span class="cm">*/</span>
<span class="n">SecureVector</span><span class="o"><</span><span class="n">byte</span><span class="o">></span> <span class="n">sha1</span><span class="p">(</span><span class="k">const</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span><span class="o">&</span> <span class="n">acct_name</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">SHA_160</span> <span class="n">hash</span><span class="p">;</span>
<span class="n">hash</span><span class="p">.</span><span class="n">update</span><span class="p">(</span><span class="n">acct_name</span><span class="p">);</span>
<span class="k">return</span> <span class="n">hash</span><span class="p">.</span><span class="k">final</span><span class="p">();</span>
<span class="p">}</span>
<span class="n">u64bit</span> <span class="n">encrypt_cc_number</span><span class="p">(</span><span class="n">u64bit</span> <span class="n">cc_number</span><span class="p">,</span>
<span class="k">const</span> <span class="n">SymmetricKey</span><span class="o">&</span> <span class="n">key</span><span class="p">,</span>
<span class="k">const</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span><span class="o">&</span> <span class="n">acct_name</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">BigInt</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">1000000000000000</span><span class="p">;</span>
<span class="n">u64bit</span> <span class="n">cc_ranked</span> <span class="o">=</span> <span class="n">cc_rank</span><span class="p">(</span><span class="n">cc_number</span><span class="p">);</span>
<span class="n">BigInt</span> <span class="n">c</span> <span class="o">=</span> <span class="n">FPE</span><span class="o">::</span><span class="n">fe1_encrypt</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">cc_ranked</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">sha1</span><span class="p">(</span><span class="n">acct_name</span><span class="p">));</span>
<span class="k">if</span><span class="p">(</span><span class="n">c</span><span class="p">.</span><span class="n">bits</span><span class="p">()</span> <span class="o">></span> <span class="mi">50</span><span class="p">)</span>
<span class="k">throw</span> <span class="n">std</span><span class="o">::</span><span class="n">runtime_error</span><span class="p">(</span><span class="s">"FPE produced a number too large"</span><span class="p">);</span>
<span class="n">u64bit</span> <span class="n">enc_cc</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">for</span><span class="p">(</span><span class="n">u32bit</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">!=</span> <span class="mi">7</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
<span class="n">enc_cc</span> <span class="o">=</span> <span class="p">(</span><span class="n">enc_cc</span> <span class="o"><<</span> <span class="mi">8</span><span class="p">)</span> <span class="o">|</span> <span class="n">c</span><span class="p">.</span><span class="n">byte_at</span><span class="p">(</span><span class="mi">6</span><span class="o">-</span><span class="n">i</span><span class="p">);</span>
<span class="k">return</span> <span class="nf">cc_derank</span><span class="p">(</span><span class="n">enc_cc</span><span class="p">);</span>
<span class="p">}</span>
<span class="n">u64bit</span> <span class="n">decrypt_cc_number</span><span class="p">(</span><span class="n">u64bit</span> <span class="n">enc_cc</span><span class="p">,</span>
<span class="k">const</span> <span class="n">SymmetricKey</span><span class="o">&</span> <span class="n">key</span><span class="p">,</span>
<span class="k">const</span> <span class="n">std</span><span class="o">::</span><span class="n">string</span><span class="o">&</span> <span class="n">acct_name</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">BigInt</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">1000000000000000</span><span class="p">;</span>
<span class="n">u64bit</span> <span class="n">cc_ranked</span> <span class="o">=</span> <span class="n">cc_rank</span><span class="p">(</span><span class="n">enc_cc</span><span class="p">);</span>
<span class="n">BigInt</span> <span class="n">c</span> <span class="o">=</span> <span class="n">FPE</span><span class="o">::</span><span class="n">fe1_decrypt</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">cc_ranked</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">sha1</span><span class="p">(</span><span class="n">acct_name</span><span class="p">));</span>
<span class="k">if</span><span class="p">(</span><span class="n">c</span><span class="p">.</span><span class="n">bits</span><span class="p">()</span> <span class="o">></span> <span class="mi">50</span><span class="p">)</span>
<span class="k">throw</span> <span class="n">std</span><span class="o">::</span><span class="n">runtime_error</span><span class="p">(</span><span class="s">"FPE produced a number too large"</span><span class="p">);</span>
<span class="n">u64bit</span> <span class="n">dec_cc</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="k">for</span><span class="p">(</span><span class="n">u32bit</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">!=</span> <span class="mi">7</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span>
<span class="n">dec_cc</span> <span class="o">=</span> <span class="p">(</span><span class="n">dec_cc</span> <span class="o"><<</span> <span class="mi">8</span><span class="p">)</span> <span class="o">|</span> <span class="n">c</span><span class="p">.</span><span class="n">byte_at</span><span class="p">(</span><span class="mi">6</span><span class="o">-</span><span class="n">i</span><span class="p">);</span>
<span class="k">return</span> <span class="nf">cc_derank</span><span class="p">(</span><span class="n">dec_cc</span><span class="p">);</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="n">main</span><span class="p">(</span><span class="kt">int</span> <span class="n">argc</span><span class="p">,</span> <span class="kt">char</span><span class="o">*</span> <span class="n">argv</span><span class="p">[])</span>
<span class="p">{</span>
<span class="n">LibraryInitializer</span> <span class="n">init</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">argc</span> <span class="o">!=</span> <span class="mi">4</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="s">"Usage: "</span> <span class="o"><<</span> <span class="n">argv</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o"><<</span> <span class="s">" cc-number acct-name passwd</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">u64bit</span> <span class="n">cc_number</span> <span class="o">=</span> <span class="n">atoll</span><span class="p">(</span><span class="n">argv</span><span class="p">[</span><span class="mi">1</span><span class="p">]);</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">acct_name</span> <span class="o">=</span> <span class="n">argv</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span>
<span class="n">std</span><span class="o">::</span><span class="n">string</span> <span class="n">passwd</span> <span class="o">=</span> <span class="n">argv</span><span class="p">[</span><span class="mi">3</span><span class="p">];</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="s">"Input was: "</span> <span class="o"><<</span> <span class="n">cc_number</span> <span class="o"><<</span> <span class="sc">' '</span>
<span class="o"><<</span> <span class="n">luhn_check</span><span class="p">(</span><span class="n">cc_number</span><span class="p">)</span> <span class="o"><<</span> <span class="sc">'\n'</span><span class="p">;</span>
<span class="cm">/*</span>
<span class="cm"> * In practice something like PBKDF2 with a salt and high iteration</span>
<span class="cm"> * count would be a good idea.</span>
<span class="cm"> */</span>
<span class="n">SymmetricKey</span> <span class="n">key</span> <span class="o">=</span> <span class="n">sha1</span><span class="p">(</span><span class="n">passwd</span><span class="p">);</span>
<span class="n">u64bit</span> <span class="n">enc_cc</span> <span class="o">=</span> <span class="n">encrypt_cc_number</span><span class="p">(</span><span class="n">cc_number</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">acct_name</span><span class="p">);</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="s">"Encrypted: "</span> <span class="o"><<</span> <span class="n">enc_cc</span>
<span class="o"><<</span> <span class="sc">' '</span> <span class="o"><<</span> <span class="n">luhn_check</span><span class="p">(</span><span class="n">enc_cc</span><span class="p">)</span> <span class="o"><<</span> <span class="sc">'\n'</span><span class="p">;</span>
<span class="n">u64bit</span> <span class="n">dec_cc</span> <span class="o">=</span> <span class="n">decrypt_cc_number</span><span class="p">(</span><span class="n">enc_cc</span><span class="p">,</span> <span class="n">key</span><span class="p">,</span> <span class="n">acct_name</span><span class="p">);</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="s">"Decrypted: "</span> <span class="o"><<</span> <span class="n">dec_cc</span>
<span class="o"><<</span> <span class="sc">' '</span> <span class="o"><<</span> <span class="n">luhn_check</span><span class="p">(</span><span class="n">dec_cc</span><span class="p">)</span> <span class="o"><<</span> <span class="sc">'\n'</span><span class="p">;</span>
<span class="k">if</span><span class="p">(</span><span class="n">dec_cc</span> <span class="o">!=</span> <span class="n">cc_number</span><span class="p">)</span>
<span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o"><<</span> <span class="s">"Something went wrong :( Bad CC checksum?</span><span class="se">\n</span><span class="s">"</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="sidebar">
<h3>Table Of Contents</h3>
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="index.html">Welcome</a></li>
<li class="toctree-l1"><a class="reference internal" href="reading.html">Recommended Reading</a></li>
<li class="toctree-l1"><a class="reference internal" href="building.html">Building The Library</a></li>
<li class="toctree-l1"><a class="reference internal" href="firststep.html">Getting Started</a></li>
<li class="toctree-l1"><a class="reference internal" href="filters.html">Information Flow: Pipes and Filters</a></li>
<li class="toctree-l1"><a class="reference internal" href="pubkey.html">Public Key Cryptography</a></li>
<li class="toctree-l1"><a class="reference internal" href="x509.html">Certificate Handling</a></li>
<li class="toctree-l1"><a class="reference internal" href="ssl.html">SSL and TLS</a></li>
<li class="toctree-l1"><a class="reference internal" href="bigint.html">BigInt</a></li>
<li class="toctree-l1"><a class="reference internal" href="lowlevel.html">The Low-Level Interface</a></li>
<li class="toctree-l1"><a class="reference internal" href="secmem.html">Secure Memory Containers</a></li>
<li class="toctree-l1"><a class="reference internal" href="kdf.html">Key Derivation Functions</a></li>
<li class="toctree-l1"><a class="reference internal" href="pbkdf.html">PBKDF Algorithms</a></li>
<li class="toctree-l1"><a class="reference internal" href="passhash.html">Password Hashing</a></li>
<li class="toctree-l1"><a class="reference internal" href="rng.html">Random Number Generators</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Format Preserving Encryption</a></li>
<li class="toctree-l1"><a class="reference internal" href="python.html">Python Binding</a></li>
</ul>
<div role="search">
<h3 style="margin-top: 1.5em;">Search</h3>
<form class="search" action="search.html" method="get">
<input type="text" name="q" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div>
<div class="clearer"></div>
</div>
</div>
<div class="footer-wrapper">
<div class="footer">
<div class="left">
<div role="navigation" aria-label="related navigaton">
<a href="rng.html" title="Random Number Generators"
accesskey="P">previous</a> |
<a href="python.html" title="Python Binding"
accesskey="N">next</a> |
<a href="genindex.html" title="General Index"
accesskey="I">index</a>
</div>
<div role="note" aria-label="source link">
<br/>
<a href="_sources/fpe.txt"
rel="nofollow">Show Source</a>
</div>
</div>
<div class="right">
<div class="footer" role="contentinfo">
© Copyright 2000-2011, Jack Lloyd.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.4.9.
</div>
</div>
<div class="clearer"></div>
</div>
</div>
</body>
</html>
