math.java

一个非常好的ssh客户端实现

/******************************************************************************
 *
 * Copyright (c) 1999-2003 AppGate Network Security AB. All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code as
 * defined in and that are subject to the MindTerm Public Source License,
 * Version 2.0, (the 'License'). You may not use this file except in compliance
 * with the License.
 * 
 * You should have received a copy of the MindTerm Public Source License
 * along with this software; see the file LICENSE.  If not, write to
 * AppGate Network Security AB, Otterhallegatan 2, SE-41118 Goteborg, SWEDEN
 *
 *****************************************************************************/

package com.mindbright.util;

import java.math.BigInteger;

import com.mindbright.jca.security.SecureRandom;

public final class Math {

    public static BigInteger findRandomGenerator(BigInteger order,
						   BigInteger modulo,
						   SecureRandom random) {
	BigInteger one = BigInteger.valueOf(1);
	BigInteger aux = modulo.subtract(BigInteger.valueOf(1));
	BigInteger t   = aux.mod(order);
	BigInteger generator;

	if(t.longValue() != 0) {
	    return null;
	}

	t = aux.divide(order);

	while(true) {
	    generator = new BigInteger(modulo.bitLength(), random);
	    generator = generator.mod(modulo);
	    generator = generator.modPow(t, modulo);
	    if(generator.compareTo(one) != 0)
		break;
	}

	aux = generator.modPow(order, modulo);

	if(aux.compareTo(one) != 0) {
	    return null;
	}

	return generator;
    }

    public static BigInteger[] findRandomStrongPrime(int primeBits,
						     int orderBits,
						     SecureRandom random) {
	BigInteger one = BigInteger.valueOf(1);
	BigInteger u, aux, aux2;
	long[] table_q, table_u, prime_table;
	PrimeSieve sieve = new PrimeSieve(16000);
	int table_count  = sieve.availablePrimes() - 1;
	int i, j;
	boolean flag;
	BigInteger prime = null, order = null;

	order = new BigInteger(orderBits, 20, random);

	prime_table = new long[table_count];
	table_q     = new long[table_count];
	table_u     = new long[table_count];

	i = 0;
	for(int pN = 2; pN != 0; pN = sieve.getNextPrime(pN), i++) {
	    prime_table[i] = (long)pN;
	}

	for(i = 0; i < table_count; i++) {
	    table_q[i] =
		(order.mod(BigInteger.valueOf(prime_table[i])).longValue() *
		 (long)2) % prime_table[i];
	}

	while(true) {
	    u = new BigInteger(primeBits, random);
	    u.setBit(primeBits - 1);
	    aux = order.shiftLeft(1);
	    aux2 = u.mod(aux);
	    u = u.subtract(aux2);
	    u = u.add(one);

	    if(u.bitLength() <= (primeBits - 1))
		continue;

	    for(j = 0; j < table_count; j++) {
		table_u[j] =
		    u.mod(BigInteger.valueOf(prime_table[j])).longValue();
	    }

	    aux2 = order.shiftLeft(1);

	    for(i = 0; i < (1 << 24); i++) {
		long cur_p;
		long value;

		flag = true;
		for(j = 1; j < table_count; j++) {
		    cur_p = prime_table[j];
		    value = table_u[j];
		    if(value >= cur_p)
			value -= cur_p;
		    if(value == 0)
			flag = false;
		    table_u[j] = value + table_q[j];
		}
		if(!flag)
		    continue;

		aux   = aux2.multiply(BigInteger.valueOf(i));
		prime = u.add(aux);

		if(prime.bitLength() > primeBits)
		    continue;

		if(prime.isProbablePrime(20))
		    break;
	    }

	    if(i < (1 << 24))
		break;
	}

	return new BigInteger[] { prime, order };
    }

}