Botan 3.9.0
Crypto and TLS for C&
idea.cpp
Go to the documentation of this file.
1/*
2* IDEA
3* (C) 1999-2010,2015 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/internal/idea.h>
9
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/loadstor.h>
12
13#if defined(BOTAN_HAS_CPUID)
14 #include <botan/internal/cpuid.h>
15#endif
16
17namespace Botan {
18
19namespace {
20
21/*
22* Multiplication modulo 65537
23*/
24inline uint16_t mul(uint16_t x, uint16_t y) {
25 const uint32_t P = static_cast<uint32_t>(x) * y;
26 const auto P_mask = CT::Mask<uint16_t>(CT::Mask<uint32_t>::is_zero(P));
27
28 const uint32_t P_hi = P >> 16;
29 const uint32_t P_lo = P & 0xFFFF;
30
31 const uint16_t carry = static_cast<uint16_t>(P_lo < P_hi);
32 const uint16_t r_1 = static_cast<uint16_t>((P_lo - P_hi) + carry);
33 const uint16_t r_2 = 1 - x - y;
34
35 return P_mask.select(r_2, r_1);
36}
37
38/*
39* Find multiplicative inverses modulo 65537
40*
41* 65537 is prime; thus Fermat's little theorem tells us that
42* x^65537 == x modulo 65537, which means
43* x^(65537-2) == x^-1 modulo 65537 since
44* x^(65537-2) * x == 1 mod 65537
45*
46* Do the exponentiation with a basic square and multiply: all bits are
47* of exponent are 1 so we always multiply
48*/
49uint16_t mul_inv(uint16_t x) {
50 uint16_t y = x;
51
52 for(size_t i = 0; i != 15; ++i) {
53 y = mul(y, y); // square
54 y = mul(y, x);
55 }
56
57 return y;
58}
59
60/**
61* IDEA is involutional, depending only on the key schedule
62*/
63void idea_op(const uint8_t in[], uint8_t out[], size_t blocks, const uint16_t K[52]) {
64 const size_t BLOCK_SIZE = 8;
65
66 CT::poison(in, blocks * 8);
67 CT::poison(out, blocks * 8);
68 CT::poison(K, 52);
69
70 for(size_t i = 0; i < blocks; ++i) {
71 uint16_t X1 = 0;
72 uint16_t X2 = 0;
73 uint16_t X3 = 0;
74 uint16_t X4 = 0;
75 load_be(in + BLOCK_SIZE * i, X1, X2, X3, X4);
76
77 for(size_t j = 0; j != 8; ++j) {
78 X1 = mul(X1, K[6 * j + 0]);
79 X2 += K[6 * j + 1];
80 X3 += K[6 * j + 2];
81 X4 = mul(X4, K[6 * j + 3]);
82
83 const uint16_t T0 = X3;
84 X3 = mul(X3 ^ X1, K[6 * j + 4]);
85
86 const uint16_t T1 = X2;
87 X2 = mul((X2 ^ X4) + X3, K[6 * j + 5]);
88 X3 += X2;
89
90 X1 ^= X2;
91 X4 ^= X3;
92 X2 ^= T0;
93 X3 ^= T1;
94 }
95
96 X1 = mul(X1, K[48]);
97 X2 += K[50];
98 X3 += K[49];
99 X4 = mul(X4, K[51]);
100
101 store_be(out + BLOCK_SIZE * i, X1, X3, X2, X4);
102 }
103
104 CT::unpoison(in, blocks * 8);
105 CT::unpoison(out, blocks * 8);
106 CT::unpoison(K, 52);
107}
108
109} // namespace
110
111size_t IDEA::parallelism() const {
112#if defined(BOTAN_HAS_IDEA_SSE2)
114 return 8;
115 }
116#endif
117
118 return 1;
119}
120
121std::string IDEA::provider() const {
122#if defined(BOTAN_HAS_IDEA_SSE2)
123 if(auto feat = CPUID::check(CPUID::Feature::SSE2)) {
124 return *feat;
125 }
126#endif
127
128 return "base";
129}
130
131/*
132* IDEA Encryption
133*/
134void IDEA::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
136
137#if defined(BOTAN_HAS_IDEA_SSE2)
139 while(blocks >= 8) {
140 sse2_idea_op_8(in, out, m_EK.data());
141 in += 8 * BLOCK_SIZE;
142 out += 8 * BLOCK_SIZE;
143 blocks -= 8;
144 }
145 }
146#endif
147
148 idea_op(in, out, blocks, m_EK.data());
149}
150
151/*
152* IDEA Decryption
153*/
154void IDEA::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
156
157#if defined(BOTAN_HAS_IDEA_SSE2)
159 while(blocks >= 8) {
160 sse2_idea_op_8(in, out, m_DK.data());
161 in += 8 * BLOCK_SIZE;
162 out += 8 * BLOCK_SIZE;
163 blocks -= 8;
164 }
165 }
166#endif
167
168 idea_op(in, out, blocks, m_DK.data());
169}
170
172 return !m_EK.empty();
173}
174
175/*
176* IDEA Key Schedule
177*/
178void IDEA::key_schedule(std::span<const uint8_t> key) {
179 m_EK.resize(52);
180 m_DK.resize(52);
181
182 CT::poison(key.data(), 16);
183 CT::poison(m_EK.data(), 52);
184 CT::poison(m_DK.data(), 52);
185
187
188 K[0] = load_be<uint64_t>(key.data(), 0);
189 K[1] = load_be<uint64_t>(key.data(), 1);
190
191 for(size_t off = 0; off != 48; off += 8) {
192 for(size_t i = 0; i != 8; ++i) {
193 m_EK[off + i] = static_cast<uint16_t>(K[i / 4] >> (48 - 16 * (i % 4)));
194 }
195
196 const uint64_t Kx = (K[0] >> 39);
197 const uint64_t Ky = (K[1] >> 39);
198
199 K[0] = (K[0] << 25) | Ky;
200 K[1] = (K[1] << 25) | Kx;
201 }
202
203 for(size_t i = 0; i != 4; ++i) {
204 m_EK[48 + i] = static_cast<uint16_t>(K[i / 4] >> (48 - 16 * (i % 4)));
205 }
206
207 m_DK[0] = mul_inv(m_EK[48]);
208 m_DK[1] = -m_EK[49];
209 m_DK[2] = -m_EK[50];
210 m_DK[3] = mul_inv(m_EK[51]);
211
212 for(size_t i = 0; i != 8 * 6; i += 6) {
213 m_DK[i + 4] = m_EK[46 - i];
214 m_DK[i + 5] = m_EK[47 - i];
215 m_DK[i + 6] = mul_inv(m_EK[42 - i]);
216 m_DK[i + 7] = -m_EK[44 - i];
217 m_DK[i + 8] = -m_EK[43 - i];
218 m_DK[i + 9] = mul_inv(m_EK[45 - i]);
219 }
220
221 std::swap(m_DK[49], m_DK[50]);
222
223 CT::unpoison(key.data(), 16);
224 CT::unpoison(m_EK.data(), 52);
225 CT::unpoison(m_DK.data(), 52);
226}
227
229 zap(m_EK);
230 zap(m_DK);
231}
232
233} // namespace Botan
static std::optional< std::string > check(CPUID::Feature feat)
Definition cpuid.h:67
static bool has(CPUID::Feature feat)
Definition cpuid.h:94
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:465
void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition idea.cpp:154
std::string provider() const override
Definition idea.cpp:121
void clear() override
Definition idea.cpp:228
bool has_keying_material() const override
Definition idea.cpp:171
void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition idea.cpp:134
size_t parallelism() const override
Definition idea.cpp:111
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:65
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:54
void zap(std::vector< T, Alloc > &vec)
Definition secmem.h:134
void carry(int64_t &h0, int64_t &h1)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:504