Botan  2.4.0
Crypto and TLS for C++11
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 
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  {
22  const uint32_t P = static_cast<uint32_t>(x) * y;
23 
24  const uint16_t Z_mask = static_cast<uint16_t>(CT::expand_mask(P) & 0xFFFF);
25 
26  const uint32_t P_hi = P >> 16;
27  const uint32_t P_lo = P & 0xFFFF;
28 
29  const uint16_t carry = (P_lo < P_hi);
30  const uint16_t r_1 = static_cast<uint16_t>((P_lo - P_hi) + carry);
31  const uint16_t r_2 = 1 - x - y;
32 
33  return CT::select(Z_mask, r_1, r_2);
34  }
35 
36 /*
37 * Find multiplicative inverses modulo 65537
38 *
39 * 65537 is prime; thus Fermat's little theorem tells us that
40 * x^65537 == x modulo 65537, which means
41 * x^(65537-2) == x^-1 modulo 65537 since
42 * x^(65537-2) * x == 1 mod 65537
43 *
44 * Do the exponentiation with a basic square and multiply: all bits are
45 * of exponent are 1 so we always multiply
46 */
47 uint16_t mul_inv(uint16_t x)
48  {
49  uint16_t y = x;
50 
51  for(size_t i = 0; i != 15; ++i)
52  {
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 */
63 void idea_op(const uint8_t in[], uint8_t out[], size_t blocks, const uint16_t K[52])
64  {
65  const size_t BLOCK_SIZE = 8;
66 
67  CT::poison(in, blocks * 8);
68  CT::poison(out, blocks * 8);
69  CT::poison(K, 52);
70 
71  BOTAN_PARALLEL_FOR(size_t i = 0; i < blocks; ++i)
72  {
73  uint16_t X1, X2, X3, X4;
74  load_be(in + BLOCK_SIZE*i, X1, X2, X3, X4);
75 
76  for(size_t j = 0; j != 8; ++j)
77  {
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  uint16_t T0 = X3;
84  X3 = mul(X3 ^ X1, K[6*j+4]);
85 
86  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 }
110 
111 size_t IDEA::parallelism() const
112  {
113 #if defined(BOTAN_HAS_IDEA_SSE2)
114  if(CPUID::has_sse2())
115  {
116  return 8;
117  }
118 #endif
119 
120  return 1;
121  }
122 
123 std::string IDEA::provider() const
124  {
125 #if defined(BOTAN_HAS_IDEA_SSE2)
126  if(CPUID::has_sse2())
127  {
128  return "sse2";
129  }
130 #endif
131 
132  return "base";
133  }
134 
135 /*
136 * IDEA Encryption
137 */
138 void IDEA::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const
139  {
140  verify_key_set(m_EK.empty() == false);
141 
142 #if defined(BOTAN_HAS_IDEA_SSE2)
143  if(CPUID::has_sse2())
144  {
145  while(blocks >= 8)
146  {
147  sse2_idea_op_8(in, out, m_EK.data());
148  in += 8 * BLOCK_SIZE;
149  out += 8 * BLOCK_SIZE;
150  blocks -= 8;
151  }
152  }
153 #endif
154 
155  idea_op(in, out, blocks, m_EK.data());
156  }
157 
158 /*
159 * IDEA Decryption
160 */
161 void IDEA::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const
162  {
163  verify_key_set(m_DK.empty() == false);
164 
165 #if defined(BOTAN_HAS_IDEA_SSE2)
166  if(CPUID::has_sse2())
167  {
168  while(blocks >= 8)
169  {
170  sse2_idea_op_8(in, out, m_DK.data());
171  in += 8 * BLOCK_SIZE;
172  out += 8 * BLOCK_SIZE;
173  blocks -= 8;
174  }
175  }
176 #endif
177 
178  idea_op(in, out, blocks, m_DK.data());
179  }
180 
181 /*
182 * IDEA Key Schedule
183 */
184 void IDEA::key_schedule(const uint8_t key[], size_t)
185  {
186  m_EK.resize(52);
187  m_DK.resize(52);
188 
189  CT::poison(key, 16);
190  CT::poison(m_EK.data(), 52);
191  CT::poison(m_DK.data(), 52);
192 
193  for(size_t i = 0; i != 8; ++i)
194  m_EK[i] = load_be<uint16_t>(key, i);
195 
196  for(size_t i = 1, j = 8, offset = 0; j != 52; i %= 8, ++i, ++j)
197  {
198  m_EK[i+7+offset] = static_cast<uint16_t>((m_EK[(i % 8) + offset] << 9) |
199  (m_EK[((i+1) % 8) + offset] >> 7));
200  offset += (i == 8) ? 8 : 0;
201  }
202 
203  m_DK[51] = mul_inv(m_EK[3]);
204  m_DK[50] = -m_EK[2];
205  m_DK[49] = -m_EK[1];
206  m_DK[48] = mul_inv(m_EK[0]);
207 
208  for(size_t i = 1, j = 4, counter = 47; i != 8; ++i, j += 6)
209  {
210  m_DK[counter--] = m_EK[j+1];
211  m_DK[counter--] = m_EK[j];
212  m_DK[counter--] = mul_inv(m_EK[j+5]);
213  m_DK[counter--] = -m_EK[j+3];
214  m_DK[counter--] = -m_EK[j+4];
215  m_DK[counter--] = mul_inv(m_EK[j+2]);
216  }
217 
218  m_DK[5] = m_EK[47];
219  m_DK[4] = m_EK[46];
220  m_DK[3] = mul_inv(m_EK[51]);
221  m_DK[2] = -m_EK[50];
222  m_DK[1] = -m_EK[49];
223  m_DK[0] = mul_inv(m_EK[48]);
224 
225  CT::unpoison(key, 16);
226  CT::unpoison(m_EK.data(), 52);
227  CT::unpoison(m_DK.data(), 52);
228  }
229 
231  {
232  zap(m_EK);
233  zap(m_DK);
234  }
235 
236 }
void verify_key_set(bool cond) const
Definition: sym_algo.h:95
void clear() override
Definition: idea.cpp:230
void zap(std::vector< T, Alloc > &vec)
Definition: secmem.h:191
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:434
uint16_t load_be< uint16_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:137
void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition: idea.cpp:138
std::string provider() const override
Definition: idea.cpp:123
void poison(const T *p, size_t n)
Definition: ct_utils.h:46
#define BOTAN_PARALLEL_FOR
Definition: compiler.h:174
T expand_mask(T x)
Definition: ct_utils.h:86
T load_be(const uint8_t in[], size_t off)
Definition: loadstor.h:105
T select(T mask, T from0, T from1)
Definition: ct_utils.h:106
Definition: alg_id.cpp:13
void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition: idea.cpp:161
size_t parallelism() const override
Definition: idea.cpp:111
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:57