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