IdeaCipher.java

00001 // IdeaCipher - the IDEA encryption method
00002 //
00003 // Copyright (C) 1996 by Jef Poskanzer <jef@acme.com>.  All rights reserved.
00004 //
00005 // Redistribution and use in source and binary forms, with or without
00006 // modification, are permitted provided that the following conditions
00007 // are met:
00008 // 1. Redistributions of source code must retain the above copyright
00009 //    notice, this list of conditions and the following disclaimer.
00010 // 2. Redistributions in binary form must reproduce the above copyright
00011 //    notice, this list of conditions and the following disclaimer in the
00012 //    documentation and/or other materials provided with the distribution.
00013 //
00014 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
00015 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00016 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00017 // ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
00018 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00019 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00020 // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00021 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00022 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00023 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00024 // SUCH DAMAGE.
00025 //
00026 // Visit the ACME Labs Java page for up-to-date versions of this and other
00027 // fine Java utilities: http://www.acme.com/java/
00028 
00029 package Acme.Crypto;
00030 
00031 import java.io.*;
00032 
00034 // <P>
00035 // The basic algorithm came from "Applied Cryptography", Bruce Schneier,
00036 // ISBN 0-471-59756-2.
00037 // <P>
00038 // This is surprisingly fast, for pure Java.  On a SPARC 20, wrapped
00039 // in Acme.Crypto.EncryptedOutputStream or Acme.Crypto.EncryptedInputStream,
00040 // it does around 7500 bytes/second, slightly faster than Acme.Crypto.DesCipher.
00041 // <P>
00042 // The IDEA(tm) block cipher is covered by patents held by ETH and a
00043 // Swiss company called Ascom-Tech AG.  The Swiss patent number is
00044 // PCT/CH91/00117, the European patent number is EP 0 482 154 B1, and
00045 // the U.S. patent number is US005214703.  IDEA(tm) is a trademark of
00046 // Ascom-Tech AG.  There is no license fee required for noncommercial
00047 // use.  Commercial users may obtain licensing details from Dieter
00048 // Profos, Ascom Tech AG, Solothurn Lab, Postfach 151, 4502 Solothurn,
00049 // Switzerland, Tel +41 65 242885, Fax +41 65 235761.
00050 // <P>
00051 // <A HREF="/resources/classes/Acme/Crypto/IdeaCipher.java">Fetch the software.</A><BR>
00052 // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
00053 // <P>
00054 // @see EncryptedOutputStream
00055 // @see EncryptedInputStream
00056 
00057 public class IdeaCipher extends BlockCipher
00058     {
00059 
00060     // Constructor, string key.
00061     public IdeaCipher( String keyStr )
00062         {
00063         super( 16, 8 );
00064         setKey( keyStr );
00065         }
00066 
00067     // Constructor, byte-array key.
00068     public IdeaCipher( byte[] key )
00069         {
00070         super( 16, 8 );
00071         setKey( key );
00072         }
00073 
00074     // Key routines.
00075 
00076     private int[] encryptKeys = new int[52];
00077     private int[] decryptKeys = new int[52];
00078 
00080     public void setKey( byte[] key )
00081         {
00082         int k1, k2, j;
00083         int t1, t2, t3;
00084 
00085         // Encryption keys.  The first 8 key values come from the 16
00086         // user-supplied key bytes.
00087         for ( k1 = 0; k1 < 8; ++k1 )
00088             encryptKeys[k1] =
00089                 ( ( key[2 * k1] & 0xff ) << 8 ) | ( key[ 2 * k1 + 1] & 0xff );
00090 
00091         // Subsequent key values are the previous values rotated to the
00092         // left by 25 bits.
00093         for ( ; k1 < 52; ++k1 )
00094             encryptKeys[k1] =
00095                 ( ( encryptKeys[k1 - 8] << 9 ) |
00096                   ( encryptKeys[k1 - 7] >>> 7 ) ) & 0xffff;
00097 
00098         // Decryption keys.  These are the encryption keys, inverted and
00099         // in reverse order.
00100         k1 = 0;
00101         k2 = 51;
00102         t1 = mulinv( encryptKeys[k1++] );
00103         t2 = -encryptKeys[k1++];
00104         t3 = -encryptKeys[k1++];
00105         decryptKeys[k2--] = mulinv( encryptKeys[k1++] );
00106         decryptKeys[k2--] = t3;
00107         decryptKeys[k2--] = t2;
00108         decryptKeys[k2--] = t1;
00109         for ( j = 1; j < 8; ++j )
00110             {
00111             t1 = encryptKeys[k1++];
00112             decryptKeys[k2--] = encryptKeys[k1++];
00113             decryptKeys[k2--] = t1;
00114             t1 = mulinv( encryptKeys[k1++] );
00115             t2 = -encryptKeys[k1++];
00116             t3 = -encryptKeys[k1++];
00117             decryptKeys[k2--] = mulinv( encryptKeys[k1++] );
00118             decryptKeys[k2--] = t2;
00119             decryptKeys[k2--] = t3;
00120             decryptKeys[k2--] = t1;
00121             }
00122         t1 = encryptKeys[k1++];
00123         decryptKeys[k2--] = encryptKeys[k1++];
00124         decryptKeys[k2--] = t1;
00125         t1 = mulinv( encryptKeys[k1++] );
00126         t2 = -encryptKeys[k1++];
00127         t3 = -encryptKeys[k1++];
00128         decryptKeys[k2--] = mulinv( encryptKeys[k1++] );
00129         decryptKeys[k2--] = t3;
00130         decryptKeys[k2--] = t2;
00131         decryptKeys[k2--] = t1;
00132         }
00133 
00134 
00135     // Block encryption routines.
00136 
00137     private int[] tempShorts = new int[4];
00138 
00140     public void encrypt( byte[] clearText, int clearOff, byte[] cipherText, int cipherOff )
00141         {
00142         squashBytesToShorts( clearText, clearOff, tempShorts, 0, 4 );
00143         idea( tempShorts, tempShorts, encryptKeys );
00144         spreadShortsToBytes( tempShorts, 0, cipherText, cipherOff, 4 );
00145         }
00146 
00148     public void decrypt( byte[] cipherText, int cipherOff, byte[] clearText, int clearOff )
00149         {
00150         squashBytesToShorts( cipherText, cipherOff, tempShorts, 0, 4 );
00151         idea( tempShorts, tempShorts, decryptKeys );
00152         spreadShortsToBytes( tempShorts, 0, clearText, clearOff, 4 );
00153         }
00154 
00155     // Run IDEA on one block.
00156     private void idea( int[] inShorts, int[] outShorts, int[] keys )
00157         {
00158         int x1, x2, x3, x4, k, t1, t2;
00159 
00160         x1 = inShorts[0];
00161         x2 = inShorts[1];
00162         x3 = inShorts[2];
00163         x4 = inShorts[3];
00164         k = 0;
00165         for ( int round = 0; round < 8; ++round )
00166             {
00167             x1 = mul( x1 & 0xffff, keys[k++] );
00168             x2 = x2 + keys[k++];
00169             x3 = x3 + keys[k++];
00170             x4 = mul( x4 & 0xffff, keys[k++] );
00171             t2 = x1 ^ x3;
00172             t2 = mul( t2 & 0xffff, keys[k++] );
00173             t1 = t2 + ( x2 ^ x4 );
00174             t1 = mul( t1 & 0xffff, keys[k++] );
00175             t2 = t1 + t2;
00176             x1 ^= t1;
00177             x4 ^= t2;
00178             t2 ^= x2;
00179             x2 = x3 ^ t1;
00180             x3 = t2;
00181             }
00182         outShorts[0] = mul( x1 & 0xffff, keys[k++] ) & 0xffff;
00183         outShorts[1] = ( x3 + keys[k++] ) & 0xffff;
00184         outShorts[2] = ( x2 + keys[k++] ) & 0xffff;
00185         outShorts[3] = mul( x4 & 0xffff, keys[k++] ) & 0xffff;
00186         }
00187 
00188     // Multiplication modulo 65537.
00189     private static int mul( int a, int b )
00190         {
00191         int ab = a * b;
00192         if ( ab != 0 )
00193             {
00194             int lo = ab & 0xffff;
00195             int hi = ab >>> 16;
00196             return ( ( lo - hi ) + ( lo < hi ? 1 : 0 ) ) & 0xffff;
00197             }
00198         if ( a != 0 )
00199             return ( 1 - a ) & 0xffff;
00200         return ( 1 - b ) & 0xffff;
00201         }
00202     
00203     // The multiplicative inverse of x, modulo 65537.  Uses Euclid's
00204     // GCD algorithm.  It is unrolled twice to avoid swapping the
00205     // meaning of the registers each iteration, and some subtracts
00206     // of t have been changed to adds.
00207     private static int mulinv( int x )
00208         {
00209         int t0, t1, q, y;
00210         if ( x <= 1 )
00211             return x;           // 0 and 1 are self-inverse
00212         t0 = 1;
00213         t1 = 0x10001 / x;       // since x >= 2, this fits into 16 bits
00214         y = ( 0x10001 % x ) & 0xffff;
00215         for (;;)
00216             {
00217             if ( y == 1 )
00218                 return ( 1 - t1 ) & 0xffff;
00219             q = x / y;
00220             x = x % y;
00221             t0 = ( t0 + q * t1 ) & 0xffff;
00222             if ( x == 1 )
00223                 return t0;
00224             q = y / x;
00225             y = y % x;
00226             t1 = ( t1 + q * t0 ) & 0xffff;
00227             }
00228         }
00229 
00230 
00232     public static void main( String[] args )
00233         {
00234         // Check that mul and mulinv are working for all 16-bit numbers.
00235         for ( int a = 0; a < 65536; ++a )
00236             {
00237             int b = mulinv( a );
00238             int c = mul( a, b );
00239             if ( c != 1 )
00240                 System.err.println( "mul/mulinv flaw: " + a + " * " + b + " = " + c );
00241             }
00242         }
00243 
00244     }

Generated on Mon Dec 4 11:03:27 2006 for OpenMobileIS by  doxygen 1.5.1-p1