This tutorial will discuss both the encryption and decryption algorithms for RSA. Overall, RSA is a very simple encryption algorithm. The mathematical formulas are extremely basic. The security comes from generating sufficiently large numbers, and generating sufficiently large primes to factor them. It hardly takes any time to add three random digits to the end of a number, but it takes significantly longer to factor the new number.
RSA relies on both public and private keys. The public key is used in the encryption schema, and the private key is used to decrypt the ciphertext. These keys are generated using basic modular arithmetic and the Euclidean algorithm.
The first step in the RSA process is to choose two distinct primes (p and q) of comparable size in terms of bit length for key generation. They are then multiplied together to get n = pq, which is the modulus for the encryption and decryption congruences.
From here, it is necessary to calculate phi(n), which is Euler's totient function. This function returns a value representing how many numbers less than n are coprime to n. It is calculated by factoring n into its prime factors, which may have exponents greater than 1. For a prime p, phi(p) = (p-1). For a composite number pn, phi(pn) = (p-1)(p)n-1. If there are multiple factors for n, they are simply multiplied together. So for RSA, phi(n) = phi(pq) = (p-1)(q-1).
The encryption schema relies on a public key. This is generated by choosing some number a that is between 1 and phi(n) exclusive, and is relatively prime to phi(n). It is also important that the message is less than n, the modulus. The congruence for encryption is as follows: c = messagea (mod n).
The decryption schema is also pretty basic. It is as follows: message = cb (mod n), where b is the private key. This is also where the security comes in, as b = a-1 (mod phi(n)). The larger the value of n, the harder it is to factor and evaluate the totient function. Therefore, it is significantly easier to expand the key while making it quickly intractable for even the most powerful computer to crack the private key.
Let's work through an example, to encrypt the message 255. The first step is to choose two primes p and q, which have the same bit length. Let p = 17 and q = 19, leaving n = 323 and phi(n) = 16(18) = 288.
The next step is to choose a number between 1 and 288 that is relatively prime to 288, which will be the public key. Since 257 is a prime number, and thus relatively prime to every other number, it satisfies the conditions and can be chosen. At this point, there is enough information to perform the encryption. So c = 255257 (mod 323), or 221 (mod 323).
Now in order to decrypt the ciphertext, the private key is needed. In order to find the private key, it is necessary to solve the congruence b = 257-1 (mod 288). Using the Euclidean algorithm, the solution is b = 65 (mod 288).
Now the original message can be recovered using the decryption congruence message = cb (mod n), or in this case message = 22165 (mod 323). Of course, message = 255, which was the original message to encrypt.
Page 1 of 1
1 Replies - 24510 Views - Last Post: 20 August 2012 - 04:44 PM
Replies To: RSA Encryption Tutorial
Page 1 of 1