Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

com.ssttr.crypto
Class DH  view DH download DH.java

java.lang.Object
  extended bycom.ssttr.crypto.DH

public class DH
extends java.lang.Object

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: gx mod m. 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.

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.

To generate a shared private key:
Jack performs:

 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);
 

Then sends keySize, gen, prime, and publicKey to Jill (but exp MUST be kept secret!).
Then Jill:
 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);
 

And sends publicKey to Jack.
Who then:
 String jacksSecretKey = dh.generateKey( jillsPublicKey, jacksExp, prime);
 
Now if everything worked properly (and it should have) jacksSecretKey == jillsSecretKey and they can now use a shared-secret algorithm (like TEA) to communicate.

Most of the code for this class was blatently stollen (and subsequently ported to Java) from http://www.cypherspace.org/~adam/rsa/dh-in-C.html. Which is copied here in case the page goes down:

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


Field Summary
(package private)  byte[] b
           
(package private)  int d
           
(package private)  byte[] e
           
(package private)  byte[] g
           
(package private)  byte[] key
           
(package private)  int keySize
           
(package private)  java.lang.Object lock
           
(package private)  byte[] m
           
(package private)  int n
           
(package private)  int S
           
(package private)  byte[] tmp
           
(package private)  int v
           
(package private)  int z
           
 
Constructor Summary
DH(int keySize)
          Creates a new instance of DH.
 
Method Summary
private  void a(byte[] x, byte[] y, int o)
           
private  void bzero(byte[] a, int len)
           
private  void generateKey()
           
 byte[] generateKey(byte[] generator, byte[] exponent, byte[] prime)
           
 java.lang.String generateKey(java.lang.String generator, java.lang.String exponent, java.lang.String prime)
           
private  void h(byte[] x, byte[] y)
           
private  void initialize()
           
private  void M(byte[] x, byte[] y)
           
private  void r(byte[] x)
           
private  void s(byte[] x)
           
private static byte[] trim(byte[] bytes)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

lock

java.lang.Object lock

m

byte[] m

g

byte[] g

e

byte[] e

b

byte[] b

key

byte[] key

tmp

byte[] tmp

n

int n

v

int v

d

int d

z

int z

S

int S

keySize

int keySize
Constructor Detail

DH

public DH(int 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.

Method Detail

initialize

private final void initialize()

generateKey

public java.lang.String generateKey(java.lang.String generator,
                                    java.lang.String exponent,
                                    java.lang.String prime)

generateKey

public byte[] generateKey(byte[] generator,
                          byte[] exponent,
                          byte[] prime)

generateKey

private final void generateKey()

s

private void s(byte[] x)

r

private void r(byte[] x)

M

private void M(byte[] x,
               byte[] y)

a

private void a(byte[] x,
               byte[] y,
               int o)

h

private void h(byte[] x,
               byte[] y)

bzero

private void bzero(byte[] a,
                   int len)

trim

private static byte[] trim(byte[] bytes)