The Rivest, Shamir, and Adleman Key Exchange
After the Diffie-Hellman key exchange, three young professors from MIT named Ron Rivest, Adi Shamir, and Len Adleman published the " Rivest, Shamir and Adleman " algorithm at MIT in 1978 as a method of exchanging keys. They created their own company named from the initials of their last names , Rivest, Shamir, and Adleman, called RSA Security , which can be found at www.rsasecurity.com . The RSA key exchange is also an asymmetric key exchange and became very popular. Understanding the RSA key exchangeThe RSA public key algorithm depends on the calculation of five numbers : p , q , n , e , and d . The numbers p and q are very large prime numbers. The n is the multiplication of p and q . The e is the encryption key that is selected by the user . Finally, the d is the decryption key that is calculated using the numbers. The key agreement for RSA is as follows :
For RSA, the public key is used to encrypt, which is depicted as the symbol e for encryption; the private key is used for decrypting , which is depicted as the symbol d for decryption. After p and q are used in the calculation, they should be thrown away or kept private because the encryption key e can be computed if p and q are found. One addition to RSA is to reuse the p and q in the Chinese Remainder Theorem (CRT) for faster computations . Because p and q are kept private, the CRT cannot be used for faster computations in decryption. Because the RSA private key supports CRT, the JDK 1.4 supports this functionality in the java.security.interface.RSAPrivateCRTKey interface.
The RSA algorithm not only includes key exchange like the DH key exchange, but also goes beyond key exchanging by defining a cipher algorithm. Cipher algorithms are discussed later in the book. RSA will use the discrete logarithm and modular exponential to encrypt and decrypt messages. See Listing 4-12 as an example.
Listing 4-12: Encrypting/decrypting the RSA message
As an example, let's encrypt the number 43: First, I will use the e and n from the example above. CipherText = Message encryption mod n = 43 79 mod 3337 = 1921 The encrypted message of 43 is 1921. To decrypt the message, the same formula applies, except with the d and n instead: Message = Ciphertext decryption mod n = 1921 1019 mod 3337 = 43 The decrypted message of 1921 is 43.
Listing 4-12 is a very simple demonstration of how the RSA algorithm works. Listing 4-13 is a sample output that verifies the results. Listing 4-13: Verifying the RSA algorithm
p = 47 q = 71 n = 3337 phi = 3220 e = 79 d = 1019 Public Key {n,e} = {3337,79} Private Key {n,d} = {3337,1019} Encrypting value.....43 Ciphertext value = 1921 Decrypting value..... Plaintext value = 43
Implementing the RSA key exchangeLike DH, the JDK 1.4 provides a KeyPairGenerator and service provider for implementing the RSA algorithm. To find out what keys are supported and which service providers are implemented on classes currently installed on your system environment, see the output of Listing 4-14 and its associated code in Listing 4-15. Listing 4-14: Service providers installed
>java com.richware.chap04.GetProviderInfo Providers installed on your system: ----------------------------------- [1] - Provider name: SUN Provider version number: 1.2 Provider information: SUN (DSA key/parameter generation; DSA signing; SHA-1, MD5 digests; SecureRandom ; X.509 certificates; JKS keystore; PKIX CertPathValidator; PKIX CertPathBuilder ; LDAP, Collection CertStores) ----------------------------------- [2] - Provider name: SunJSSE Provider version number: 1.4 Provider information: Sun JSSE provider(implements RSA Signatures, PKCS12, SunX509 key/trust factories , SSLv3, TLSv1) ----------------------------------- [3] - Provider name: SunRsaSign Provider version number: 1.0 Provider information: SUN's provider for RSA signatures ----------------------------------- [4] - Provider name: SunJCE Provider version number: 1.4 Provider information: SunJCE Provider (implements DES, Triple DES, Blowfish, PBE, Diffie-Hellman, HMAC -MD5, HMAC-SHA1) ----------------------------------- [5] - Provider name: SunJGSS Provider version number: 1.0 Provider information: Sun (Kerberos v5) -----------------------------------
Listing 4-15: The GetProviderInfo class: Code for generating Listing 4-14
package com.richware.chap04; import java.security.*; import java.util.*; /** * Class GetProviderInfo * Description: This is an example of * retrieving providers * * 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. */ class GetProviderInfo { public static void main(String[] args) { System.out.println("Providers installed on your system:"); System.out.println("-----------------------------------"); Provider[] providerList = Security.getProviders(); for (int i = 0; i < providerList.length; i++) { System.out.println("[" + (i + 1) + "] - Provider name: " + providerList[i].getName()); System.out.println("Provider version number: " + providerList[i].getVersion()); System.out.println("Provider information:\n" + providerList[i].getInfo()); System.out.println("-----------------------------------"); } } }
From Listing 4-14, the service providers for supporting RSA are found in both SunJSSE and SunRsaSign . To specify a particular service provider in code, the provider parameter can be passed in the java.security.KeypairGenerator class like KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA", "SunRsaSign"). If the provider name is not specified, the lookup for the first provider name will be used; in this case, it is the SunJSSE service provider interface for RSA. Just as in the DH code example, after the service provider is selected for generating the keys, the KeyPairGenerator only requires a key size and it will generate the variables to use. The default for the public key exponent is 65537. The java.security.spec.AlgorithmParameterSpec interface can be used to pass in selectable RSA values to prime the RSA KeyPairGenerator class. The AlgorithmParameterSpec is algorithm specific. In the DH sample, the javax.crytpo.spec.DHParameterSpec class was used to pass in values p and g; and now for RSA, the keysize and the exponent e are the only values that can be entered in the AlgorithmParameterSpec as the RSA equivalent of a java.security.spec.RSAKeyGenParameter class. The key size must fall in the range of 512- to 2048-bit size and must be a multiple of 8. The default key size value is 1024. For an example of the calculations done in the explanation of the algorithm, letting the KeyPairGenerator choose the values for you, and choosing your own exponent, see Listing 4-16. Listing 4-17shows the associated output. Listing 4-16: The RSASimpleApp class: An RSA sample application
package com.richware.chap04; import java.util.*; import java.math.*; import java.security.*; import java.security.spec.*; /** * Class RSASimpleApp * Description: This is an example of a * simple RSA * * 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 RSASimpleApp { public final static int p = 47; public final static int q = 71; public final static int eValue = 79; public final static int mValue = 43; public final static int KEYSIZE_MIN = 512; public final static int KEYSIZE_DEFAULT = 1024; public final static int KEYSIZE_MAX = 2048; public final static int bitLength = KEYSIZE_DEFAULT; // KeySize /** * Method main * Description: This is a Sample JAAS application * @param args none * */ public static void main(String[] args) { try { BigInteger c = null; BigInteger d = null; BigInteger phi = null; BigInteger minusOne = null; BigInteger e = null; BigInteger m = null; System.out.println(); System.out.println( "RSA Proving the algorithm*************************"); /* * Step 1 * Pick p and q */ System.out.println("p = " + RSASimpleApp.p); System.out.println("q = " + RSASimpleApp.q); /* * Step 2 * Calculate n = p * q */ BigInteger n = new BigInteger(Integer.toString(p * q)); System.out.println("n = " + n); /* * Step 3 * Calculate phi = (p - 1) * (q - 1) */ phi = new BigInteger(Integer.toString((p - 1) * (q - 1))); System.out.println("phi = " + phi); /* * Step 4 * Select e a prime less than phi */ e = new BigInteger(Integer.toString(eValue)); if (e.intValue() < phi.intValue()) { System.out.println("e = " + e); minusOne = new BigInteger(Integer.toString(-1)); /* * Step 5 * Calculate d */ d = e.modPow(minusOne, phi); System.out.println("d = " + d); /* * Step 6 * Display private and public key */ System.out.println("Public Key {n,e} = {" + n + "," + e + "}"); System.out.println("Private Key {n,d} = {" + n + "," + d + "}"); m = new BigInteger(Integer.toString(mValue)); System.out.println("Encrypting value....." + m); c = m.modPow(e, n); System.out.println("Ciphertext value = " + c); System.out.println("Decrypting value....."); BigInteger plaintext = c.modPow(d, n); System.out.println("Plaintext value = " + plaintext); } else { System.out.println("e must be less than phi"); } RSASimpleApp app = new RSASimpleApp(); app.createKey(); app.createSpecificKey(); } /* * Catches */ catch (Exception ex) { ex.printStackTrace(); } } /** * Method createKey * Description: This is an example of * letting the algorithm choose * the values * */ public void createKey() { try { System.out.println(); System.out.println( "RSA letting the algorithm choose******************"); KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA"); /* * A strong key uses 512 to 2048 bits * the bits must be multiples of 8 */ System.out.println("Provider =" + kpg.getProvider()); kpg.initialize(bitLength); KeyPair kp = kpg.generateKeyPair(); /* * Read the keys * produced by the algorithm */ System.out.println("Public Key =" + kp.getPublic().getEncoded()); System.out.println("Public Key Algorithm =" + kp.getPublic().getAlgorithm()); System.out.println("Public Key Format =" + kp.getPublic().getFormat()); System.out.println("Private Key =" + kp.getPrivate().getEncoded()); System.out.println("Private Key Algorithm =" + kp.getPrivate().getAlgorithm()); System.out.println("Private Key Format =" + kp.getPrivate().getFormat()); /* * Initialize the KeyFactory for DSA */ KeyFactory kfactory = KeyFactory.getInstance("RSA"); /* * Create the RSA public key spec */ RSAPublicKeySpec kspec = (RSAPublicKeySpec) kfactory .getKeySpec(kp.getPublic(), RSAPublicKeySpec.class); /* * Print out public key values */ System.out.println("Public Key Modulus =" + kspec.getModulus()); System.out.println("Public Key Exponent =" + kspec.getPublicExponent()); } /* * Catches */ catch (java.security.NoSuchAlgorithmException ex) { ex.printStackTrace(); } catch (Exception ex) { ex.printStackTrace(); } } /** * Method createSpecificKey * Description: This is an example of * choosing e * */ public void createSpecificKey() { try { /* * Another provider specific to the signature instead of JSSE */ System.out.println(); System.out.println( "RSA Choosing the exponent*************************"); KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA", "SunRsaSign"); /* A strong key uses 512 to 2048 bits * the bits must be multiples of 8 */ System.out.println("Provider =" + kpg.getProvider()); BigInteger e = new BigInteger(Integer.toString(eValue)); System.out.println("e =" + e); /* * Select the exponent */ RSAKeyGenParameterSpec param = new RSAKeyGenParameterSpec(bitLength, e); kpg.initialize(param); KeyPair kp = kpg.generateKeyPair(); /* Read the keys * produced by the algorithm */ System.out.println("Public Key =" + kp.getPublic().getEncoded()); System.out.println("Public Key Algorithm =" + kp.getPublic().getAlgorithm()); System.out.println("Public Key Format =" + kp.getPublic().getFormat()); System.out.println("Private Key =" + kp.getPrivate().getEncoded()); System.out.println("Private Key Algorithm =" + kp.getPrivate().getAlgorithm()); System.out.println("Private Key Format =" + kp.getPrivate().getFormat()); /* * Initialize the KeyFactory for DSA */ KeyFactory kfactory = KeyFactory.getInstance("RSA", "SunRsaSign"); /* * Create the RSA public key spec */ RSAPublicKeySpec kspec = (RSAPublicKeySpec) kfactory .getKeySpec(kp.getPublic(), RSAPublicKeySpec.class); /* * Print out public key values */ System.out.println("Public Key Modulus =" + kspec.getModulus()); System.out.println("Public Key Exponent =" + kspec.getPublicExponent()); } /* * Catches */ catch (java.security.NoSuchAlgorithmException ex) { ex.printStackTrace(); } catch (Exception ex) { ex.printStackTrace(); } } }
Listing 4-17: Output for Listing 4-16
>java com.richware.chap04.RSASimpleApp RSA Proving the algorithm************************* p = 47 q = 71 n = 3337 phi = 3220 e = 79 d = 1019 Public Key {n,e} = {3337,79} Private Key {n,d} = {3337,1019} Encrypting value.....43 Ciphertext value = 1921 Decrypting value..... Plaintext value = 43 RSA letting the algorithm choose****************** Provider =SunJSSE version 1.4 Public Key =[B@50d89c Public Key Algorithm =RSA Public Key Format =X509 Private Key =[B@f6f0bf Private Key Algorithm =RSA Private Key Format =PKCS8 Public Key Modulus =160629459826185796665280814291240383123828641198923436253181 900151059676009009931793798135188379533611524490714175573620656352311527 37493397 231466624073605140549946017315383317656384495712549851358009017662016812 46302404 563577825705424590255543936627122544477881995474962649565610908776310973 57422561 127783459 Public Key Exponent =65537 RSA Choosing the exponent************************* Provider =SunRsaSign version 1.0 e =79 Public Key =[B@1cdeff Public Key Algorithm =RSA Public Key Format =X509 Private Key =[B@d2068d Private Key Algorithm =RSA Private Key Format =PKCS8 Public Key Modulus =128261306992585359665395952539443220045386526780114740630578 970758473343123238408439701859431727952561489518706444193406404029586739 21381081 594335798940786032112792814979484184076240628061477171232842299850564015 69445325 361117873185927125286725549365015684352386856635813114175654389976223996 59613722 180552193 Public Key Exponent =79
Using symmetric keysSo far the discussion has centered on the key pair algorithms. From Listing 4-14, there are several secret keys, or symmetric keys, that the standard service providers shipped with the JDK 1.4. Most noteworthy of the secret keys are Data Encryption Standard (DES), the oldest of all keys, and its replacement, Triple-DES .
Understanding the Data Encryption Standard (DES) keyThe Data Encryption Standard (DES) has been around since before the DH key exchange. It originally started out as Lucifer from IBM, which was bought by Lloyd's of London in 1973. Also in 1973, the National Bureau of Standards (NBS) was looking for a national encryption standard for encrypting unclassified documents, to be known as DES. The NBS eventually became the National Institute of Standards and Technology and published DES as the algorithm for encrypting unclassified information. Lucifer started out as a 128-bit encryption. The National Security Agency (NSA) started the change over of Lucifer into DES and changed the key size to 64 bits. Of the 64-bit key, 8 bits are used for error correction in a parity check, which changes the key size to 56 bits. The 56-bit key makes the brute-force attack (to discover every key combination) possible since there are approximately 2 56 key combinations, or approximately 7.2 x 10 16 keys. DES encrypts and decrypts 64 bits (8 bytes) at a time and produces 64 bits of cipher text. Because of the decrease in key size, there were many rumors that the NSA purposely weakened DES so that a brute-force attack could be easier. The NSA denies any wrongdoing, but many brute-force attacks in the mid-1990s were successful. Two of the biggest opponents of DES were Martin Hellman and Whitfield Diffie, who came up with the DH key agreement. The Electronic Frontier Foundation (EFF) announced several successful DES attacks in 1997. By January 1999, the EFF was breaking DES within 24 hours. Many cryptographers and authors still suggest that DES is a viable algorithm and that the cost of the brute-force attacks outweigh the gain of decrypting the ciphertext. With the availability of computer power in the 21 st century, and the ability to use idle computers from around the world for their processing power, I believe that this is a serious weakness. I will just reference the "Data Encryption Standard" from the National Institute of Standards and Technology, which you can find at http://csrc.nist.gov/ publications /fips/fips46-3/fips46-3.pdf , and paraphrase : Use single DES for legacy systems where there isn't a choice, and whenever possible use Triple-DES. Other algorithms that were considered to replace DES are the SkipJack algorithm and the Clipper Chip. Understanding the Triple-DES keyBecause DES was a very popular algorithm, accepted and distributed by many, any substitution of DES in legacy systems would take time. In the mid-1990s many cracks and exposure of the DES weaknesses have become known.
A way of strengthening DES without changing the cipher was underway. The result became known as Triple-DES because of the use of three DES keys. For many, this algorithm also became known as DES EDE for DES Encrypt-Decrypt-Encrypt. The reasoning behind the EDE is that the Triple-DES key algorithm performs an encryption operation with one key, K 1 , and decrypts with another key, K 2 . At a minimum, Triple-DES must use two keys. Three keys can also be used. When Triple-DES decrypts with the K 2 , it doesn't return the original plaintext, but a new ciphertext that has been changed through the decryption process by not using the original key K 1 . A third key can be used, K 3 , to encrypt again with the second encryption. Even if K 1 is used with the second encryption, it will still produce a unique output from the Encrypt-Decrypt because the ciphertext has already been modified by the decryption with a different key. The two-key implementation of Triple-DES uses a key, K 1 , for both encryptions, and a second key for the decryption, as shown in Listing 4-18. Listing 4-18: Triple-DES two-key implementation
A pseudo code example is as follows: CipherText = Encrypt K1 (Decrypt K2 (Encrypt K1 (PlainText))) The first encryption uses K 1 : CipherText E1 = Encrypt K1 ("Password"); The next step is an encryption with a different key K 2 : CipherText D1 = Decrypt K2 (CipherText E1 ); The next step is an encryption with the K 1 , but the input for the plaintext is now a ciphertext returned by the decryption: CipherText E2 = Encrypt K1 (CipherText D1 );
Listing 4-18 describes the use of the Triple-DES two-key implementation. Now the algorithm not only has the strength of the two 56-bit keys, but also uses the same key to re-encrypt a new ciphertext. A typical strength of adding the two DES keys K 1 and K 2 would be 2 56 + 2 56 or 2 122 . By using the keys multiple times, a different combination of encryption and decryption is achieved and the strength is greater. The three-key implementation is also used in Triple-DES. The three-key implementation is used the same way as the two-key implementation, except that the second encryption doesn't use K 1 . The second encryption uses a third key, K 3 . See Listing 4-19 for an example of the implementation. Listing 4-19: Triple-DES three-key implementation
A pseudo code example is as follows: CipherText = Encrypt K3 (Decrypt K2 (Encrypt K1 (PlainText))) The first encryption uses K 1 : CipherText E1 = Encrypt K1 ("Password"); The next step is an encryption with a different key K 2 : CipherText D1 = Decrypt K2 (CipherText E1 ); The next step is an encryption with the K 3 , but the input for the palintext is now a ciphertext returned by the decryption: CipherText E2 = Encrypt K3 (CipherText D1 );
Listing 4-19 describes the use of the Triple-DES three-key implementation. Now the algorithm has the strength of the three 56-bit keys. The typical strength of three DES keys would be 2 56 + 2 56 + 2 56 or 2 168 . The strength of 2 168 would make any brute-force attack very time consuming. By supplying a higher key with the same algorithm, Triple-DES has increased the comfort level of using the DES algorithm.
 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 |
