Botan  2.11.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 Internal_Error("Could not factor n for use in FPE");
54  }
55 
56 }
57 
58 FPE_FE1::FPE_FE1(const BigInt& n,
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 
67  m_mac = MessageAuthenticationCode::create_or_throw(mac_algo);
68 
69  m_n_bytes = BigInt::encode(n);
70 
71  if(m_n_bytes.size() > MAX_N_BYTES)
72  throw Invalid_Argument("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 
90 FPE_FE1::~FPE_FE1()
91  {
92  // for ~unique_ptr
93  }
94 
95 void FPE_FE1::clear()
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 
105 Key_Length_Specification FPE_FE1::key_spec() const
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  if(tweak_len > 0)
138  m_mac->update(tweak, tweak_len);
139 
140  return m_mac->final();
141  }
142 
143 BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
144  {
145  const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
146 
147  BigInt X = input;
148 
149  secure_vector<uint8_t> tmp;
150 
151  BigInt L, R, Fi;
152  for(size_t i = 0; i != m_rounds; ++i)
153  {
154  ct_divide(X, m_b, L, R);
155  Fi = F(R, i, tweak_mac, tmp);
156  X = m_a * R + mod_a->reduce(L + Fi);
157  }
158 
159  return X;
160  }
161 
162 BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
163  {
164  const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
165 
166  BigInt X = input;
167  secure_vector<uint8_t> tmp;
168 
169  BigInt W, R, Fi;
170  for(size_t i = 0; i != m_rounds; ++i)
171  {
172  ct_divide(X, m_a, R, W);
173 
174  Fi = F(R, m_rounds-i-1, tweak_mac, tmp);
175  X = m_b * mod_a->reduce(W - Fi) + R;
176  }
177 
178  return X;
179  }
180 
181 BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const
182  {
183  uint8_t tweak8[8];
184  store_be(tweak, tweak8);
185  return encrypt(x, tweak8, sizeof(tweak8));
186  }
187 
188 BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const
189  {
190  uint8_t tweak8[8];
191  store_be(tweak, tweak8);
192  return decrypt(x, tweak8, sizeof(tweak8));
193  }
194 
195 namespace FPE {
196 
197 BigInt fe1_encrypt(const BigInt& n, const BigInt& X,
198  const SymmetricKey& key,
199  const std::vector<uint8_t>& tweak)
200  {
201  FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
202  fpe.set_key(key);
203  return fpe.encrypt(X, tweak.data(), tweak.size());
204  }
205 
206 BigInt fe1_decrypt(const BigInt& n, const BigInt& X,
207  const SymmetricKey& key,
208  const std::vector<uint8_t>& tweak)
209  {
210  FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
211  fpe.set_key(key);
212  return fpe.decrypt(X, tweak.data(), tweak.size());
213  }
214 
215 }
216 
217 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:276
fe X
Definition: ge.cpp:27
BigInt const BigInt & x
Definition: numthry.h:139
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:26
BigInt size_t n
Definition: bigint.h:1096
BigInt fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:197
bool const OID & b
Definition: asn1_oid.h:109
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:436
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
char * name
Definition: ffi.h:330
BigInt const BigInt const SymmetricKey & key
Definition: fpe_fe1.h:101
BigInt const BigInt const SymmetricKey const std::vector< uint8_t > & tweak
Definition: fpe_fe1.h:101
std::string encode(const uint8_t der[], size_t length, const std::string &label, size_t width)
Definition: pem.cpp:43
const uint16_t PRIMES[PRIME_TABLE_SIZE+1]
Definition: primes.cpp:12
std::string decrypt(const uint8_t input[], size_t input_len, const std::string &passphrase)
Definition: cryptobox.cpp:162
size_t const BigInt & a
Definition: numthry.h:111
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:52
class BOTAN_PUBLIC_API(2, 11) Argon2 final class BOTAN_PUBLIC_API(2, 11) Argon2_Family final void size_t const char size_t const uint8_t size_t const uint8_t key[]
Definition: argon2.h:87
Definition: alg_id.cpp:13
OctetString SymmetricKey
Definition: symkey.h:141
BigInt const BigInt & X
Definition: fpe_fe1.h:101
size_t const uint8_t input[]
Definition: base32.h:30
std::string encrypt(const uint8_t input[], size_t input_len, const std::string &passphrase, RandomNumberGenerator &rng)
Definition: cryptobox.cpp:43
BigInt fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:206