Botan  1.10.9
idea.cpp
Go to the documentation of this file.
1 /*
2 * IDEA
3 * (C) 1999-2010 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/idea.h>
9 #include <botan/loadstor.h>
10 
11 namespace Botan {
12 
13 namespace {
14 
15 /*
16 * Multiplication modulo 65537
17 */
18 inline u16bit mul(u16bit x, u16bit y)
19  {
20  const u32bit P = static_cast<u32bit>(x) * y;
21 
22  // P ? 0xFFFF : 0
23  const u16bit P_mask = !P - 1;
24 
25  const u32bit P_hi = P >> 16;
26  const u32bit P_lo = P & 0xFFFF;
27 
28  const u16bit r_1 = (P_lo - P_hi) + (P_lo < P_hi);
29  const u16bit r_2 = 1 - x - y;
30 
31  return (r_1 & P_mask) | (r_2 & ~P_mask);
32  }
33 
34 /*
35 * Find multiplicative inverses modulo 65537
36 *
37 * 65537 is prime; thus Fermat's little theorem tells us that
38 * x^65537 == x modulo 65537, which means
39 * x^(65537-2) == x^-1 modulo 65537 since
40 * x^(65537-2) * x == 1 mod 65537
41 *
42 * Do the exponentiation with a basic square and multiply: all bits are
43 * of exponent are 1 so we always multiply
44 */
45 u16bit mul_inv(u16bit x)
46  {
47  u16bit y = x;
48 
49  for(size_t i = 0; i != 15; ++i)
50  {
51  y = mul(y, y); // square
52  y = mul(y, x);
53  }
54 
55  return y;
56  }
57 
58 /**
59 * IDEA is involutional, depending only on the key schedule
60 */
61 void idea_op(const byte in[], byte out[], size_t blocks, const u16bit K[52])
62  {
63  const size_t BLOCK_SIZE = 8;
64 
65  for(size_t i = 0; i != blocks; ++i)
66  {
67  u16bit X1 = load_be<u16bit>(in, 0);
68  u16bit X2 = load_be<u16bit>(in, 1);
69  u16bit X3 = load_be<u16bit>(in, 2);
70  u16bit X4 = load_be<u16bit>(in, 3);
71 
72  for(size_t j = 0; j != 8; ++j)
73  {
74  X1 = mul(X1, K[6*j+0]);
75  X2 += K[6*j+1];
76  X3 += K[6*j+2];
77  X4 = mul(X4, K[6*j+3]);
78 
79  u16bit T0 = X3;
80  X3 = mul(X3 ^ X1, K[6*j+4]);
81 
82  u16bit T1 = X2;
83  X2 = mul((X2 ^ X4) + X3, K[6*j+5]);
84  X3 += X2;
85 
86  X1 ^= X2;
87  X4 ^= X3;
88  X2 ^= T0;
89  X3 ^= T1;
90  }
91 
92  X1 = mul(X1, K[48]);
93  X2 += K[50];
94  X3 += K[49];
95  X4 = mul(X4, K[51]);
96 
97  store_be(out, X1, X3, X2, X4);
98 
99  in += BLOCK_SIZE;
100  out += BLOCK_SIZE;
101  }
102  }
103 
104 }
105 
106 /*
107 * IDEA Encryption
108 */
109 void IDEA::encrypt_n(const byte in[], byte out[], size_t blocks) const
110  {
111  idea_op(in, out, blocks, &EK[0]);
112  }
113 
114 /*
115 * IDEA Decryption
116 */
117 void IDEA::decrypt_n(const byte in[], byte out[], size_t blocks) const
118  {
119  idea_op(in, out, blocks, &DK[0]);
120  }
121 
122 /*
123 * IDEA Key Schedule
124 */
125 void IDEA::key_schedule(const byte key[], size_t)
126  {
127  for(size_t i = 0; i != 8; ++i)
128  EK[i] = load_be<u16bit>(key, i);
129 
130  for(size_t i = 1, j = 8, offset = 0; j != 52; i %= 8, ++i, ++j)
131  {
132  EK[i+7+offset] = static_cast<u16bit>((EK[(i % 8) + offset] << 9) |
133  (EK[((i+1) % 8) + offset] >> 7));
134  offset += (i == 8) ? 8 : 0;
135  }
136 
137  DK[51] = mul_inv(EK[3]);
138  DK[50] = -EK[2];
139  DK[49] = -EK[1];
140  DK[48] = mul_inv(EK[0]);
141 
142  for(size_t i = 1, j = 4, counter = 47; i != 8; ++i, j += 6)
143  {
144  DK[counter--] = EK[j+1];
145  DK[counter--] = EK[j];
146  DK[counter--] = mul_inv(EK[j+5]);
147  DK[counter--] = -EK[j+3];
148  DK[counter--] = -EK[j+4];
149  DK[counter--] = mul_inv(EK[j+2]);
150  }
151 
152  DK[5] = EK[47];
153  DK[4] = EK[46];
154  DK[3] = mul_inv(EK[51]);
155  DK[2] = -EK[50];
156  DK[1] = -EK[49];
157  DK[0] = mul_inv(EK[48]);
158  }
159 
160 }
unsigned char byte
Definition: types.h:22
u16bit load_be< u16bit >(const byte in[], size_t off)
Definition: loadstor.h:132
unsigned short u16bit
Definition: types.h:27
void decrypt_n(const byte in[], byte out[], size_t blocks) const
Definition: idea.cpp:117
void store_be(u16bit in, byte out[2])
Definition: loadstor.h:412
void encrypt_n(const byte in[], byte out[], size_t blocks) const
Definition: idea.cpp:109
unsigned int u32bit
Definition: types.h:32