Handbook of Local Area Networks, 1998 Edition:LAN Security Click Here! Search the site:   ITLibrary ITKnowledge EXPERT SEARCH Programming Languages Databases Security Web Services Network Services Middleware Components Operating Systems User Interfaces Groupware & Collaboration Content Management Productivity Applications Hardware Fun & Games EarthWeb sites Crossnodes Datamation Developer.com DICE EarthWeb.com EarthWeb Direct ERP Hub Gamelan GoCertify.com HTMLGoodies Intranet Journal IT Knowledge IT Library JavaGoodies JARS JavaScripts.com open source IT RoadCoders Y2K Info Previous Table of Contents Next PUBLIC-KEY ENCRYPTION One essential characteristic of IDEA and all conventional encryption algorithms is the need for the two parties to share a secret key that is not known to anyone else. This is a tremendous limitation, especially for an E-mail application. If PGP depended solely on the use of IDEA, before a user could correspond with anyone, that user would somehow have to arrange to share a secret 128-bit number with the message recipient. If there is no way to communicate securely, it becomes difficult to send the key. A new approach to encryption known as public-key encryption offers a solution to this problem. With this method, developed in 1976 by Whitfield Diffie, there is no need to convey a secret key. Instead, each person has a private key and a matching public key. Encryption is done with one of these two keys and decryption uses the other. The private key is kept secret, known only to its holder. The matching public key is just that—public. The private key holder can broadcast the matching public key. Public-key encryption can be used to ensure privacy in much the same way as IDEA (see Exhibit 8-7-4). Users put plaintext and the intended recipient’s public key in the encryption algorithm. The algorithm uses the plaintext and the public key to produce ciphertext. At the receiving end, the decryption algorithm, which is the reverse of the encryption algorithm, is used. In this case, the input is the ciphertext and the receiver’s private key. This message is secure from eavesdropping because only the receiver has the private key necessary for decryption. Anyone who has a copy of the recipient’s public key can create a message that can be read only by this recipient. Exhibit 8-7-4.  Public-Key Encryption Authentication can also be performed by putting plaintext and the sender’s private key in the encryption algorithm. The algorithm uses the plaintext and the private key to produce ciphertext. At the receiving end, the decryption algorithm, which is the reverse of the encryption algorithm, is used. In this case, the input is the ciphertext and the sender’s public key. This message is guaranteed to be authentic because only the sender has the private key necessary for encryption. Anyone who has a copy of the sender’s public key can read the message and verify that it must have come from the alleged sender. The public-key scheme used for PGP is the RSA algorithm. RSA takes variable-length keys. Typically, the key size for both the private and public keys is 512 bits. The RSA Algorithm One of the first public-key schemes was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978. Named for its creators, the RSA scheme has since reigned as the only widely accepted and implemented approach to public-key encryption. RSA is a block cipher in which the plaintext and ciphertext are integers between 0 and n - 1 for some n. Encryption and decryption take the following form for some plaintext block M and ciphertext block C:     C = Me mod n       M = Cd mod n = (Me) d mod n = Med mod n Both sender and receiver must know the value of n. The sender knows the value of e, and only the receiver knows the value of d. Thus, this is a public-key encryption algorithm with a public key of KU = {e, n} and a private key of KR = {d, n}. For this algorithm to be satisfactory for public-key encryption, the following requirements must be met: •  It should be possible to find values of e, d, n such that Med = M mod n for all M < n. •  It should be relatively easy to calculate Me and Cd for all values of M < n. •  It should be infeasible to determine d given e and n. Exhibit 8-7-5 summarizes the RSA algorithm. To understand the algorithm, users should begin by selecting two prime numbers, p and q, and calculating their product n, which is the modulus for encryption and decryption. Next, the quantity (n), which is referred to as the Euler quotient of n, which is the number of positive integers less than n and relatively prime to n should be determined. Then an integer d, that is relatively prime to (n), (i.e., the greatest common divisor of d and (n) is 1) should be selected. Finally, e should be calculated as the multiplicative inverse of d, modulo (n). It can be shown that d and e have the desired properties. Exhibit 8-7-5.  The RSA Algorithm The private key consists of {d, n} and the public key consists of {e, n}. Suppose that user A has published its public key and that user B wishes to send the message M to A. Then, B calculates C = Me (mod n) and transmits C. On receipt of this ciphertext, user A decrypts by calculating M = Cd (mod n). An example is shown in Exhibit 8-7-6. For this example, the keys are generated as follows: •  Two prime numbers, p = 7 and q = 17, are selected. •  Calculate n = pq = 7 × 17 = 119. •  Calculate (n) = (p-1)(q-1) = 96. •  Select e such that e is relatively prime to (n) = 96 and less than (n); in this case, e = 5. •  Determine d such that de = 1 mod 96 and d <96. The correct value is d = 77, because 77 × 5 = 385 = 4 × 96 + 1. The resulting keys are public key KU = {5, 119} and private key KR = {77, 119}. The example shows the use of these keys for a plaintext input of M = 19. For encryption, 19 is raised to the fifth power, yielding 2,476,099. Upon division by 119, the remainder is determined to be 66. Therefore, 195 66 mod 119, and the ciphertext is 66. For decryption, it is determined that 6677 19 mod 119. Exhibit 8-7-6.  Example of RSA Algorithm Previous Table of Contents Next Use of this site is subject certain Terms & Conditions. Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.