jan04_daniels.txt

TechTips.zip

Core Java Technologies Tech Tips


                      Tips, Techniques, and Sample Code


Welcome to the Core Java Technologies Tech Tips for January 16,
2004. Here you'll get tips on using core Java technologies and
APIs, such as those in Java 2 Platform, Standard Edition (J2SE).

This issue covers two tips about encryption:

          * Asymmetric Encryption Keys With the KeyPairGenerator
          * Encryption and Decryption Using Symmetric Keys

These tips were developed using Java 2 SDK, Standard Edition,
v 1.4.2.

This issue of the Core Java Technologies Tech Tips is written by
Daniel H. Steinberg, Director of Java Offerings for Dim Sum
Thinking, Inc, and editor-in-chief for java.net (http://java.net).

You can view this issue of the Tech Tips on the Web at
http://java.sun.com/developer/JDCTechTips/2004/tt0116.html.

See the Subscribe/Unsubscribe note at the end of this newsletter
to subscribe to Tech Tips that focus on technologies and products
in other Java platforms.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

ASYMMETRIC ENCRYPTION KEYS WITH THE KEYPAIRGENERATOR

Public key encryption allows you to provide a public key that can
be used to both decrypt messages you have encrypted and encrypt
messages that only you can decrypt. Dr. Ronald L. Rivest,
Dr. Adi Shamir, and Dr. Leonard M. Adleman are the R, S, and A of
the RSA encryption code. The three were the ACM's 2002 Turing
Award Winners for their work in public key cryptography. At the
ACM Turing Award Winners page 
(http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.
html), you can find presentations from June 7, 2003 by them on
the "Early Days of RSA", on "Cryptology: A Status Report", and on
"Pre-RSA."

The RSA encryption algorithm begins with the random and
independent selection of two large primes p and q, for example,
p=11 and q=31. The next step is to calculate N=(p)(q). For p=11
and q=31, N=(11)(31)=341. Next an integer e is selected between
3 and N-1 (inclusive) that has no factors in common with 
(p-1)(q-1). In this case, (11-1)(31-1) is 300. The number 300 can 
be prime factored as (2) (2) (3)(5)(5). So e must not be a 
multiple of 2, 3, or 5. The algorithm does not require you to 
choose a prime number. For example 49 or 77 would do. To keep the 
numbers small and simple, let's choose e= 7.

Next, the algorithm requires an integer d such that (d)(e)=1
(mod(p-1)(q-1)). The Java programmer's equivalent of mod is the
remainder operator. In this example, e = 7 and (p -1)(q-1) = 300,
so the number d requires that 7d % 300 = 1. One way to find this
number is to look at one more than the multiples of 300, then
check for the first one that is divisible by 7. In other words,
you would check 301, 601, 901, and so on. The number 301 is
divisible by 7 (43 times 7 is 301), so d = 43.

Two pairs of numbers are important. The number N = (p)(q), known 
as the RSA modulus, is a component of both pairs. The first
pair is (N,d), which is known as the RSA private key. The second 
pair is (N,e), which is known as the RSA public key.  The number 
d is the RSA private exponent (d=43). The number e is the RSA 
public exponent (e=7). You publish or otherwise make known the 
public key. You keep the private key (in particular d) and the 
original prime numbers (p and q) a secret.

So where does the Java programming language come into the RSA
picture? It comes in through the java.security package. Using
this package, you can generate the pair of keys for the RSA
algorithm. You do this by first creating an instance of a 
KeyPairGenerator for the RSA algorithm, initializing it with the 
desired key size in number of bits. Then you call the 
generateKeyPair() method to generate the RSA key pair.

   KeyPairGenerator generator =
                   KeyPairGenerator.getInstance("RSA");
   generator.initialize(1024);
   KeyPair keyPair = generator.generateKeyPair();

The algorithm is passed to the factory getInstance() method as
a String. If the algorithm is not supported by the installed 
provider(s), a NoSuchAlgorithmException is thrown.

Each provider must supply (and document) a default initialization. 
If the provider default suits your requirements, you don't have 
to save the intermediate KeyPairGenerator object. You can simply 
generate the key pair with one line of code. However, if you need 
to generate more than one key pair, you can reuse the 
KeyPairGenerator object. This gives you much better performance 
than using a new KeyPairGenerator object every time.

   import java.security.KeyPairGenerator;
   import java.security.NoSuchAlgorithmException;
   import java.security.KeyPair;

   public class AsymmetricKeyMaker {

      public static void main(String[] args) {
        String algorithm = "";
        if (args.length == 1) algorithm = args[0];

        try {
          KeyPair keyPair = KeyPairGenerator
                               .getInstance(algorithm)
                               .generateKeyPair();

          System.out.println(keyPair.getPublic());
          System.out.println(keyPair.getPrivate());

        } catch (NoSuchAlgorithmException e) {
          System.err.println(
            "usage: java AsymmetricKeyMaker <RSA | DSA>");
        }

      }
   }

The String is not case sensitive and so RSA could be entered as
rsa, Rsa, or any other variation. If you run the program like
this:

   java AsymmetricKeyMaker RSA

You should see output that looks like this:

   SunJSSE RSA public key:
      public exponent:
        010001
      modulus:
        b24a9b5b ba01c0cd 65096370 0b5a1b92 08f8555e
        7c1b5017 ec444c58 422b4109
        59f2e15d 43714d92 031db66c 7f5d48cd 17ecd74c
        39b17be2 bf9677be d0a0f02d
        6b24aa14 ba827910 9b166847 8154a2fa 919e0a2a
        53a6e79e 7d2933d8 05fc023f
        bdc76eed aa306c5f 52ed3565 4b0ec8a7 12105637
        af11fa21 0e99fffa 8c658e6d

   SunJSSE RSA private CRT key:
      private exponent:
        78417240 9059965d f3843d99 d94e51c2 52628dd2
        490b731e 6fb2317c 66451e7c
        dc3ac25f 519a1ea4 198df4f9 817ebe17 f7c73c00
        a1f96082 348f9cfd 0b63421b
        7f45f131 c363475c c1b25f57 ee029f5e 0848ba74
        ba81b730 ac4c0135 ce46478c
        e462361a 650e3356 f9b7a0c4 b682557d 3655c052
        5e3554bd 970100bf 10dc1b51
      modulus:
        b24a9b5b ba01c0cd 65096370 0b5a1b92 08f8555e
        7c1b5017 ec444c58 422b4109
        59f2e15d 43714d92 031db66c 7f5d48cd 17ecd74c
        39b17be2 bf9677be d0a0f02d
        6b24aa14 ba827910 9b166847 8154a2fa 919e0a2a
        53a6e79e 7d2933d8 05fc023f
        bdc76eed aa306c5f 52ed3565 4b0ec8a7 12105637
        af11fa21 0e99fffa 8c658e6d
      public exponent:
        010001
      prime p:
        e768033e 21646824 7bd031a0 a2d9876d 79818f8f
        2d7a952e 559fd786 2993bd04
        7e4fdb56 f175d04b 003ae026 f6ab9e0b 2af4a8d7
        ffbe01eb 9b81c75f 0273e12b
      prime q:
        c53d78ab e6ab3e29 fd98d0a4 3e58ee48 45a366ac
        e94dbd60 ea24ffed 0c67c5fd
        3628ea74 88d1d1ad 58d7f067 20c1e3b3 db52adf3
        c421d88c 4c4127db d03592c7
      prime exponent p:
        e09942b4 76029755 f9da3ba0 d70edcf4 337fbdcf
        d0eb6e89 f74f5a07 7ca94947
        6835a805 3dfd047b 17310dc8 a39834a0 504400f1
        0ce6e5c4 413df83d 4e0b1cdb
      prime exponent q:
        829b8afd a1984168 c2d1df4e f32e2653 5b31b17a
        cc5ebb09 a2e26f4a 040def90
        15be104a ac92ebda 72db4308 b72b4ce1 bb58cb71
        80adbcdc 625e3ecb 92daf6df
      crt coefficient:
        4d8190c5 7730b729 00a8f1b4 ae526300 b22d3e7d
        d64df98a c1b19889 5240141b
        0e618ff4 be597979 95195c51 0866c142 30b37a86
        9f3ef519 a3ae6469 14075097

If you are new to Java programming, this output highlights the
value of properly overloading the toString() method. The text
that begins "SunJSSE RSA public key:" is the result of calling
the toString() method in the class RSAPublicKey. It contains the
value of the public exponent which was referred to as e, and the 
modulus N. The text that begins "SunJSSE RSA private key:" is
the result of calling the same method in the class RSAPrivateKey.
It contains the private exponent d and the modulus N. It also 
contains the public exponent e and the generating primes as well 
as some other data. If you are encrypting data you should be 
careful about how you send the public key values. However, if the
values are being used to authenticate a transmission, you should 
make them publicly available so that others can verify that a 
file, for example, originated with you and was delivered 
unaltered.

If you rerun the code and pass in the String DSA, you will find
values for p, q, and g in both the public and private keys. A
value for y is provided in the public key and for x in the
private key. The algorithms are different and so the information
that must be calculated and shared differ.

So how do you use this key pair for encryption? In the case of 
RSA,  you begin by taking some text that you want to encrypt, and 
turn it into a number m that is less than the modulus. You'll 
learn more about this later. However, it's easy see the importance 
of choosing large primes. That's because the product of the 
primes determines the size of what can be encrypted. For example, 
suppose m=2. Then you encrypt by calculating c=m^e (mod N). In 
other words, you raise the number that you are encrypting to the 
power of your public exponent, and take the remainder when 
dividing by the modulus. In this example, 2^43 is 8 more than a 
multiple of 341, so you send the encrypted message c = 8.

Decryption requires you to repeat the process with the private 
key. Take c^d (mod N). In this example, calculate 8^7. Then take 
its remainder when dividing by 341. You get back the original 
message of 2. This is, of course, no accident and will always 
happen. The result follows from an application of Fermat's little