RSA Encryption Algorithm

From Computing and Software Wiki

Revision as of 18:23, 12 April 2009

The RSA Encryption Algorithm is a form of encryption used in Public Key Encryption Algorithms. The algorithm consists of three phases, Key Generation, Encryption, and Decryption. It is the first publicly disclosed algorithm suitable for digital signing. Messages encrypted with with your Public Key can only be decrypted with your own private key. Conversly, messages encrypted with your own Private Key, can only be decrypted with your public key.

Algorithm

The RSA Algorithm consists of three phases, Key Generation, Encryption, and Decryption.

Key Generation

RSA utilizes two keys, a Public Key, and a Private key. These keys are created in the following way.

1. Two suitably large different prime numbers are randomly generated, i, j.

2. The product of these two numbers is calculated and used as the modulus for both the public, and private keys. k = ij

3. Compute the Totient of k. T(k) = (i-1)(j-1)

4. Choose an integer e such that 1 < e < T(k), and e and T(k) are coprime. e is the Public Key Exponent.

5. Compute d such that ed = 1 mod(T(k)). In other words ed mod (T(k)) = 1. d is the Private Key Exponent.

The two keys are a tuple. The public key consists of the Public Key Exponent, and the Modulous, (e,k). The Private Key consists of the Private Key Exponent, and again, the Modulous, (d,k).

Encryption

Person A wants to send a message to Person B. Person B requests person A's Public key, (e,k)

The message to be sent is then turned into a number, m, an integer between 0 and k. The encrypted c message can then be calculated by c = (m^e)(mod k)

Decryption

Person B wants to decrypt a message send from Person A. Person B uses their own private key (d,k) to decrypt the message in the following way. m = (c^d)(mod k)

Example

1. choose 2 prime numbers. For examples sake i=11, j=5

2. compute k=ij

k = 11*5 = 55

3. compute T(k)=(i-1)*(j-1)

T(k) = (11-1)*(5-1) = 10*4 = 40

4. Choose an integer e such that 1 < e < T(k), and e and T(k) are coprime.

Choose e = 3

5. compute d such that 3*d = 1 mod 40

d = 13 such that 3*13 = 1 mod 40

6. public key is (k,e), private key is (k,d)

Private Key = (50, 3), SK= (50, 13)

7. Encrypt message using Private Key with c = (m^e)(mod k)

Assume a message M=10 cipher text ''c = (m^e)(mod k) = 10^3 mod 50 = 100 mod 33 =13

8. Decrypt cipher text using SK with M' = C^D mod N:

Decrypted message M’ = C^D mod N = 13^7 mod 33 = 7

Digital Signing

Messages encrypted with with your Public Key can only be decrypted with your own private key. Conversly, messages encrypted with your own Private Key, can only be decrypted with your public key. Thus, Digital Signing is accomplished in the following way.

Person B wishes to send an encrypted message to Person A

1. The two parties exchange public keys.

2. Person B Encrypts the message with their own Private Key.

3. Person B then Encrypts the message again with Person A's Public Key, and sends the message to Person A.

4. Person A recieves the message, and decrypts it once with their own private key, and then again with Person B's Public Key.

Since the message was encrypted with Person A's public key, only Person A can decrypt the message with their private key. Since the message was also decrypted with Person B's public key, Person A also knows that the message must have been encrypted with Person B's Public key verifying the source of the message.

History

The algorithm was first publicized in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. The three worked at MIT at the time. RSA stands for Rivest, Shamir, and Adleman.

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill, 2001, isbn 0-262-03293-7, pp.881–887

External Links

• http://en.wikipedia.org/wiki/RSA
• http://en.wikipedia.org/wiki/Public-key_cryptography

See Also

• http://imps.mcmaster.ca/courses/SE-4C03-09/project/wiki-pages.html

--Holtzmt 13:16, 12 April 2009 (EDT)