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