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