Botan  2.13.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/loadstor.h>
10 #include <botan/numthry.h>
11 #include <botan/divide.h>
12 #include <botan/reducer.h>
13 #include <botan/mac.h>
14 
15 namespace Botan {
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 void factor(BigInt n, BigInt& a, BigInt& b)
28  {
29  a = 1;
30  b = 1;
31 
32  size_t n_low_zero = low_zero_bits(n);
33 
34  a <<= (n_low_zero / 2);
35  b <<= n_low_zero - (n_low_zero / 2);
36  n >>= n_low_zero;
37 
38  for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
39  {
40  while(n % PRIMES[i] == 0)
41  {
42  a *= PRIMES[i];
43  if(a > b)
44  std::swap(a, b);
45  n /= PRIMES[i];
46  }
47  }
48 
49  if(a > b)
50  std::swap(a, b);
51  a *= n;
52 
53  if(a <= 1 || b <= 1)
54  throw Internal_Error("Could not factor n for use in FPE");
55  }
56 
57 }
58 
60  size_t rounds,
61  bool compat_mode,
62  const std::string& mac_algo) :
63  m_rounds(rounds)
64  {
65  if(m_rounds < 3)
66  throw Invalid_Argument("FPE_FE1 rounds too small");
67 
69 
70  m_n_bytes = BigInt::encode(n);
71 
72  if(m_n_bytes.size() > MAX_N_BYTES)
73  throw Invalid_Argument("N is too large for FPE encryption");
74 
75  factor(n, m_a, m_b);
76 
77  if(compat_mode)
78  {
79  if(m_a < m_b)
80  std::swap(m_a, m_b);
81  }
82  else
83  {
84  if(m_a > m_b)
85  std::swap(m_a, m_b);
86  }
87 
88  mod_a.reset(new Modular_Reducer(m_a));
89  }
90 
92  {
93  // for ~unique_ptr
94  }
95 
97  {
98  m_mac->clear();
99  }
100 
101 std::string FPE_FE1::name() const
102  {
103  return "FPE_FE1(" + m_mac->name() + "," + std::to_string(m_rounds) + ")";
104  }
105 
107  {
108  return m_mac->key_spec();
109  }
110 
111 void FPE_FE1::key_schedule(const uint8_t key[], size_t length)
112  {
113  m_mac->set_key(key, length);
114  }
115 
116 BigInt FPE_FE1::F(const BigInt& R, size_t round,
117  const secure_vector<uint8_t>& tweak_mac,
118  secure_vector<uint8_t>& tmp) const
119  {
120  tmp = BigInt::encode_locked(R);
121 
122  m_mac->update(tweak_mac);
123  m_mac->update_be(static_cast<uint32_t>(round));
124 
125  m_mac->update_be(static_cast<uint32_t>(tmp.size()));
126  m_mac->update(tmp.data(), tmp.size());
127 
128  tmp = m_mac->final();
129  return BigInt(tmp.data(), tmp.size());
130  }
131 
132 secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const
133  {
134  m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size()));
135  m_mac->update(m_n_bytes.data(), m_n_bytes.size());
136 
137  m_mac->update_be(static_cast<uint32_t>(tweak_len));
138  if(tweak_len > 0)
139  m_mac->update(tweak, tweak_len);
140 
141  return m_mac->final();
142  }
143 
144 BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
145  {
146  const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
147 
148  BigInt X = input;
149 
151 
152  BigInt L, R, Fi;
153  for(size_t i = 0; i != m_rounds; ++i)
154  {
155  ct_divide(X, m_b, L, R);
156  Fi = F(R, i, tweak_mac, tmp);
157  X = m_a * R + mod_a->reduce(L + Fi);
158  }
159 
160  return X;
161  }
162 
163 BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
164  {
165  const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
166 
167  BigInt X = input;
169 
170  BigInt W, R, Fi;
171  for(size_t i = 0; i != m_rounds; ++i)
172  {
173  ct_divide(X, m_a, R, W);
174 
175  Fi = F(R, m_rounds-i-1, tweak_mac, tmp);
176  X = m_b * mod_a->reduce(W - Fi) + R;
177  }
178 
179  return X;
180  }
181 
182 BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const
183  {
184  uint8_t tweak8[8];
185  store_be(tweak, tweak8);
186  return encrypt(x, tweak8, sizeof(tweak8));
187  }
188 
189 BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const
190  {
191  uint8_t tweak8[8];
192  store_be(tweak, tweak8);
193  return decrypt(x, tweak8, sizeof(tweak8));
194  }
195 
196 namespace FPE {
197 
198 BigInt fe1_encrypt(const BigInt& n, const BigInt& X,
199  const SymmetricKey& key,
200  const std::vector<uint8_t>& tweak)
201  {
202  FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
203  fpe.set_key(key);
204  return fpe.encrypt(X, tweak.data(), tweak.size());
205  }
206 
207 BigInt fe1_decrypt(const BigInt& n, const BigInt& X,
208  const SymmetricKey& key,
209  const std::vector<uint8_t>& tweak)
210  {
211  FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
212  fpe.set_key(key);
213  return fpe.decrypt(X, tweak.data(), tweak.size());
214  }
215 
216 }
217 
218 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:276
fe X
Definition: ge.cpp:27
const uint16_t PRIMES[]
Definition: primes.cpp:12
std::string name() const override
Definition: fpe_fe1.cpp:101
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:40
void clear() override
Definition: fpe_fe1.cpp:96
BigInt fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:198
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:438
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:763
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:59
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
static secure_vector< uint8_t > encode_locked(const BigInt &n)
Definition: bigint.h:775
void set_key(const SymmetricKey &key)
Definition: sym_algo.h:65
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:52
Definition: alg_id.cpp:13
BigInt decrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition: fpe_fe1.cpp:163
BigInt encrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition: fpe_fe1.cpp:144
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:65
Key_Length_Specification key_spec() const override
Definition: fpe_fe1.cpp:106
BigInt fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:207