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