Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

fpe_fe1.cpp
Go to the documentation of this file.
1 /*
2 * Format Preserving Encryption (FE1 scheme)
3 * (C) 2009 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7
8 #include <botan/fpe_fe1.h>
9 #include <botan/numthry.h>
10 #include <botan/hmac.h>
11 #include <botan/sha2_32.h>
12
13 namespace Botan {
14
15 namespace FPE {
16
17 namespace {
18
19 // Normally FPE is for SSNs, CC#s, etc, nothing too big
20 const size_t MAX_N_BYTES = 128/8;
21
22 /*
23 * Factor n into a and b which are as close together as possible.
24 * Assumes n is composed mostly of small factors which is the case for
25 * typical uses of FPE (typically, n is a power of 10)
26 *
27 * Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b
28 * then this is always 3
29 */
30 void factor(BigInt n, BigInt& a, BigInt& b)
31 {
32 a = 1;
33 b = 1;
34
35 size_t n_low_zero = low_zero_bits(n);
36
37 a <<= (n_low_zero / 2);
38 b <<= n_low_zero - (n_low_zero / 2);
39 n >>= n_low_zero;
40
41 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
42 {
43 while(n % PRIMES[i] == 0)
44 {
45 a *= PRIMES[i];
46 if(a > b)
47 std::swap(a, b);
48 n /= PRIMES[i];
49 }
50 }
51
52 if(a > b)
53 std::swap(a, b);
54 a *= n;
55 if(a < b)
56 std::swap(a, b);
57
58 if(a <= 1 || b <= 1)
59 throw Exception("Could not factor n for use in FPE");
60 }
61
62 /*
63 * According to a paper by Rogaway, Bellare, etc, the min safe number
64 * of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1
65 * so 3 rounds is safe. The FPE factorization routine should always
66 * return a >= b, so just confirm that and return 3.
67 */
68 size_t rounds(const BigInt& a, const BigInt& b)
69 {
70 if(a < b)
71 throw Internal_Error("FPE rounds: a < b");
72 return 3;
73 }
74
75 /*
76 * A simple round function based on HMAC(SHA-256)
77 */
78 class FPE_Encryptor
79 {
80 public:
81 FPE_Encryptor(const SymmetricKey& key,
82 const BigInt& n,
83 const std::vector<uint8_t>& tweak);
84
85 BigInt operator()(size_t i, const BigInt& R);
86
87 private:
88 std::unique_ptr<MessageAuthenticationCode> m_mac;
89 std::vector<uint8_t> m_mac_n_t;
90 };
91
92 FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key,
93 const BigInt& n,
94 const std::vector<uint8_t>& tweak)
95 {
96 m_mac.reset(new HMAC(new SHA_256));
97 m_mac->set_key(key);
98
99 std::vector<uint8_t> n_bin = BigInt::encode(n);
100
101 if(n_bin.size() > MAX_N_BYTES)
102 throw Exception("N is too large for FPE encryption");
103
104 m_mac->update_be(static_cast<uint32_t>(n_bin.size()));
105 m_mac->update(n_bin.data(), n_bin.size());
106
107 m_mac->update_be(static_cast<uint32_t>(tweak.size()));
108 m_mac->update(tweak.data(), tweak.size());
109
110 m_mac_n_t = unlock(m_mac->final());
111 }
112
113 BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R)
114 {
115 secure_vector<uint8_t> r_bin = BigInt::encode_locked(R);
116
117 m_mac->update(m_mac_n_t);
118 m_mac->update_be(static_cast<uint32_t>(round_no));
119
120 m_mac->update_be(static_cast<uint32_t>(r_bin.size()));
121 m_mac->update(r_bin.data(), r_bin.size());
122
123 secure_vector<uint8_t> X = m_mac->final();
124 return BigInt(X.data(), X.size());
125 }
126
127 }
128
129 /*
130 * Generic Z_n FPE encryption, FE1 scheme
131 */
132 BigInt fe1_encrypt(const BigInt& n, const BigInt& X0,
133 const SymmetricKey& key,
134 const std::vector<uint8_t>& tweak)
135 {
136 FPE_Encryptor F(key, n, tweak);
137
138 BigInt a, b;
139 factor(n, a, b);
140
141 const size_t r = rounds(a, b);
142
143 BigInt X = X0;
144
145 for(size_t i = 0; i != r; ++i)
146 {
147 BigInt L = X / b;
148 BigInt R = X % b;
149
150 BigInt W = (L + F(i, R)) % a;
151 X = a * R + W;
152 }
153
154 return X;
155 }
156
157 /*
158 * Generic Z_n FPE decryption, FD1 scheme
159 */
160 BigInt fe1_decrypt(const BigInt& n, const BigInt& X0,
161 const SymmetricKey& key,
162 const std::vector<uint8_t>& tweak)
163 {
164 FPE_Encryptor F(key, n, tweak);
165
166 BigInt a, b;
167 factor(n, a, b);
168
169 const size_t r = rounds(a, b);
170
171 BigInt X = X0;
172
173 for(size_t i = 0; i != r; ++i)
174 {
175 BigInt W = X % a;
176 BigInt R = X / a;
177
178 BigInt L = (W - F(r-i-1, R)) % a;
179 X = b * L + R;
180 }
181
182 return X;
183 }
184
185 }
186
187 }
Botan::PRIME_TABLE_SIZE
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
Botan::PRIMES
const uint16_t BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
Botan::Exception
Definition: exceptn.h:21
Botan::OctetString
Definition: symkey.h:19
Botan::BigInt
Definition: bigint.h:23
m_mac
std::unique_ptr< MessageAuthenticationCode > m_mac
Definition: fpe_fe1.cpp:88
Botan::Internal_Error
Definition: exceptn.h:88
Botan::BigInt::encode_locked
static secure_vector< uint8_t > encode_locked(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:68
Botan::FPE::fe1_decrypt
BigInt fe1_decrypt(const BigInt &n, const BigInt &X0, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:160
Botan
Definition: alg_id.cpp:13
Botan::SymmetricKey
OctetString SymmetricKey
Definition: symkey.h:136
Botan::low_zero_bits
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:20
Botan::unlock
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:125
Botan::BigInt::encode
static std::vector< uint8_t > encode(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:54
Botan::FPE::fe1_encrypt
BigInt fe1_encrypt(const BigInt &n, const BigInt &X0, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:132
m_mac_n_t
std::vector< uint8_t > m_mac_n_t
Definition: fpe_fe1.cpp:89