The key pair relationship in most algorithms is accomplished by the use of a logarithm .
LogarithmsA logarithm function is simply a curve that has an inverse of an exponential function. Figure 4-6 demonstrates two logarithms x = log 2 y and y = log 2 x, or the same functions in exponential form as y = 2 x and x = 2 y , respectively. Figure 4-6: The logarithmic function The formulas in Figure 4-6 cover all points along each curve. In most cases, when finding a key a positive integer is found. Ensuring that the logarithmic function results in an integer limits the logarithmic functions and numbers that can be used. The limitation to a specific result defines the logarithmic functions to be discrete.
Just using the formula and mapping all of the points, as in either formula in Figure 4-6, produces an infinite number of results. A discrete logarithm requires one point as the result. To help force the discrete logarithm into a non-negative integer result, modular exponentials are used. A modular exponential is used to compute the remainder of a value. Using a modulus that is positive from a positive number will usually produce these results. See Listing 4-3 for an example and the tip that follows for a simple explanation of modular math.
Listing 4-3: Modular exponential An example: 5 9 mod 563 = 1953125 mod 563 = 78 1953125 / 563 roughly equals 3469, not an integer 563 X 3469 = 1953047, which is an integer 1953125 - 1953047 = 78, which is an integer
Most key algorithms start with at least two numbers that are used to calculate the key. The purpose of the key algorithms is to provide numbers without providing the key. Listing 4-3 shows a formula in which three numbers, 5, 9, and 563, can be used to calculate the key 78. If only two of the numbers are transmitted across the network, and the third number is agreed upon secretly , then anyone watching the network has no way to compute the key 78.
Listing 4-4 demonstrates performing the modular exponential calculation in Java using the java.math.BigInteger class and the modPow method. The sample code selects prime numbers at random. Many keying algorithms will use both prime numbers and random numbers. An output of the sample is shown in Listing 4-5. Listing 4-4: The TestRandomMod class: A sample code for performing the modular exponential package com.richware.chap04; import java.util.*; import java.math.*; import java.security.*; /** * Class TestRandomMod * Description: This is an example of * a random modular exponent * * Copyright: Copyright (c) 2002 Wiley Publishing, Inc. * @author Rich Helton <rhelton@richware.com> * @version 1.0 * DISCLAIMER: Please refer to the disclaimer at the beginning of this book. */ public class TestRandomMod { /** * Method main * Description: Main Driver * @param args none * */ public static void main(String[] args) { try { /* * bitLength - bitLength of the returned BigInteger. * certainty - a measure of the uncertainty * that the caller is willing to tolerate. * The probability that the new BigInteger * represents a prime number will exceed (1 - 1/2certainty). * The execution time of this constructor is proportional * to the value of this parameter. * rnd - source of random bits used to * select candidates to be tested for primality. */ int bitLength = 512; // 512 bits SecureRandom rnd = new SecureRandom(); int certainty = 90; // 1 - 1/2(90) certainty System.out.println("BitLength : " + bitLength); System.out .println("Selecting Prime Numbers.............."); BigInteger mod = new BigInteger(bitLength, certainty, rnd); /* probablePrime * Returns a positive BigInteger * that is probably prime, with the * specified bitLength. * The probability that a BigInteger * returned by this method * is composite does not exceed 2-100. * Parameters: * bitLength - bitLength of the returned BigInteger. * rnd - source of random bits * used to select candidates to be * tested for primality. */ BigInteger exponent = BigInteger.probablePrime(bitLength, rnd); BigInteger n = BigInteger.probablePrime(bitLength, rnd); /* modPow * Returns a BigInteger whose * value is (thisexponent mod m). *(Unlike pow, this method permits negative exponents.) */ BigInteger result = n.modPow(exponent, mod); System.out .println("Number ^ Exponent MOD Modulus = Result"); System.out.println("Number*****************"); System.out.println(n); System.out.println("Exponent***************"); System.out.println(exponent); System.out.println("Modulus****************"); System.out.println(mod); System.out.println("Result*****************"); System.out.println(result); } catch (Exception ex) { ex.printStackTrace(); } } } Listing 4-5: Output of Listing 4-4 >java com.richware.chap04.TestRandomMod BitLength : 512 Selecting Prime Numbers.............. Number ^ Exponent MOD Modulus = Result Number***************** 124360609876767768746348060816505096975456907380052542286710384110642464 64229619 814100649940039019797203550709079415708490106455932087830562917582234446 223 Exponent*************** 117965214013400606904211878217384250281335644213112378626958218353006681 79928419 897743830953398844532112367553465950056215247923594911381025265273981821 493 Modulus**************** 115489877797216423545391503051833238692683204592038044780171620913714773 58398072 616196114232532083215056159039067285541221229508244782320138555251395447 511 Result***************** 846763518042672486773471573681072795400983482860144851076895903369780711 74521773 323544235221767874853119459005693347307484749729099211610361676171018807 52 Listing 4-5 displays the results of choosing prime random numbers that are 512 bits long to perform the calculation. Prime and random numbersMany keys will use prime and random numbers for their agreements. A prime number is a natural number that has no integer factors except itself and 1. These numbers cannot be broken down into further multiplications. Listing 4-4 demonstrates getting prime numbers using the java.math.BigInteger class. The demonstration sets the certainty to 90, thus using 1/2 90 , or 8.0779356694631608874161005084957e-28 probability that the number might not be prime. The higher the certainty number, the longer the method takes to calculate the prime number. Prime numbers play a significant role because some of the algorithms to calculate the key will only work with a prime number. Random numbers are used so that the same numbers or a pattern is not used to generate a key. For instance, if a user always used 9 and 10 as the primary numbers to generate the keys, the keys would most likely be same value. To avoid any type of pattern, a random number is used. The random number is required to be a certain bit size so that it is not too large or too small to be applied to the algorithm. Listing 4-4 displays the use of the java.security.SecureRandom class. This is discussed in more detail later in the book.
Java Security Solutions ISBN: 0764549286
EAN: 2147483647 Year: 2001
Pages: 222 Authors: Rich Helton, Johennie Helton
flylib.com © 2008-2017. If you may any questions please contact us: flylib@qtcs.net |