Understanding the Mathematics | Java Security Solutions

The key pair relationship in most algorithms is accomplished by the use of a logarithm .

Note	Recall that logarithms have the mathematical capability to have inverse functions, and also provide the result of the equation by using exponentials.

Logarithms

A logarithm function is simply a curve that has an inverse of an exponential function. Figure 4-6 demonstrates two logarithms x = log ₂ y and y = log ₂ 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.

Tip	Keys are always integers, and in most cases positive. Some algorithms, such as Elliptic Curve, do use negative integers. With logarithmic algorithms, however, keys are positive integers.

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.

Note	Recall that integers do not have a dot, such as 34454 rather than 34454.57567. There are many good mathematics books that address integers, natural numbers, logarithms, discrete logarithms, and modular exponentiation. A discussion of these concepts is beyond the scope of this book.

Listing 4-3: Modular exponential

 An example: 5 ⁹ 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

Tip

Here are a few modular math concepts to refresh your memory:

Modular math uses division and only uses the whole number remainder (never fractions or negative numbers).
The modulus is the remainder.
Modular inverse pairs are two numbers that multiplied together equal one.
Use Fermat and Euler for exponentiation properties. Recall that:

Fermant showed m ^(p-1) mod p = 1, when the modulus is prime.

Euler showed that m ^(p-1)(q-1) mod n = 1, when m and n are relative prime numbers.

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.

Tip	Keys are usually prime numbers and some algorithms only work with prime numbers. Recall that a prime number is only divisible by one (1) and itself.

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 numbers

Many 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 ⁹⁰ , 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.

Cross-Reference

Chapter 7 describes random numbers and SecureRandom .

Table of content

Java Security Solutions

ISBN: 0764549286
EAN: 2147483647

Year: 2001
Pages: 222

Authors: Rich Helton, Johennie Helton

BUY ON AMAZON

CISSP Exam Cram 2

Introduction to 80x86 Assembly Language and Computer Architecture

Programming Microsoft ASP.NET 3.5

Logistics and Retail Management: Emerging Issues and New Challenges in the Retail Supply Chain

Persuasive Technology: Using Computers to Change What We Think and Do (Interactive Technologies)

After Effects and Photoshop: Animation and Production Effects for DV and Film, Second Edition