Cryptography Reference
In-Depth Information
//Now, start looking for a generator
boolean isGenerator;
BigInteger pMinusOne=p[0].subtract(BigIntegerMath.ONE);
BigInteger x,z,lnr;
do {
//Start by assuming the test # is a generator
isGenerator=true;
//Pick a random integer x smaller than the safe prime p
x=new BigInteger(p[0].bitLength()-1,sr);
for (int i=0;i<factors.size();i++) {
//Compute z as p-1 divided by the i-th prime factor in the Vector
z=pMinusOne.divide((BigInteger)factors.elementAt(i));
//Raise x to the z power modulo p
lnr=x.modPow(z,p[0]);
//If this equals 1, x is not a generator
if (lnr.equals(BigIntegerMath.ONE)) {
isGenerator=false;
//break-no reason to try the other prime factors for this failed x
break;
}
}
//While x is not a generator, go back and pick another random x
} while (!isGenerator);
//If we get here, we found a generator-set it and return it
p[1]=x;
return p;
}
//getSafePrime() is identical to this, but does not search for a generator.
}
The TestPrimeGeneratorApplet class allows us to retrieve safe primes. Here is a shot of
it, displaying a safe prime and its generator. (See Figure 13.1.)
13.4
CALCULATING DISCRETE LOGARITHMS
There are a variety of discrete log finding algorithms known; however, none of them are fast
enough to break the cryptosystems based on DLP. However, those implementing such ciphers
should take care that the primes they use do not have certain weaknesses, which some of these
algorithms exploit.
Search WWH ::




Custom Search