RSA Encryption Algorithm
From Computing and Software Wiki
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.
Contents |
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)) = 0. 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)
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, pages = pp.881–887
