Botan  1.11.15
src/lib/block/idea/idea.cpp
Go to the documentation of this file.
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 }