RSA Encryption Algorithm - Computing and Software Wiki (2024)

From Computing and Software Wiki

Jump to: navigation, search

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.

1 Algorithm
- 1.1 Key Generation
- 1.2 Encryption
- 1.3 Decryption
2 Example
3 Digital Signing
4 History
5 References
6 External Links
7 See Also

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

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=17, j=3

2. compute k=ij, k = 17*3 = 51

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