Botan
1.11.15
|
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 }