IBM Z Security - Group home

RSA is an asymmetric encryption system which is named after its creators, Rivest, Shamir and Adleman. Published in 1977, RSA still forms the basis of many encryption schemes today, including the HTTPS (Hypertext Transfer Protocol Secure) security protocol. Before going into the details of understanding how the RSA asymmetric encryption system works, let us first look at what asymmetric encryption is.

A brief look at what Asymmetric Encryption is all about
Asymmetric Encryption is also known as public-key cryptography. An asymmetric encryption scheme’s key generation algorithm generates a public key that is used for data encryption and private key that is used for data decryption.

As the name suggests, the public key can be made public; that is, you can give the public key to anyone and it shouldn’t matter a lot because as we have just seen, the public key can only be used for data encryption. If you must decrypt the information, you should know the private key. Thus, an asymmetric encryption scheme helps solve the ‘key sharing’ problem that is associated with the symmetric encryption schemes.

How does Public-Key Cryptography work?
Assume that there are two entities, PersonB and PersonA, and that PersonB wishes to send a very, very secret message to PersonA. PersonB would obviously want to fully encrypt, for obvious security reasons and privacy concerns, the content of the very, very secret message that he wishes to send to PersonA, before PersonB sends out the message to PersonA.

In this situation, PersonA creates a Public and Private Key pair. PersonA sends the public key to PersonB. Anyone can be aware of what the public key is and so, it really doesn’t matter how PersonA sends it to PersonB – the encryption scheme wouldn’t be compromised in any manner whatsoever, even if a rogue person gets hold of the public key. PersonB writes the very, very secret message, encrypts the message using the public key received from PersonA, sends the encrypted message to PersonA who can then decrypt the message using the private key.


A point to ponder about
The public and private keys are generated together. While the public key is used to encrypt the data, the private key is used to decrypt the encrypted data. So, how does it become possible that you can make the public key public, without revealing any information at all about the private key? The answer to this question forms the basis of the whole RSA asymmetric encryption scheme.

Well, mathematically, it turns out that a seemingly very simple, yet not-so-simple calculation, forms the basis of the whole RSA asymmetric encryption scheme
Yes, this (making the public key public, without revealing any information at all about the private key) becomes possible because of a type of mathematical function, which is called a one-way function, which is a function that is very, very simple enough to be performed in one direction but computationally very, very hard to reverse – well, technically, the process of reverse engineering a one-way function would be extremely resource-intensive for a computer to be able to produce, within a reasonable/short enough time period, an output to be useful. Yes, we are talking about the power of prime numbers.

For example, let us consider the two prime numbers, 19 and 23. Multiplying both the prime numbers, 19*23, is an extremely simple calculation for a computer to perform.

However, if the computer is provided with the product 437 and asked to find the two prime factors, it turns out that it is one of those types of calculations that a computer will need to spend considerable time, effort and resources before it can come up with the correct answer. With a number as small as 437, it might probably take a computer only a few seconds to figure out the two prime factors. However, for real big numbers, modern computing machines will not be able to find the prime factors even in a human lifetime and the RSA asymmetric encryption scheme relies upon this principle. The RSA asymmetric encryption scheme uses keys that are 1024, 2048 or 4096 bits long – remember that a 4096-bit number can be 1234 digits long in decimal.


RSA Public-Key generation algorithm
<i> Two very, very large prime numbers, p and q, are to be chosen.

<ii> The RSA Modulus r needs to be calculated. r = p*q
           As already seen above, calculating the RSA Modulus r (= p*q) is computationally extremely easy, but extremely difficult to reverse.

<iii> Euler’s totient function, ϕ = (p-1)(q-1) needs to be computed
                                                         [ ϕ (Greek letter phi) ]

<iv> A number that is greater than 1 and less than ϕ and is relatively prime to ϕ is chosen. In other words, you choose a number that is greater than 1 and less than ϕ and has no common divisor with ϕ. Let us call the chosen number, e.

e must be chosen by following the following two conditions.
                      1. 1 < e < ϕ, and
                      2. out of the numbers that lie within the range 1 < e < ϕ, a number that is co-prime with r and ϕ should be selected.

<v> e becomes the Public Key. In fact, the encryption key (public key) is (e, r). Think of (e, r) as the LOCK using which you encrypt your data.


RSA Private-Key generation algorithm
Using the public key e, we can calculate the private key. Let us call the private key d. d is the inverse of e modulus ϕ.

(e*d) mod ϕ = 1
=> e*d = 1 / mod ϕ
=> d = 1 / e mod ϕ
=> d = (e mod ϕ)<sup>-1

The decryption key (private key) is (d, r). You can think of (d, r) as the KEY to your LOCK – using the KEY, you can unlock the LOCK; in other words, using the KEY (private key), you can decrypt (unlock) the data that had previously been encrypted (locked) using the LOCK (public key).


NOTE: -
Both e and r can be made public. Considering that p and q are two very, very large prime numbers, it is extremely difficult to guess p and q using r. Therefore, r can be made public. Since p and q cannot be guessed using r, being able to find out the private key d, using e and r, is also not possible.


RSA Encryption Algorithm
If you would want to encrypt a message m using RSA, the message is raised to the power e and the RSA modulus r applied. Remember that the public key e is used to encrypt data.

Therefore, the ciphertext becomes c = ENCRYPT (m) = m^e mod r


RSA Decryption Algorithm
If you would want to decrypt the ciphertext c using RSA, the ciphertext c is raised to the power d and the RSA modulus r applied. Remember that the private key d is used to decrypt the encrypted data.

m = DECRYPT (c) = c^d mod r
This is because c^d = (m^e)^d = m^ed = m^1 = m</sup>