From a6177d3af54437375c752b8046230b7fb98c8563 Mon Sep 17 00:00:00 2001 From: lloyd Date: Thu, 5 Nov 2009 07:52:35 +0000 Subject: Add format preserving encryption, design is FE1/FD1 from the paper Format-Preserving Encryption (http://eprint.iacr.org/2009/251). This doesn't implement the rank functions which are necessary for the actual format-preserving part, though that would be nice to add to the example. --- doc/examples/fpe.cpp | 22 +++++++ src/fpe/fpe.cpp | 166 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/fpe/fpe.h | 26 ++++++++ src/fpe/info.txt | 13 ++++ 4 files changed, 227 insertions(+) create mode 100644 doc/examples/fpe.cpp create mode 100644 src/fpe/fpe.cpp create mode 100644 src/fpe/fpe.h create mode 100644 src/fpe/info.txt diff --git a/doc/examples/fpe.cpp b/doc/examples/fpe.cpp new file mode 100644 index 000000000..9384a0d2d --- /dev/null +++ b/doc/examples/fpe.cpp @@ -0,0 +1,22 @@ +#include +#include + +using namespace Botan; + +#include + +int main() + { + LibraryInitializer init; + + BigInt n = 100000000; + BigInt x = 49604394; + + SymmetricKey key("AAAAAAAAAAAAAAAA"); + MemoryVector tweak(4); + + BigInt c = fpe_encrypt(n, x, key, tweak); + BigInt p = fpe_decrypt(n, c, key, tweak); + + std::cout << c << ' ' << p << ' ' << x << '\n'; + } diff --git a/src/fpe/fpe.cpp b/src/fpe/fpe.cpp new file mode 100644 index 000000000..b2dbf7eb1 --- /dev/null +++ b/src/fpe/fpe.cpp @@ -0,0 +1,166 @@ +/* +* Format Preserving Encryption +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include +#include + +#include + +namespace Botan { + +namespace { + +// Normally FPE is for SSNs, CC#s, etc, nothing too big +const u32bit MAX_N_BYTES = 128/8; + +void factor(BigInt n, BigInt& a, BigInt& b) + { + a = 1; + b = 1; + + for(u32bit i = 0; i != PRIME_TABLE_SIZE; ++i) + { + while(n % PRIMES[i] == 0) + { + a *= PRIMES[i]; + std::swap(a, b); + n /= PRIMES[i]; + } + } + + a *= n; + + if(a <= 1 || b <= 1) + throw std::runtime_error("Could not factor n for use in FPE"); + } + +u32bit rounds(const BigInt& a, const BigInt& b) + { + return 8; + } + +class FPE_Encryptor + { + public: + FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const MemoryRegion& tweak); + + ~FPE_Encryptor() { delete mac; } + + BigInt operator()(u32bit i, const BigInt& R); + + private: + MessageAuthenticationCode* mac; + SecureVector mac_n_t; + }; + +FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const MemoryRegion& tweak) + { + mac = new HMAC(new SHA_256); + mac->set_key(key); + + SecureVector n_bin = BigInt::encode(n); + + if(n_bin.size() > MAX_N_BYTES) + throw std::runtime_error("N is too large for FPE encryption"); + + for(u32bit i = 0; i != 4; ++i) + mac->update(get_byte(i, n_bin.size())); + mac->update(&n_bin[0], n_bin.size()); + + for(u32bit i = 0; i != 4; ++i) + mac->update(get_byte(i, tweak.size())); + mac->update(&tweak[0], tweak.size()); + + mac_n_t = mac->final(); + } + +BigInt FPE_Encryptor::operator()(u32bit round_no, const BigInt& R) + { + mac->update(mac_n_t); + + for(u32bit i = 0; i != 4; ++i) + mac->update(get_byte(i, round_no)); + + SecureVector r_bin = BigInt::encode(R); + + for(u32bit i = 0; i != 4; ++i) + mac->update(get_byte(i, r_bin.size())); + mac->update(&r_bin[0], r_bin.size()); + + SecureVector X = mac->final(); + return BigInt(&X[0], X.size()); + } + +} + +/** +* Generic Z_n FPE encryption, FE1 scheme +* See http://eprint.iacr.org/2009/251 +*/ +BigInt fpe_encrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const MemoryRegion& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const u32bit r = rounds(a, b); + + BigInt X = X0; + + for(u32bit 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 +* See http://eprint.iacr.org/2009/251 +*/ +BigInt fpe_decrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const MemoryRegion& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const u32bit r = rounds(a, b); + + BigInt X = X0; + + for(u32bit i = 0; i != r; ++i) + { + BigInt W = X % a; + BigInt R = X / a; + + BigInt L = (W - F(r-i, R)) % a; + X = b*L + R; + } + + return X; + } + +} diff --git a/src/fpe/fpe.h b/src/fpe/fpe.h new file mode 100644 index 000000000..677304b1d --- /dev/null +++ b/src/fpe/fpe.h @@ -0,0 +1,26 @@ +/* +* Format Preserving Encryption +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_FORMAT_PRESERVING_ENCRYPTION_H__ +#define BOTAN_FORMAT_PRESERVING_ENCRYPTION_H__ + +#include +#include + +namespace Botan { + +BigInt fpe_encrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const MemoryRegion& tweak); + +BigInt fpe_decrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const MemoryRegion& tweak); + +} + +#endif diff --git a/src/fpe/info.txt b/src/fpe/info.txt new file mode 100644 index 000000000..f7a8c4ae4 --- /dev/null +++ b/src/fpe/info.txt @@ -0,0 +1,13 @@ +define FORMAT_PRESERVING_ENCRYPTION + +load_on auto + + +fpe.cpp +fpe.h + + + +cbc_mac +bigint + -- cgit v1.2.3