Botan  1.11.15
src/lib/misc/fpe_fe1/fpe_fe1.cpp
Go to the documentation of this file.
00001 /*
00002 * Format Preserving Encryption (FE1 scheme)
00003 * (C) 2009 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/fpe_fe1.h>
00009 #include <botan/numthry.h>
00010 #include <botan/hmac.h>
00011 #include <botan/sha2_32.h>
00012 #include <stdexcept>
00013 
00014 namespace Botan {
00015 
00016 namespace FPE {
00017 
00018 namespace {
00019 
00020 // Normally FPE is for SSNs, CC#s, etc, nothing too big
00021 const size_t MAX_N_BYTES = 128/8;
00022 
00023 /*
00024 * Factor n into a and b which are as close together as possible.
00025 * Assumes n is composed mostly of small factors which is the case for
00026 * typical uses of FPE (typically, n is a power of 10)
00027 *
00028 * Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b
00029 * then this is always 3
00030 */
00031 void factor(BigInt n, BigInt& a, BigInt& b)
00032    {
00033    a = 1;
00034    b = 1;
00035 
00036    size_t n_low_zero = low_zero_bits(n);
00037 
00038    a <<= (n_low_zero / 2);
00039    b <<= n_low_zero - (n_low_zero / 2);
00040    n >>= n_low_zero;
00041 
00042    for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
00043       {
00044       while(n % PRIMES[i] == 0)
00045          {
00046          a *= PRIMES[i];
00047          if(a > b)
00048             std::swap(a, b);
00049          n /= PRIMES[i];
00050          }
00051       }
00052 
00053    if(a > b)
00054       std::swap(a, b);
00055    a *= n;
00056    if(a < b)
00057       std::swap(a, b);
00058 
00059    if(a <= 1 || b <= 1)
00060       throw std::runtime_error("Could not factor n for use in FPE");
00061    }
00062 
00063 /*
00064 * According to a paper by Rogaway, Bellare, etc, the min safe number
00065 * of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1
00066 * so 3 rounds is safe. The FPE factorization routine should always
00067 * return a >= b, so just confirm that and return 3.
00068 */
00069 size_t rounds(const BigInt& a, const BigInt& b)
00070    {
00071    if(a < b)
00072       throw std::logic_error("FPE rounds: a < b");
00073    return 3;
00074    }
00075 
00076 /*
00077 * A simple round function based on HMAC(SHA-256)
00078 */
00079 class FPE_Encryptor
00080    {
00081    public:
00082       FPE_Encryptor(const SymmetricKey& key,
00083                     const BigInt& n,
00084                     const std::vector<byte>& tweak);
00085 
00086       BigInt operator()(size_t i, const BigInt& R);
00087 
00088    private:
00089       std::unique_ptr<MessageAuthenticationCode> mac;
00090       std::vector<byte> mac_n_t;
00091    };
00092 
00093 FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key,
00094                              const BigInt& n,
00095                              const std::vector<byte>& tweak)
00096    {
00097    mac.reset(new HMAC(new SHA_256));
00098    mac->set_key(key);
00099 
00100    std::vector<byte> n_bin = BigInt::encode(n);
00101 
00102    if(n_bin.size() > MAX_N_BYTES)
00103       throw std::runtime_error("N is too large for FPE encryption");
00104 
00105    mac->update_be(static_cast<u32bit>(n_bin.size()));
00106    mac->update(&n_bin[0], n_bin.size());
00107 
00108    mac->update_be(static_cast<u32bit>(tweak.size()));
00109    mac->update(&tweak[0], tweak.size());
00110 
00111    mac_n_t = unlock(mac->final());
00112    }
00113 
00114 BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R)
00115    {
00116    secure_vector<byte> r_bin = BigInt::encode_locked(R);
00117 
00118    mac->update(mac_n_t);
00119    mac->update_be(static_cast<u32bit>(round_no));
00120 
00121    mac->update_be(static_cast<u32bit>(r_bin.size()));
00122    mac->update(&r_bin[0], r_bin.size());
00123 
00124    secure_vector<byte> X = mac->final();
00125    return BigInt(&X[0], X.size());
00126    }
00127 
00128 }
00129 
00130 /*
00131 * Generic Z_n FPE encryption, FE1 scheme
00132 */
00133 BigInt fe1_encrypt(const BigInt& n, const BigInt& X0,
00134                    const SymmetricKey& key,
00135                    const std::vector<byte>& tweak)
00136    {
00137    FPE_Encryptor F(key, n, tweak);
00138 
00139    BigInt a, b;
00140    factor(n, a, b);
00141 
00142    const size_t r = rounds(a, b);
00143 
00144    BigInt X = X0;
00145 
00146    for(size_t i = 0; i != r; ++i)
00147       {
00148       BigInt L = X / b;
00149       BigInt R = X % b;
00150 
00151       BigInt W = (L + F(i, R)) % a;
00152       X = a * R + W;
00153       }
00154 
00155    return X;
00156    }
00157 
00158 /*
00159 * Generic Z_n FPE decryption, FD1 scheme
00160 */
00161 BigInt fe1_decrypt(const BigInt& n, const BigInt& X0,
00162                    const SymmetricKey& key,
00163                    const std::vector<byte>& tweak)
00164    {
00165    FPE_Encryptor F(key, n, tweak);
00166 
00167    BigInt a, b;
00168    factor(n, a, b);
00169 
00170    const size_t r = rounds(a, b);
00171 
00172    BigInt X = X0;
00173 
00174    for(size_t i = 0; i != r; ++i)
00175       {
00176       BigInt W = X % a;
00177       BigInt R = X / a;
00178 
00179       BigInt L = (W - F(r-i-1, R)) % a;
00180       X = b * L + R;
00181       }
00182 
00183    return X;
00184    }
00185 
00186 }
00187 
00188 }