Botan 2.19.3
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/idea.h>
9#include <botan/loadstor.h>
10#include <botan/cpuid.h>
11#include <botan/internal/ct_utils.h>
12
13namespace Botan {
14
15namespace {
16
17/*
18* Multiplication modulo 65537
19*/
20inline uint16_t mul(uint16_t x, uint16_t y)
21 {
22 const uint32_t P = static_cast<uint32_t>(x) * y;
23 const auto P_mask = CT::Mask<uint16_t>(CT::Mask<uint32_t>::is_zero(P));
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
32 return P_mask.select(r_2, r_1);
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 {
48 uint16_t y = x;
49
50 for(size_t i = 0; i != 15; ++i)
51 {
52 y = mul(y, y); // square
53 y = mul(y, x);
54 }
55
56 return y;
57 }
58
59/**
60* IDEA is involutional, depending only on the key schedule
61*/
62void idea_op(const uint8_t in[], uint8_t out[], size_t blocks, const uint16_t K[52])
63 {
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 BOTAN_PARALLEL_FOR(size_t i = 0; i < blocks; ++i)
71 {
72 uint16_t X1, X2, X3, X4;
73 load_be(in + BLOCK_SIZE*i, X1, X2, X3, X4);
74
75 for(size_t j = 0; j != 8; ++j)
76 {
77 X1 = mul(X1, K[6*j+0]);
78 X2 += K[6*j+1];
79 X3 += K[6*j+2];
80 X4 = mul(X4, K[6*j+3]);
81
82 const uint16_t T0 = X3;
83 X3 = mul(X3 ^ X1, K[6*j+4]);
84
85 const uint16_t T1 = X2;
86 X2 = mul((X2 ^ X4) + X3, K[6*j+5]);
87 X3 += X2;
88
89 X1 ^= X2;
90 X4 ^= X3;
91 X2 ^= T0;
92 X3 ^= T1;
93 }
94
95 X1 = mul(X1, K[48]);
96 X2 += K[50];
97 X3 += K[49];
98 X4 = mul(X4, K[51]);
99
100 store_be(out + BLOCK_SIZE*i, X1, X3, X2, X4);
101 }
102
103 CT::unpoison(in, blocks * 8);
104 CT::unpoison(out, blocks * 8);
105 CT::unpoison(K, 52);
106 }
107
108}
109
110size_t IDEA::parallelism() const
111 {
112#if defined(BOTAN_HAS_IDEA_SSE2)
113 if(CPUID::has_sse2())
114 {
115 return 8;
116 }
117#endif
118
119 return 1;
120 }
121
122std::string IDEA::provider() const
123 {
124#if defined(BOTAN_HAS_IDEA_SSE2)
125 if(CPUID::has_sse2())
126 {
127 return "sse2";
128 }
129#endif
130
131 return "base";
132 }
133
134/*
135* IDEA Encryption
136*/
137void IDEA::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const
138 {
139 verify_key_set(m_EK.empty() == false);
140
141#if defined(BOTAN_HAS_IDEA_SSE2)
142 if(CPUID::has_sse2())
143 {
144 while(blocks >= 8)
145 {
146 sse2_idea_op_8(in, out, m_EK.data());
147 in += 8 * BLOCK_SIZE;
148 out += 8 * BLOCK_SIZE;
149 blocks -= 8;
150 }
151 }
152#endif
153
154 idea_op(in, out, blocks, m_EK.data());
155 }
156
157/*
158* IDEA Decryption
159*/
160void IDEA::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const
161 {
162 verify_key_set(m_DK.empty() == false);
163
164#if defined(BOTAN_HAS_IDEA_SSE2)
165 if(CPUID::has_sse2())
166 {
167 while(blocks >= 8)
168 {
169 sse2_idea_op_8(in, out, m_DK.data());
170 in += 8 * BLOCK_SIZE;
171 out += 8 * BLOCK_SIZE;
172 blocks -= 8;
173 }
174 }
175#endif
176
177 idea_op(in, out, blocks, m_DK.data());
178 }
179
180/*
181* IDEA Key Schedule
182*/
183void IDEA::key_schedule(const uint8_t key[], size_t)
184 {
185 m_EK.resize(52);
186 m_DK.resize(52);
187
188 CT::poison(key, 16);
189 CT::poison(m_EK.data(), 52);
190 CT::poison(m_DK.data(), 52);
191
193
194 K[0] = load_be<uint64_t>(key, 0);
195 K[1] = load_be<uint64_t>(key, 1);
196
197 for(size_t off = 0; off != 48; off += 8)
198 {
199 for(size_t i = 0; i != 8; ++i)
200 m_EK[off+i] = static_cast<uint16_t>(K[i/4] >> (48-16*(i % 4)));
201
202 const uint64_t Kx = (K[0] >> 39);
203 const uint64_t Ky = (K[1] >> 39);
204
205 K[0] = (K[0] << 25) | Ky;
206 K[1] = (K[1] << 25) | Kx;
207 }
208
209 for(size_t i = 0; i != 4; ++i)
210 m_EK[48+i] = static_cast<uint16_t>(K[i/4] >> (48-16*(i % 4)));
211
212 m_DK[0] = mul_inv(m_EK[48]);
213 m_DK[1] = -m_EK[49];
214 m_DK[2] = -m_EK[50];
215 m_DK[3] = mul_inv(m_EK[51]);
216
217 for(size_t i = 0; i != 8*6; i += 6)
218 {
219 m_DK[i+4] = m_EK[46-i];
220 m_DK[i+5] = m_EK[47-i];
221 m_DK[i+6] = mul_inv(m_EK[42-i]);
222 m_DK[i+7] = -m_EK[44-i];
223 m_DK[i+8] = -m_EK[43-i];
224 m_DK[i+9] = mul_inv(m_EK[45-i]);
225 }
226
227 std::swap(m_DK[49], m_DK[50]);
228
229 CT::unpoison(key, 16);
230 CT::unpoison(m_EK.data(), 52);
231 CT::unpoison(m_DK.data(), 52);
232 }
233
235 {
236 zap(m_EK);
237 zap(m_DK);
238 }
239
240}
static Mask< T > is_zero(T x)
Definition ct_utils.h:141
void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition idea.cpp:160
std::string provider() const override
Definition idea.cpp:122
void clear() override
Definition idea.cpp:234
void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition idea.cpp:137
size_t parallelism() const override
Definition idea.cpp:110
void verify_key_set(bool cond) const
Definition sym_algo.h:171
#define BOTAN_PARALLEL_FOR
Definition compiler.h:188
void poison(const T *p, size_t n)
Definition ct_utils.h:48
void unpoison(const T *p, size_t n)
Definition ct_utils.h:59
void zap(std::vector< T, Alloc > &vec)
Definition secmem.h:124
void store_be(uint16_t in, uint8_t out[2])
Definition loadstor.h:438
T load_be(const uint8_t in[], size_t off)
Definition loadstor.h:107
void carry(int64_t &h0, int64_t &h1)
uint64_t load_be< uint64_t >(const uint8_t in[], size_t off)
Definition loadstor.h:217
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:65