Botan  2.8.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  const uint16_t P_mask = static_cast<uint16_t>(CT::is_zero(P) & 0xFFFF);
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 CT::select(P_mask, 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 */
46 uint16_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 */
62 void 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 
110 size_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 
122 std::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 */
137 void 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 */
160 void 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 */
183 void 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 }
void verify_key_set(bool cond) const
Definition: sym_algo.h:89
void clear() override
Definition: idea.cpp:234
void zap(std::vector< T, Alloc > &vec)
Definition: secmem.h:193
void carry(int64_t &h0, int64_t &h1)
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:434
void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition: idea.cpp:137
std::string provider() const override
Definition: idea.cpp:122
void poison(const T *p, size_t n)
Definition: ct_utils.h:47
#define BOTAN_PARALLEL_FOR
Definition: compiler.h:183
uint64_t load_be< uint64_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:215
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:110
Definition: alg_id.cpp:13
T is_zero(T x)
Definition: ct_utils.h:88
void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition: idea.cpp:160
size_t parallelism() const override
Definition: idea.cpp:110
void unpoison(const T *p, size_t n)
Definition: ct_utils.h:58
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88