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