Source code: com/ssttr/crypto/DH.java

   /*
    * DH.java
    * 
    * This code is considered to be Public Domain as it was originaly posted anonymously to
    * Usenet.  See the comments below for details.
    *
    * Created on July 3, 2003, 9:24 PM
    */
   
  package com.ssttr.crypto;
  
  import com.ssttr.util.Strings;
  
  /**
   * This class performs the basic essential functions for Diffie-Hellman key genereration.
   * Specifily, given a generator (g), exponent (x), and prime modulus (m), it performs:
   * <code>g<sup>x</sup> mod m</code>.  Of course this could also be done just as easily
   * with the java.math.BigInteger.modPow() method, but that class is rarely included
   * in J2ME and embeded JVMs this can still be usefull.
   * <p>
   * It is worth noting that this class has been tested to reliably work on key sizes >= 64 bits.
   * It will often fail on a keys < 64 bits.  This could (in theory) be fixed but since key sizes
   * less than 64 bits are generally considered worthless (due to the ability to brute force the
   * entire keyspace in short order) this has been classified as a featurenotbug.
   * <p>
   * To generate a shared private key:<br>
   * Jack performs:<br>
   * <pre>
   * int keySize = 128;
   * DH dh = new DH(keySize);
   * Random rnd = new Random();
   * String gen = "3";
   * String jacksExp = Long.toString( Math.abs(rnd.nextLong()), 16 ).toUpperCase();
   * String prime = "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF61";
   * String publicKey = dh.generateKey( gen, jacksExp, prime);
   * </pre>
   * <br>
   * Then sends keySize, gen, prime, and publicKey to Jill (but exp MUST be kept secret!).<br>
   * Then Jill:<br>
   * <pre>
   * DH dh = new DH(jacksKeySize);
   * Random rnd = new Random();
   * String jillsExp = Long.toString( Math.abs(rnd.nextLong()), 16 ).toUpperCase();
   * String publicKey = dh.generateKey( jacksGen,       jillsExp, jacksPrime);
   * String jillsSecretKey = dh.generateKey( jacksPublicKey, jillsExp, jacksPrime);
   * </pre>
   * <br>
   * And sends publicKey to Jack.<br>
   * Who then:<br>
   * <pre>
   * String jacksSecretKey = dh.generateKey( jillsPublicKey, jacksExp, prime);
   * </pre>
   * Now if everything worked properly (and it should have) jacksSecretKey == jillsSecretKey
   * and they can now use a shared-secret algorithm (like {@link TEA}) to communicate.
   * <p>
   * Most of the code for this class was blatently stollen (and subsequently ported to Java) from
   * <a href="http://www.cypherspace.org/~adam/rsa/dh-in-C.html">http://www.cypherspace.org/~adam/rsa/dh-in-C.html</a>.
   * Which is copied here in case the page goes down:
   * <p>
   * <p>
   * <xmp>
   * Diffie-Hellman Key Exchange
   * This 10 line C program was written by an anonymous poster to sci.crypt. Possibly the poster is located in the US,
   * though there is no way of telling. Anyway nobody's code includes a beautifully compacted big num implementation,
   * so all you need is a C compiler.
   *
   * If you are trying this out with the example nobody gives in his message you should note that you must change the
   * initialisation of S=129 on the first line to be S=3 (size of key in bytes + 1) - nobody says this in the text,
   * it just caught me out first time.
   *
   * I posted a follow up to this message to sci.crypt in which I mail dropped nobody a message using the 1024 bit
   * Diffie-Hellman key exchange he/she initiated. This message includes the Diffie-Hellman in perl I wrote (it's
   * very similar to RSA in it's use of modular exponentiation) inspired by nobody's code.
   *
   * My perl-diffie-hellman plus examples of use (inspired by nobody's C code)
   *
   * Here is nobody's posting to sci.crypt (it was cross posted to talk.politics.crypto and alt.anonymous.messages also):
   *
   * Newsgroups: sci.crypt,talk.politics.crypto,alt.anonymous.messages
   * From: nobody@replay.com (Name withheld by request)
   * Organization: Replay and Company UnLimited.
   * X-Warning: This message was forwarded by an Anonymous Remailer.
   * X-Comment: Replay does not necessarily approve of the contents of this posting.
   * X-Comment: Please report inappropriate use to &lt;postmaster@replay.com&gt;
   * Subject: Export-a-crypto-system: Diffie-Hellman
   * X-Posting-Host: xs1.xs4all.nl
   * Date: Sun, 2 Apr 1995 02:25:08 +0000
   * Sender: usenet@demon.co.uk
   * Lines: 88
   *
   * Inspired by Adam Back's RSA code...
   *
   * The export-a-crypto-system sig II - Diffie-Hellman in 10 lines of C:
   *
   * #include &lt;stdio.h&gt; // Usage: dh base exponent modulus
   * typedef unsigned char u;u m[1024],g[1024],e[1024],b[1024];int n,v,d,z,S=129;a(
   * u *x,u *y,int o){d=0;for(v=S;v--;){d+=x[v]+y[v]*o;x[v]=d;d=d>>8;}}s(u *x){for(
   * v=0;(v<S-1)&&(x[v]==m[v]);)v++;if(x[v]>=m[v])a(x,m,-1);}r(u *x){d=0;for(v=0;v<
   * S;){d|=x[v];x[v++]=d/2;d=(d&1)<<8;}}M(u *x,u *y){u X[1024],Y[1024];bcopy(x,X,S
  * );bcopy(y,Y,S);bzero(x,S);for(z=S*8;z--;){if(X[S-1]&1){a(x,Y,1);s(x);}r(X);a(Y
  * ,Y,1);s(Y);}}h(char *x,u *y){bzero(y,S);for(n=0;x[n]>0;n++){for(z=4;z--;)a(y,y
  * ,1);x[n]|=32;y[S-1]|=x[n]-48-(x[n]>96)*39;}}p(u *x){for(n=0;!x[n];)n++;for(;n<
  * S;n++)printf("%c%c",48+x[n]/16+(x[n]>159)*7,48+(x[n]&15)+7*((x[n]&15)>9));
  * printf("\n");}main(int c,char **v){h(v[1],g);h(v[2],e);h(v[3],m);bzero(b,S);b[
  * S-1]=1;for(n=S*8;n--;){if(e[S-1]&1)M(b,g);M(g,g);r(e);}p(b);}
  * </code>
  *
  * To compile it, type: gcc dh.c -o dh
 
  * The program is somewhat slow, but it works, and it's almost small enough to
  * attach to your posts as a signature.  It's set up for 1024-bit numbers, but
  * you can allow bigger numbers by setting the value of the S variable.  To
  * allow for carry digits, the value set for S must be one greater than the
  * maximum length in bytes of the modulus that you wish to use.  The time to
  * calculate a modular exponent is roughly proportional to the cube of the
  * number of bits, so if a 1024-bit number takes 5 minutes, a 2048-bit number
  * will take 40 minutes, and a 4096-bit number would take about 5 hours.
  * All numbers are entered and printed in hexadecimal.  Because of the minimal
  * size, the program doesn't check for human error; it may do strange things
  * if you give it bad data.
  * 
  * For example purposes, the numbers used below are small, any practical
  * use would require numbers of 512-1024 bits in length.
  * 
  * To generate a key, Joe selects a public generator (3 in this example), a
  * public prime modulus (10001 hexadecimal), and a secret exponent (9A2E hex).
  * Joe then calculates the following:
  * 
  * joe% dh 3 9A2E 10001
  * C366
  * 
  * This is his public key.  Joe sends these three numbers (3,10001,C366)
  * to Alice.
  * 
  * To encrypt a message to Joe, Alice picks a secret random number (4C20 in
  * this example) and using Joe's generator and modulus, calculates:
  * 
  * alice% dh 3 4C20 10001
  * 6246
  * 
  * She sends this result to Joe.  Alice then takes Joe's public key and her
  * secret random number and calculates:
  * 
  * alice% dh C366 4C20 10001
  * DED4
  * 
  * She uses this result as a session key to encrypt her message to Joe.
  * 
  * To decrypt the message, Joe uses the number Alice sent him, and his
  * secret key to calculate:
  * 
  * joe% dh 6246 9A2E 10001
  * DED4
  * 
  * Joe now has the session key and can decrypt Alice's message.
  * 
  * An eavesdropper sees Joe send Alice three numbers (3,10001,C366), and
  * sees Alice send Joe '6246'.  But the eavesdropper can not use these
  * numbers to calculate the secret session key (DED4), and thus can not
  * decrypt the message.
  * 
  * 
  * You can use this program to do RSA also, but generating a key is more
  * difficult.
  * 
  * I wonder if the USA ITAR law covers integer math programs?
  * 
  * 
  * Here is my key:
  * 
  * g=2
  * X=28D4FEFED5CC1ACDBE7D550813A1518DB56812855014EFDDD9E038A15BE52FD524D6FFA9C9E3
  * 1E59DDFEF705EAB75DD031908F10B584F5A2495BC2C1433ACB6FA065FB0850ECCF139993BA4564
  * B97A289FBCD59524FC30F377060366077378288F93173AC508D1DC5B4D9DAE0AFECFFA9E5494C5
  * 3EED74C4E29DEBAF0C08B720
  * m=DE9B707D4C5A4633C0290C95FF30A605AEB7AE864FF48370F13CF01D49ADB9F23D19A439F753
  * EE7703CF342D87F431105C843C78CA4DF639931F3458FAE8A94D1687E99A76ED99D0BA87189F42
  * FD31AD8262C54A8CF5914AE6C28C540D714A5F6087A171FB74F4814C6F968D72386EF356A05180
  * C3BEC7DDD5EF6FE76B0531C3
  * </xmp>
  *
  * <p>
  * @author  anonymous
  */
 public class DH
 {
     Object lock = new Object();
     
     byte[] m,g,e,b,key,tmp;
     
     int n,v,d,z,S,keySize;
     
     /**
      * Creates a new instance of DH.  Each instance of DH is threadsafe in that
      * it uses a lock to guarentee that all calls to generateKey() are serialized.
      *
      * @param keySize The size of the key(s) to be generated, in bits.
      *
      * @throws IllegalArgumentException if keySize < 64
      */
     public DH (final int keySize)
     {
         if( keySize < 64 )
             throw new IllegalArgumentException("keySize < 64");
         
         this.keySize = keySize;
         S = keySize / 8 + 1;
     }
     
     private final void initialize()
     {
         m = new byte[S];
         g = new byte[S];
         e = new byte[S];
         b = new byte[S];
         key = new byte[S*2];
     }
     
     public String generateKey (String generator, String exponent, String prime)
     {
         synchronized ( lock )
         {
             initialize();
 
             h (generator.getBytes(),g);
             h (exponent.getBytes(),e);
             h (prime.getBytes(),m);
 
             generateKey();
 
             tmp = trim(b);
             final String k = Strings.toHex(tmp);
             // Save a little memory
             m = g = e = b = key = tmp = null;
             return k;
             
             /*
             p (b);
 
             tmp = new byte[(S-1)*2];
             System.arraycopy(key,0,tmp,0,tmp.length);
 
             final String k = new String(tmp);
             // Save a little memory
             m = g = e = b = key = tmp = null;
             
             return k;
             */
         }
     }
     
     public byte[] generateKey (byte[] generator, byte[] exponent, byte[] prime)
     {
         synchronized ( lock )
         {
             initialize();
 
             int l;
             l = Math.min(S,generator.length);
             System.arraycopy( generator, 0, g, S - l, l );
             l = Math.min(S,exponent.length);
             System.arraycopy( exponent, 0, e, S - l, l );
             l = Math.min(S,prime.length);
             System.arraycopy( prime, 0, m, S - l, l );
 
             generateKey();
 
             final byte[] k = trim(b);
             // Save a little memory
             m = g = e = b = key = tmp = null;
 
             return k;
         }
     }
     
     private final void generateKey()
     {
         bzero (b,S);
         
         b[S-1] = 1;
         
         for( n = keySize; n-- > 0; )
         {
             if( (e[S-1] & 1) != 0 )
                 M (b,g);
             M (g,g);
             r (e);
         }
     }
     
     private void s (byte[] x)
     {
         for( v = 0; (v < S - 1) && (x[v] == m[v]); v++ );
 
         if( (x[v] & 0xFF) >= (m[v] & 0xFF) )
             a (x,m,-1);
     }
     
     private void r (byte[] x)
     {
         d = 0;
         for( v = 0; v < S; )
         {
             d |= (x[v] & 0xFF);
             x[v++] = (byte)(d / 2);
             d = ( d & 1 ) << 8;
         }
     }
     
     private void M (byte[] x,byte[] y)
     {
         byte[] X = new byte[S], Y = new byte[S];
         
         System.arraycopy (x,0,X,0,S);
         System.arraycopy (y,0,Y,0,S);
         bzero (x,S);
         
         for( z = keySize; z > 0; z-- )
         {
             if( (X[S-1] & 1) != 0 )
             {
                 a (x,Y,1);
                 s (x);
             }
             r (X);
             a (Y,Y,1);
             s (Y);
         }
     }
     
     private void a ( byte[] x,byte[] y,int o)
     {
         d = 0;
         for( v = S - 1; v >= 0; v -- )
         {
             d += (x[v] & 0xFF) + (y[v] & 0xFF) * o;
             x[v] = (byte)d;
             d >>= 8;
         }
     }
     
     private void h (byte[] x,byte[] y)
     {
         int j;
         bzero (y,S);
         for( n = 0; n < x.length && x[n] > 0; n++ )
         {
             for( z = 4; z-- > 0; )
                 a (y,y,1);
             x[n] |= 0x20;
             j = x[n] & 0xFF;
             y[S-1] |= (byte)(j - 48 - (j > 0x60 ? 39 : 0));
         }
     }
 /*    
     private void p (byte[] x)
     {
         for( n = 0; x[n] == 0;)
             n++;
         
         bzero(key,key.length);
         
         int i = 0, j;
 
         for( ; n < S; n++ )
         {
             j = x[n] & 0xFF;
             key[i++] = (byte)(48 +  j / 0x10 + (    j        > 0x9f ? 0x7 : 0) );
             key[i++] = (byte)(48 + (j & 0xF) + ( ( (j & 0xf) > 0x9) ? 0x7 : 0) );
         }
     }
 */    
     private void bzero(final byte[] a, int len)
     {
         while( --len >= 0 )
             a[len] = 0;
     }
     
     private static byte[] trim(final byte[] bytes)
     {
         int i;
         for( i = 0; i < bytes.length && bytes[i] == 0; i ++ );
         
         byte[] tmp = new byte[ bytes.length - i ];
         System.arraycopy( bytes, i, tmp, 0, tmp.length );
         
         return tmp;
     }
     
 }