Author: j16sdiz
Date: 2009-04-22 07:41:24 +0000 (Wed, 22 Apr 2009)
New Revision: 27199
Added:
trunk/freenet/test/freenet/crypt/DSAGroupGenerator.java
Log:
Doh! DSAGroupGenerator is required for unit test
Copied: trunk/freenet/test/freenet/crypt/DSAGroupGenerator.java (from rev
27195, trunk/freenet/src/freenet/crypt/DSAGroupGenerator.java)
===================================================================
--- trunk/freenet/test/freenet/crypt/DSAGroupGenerator.java
(rev 0)
+++ trunk/freenet/test/freenet/crypt/DSAGroupGenerator.java 2009-04-22
07:41:24 UTC (rev 27199)
@@ -0,0 +1,202 @@
+/* This code is part of Freenet. It is distributed under the GNU General
+ * Public License, version 2 (or at your option any later version). See
+ * http://www.gnu.org/ for further details of the GPL. */
+package freenet.crypt;
+
+import java.math.BigInteger;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+
+import net.i2p.util.NativeBigInteger;
+
+import freenet.support.HexUtil;
+
+/**
+ * DSA Group Generator.
+ * Adapted from FIPS 186-2.
+ * Can generate valid groups of any keysize and any hash length.
+ */
+public class DSAGroupGenerator {
+
+ static BigInteger smallPrimes[] = new BigInteger[] { BigInteger.valueOf(3),
+ BigInteger.valueOf(5), BigInteger.valueOf(7),
+ BigInteger.valueOf(11), BigInteger.valueOf(13),
+ BigInteger.valueOf(17), BigInteger.valueOf(19),
+ BigInteger.valueOf(23), BigInteger.valueOf(29)};
+
+ public static void main(String[] args) throws NoSuchAlgorithmException {
+ Yarrow r = new Yarrow();
+ int keyLength = Integer.parseInt(args[0]);
+ int hashLength = Integer.parseInt(args[1]);
+ System.out.println("Key length: "+keyLength);
+ System.out.println("Hash length: "+hashLength);
+ if(hashLength > keyLength)
+ throw new IllegalArgumentException("hashLength must not
be greater than keyLength");
+ MessageDigest md;
+ if(hashLength == 256) {
+ md = SHA256.getMessageDigest();
+ } else if(hashLength == 160) {
+ md = MessageDigest.getInstance("SHA-160");
+ } else {
+ throw new IllegalArgumentException("Invalid hash length
"+hashLength);
+ }
+ if(keyLength % 64 != 0)
+ throw new IllegalArgumentException("Key length must be
divisible by 64");
+ if(keyLength % hashLength != 0)
+ throw new IllegalArgumentException("Key length must be
divisible by hash length (short cut taken here)");
+ while(!generate(r, keyLength, hashLength, md));
+ }
+
+ private static boolean generate(RandomSource r, int keyLength, int
hashLength, MessageDigest md) {
+
+ int n = keyLength / hashLength;
+
+ // 1: SEED = arbitrary sequence of at least hashLength bits
+ // g = length of SEED in bits
+ int g = hashLength * 2;
+ byte[] seed = new byte[g/8];
+ r.nextBytes(seed);
+
+ // 2: U = SHA-256(SEED) XOR SHA-256(SEED+1 mod 2^g)
+ byte[] seedPlus1 = increment(seed);
+ byte[] seedHash = md.digest(seed);
+ byte[] seedPlus1Hash = md.digest(seedPlus1);
+ byte[] U = new byte[hashLength/8];
+ for(int i=0;i<U.length;i++)
+ U[i] = (byte) (seedHash[i] ^ seedPlus1Hash[i]);
+
+ // 3: Set LSB and MSB on U to 1, q = U
+ byte[] qBuf = new byte[hashLength/8];
+ System.arraycopy(U, 0, qBuf, 0, hashLength/8);
+ qBuf[0] = (byte) (qBuf[0] | 128);
+ qBuf[qBuf.length-1] = (byte) (qBuf[qBuf.length-1] | 1);
+ BigInteger q = new BigInteger(1, qBuf);
+
+ // 4: Check that q is prime, and 2q+1 is prime
+ // 5: If not, restart from step 1
+
+ System.out.println("Maybe got prime: "+q.toString(16)+ "
("+q.bitLength()+ ')');
+
+ if(!isPrime(q))
+ return false;
+
+ System.out.println("Got prime q");
+
+ BigInteger sophieGermainCheck = q.add(q).add(BigInteger.ONE);
+ if(!isPrime(sophieGermainCheck))
+ return false;
+
+ System.out.println("Got SG-prime q");
+
+ // 6: Let counter = 0 and offset = 2
+
+ int counter = 0;
+ int offset = 2;
+
+ byte[] curSeed = seedPlus1;
+
+ while(true) {
+
+ // 7: For k = 0...n let V_k = SHA-256((SEED+offset+k)
mod 2^g)
+
+ byte[][] V = new byte[n][];
+
+ for(int i=0;i<n;i++) {
+ curSeed = increment(curSeed);
+ V[i] = md.digest(curSeed);
+ }
+
+ // 8: Pack all the V's into W bit-wise, set the top bit
so is between 2^(L-1) and 2^L
+ byte[] Wbuf = new byte[keyLength/8];
+ for(int i=0;i<keyLength;i+=hashLength) {
+ System.arraycopy(V[i/hashLength], 0, Wbuf, i/8,
hashLength/8);
+ }
+ Wbuf[0] = (byte) (Wbuf[0] | 128);
+
+ BigInteger X = new NativeBigInteger(1, Wbuf);
+
+ // 9: Let c = X mod 2q. Set p = X - ( c - 1 ).
Therefore p mod 2q = 1.
+
+ BigInteger c = X.mod(q.add(q));
+ BigInteger p = X.subtract(c.subtract(BigInteger.ONE));
+
+ if(p.bitLength() >= keyLength-1) {
+ if(isPrime(p)) {
+ finish(r, hashLength, new
NativeBigInteger(p), new NativeBigInteger(q), seed, counter);
+ return true;
+ }
+ }
+
+ counter++;
+ offset += n;
+ if(counter >= 4096) return false;
+ }
+ }
+
+ private static void finish(RandomSource r, int hashLength,
NativeBigInteger p, NativeBigInteger q, byte[] seed, int counter) {
+ System.out.println("SEED: "+HexUtil.bytesToHex(seed));
+ System.out.println("COUNTER: "+counter);
+ System.out.println("p: "+p.toString(16)+" ("+p.bitLength()+ ')');
+ System.out.println("q: "+q.toString(16)+" ("+q.bitLength()+ ')');
+ // Now generate g (algorithm from appendix 4 of FIPS 186-2)
+ NativeBigInteger g;
+ do {
+ BigInteger e = p.subtract(BigInteger.ONE).divide(q);
+ NativeBigInteger h;
+ do {
+ h = new NativeBigInteger(hashLength, r);
+ } while(h.compareTo(p.subtract(BigInteger.ONE)) >= 0);
+ g = (NativeBigInteger) h.modPow(e, p);
+ } while (g.equals(BigInteger.ONE));
+ DSAGroup group = new DSAGroup(p, q, g);
+ System.out.println("g: "+g.toHexString()+" ("+g.bitLength()+ ')');
+ System.out.println("Group: "+group.verboseToString());
+ long totalSigTime = 0;
+ long totalVerifyTime = 0;
+ for(int i=0;i<10000;i++) {
+ byte[] testHash = new byte[hashLength/8];
+ r.nextBytes(testHash);
+ NativeBigInteger m = new NativeBigInteger(1, testHash);
+ DSAPrivateKey privKey = new DSAPrivateKey(group, r);
+ DSAPublicKey pubKey = new DSAPublicKey(group, privKey);
+ long now = System.currentTimeMillis();
+ DSASignature sig = DSA.sign(group, privKey, m, r);
+ long middle = System.currentTimeMillis();
+ boolean success = DSA.verify(pubKey, sig, m, false);
+ long end = System.currentTimeMillis();
+ if(success) {
+ totalSigTime += (middle - now);
+ totalVerifyTime += (end - middle);
+ } else {
+ System.out.println("SIGNATURE VERIFICATION FAILED!!!");
+ System.exit(1);
+ }
+ }
+ System.out.println("Successfully signed and verified 10,000 times,
average sig time "+totalSigTime / 10000.0 +", average verify time
"+totalVerifyTime/10000.0);
+ }
+
+ private static byte[] increment(byte[] seed) {
+ byte[] obuf = new byte[seed.length];
+ System.arraycopy(seed, 0, obuf, 0, seed.length);
+ int pos = seed.length-1;
+ while(pos >= 0) {
+ byte b = (byte) (obuf[pos] + 1);
+ obuf[pos] = b;
+ if(b != 0) return obuf;
+ pos--;
+ }
+ return obuf;
+ }
+
+ public static boolean isPrime(BigInteger b) {
+ if(BigInteger.ONE.compareTo(b) > -1)
+ throw new IllegalArgumentException("Can't be a prime
number!");
+ for(int i = 0; i < smallPrimes.length; i++) {
+ if(b.mod(smallPrimes[i]).equals(BigInteger.ZERO))
+ return false;
+ }
+ // FIPS 186-2 recommends 2^100:1 confidence
+ return b.isProbablePrime(200);
+ }
+
+}
Property changes on: trunk/freenet/test/freenet/crypt/DSAGroupGenerator.java
___________________________________________________________________
Added: svn:mergeinfo
+ /branches/db4o/freenet/src/freenet/crypt/DSAGroupGenerator.java:19964-26320
/branches/db4o/src/freenet/crypt/DSAGroupGenerator.java:25594
_______________________________________________
cvs mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/cvs
