87.

Learn Encryption Techniques with BASIC and C++
(Publisher: Wordware Publishing, Inc.)
Author(s): Gil Held
ISBN: 1556225989
Publication Date: 10/01/98

Previous Table of Contents Next


RSA

RSA is a public key encryption system invented by Rivest, Shamir, and Adleman in 1978. Under this technique, both encryption and decryption are performed using exponentiation. RSA obtains security from the difficulty associated with factoring large prime numbers. As you will shortly note, public and private keys are functions of a pair of large prime numbers. Thus, the ability to decipher plaintext from the use of a public key and ciphertext is the equivalent of factoring two large primes.

Using the RSA system, each party generates a public key and a corresponding private key. To do so, two large primes of equal length are selected, p and q. To facilitate security, each prime should be a minimum of 32 bytes, or 256 bits, in length. Once the two primes are selected, you multiply them together and find their product n, which is referred to as the modulus of pq.

Public Key Generation

To generate a public key, each person using the RSA algorithm generates their encryption (e) and decryption (d) keys. The encryption key, e, is selected such that it is less than n and relatively prime to (p-1)(q-1), which represents the totient function 0(n). This means that e and (p-1)(q-1) have no common factors other than 1. Your public key then becomes the pair <e,n>.

Private Key Generation

To compute your private key, you will find another number d, such that (ed-1) is divisible by (p-1)(q-1). That is, d represents the multiplicative inverse of e mod 0(n). Then, the private key becomes the pair <d,n>. Once your public and private keys are selected, the primes p and q are no longer needed. Although it is safe to discard them, they should not be revealed.

Message Encipherment

To encipher a message m you would first subdivide it into blocks smaller than n (m<n). When working with binary data this would be equivalent to selecting the largest power of 2 less than n. You would then use your public key (e) to compute ciphertext (c) as follows:

     c = mie mod n 

where mi represents block I of message m.

To decrypt a message you would use your private key (d) on each ciphertext block ci as follows:

     mi = cid mod n 

To illustrate the use of RSA, let’s use a few small primes to facilitate observing the relevant computations. First, let’s assume you selected p = 53 and q = 61. Then:

     n = p*q = 53*61 = 3233 

Next you would randomly select an encryption key, e, such that it has no common factors with 3233. For our example, let’s select e to be 41. Then, the private key d would be:

     d = 41-1 mod 3233 

To compute d, you must obtain the multiplicative inverse of 41 mod 3233. That is, you must determine the number which when multiplied by 41 mod 3233 yields a result of unity. Based upon Euler’s application of the totient function, if n is a prime, the 0(n) = n-1. If p and q are primes and n = pq, then 0(n) = (p-1)(q-1). Thus, if the gcd (a,n) = 1, where x is not a multiple of n, then:

     x0(n) mod n = 1 

This means you can compute the multiplicative inverse x-1 mod n as follows:

     X = x0(n)-1 mod n 

Returning to your computation, you need to determine the private key d, such that:

     d = 41-1 mod 3233 

Since 3233 is prime, then 0(3233) = 3233-1 = 3232. Thus, the inverse of 41 mod 3233 becomes:

     413232-1 mod 3233 = 413231 mod 3233 


Previous Table of Contents Next


Learn Encryption Techniques with Basic and C++
Learn Encryption Techniques with BASIC and C++
ISBN: 1556225989
EAN: 2147483647
Year: 2005
Pages: 92
Authors: Gil Held

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net