Botan
1.11.15
|
00001 /* 00002 * IDEA 00003 * (C) 1999-2010 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/internal/block_utils.h> 00009 #include <botan/idea.h> 00010 00011 namespace Botan { 00012 00013 BOTAN_REGISTER_BLOCK_CIPHER_NOARGS(IDEA); 00014 00015 namespace { 00016 00017 /* 00018 * Multiplication modulo 65537 00019 */ 00020 inline u16bit mul(u16bit x, u16bit y) 00021 { 00022 const u32bit P = static_cast<u32bit>(x) * y; 00023 00024 // P ? 0xFFFF : 0 00025 const u16bit P_mask = !P - 1; 00026 00027 const u32bit P_hi = P >> 16; 00028 const u32bit P_lo = P & 0xFFFF; 00029 00030 const u16bit r_1 = (P_lo - P_hi) + (P_lo < P_hi); 00031 const u16bit r_2 = 1 - x - y; 00032 00033 return (r_1 & P_mask) | (r_2 & ~P_mask); 00034 } 00035 00036 /* 00037 * Find multiplicative inverses modulo 65537 00038 * 00039 * 65537 is prime; thus Fermat's little theorem tells us that 00040 * x^65537 == x modulo 65537, which means 00041 * x^(65537-2) == x^-1 modulo 65537 since 00042 * x^(65537-2) * x == 1 mod 65537 00043 * 00044 * Do the exponentiation with a basic square and multiply: all bits are 00045 * of exponent are 1 so we always multiply 00046 */ 00047 u16bit mul_inv(u16bit x) 00048 { 00049 u16bit y = x; 00050 00051 for(size_t i = 0; i != 15; ++i) 00052 { 00053 y = mul(y, y); // square 00054 y = mul(y, x); 00055 } 00056 00057 return y; 00058 } 00059 00060 /** 00061 * IDEA is involutional, depending only on the key schedule 00062 */ 00063 void idea_op(const byte in[], byte out[], size_t blocks, const u16bit K[52]) 00064 { 00065 const size_t BLOCK_SIZE = 8; 00066 00067 for(size_t i = 0; i != blocks; ++i) 00068 { 00069 u16bit X1 = load_be<u16bit>(in, 0); 00070 u16bit X2 = load_be<u16bit>(in, 1); 00071 u16bit X3 = load_be<u16bit>(in, 2); 00072 u16bit X4 = load_be<u16bit>(in, 3); 00073 00074 for(size_t j = 0; j != 8; ++j) 00075 { 00076 X1 = mul(X1, K[6*j+0]); 00077 X2 += K[6*j+1]; 00078 X3 += K[6*j+2]; 00079 X4 = mul(X4, K[6*j+3]); 00080 00081 u16bit T0 = X3; 00082 X3 = mul(X3 ^ X1, K[6*j+4]); 00083 00084 u16bit T1 = X2; 00085 X2 = mul((X2 ^ X4) + X3, K[6*j+5]); 00086 X3 += X2; 00087 00088 X1 ^= X2; 00089 X4 ^= X3; 00090 X2 ^= T0; 00091 X3 ^= T1; 00092 } 00093 00094 X1 = mul(X1, K[48]); 00095 X2 += K[50]; 00096 X3 += K[49]; 00097 X4 = mul(X4, K[51]); 00098 00099 store_be(out, X1, X3, X2, X4); 00100 00101 in += BLOCK_SIZE; 00102 out += BLOCK_SIZE; 00103 } 00104 } 00105 00106 } 00107 00108 /* 00109 * IDEA Encryption 00110 */ 00111 void IDEA::encrypt_n(const byte in[], byte out[], size_t blocks) const 00112 { 00113 idea_op(in, out, blocks, &EK[0]); 00114 } 00115 00116 /* 00117 * IDEA Decryption 00118 */ 00119 void IDEA::decrypt_n(const byte in[], byte out[], size_t blocks) const 00120 { 00121 idea_op(in, out, blocks, &DK[0]); 00122 } 00123 00124 /* 00125 * IDEA Key Schedule 00126 */ 00127 void IDEA::key_schedule(const byte key[], size_t) 00128 { 00129 EK.resize(52); 00130 DK.resize(52); 00131 00132 for(size_t i = 0; i != 8; ++i) 00133 EK[i] = load_be<u16bit>(key, i); 00134 00135 for(size_t i = 1, j = 8, offset = 0; j != 52; i %= 8, ++i, ++j) 00136 { 00137 EK[i+7+offset] = static_cast<u16bit>((EK[(i % 8) + offset] << 9) | 00138 (EK[((i+1) % 8) + offset] >> 7)); 00139 offset += (i == 8) ? 8 : 0; 00140 } 00141 00142 DK[51] = mul_inv(EK[3]); 00143 DK[50] = -EK[2]; 00144 DK[49] = -EK[1]; 00145 DK[48] = mul_inv(EK[0]); 00146 00147 for(size_t i = 1, j = 4, counter = 47; i != 8; ++i, j += 6) 00148 { 00149 DK[counter--] = EK[j+1]; 00150 DK[counter--] = EK[j]; 00151 DK[counter--] = mul_inv(EK[j+5]); 00152 DK[counter--] = -EK[j+3]; 00153 DK[counter--] = -EK[j+4]; 00154 DK[counter--] = mul_inv(EK[j+2]); 00155 } 00156 00157 DK[5] = EK[47]; 00158 DK[4] = EK[46]; 00159 DK[3] = mul_inv(EK[51]); 00160 DK[2] = -EK[50]; 00161 DK[1] = -EK[49]; 00162 DK[0] = mul_inv(EK[48]); 00163 } 00164 00165 void IDEA::clear() 00166 { 00167 zap(EK); 00168 zap(DK); 00169 } 00170 00171 }