diff options
Diffstat (limited to 'src/lib/constructs/fpe_fe1')
| -rw-r--r-- | src/lib/constructs/fpe_fe1/fpe_fe1.cpp | 193 | ||||
| -rw-r--r-- | src/lib/constructs/fpe_fe1/fpe_fe1.h | 44 | ||||
| -rw-r--r-- | src/lib/constructs/fpe_fe1/info.txt | 7 |
3 files changed, 244 insertions, 0 deletions
diff --git a/src/lib/constructs/fpe_fe1/fpe_fe1.cpp b/src/lib/constructs/fpe_fe1/fpe_fe1.cpp new file mode 100644 index 000000000..b22d3a8df --- /dev/null +++ b/src/lib/constructs/fpe_fe1/fpe_fe1.cpp @@ -0,0 +1,193 @@ +/* +* Format Preserving Encryption using the scheme FE1 from the paper +* "Format-Preserving Encryption" by Bellare, Rogaway, et al +* (http://eprint.iacr.org/2009/251) +* +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/fpe_fe1.h> +#include <botan/numthry.h> +#include <botan/hmac.h> +#include <botan/sha2_32.h> +#include <stdexcept> + +namespace Botan { + +namespace FPE { + +namespace { + +// Normally FPE is for SSNs, CC#s, etc, nothing too big +const size_t MAX_N_BYTES = 128/8; + +/* +* Factor n into a and b which are as close together as possible. +* Assumes n is composed mostly of small factors which is the case for +* typical uses of FPE (typically, n is a power of 10) +* +* Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b +* then this is always 3 +*/ +void factor(BigInt n, BigInt& a, BigInt& b) + { + a = 1; + b = 1; + + size_t n_low_zero = low_zero_bits(n); + + a <<= (n_low_zero / 2); + b <<= n_low_zero - (n_low_zero / 2); + n >>= n_low_zero; + + for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) + { + while(n % PRIMES[i] == 0) + { + a *= PRIMES[i]; + if(a > b) + std::swap(a, b); + n /= PRIMES[i]; + } + } + + if(a > b) + std::swap(a, b); + a *= n; + if(a < b) + std::swap(a, b); + + if(a <= 1 || b <= 1) + throw std::runtime_error("Could not factor n for use in FPE"); + } + +/* +* According to a paper by Rogaway, Bellare, etc, the min safe number +* of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1 +* so 3 rounds is safe. The FPE factorization routine should always +* return a >= b, so just confirm that and return 3. +*/ +size_t rounds(const BigInt& a, const BigInt& b) + { + if(a < b) + throw std::logic_error("FPE rounds: a < b"); + return 3; + } + +/* +* A simple round function based on HMAC(SHA-256) +*/ +class FPE_Encryptor + { + public: + FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const std::vector<byte>& tweak); + + ~FPE_Encryptor() { delete mac; } + + BigInt operator()(size_t i, const BigInt& R); + + private: + MessageAuthenticationCode* mac; + std::vector<byte> mac_n_t; + }; + +FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const std::vector<byte>& tweak) + { + mac = new HMAC(new SHA_256); + mac->set_key(key); + + std::vector<byte> n_bin = BigInt::encode(n); + + if(n_bin.size() > MAX_N_BYTES) + throw std::runtime_error("N is too large for FPE encryption"); + + mac->update_be(static_cast<u32bit>(n_bin.size())); + mac->update(&n_bin[0], n_bin.size()); + + mac->update_be(static_cast<u32bit>(tweak.size())); + mac->update(&tweak[0], tweak.size()); + + mac_n_t = unlock(mac->final()); + } + +BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R) + { + secure_vector<byte> r_bin = BigInt::encode_locked(R); + + mac->update(mac_n_t); + mac->update_be(static_cast<u32bit>(round_no)); + + mac->update_be(static_cast<u32bit>(r_bin.size())); + mac->update(&r_bin[0], r_bin.size()); + + secure_vector<byte> X = mac->final(); + return BigInt(&X[0], X.size()); + } + +} + +/* +* Generic Z_n FPE encryption, FE1 scheme +*/ +BigInt fe1_encrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const std::vector<byte>& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const size_t r = rounds(a, b); + + BigInt X = X0; + + for(size_t i = 0; i != r; ++i) + { + BigInt L = X / b; + BigInt R = X % b; + + BigInt W = (L + F(i, R)) % a; + X = a * R + W; + } + + return X; + } + +/* +* Generic Z_n FPE decryption, FD1 scheme +*/ +BigInt fe1_decrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const std::vector<byte>& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const size_t r = rounds(a, b); + + BigInt X = X0; + + for(size_t i = 0; i != r; ++i) + { + BigInt W = X % a; + BigInt R = X / a; + + BigInt L = (W - F(r-i-1, R)) % a; + X = b * L + R; + } + + return X; + } + +} + +} diff --git a/src/lib/constructs/fpe_fe1/fpe_fe1.h b/src/lib/constructs/fpe_fe1/fpe_fe1.h new file mode 100644 index 000000000..66e7f1cfa --- /dev/null +++ b/src/lib/constructs/fpe_fe1/fpe_fe1.h @@ -0,0 +1,44 @@ +/* +* Format Preserving Encryption (FE1 scheme) +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_FPE_FE1_H__ +#define BOTAN_FPE_FE1_H__ + +#include <botan/bigint.h> +#include <botan/symkey.h> + +namespace Botan { + +namespace FPE { + +/** +* Encrypt X from and onto the group Z_n using key and tweak +* @param n the modulus +* @param X the plaintext as a BigInt +* @param key a random key +* @param tweak will modify the ciphertext (think of as an IV) +*/ +BigInt BOTAN_DLL fe1_encrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const std::vector<byte>& tweak); + +/** +* Decrypt X from and onto the group Z_n using key and tweak +* @param n the modulus +* @param X the ciphertext as a BigInt +* @param key is the key used for encryption +* @param tweak the same tweak used for encryption +*/ +BigInt BOTAN_DLL fe1_decrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const std::vector<byte>& tweak); + +} + +} + +#endif diff --git a/src/lib/constructs/fpe_fe1/info.txt b/src/lib/constructs/fpe_fe1/info.txt new file mode 100644 index 000000000..42264e54e --- /dev/null +++ b/src/lib/constructs/fpe_fe1/info.txt @@ -0,0 +1,7 @@ +define FPE_FE1 20131128 + +<requires> +hmac +sha2_32 +bigint +</requires> |