This Tech Tip reprinted with permission by java.sun.com

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, 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 theorem which results in m^(e d) = m (mod N). For security, each party encrypts with the other party's public key.

You can find more information about the RSA algorithm here. You can find more information about the DSA algorithm here.

Copyright (c) 2004-2005 Sun Microsystems, Inc.

All Rights Reserved.