Botan  2.4.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 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/mac.h>
11 
12 namespace Botan {
13 
14 namespace FPE {
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 * Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b
27 * then this is always 3
28 */
29 void factor(BigInt n, BigInt& a, BigInt& b)
30  {
31  a = 1;
32  b = 1;
33 
34  size_t n_low_zero = low_zero_bits(n);
35 
36  a <<= (n_low_zero / 2);
37  b <<= n_low_zero - (n_low_zero / 2);
38  n >>= n_low_zero;
39 
40  for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
41  {
42  while(n % PRIMES[i] == 0)
43  {
44  a *= PRIMES[i];
45  if(a > b)
46  std::swap(a, b);
47  n /= PRIMES[i];
48  }
49  }
50 
51  if(a > b)
52  std::swap(a, b);
53  a *= n;
54  if(a < b)
55  std::swap(a, b);
56 
57  if(a <= 1 || b <= 1)
58  throw Exception("Could not factor n for use in FPE");
59  }
60 
61 /*
62 * According to a paper by Rogaway, Bellare, etc, the min safe number
63 * of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1
64 * so 3 rounds is safe. The FPE factorization routine should always
65 * return a >= b, so just confirm that and return 3.
66 */
67 size_t rounds(const BigInt& a, const BigInt& b)
68  {
69  if(a < b)
70  throw Internal_Error("FPE rounds: a < b");
71  return 3;
72  }
73 
74 /*
75 * A simple round function based on HMAC(SHA-256)
76 */
77 class FPE_Encryptor final
78  {
79  public:
80  FPE_Encryptor(const SymmetricKey& key,
81  const BigInt& n,
82  const std::vector<uint8_t>& tweak);
83 
84  BigInt operator()(size_t i, const BigInt& R);
85 
86  private:
87  std::unique_ptr<MessageAuthenticationCode> m_mac;
88  std::vector<uint8_t> m_mac_n_t;
89  };
90 
91 FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key,
92  const BigInt& n,
93  const std::vector<uint8_t>& tweak)
94  {
95  m_mac = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)");
96  m_mac->set_key(key);
97 
98  std::vector<uint8_t> n_bin = BigInt::encode(n);
99 
100  if(n_bin.size() > MAX_N_BYTES)
101  throw Exception("N is too large for FPE encryption");
102 
103  m_mac->update_be(static_cast<uint32_t>(n_bin.size()));
104  m_mac->update(n_bin.data(), n_bin.size());
105 
106  m_mac->update_be(static_cast<uint32_t>(tweak.size()));
107  m_mac->update(tweak.data(), tweak.size());
108 
109  m_mac_n_t = unlock(m_mac->final());
110  }
111 
112 BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R)
113  {
115 
116  m_mac->update(m_mac_n_t);
117  m_mac->update_be(static_cast<uint32_t>(round_no));
118 
119  m_mac->update_be(static_cast<uint32_t>(r_bin.size()));
120  m_mac->update(r_bin.data(), r_bin.size());
121 
122  secure_vector<uint8_t> X = m_mac->final();
123  return BigInt(X.data(), X.size());
124  }
125 
126 }
127 
128 /*
129 * Generic Z_n FPE encryption, FE1 scheme
130 */
131 BigInt fe1_encrypt(const BigInt& n, const BigInt& X0,
132  const SymmetricKey& key,
133  const std::vector<uint8_t>& tweak)
134  {
135  FPE_Encryptor F(key, n, tweak);
136 
137  BigInt a, b;
138  factor(n, a, b);
139 
140  const size_t r = rounds(a, b);
141 
142  BigInt X = X0;
143 
144  for(size_t i = 0; i != r; ++i)
145  {
146  BigInt L = X / b;
147  BigInt R = X % b;
148 
149  BigInt W = (L + F(i, R)) % a;
150  X = a * R + W;
151  }
152 
153  return X;
154  }
155 
156 /*
157 * Generic Z_n FPE decryption, FD1 scheme
158 */
159 BigInt fe1_decrypt(const BigInt& n, const BigInt& X0,
160  const SymmetricKey& key,
161  const std::vector<uint8_t>& tweak)
162  {
163  FPE_Encryptor F(key, n, tweak);
164 
165  BigInt a, b;
166  factor(n, a, b);
167 
168  const size_t r = rounds(a, b);
169 
170  BigInt X = X0;
171 
172  for(size_t i = 0; i != r; ++i)
173  {
174  BigInt W = X % a;
175  BigInt R = X / a;
176 
177  BigInt L = (W - F(r-i-1, R)) % a;
178  X = b * L + R;
179  }
180 
181  return X;
182  }
183 
184 }
185 
186 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
fe X
Definition: ge.cpp:27
const uint16_t PRIMES[]
Definition: primes.cpp:12
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:21
BigInt fe1_decrypt(const BigInt &n, const BigInt &X0, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:159
static secure_vector< uint8_t > encode_locked(const BigInt &n, Base base=Binary)
Definition: big_code.cpp:68
Definition: alg_id.cpp:13
std::vector< T > unlock(const secure_vector< T > &in)
Definition: secmem.h:95
static std::unique_ptr< MessageAuthenticationCode > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: mac.cpp:140
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
BigInt fe1_encrypt(const BigInt &n, const BigInt &X0, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:131