Botan  2.7.0
Crypto and TLS for C++11
fpe_fe1.cpp
Go to the documentation of this file.
1 /*
2 * Format Preserving Encryption (FE1 scheme)
3 * (C) 2009,2018 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/divide.h>
11 #include <botan/reducer.h>
12 #include <botan/mac.h>
13 
14 namespace Botan {
15 
16 namespace {
17 
18 // Normally FPE is for SSNs, CC#s, etc, nothing too big
19 const size_t MAX_N_BYTES = 128/8;
20 
21 /*
22 * Factor n into a and b which are as close together as possible.
23 * Assumes n is composed mostly of small factors which is the case for
24 * typical uses of FPE (typically, n is a power of 10)
25 */
26 void factor(BigInt n, BigInt& a, BigInt& b)
27  {
28  a = 1;
29  b = 1;
30 
31  size_t n_low_zero = low_zero_bits(n);
32 
33  a <<= (n_low_zero / 2);
34  b <<= n_low_zero - (n_low_zero / 2);
35  n >>= n_low_zero;
36 
37  for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
38  {
39  while(n % PRIMES[i] == 0)
40  {
41  a *= PRIMES[i];
42  if(a > b)
43  std::swap(a, b);
44  n /= PRIMES[i];
45  }
46  }
47 
48  if(a > b)
49  std::swap(a, b);
50  a *= n;
51 
52  if(a <= 1 || b <= 1)
53  throw Exception("Could not factor n for use in FPE");
54  }
55 
56 }
57 
59  size_t rounds,
60  bool compat_mode,
61  const std::string& mac_algo) :
62  m_rounds(rounds)
63  {
64  if(m_rounds < 3)
65  throw Invalid_Argument("FPE_FE1 rounds too small");
66 
68 
69  m_n_bytes = BigInt::encode(n);
70 
71  if(m_n_bytes.size() > MAX_N_BYTES)
72  throw Exception("N is too large for FPE encryption");
73 
74  factor(n, m_a, m_b);
75 
76  if(compat_mode)
77  {
78  if(m_a < m_b)
79  std::swap(m_a, m_b);
80  }
81  else
82  {
83  if(m_a > m_b)
84  std::swap(m_a, m_b);
85  }
86 
87  mod_a.reset(new Modular_Reducer(m_a));
88  }
89 
91  {
92  // for ~unique_ptr
93  }
94 
96  {
97  m_mac->clear();
98  }
99 
100 std::string FPE_FE1::name() const
101  {
102  return "FPE_FE1(" + m_mac->name() + "," + std::to_string(m_rounds) + ")";
103  }
104 
106  {
107  return m_mac->key_spec();
108  }
109 
110 void FPE_FE1::key_schedule(const uint8_t key[], size_t length)
111  {
112  m_mac->set_key(key, length);
113  }
114 
115 BigInt FPE_FE1::F(const BigInt& R, size_t round,
116  const secure_vector<uint8_t>& tweak_mac,
117  secure_vector<uint8_t>& tmp) const
118  {
119  tmp = BigInt::encode_locked(R);
120 
121  m_mac->update(tweak_mac);
122  m_mac->update_be(static_cast<uint32_t>(round));
123 
124  m_mac->update_be(static_cast<uint32_t>(tmp.size()));
125  m_mac->update(tmp.data(), tmp.size());
126 
127  tmp = m_mac->final();
128  return BigInt(tmp.data(), tmp.size());
129  }
130 
131 secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const
132  {
133  m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size()));
134  m_mac->update(m_n_bytes.data(), m_n_bytes.size());
135 
136  m_mac->update_be(static_cast<uint32_t>(tweak_len));
137  m_mac->update(tweak, tweak_len);
138 
139  return m_mac->final();
140  }
141 
142 BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
143  {
144  const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
145 
146  BigInt X = input;
147 
149 
150  BigInt L, R, Fi;
151  for(size_t i = 0; i != m_rounds; ++i)
152  {
153  divide(X, m_b, L, R);
154  Fi = F(R, i, tweak_mac, tmp);
155  X = m_a * R + mod_a->reduce(L + Fi);
156  }
157 
158  return X;
159  }
160 
161 BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
162  {
163  const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
164 
165  BigInt X = input;
167 
168  BigInt W, R, Fi;
169  for(size_t i = 0; i != m_rounds; ++i)
170  {
171  divide(X, m_a, R, W);
172 
173  Fi = F(R, m_rounds-i-1, tweak_mac, tmp);
174  X = m_b * mod_a->reduce(W - Fi) + R;
175  }
176 
177  return X;
178  }
179 
180 BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const
181  {
182  uint8_t tweak8[8];
183  store_be(tweak, tweak8);
184  return encrypt(x, tweak8, sizeof(tweak8));
185  }
186 
187 BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const
188  {
189  uint8_t tweak8[8];
190  store_be(tweak, tweak8);
191  return decrypt(x, tweak8, sizeof(tweak8));
192  }
193 
194 namespace FPE {
195 
196 BigInt fe1_encrypt(const BigInt& n, const BigInt& X,
197  const SymmetricKey& key,
198  const std::vector<uint8_t>& tweak)
199  {
200  FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
201  fpe.set_key(key);
202  return fpe.encrypt(X, tweak.data(), tweak.size());
203  }
204 
205 BigInt fe1_decrypt(const BigInt& n, const BigInt& X,
206  const SymmetricKey& key,
207  const std::vector<uint8_t>& tweak)
208  {
209  FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
210  fpe.set_key(key);
211  return fpe.decrypt(X, tweak.data(), tweak.size());
212  }
213 
214 }
215 
216 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:269
fe X
Definition: ge.cpp:27
const uint16_t PRIMES[]
Definition: primes.cpp:12
std::string name() const override
Definition: fpe_fe1.cpp:100
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:24
void clear() override
Definition: fpe_fe1.cpp:95
BigInt fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:196
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:434
FPE_FE1(const BigInt &n, size_t rounds=5, bool compat_mode=false, const std::string &mac_algo="HMAC(SHA-256)")
Definition: fpe_fe1.cpp:58
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:210
void divide(const BigInt &x, const BigInt &y_arg, BigInt &q, BigInt &r)
Definition: divide.cpp:58
static secure_vector< uint8_t > encode_locked(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:68
void set_key(const SymmetricKey &key)
Definition: sym_algo.h:65
Definition: alg_id.cpp:13
BigInt decrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition: fpe_fe1.cpp:161
BigInt encrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition: fpe_fe1.cpp:142
static std::unique_ptr< MessageAuthenticationCode > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: mac.cpp:141
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
static std::vector< uint8_t > encode(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:54
Key_Length_Specification key_spec() const override
Definition: fpe_fe1.cpp:105
BigInt fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:205