RSA Encryption Algorithm

Lab Number 9
What Is Asymmetric Encryption?

In Asymmetric Encryption algorithms, you use two different keys, one for encryption and
the other for decryption. The key used for encryption is the public key, and the key used
for decryption is the private key. But, of course, both the keys must belong to the
receiver.

As seen in the image above, using different keys for encryption and decryption has
helped avoid key exchange, as seen in symmetric encryption.

For example, if Alice needs to send a message to Bob, both the keys, private and
public, must belong to Bob.

The process for the above image is as follows:

 Step 1: Alice uses Bob’s public key to encrypt the message

 Step 2: The encrypted message is sent to Bob

 Step 3: Bob uses his private key to decrypt the message

This eliminates the need to exchange any secret key between sender and receiver,
thereby reducing the window of exploitation.

Now that you understand how asymmetric encryption occurs, you can look at how the
digital signature architecture is set up.

RSA encryption algorithm is a type of public-key encryption algorithm. To better

understand RSA, lets first understand what is public-key encryption algorithm.

Public key encryption algorithm:

Public Key encryption algorithm is also called the Asymmetric algorithm. Asymmetric
algorithms are those algorithms in which sender and receiver use different keys for
encryption and decryption. Each sender is assigned a pair of keys:

o Public key
o Private key

The Public key is used for encryption, and the Private Key is used for decryption.
Decryption cannot be done using a public key. The two keys are linked, but the private
key cannot be derived from the public key. The public key is well known, but the private
key is secret and it is known only to the user who owns the key. It means that everybody
can send a message to the user using user's public key. But only the user can decrypt
the message using his private key.
The Public key algorithm operates in the following
manner:

o The data to be sent is encrypted by sender A using the public key of the intended
receiver
o B decrypts the received ciphertext using its private key, which is known only to B.
B replies to A encrypting its message using A's public key.
o A decrypts the received ciphertext using its private key, which is known only to
him.

The most important properties of public key encryption scheme are −

 Different keys are used for encryption and decryption. This is a property which set
this scheme different than symmetric encryption scheme.
 Each receiver possesses a unique decryption key, generally referred to as his
private key.
 Receiver needs to publish an encryption key, referred to as his public key.
 Some assurance of the authenticity of a public key is needed in this scheme to
avoid spoofing by adversary as the receiver. Generally, this type of cryptosystem
 involves trusted third party which certifies that a particular public key belongs to
a specific person or entity only.
 Encryption algorithm is complex enough to prohibit attacker from deducing the
plaintext from the ciphertext and the encryption (public) key.
 Though private and public keys are related mathematically, it is not be feasible to
calculate the private key from the public key. In fact, intelligent part of any
public-key cryptosystem is in designing a relationship between two keys.

Steps in RSA Algorithm

This cryptosystem is one the initial system. It remains most employed cryptosystem even today.
The system was invented by three scholars Ron Rivest, Adi Shamir, and Len Adleman and
hence, it is termed as RSA cryptosystem. Keeping the image above in mind, go ahead and
see how the entire process works, starting from creating the key pair, to encrypting and
decrypting the information.

Key Generation

You need to generate public and private keys before running the functions to generate
your ciphertext and plaintext. They use certain variables and parameters, all of which
are explained below:

 Choose two large prime numbers (p and q)

 Calculate n = p*q and z = (p-1)(q-1)

 Choose a number e where 1 < e < z

 Calculate d = e-1mod(p-1)(q-1)

 You can bundle private key pair as (n,d)

 You can bundle public key pair as (n,e)

Encryption/Decryption Function

Once you generate the keys, you pass the parameters to the functions that calculate
your ciphertext and plaintext using the respective key.
 If the plaintext is m, ciphertext = me mod n.

 If the ciphertext is c, plaintext = cd mod n

To understand the above steps better, you can take an example where p = 17 and
q=13. Value of e can be 5 as it satisfies the condition 1 < e < (p-1)(q-1).

N = p * q = 91

D = e-1mod(p-1)(q-1) = 29

Public Key pair = (91,5)

Private Key pair = (91,29)

If the plaintext(m) value is 10, you can encrypt it using the formula me mod n = 82.

To decrypt this ciphertext(c) back to original data, you must use the formula cd mod n =
29.
RSA encryption algorithm:
RSA is the most common public-key algorithm, named after its inventors Rivest,
Shamir, and Adelman (RSA).

RSA algorithm uses the following procedure to generate public and private keys:

o Select two large prime numbers, p and q.

o Multiply these numbers to find n = p x q, where n is called the modulus for
encryption and decryption.
o Choose a number e less than n, such that n is relatively prime to (p - 1) x (q -
1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose
"e" such that 1<e < φ (n), e is prime to φ (n),
gcd (e,d(n)) =1
o If n = p x q, then the public key is <e, n>. A plaintext message m is encrypted
using public key <e, n>. To find ciphertext from the plain text following formula
is used to get ciphertext C.
 C = me mod n
Here, m must be less than n. A larger message (>n) is treated as a concatenation
of messages, each of which is encrypted separately.
o To determine the private key, we use the following formula to calculate the d
such that:
De mod {(p - 1) x (q - 1)} = 1
Or
De mod φ (n) = 1
o The private key is <d, n>. A ciphertext message c is decrypted using private key
<d, n>. To calculate plain text m from the ciphertext c following formula is used
to get plain text m.
m = c mod n
d

Let's take some example of RSA encryption

algorithm:

Example 1:
This example shows how we can encrypt plaintext 9 using the RSA public-key encryption
algorithm. This example uses prime numbers 7 and 11 to generate the public and
private keys.

Explanation:

Step 1: Select two large prime numbers, p, and q.

p=7

q = 11

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for
encryption and decryption.

First, we calculate

n=pxq

n = 7 x 11
n = 77

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -

1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e"
such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (7 - 1) x (11 - 1)

φ (n) = 6 x 10

φ (n) = 60

Let us now choose relative prime e of 60 as 7.

Thus the public key is <e, n> = (7, 77)

Step 4: A plaintext message m is encrypted using public key <e, n>. To find ciphertext
from the plain text following formula is used to get ciphertext C.

To find ciphertext from the plain text following formula is used to get ciphertext C.

C = me mod n

C = 97 mod 77

C = 37

Step 5: The private key is <d, n>. To determine the private key, we use the following
formula d such that:

De mod {(p - 1) x (q - 1)} = 1

7d mod 60 = 1, which gives d = 43

The private key is <d, n> = (43, 77)

Step 6: A ciphertext message c is decrypted using private key <d, n>. To calculate plain
text m from the ciphertext c following formula is used to get plain text m.
m = cd mod n

m = 3743 mod 77

m=9

In this example, Plain text = 9 and the ciphertext = 37

Example 2:
In an RSA cryptosystem, a particular A uses two prime numbers, 13 and 17, to generate
the public and private keys. If the public of A is 35. Then the private key of A is
……………?.

Explanation:

Step 1: in the first step, select two large prime numbers, p and q.

p = 13

q = 17

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for
encryption and decryption.

First, we calculate

n=pxq

n = 13 x 17

n = 221

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -

1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e"
such that 1<e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (13 - 1) x (17 - 1)

φ (n) = 12 x 16

φ (n) = 192

g.c.d (35, 192) = 1

Step 3: To determine the private key, we use the following formula to calculate the d
such that:

Calculate d = de mod φ (n) = 1

d = d x 35 mod 192 = 1

d = (1 + k.φ (n))/e [let k =0, 1, 2, 3………………]

Put k = 0

d = (1 + 0 x 192)/35

d = 1/35

Put k = 1

d = (1 + 1 x 192)/35

d = 193/35

Put k = 2

d = (1 + 2 x 192)/35

d = 385/35

d = 11

The private key is <d, n> = (11, 221)

Hence, private key i.e. d = 11

Example 3:
A RSA cryptosystem uses two prime numbers 3 and 13 to generate the public key= 3
and the private key = 7. What is the value of cipher text for a plain text?

Explanation:

Step 1: In the first step, select two large prime numbers, p and q.

p=3

q = 13

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for
encryption and decryption.

First, we calculate

n=pxq

n = 3 x 13

n = 39

Step 3: If n = p x q, then the public key is <e, n>. A plaintext message m is encrypted
using public key <e, n>. Thus the public key is <e, n> = (3, 39).

To find ciphertext from the plain text following formula is used to get ciphertext C.

C = me mod n

C = 53 mod 39

C = 125 mod 39

C=8

Hence, the ciphertext generated from plain text, C = 8.

Example 4:
A RSA cryptosystem uses two prime numbers, 3 and 11, to generate private key = 7.
What is the value of ciphertext for a plain text 5 using the RSA public-key encryption
algorithm?
Explanation:

Step 1: in the first step, select two large prime numbers, p and q.

p=3

q = 11

Step 2: Multiply these numbers to find n = p x q, where n is called the modulus for
encryption and decryption.

First, we calculate

n=pxq

n = 3 x 11

n = 33

Step 3: Choose a number e less that n, such that n is relatively prime to (p - 1) x (q -

1). It means that e and (p - 1) x (q - 1) have no common factor except 1. Choose "e"
such that 1< e < φ (n), e is prime to φ (n), gcd (e, d (n)) =1.

Second, we calculate

φ (n) = (p - 1) x (q-1)

φ (n) = (3 - 1) x (11 - 1)

φ (n) = 2 x 10

φ (n) = 20

Step 4: To determine the public key, we use the following formula to calculate the d
such that:

Calculate e x d = 1 mod φ (n)

e x 7 = 1 mod 20

e x 7 = 1 mod 20
e = (1 + k. φ (n))/ d [let k =0, 1, 2, 3………………]

Put k = 0

e = (1 + 0 x 20) / 7

e = 1/7

Put k = 1

e = (1 + 1 x 20) / 7

e = 21/7

e=3

The public key is <e, n> = (3, 33)

Hence, public key i.e. e = 3

Example 5
An example of generating RSA Key pair is given below. (For ease of understanding,
the primes p & q taken here are small values. Practically, these values are very high).

 Let two primes be p = 7 and q = 13. Thus, modulus n = pq = 7 x 13 = 91.

 Select e = 5, which is a valid choice since there is no number that is common

factor of 5 and (p − 1)(q − 1) = 6 × 12 = 72, except for 1.

 The pair of numbers (n, e) = (91, 5) forms the public key and can be made
available to anyone whom we wish to be able to send us encrypted messages.

 Input p = 7, q = 13, and e = 5 to the Extended Euclidean Algorithm. The output

will be d = 29.

 Check that the d calculated is correct by computing −

de = 29 × 5 = 145 = 1 mod 72

 Hence, public key is (91, 5) and private keys is (91, 29).

Advantages of RSA

 No Key Sharing: RSA encryption depends on using the receiver’s public key, so you
don’t have to share any secret key to receive messages from others.

 Proof of Authenticity: Since the key pairs are related to each other, a receiver can’t
intercept the message since they won’t have the correct private key to decrypt the
information.

 Faster Encryption: The encryption process is faster than that of the DSA algorithm.
 Data Can’t Be Modified: Data will be tamper-proof in transit since meddling with the
data will alter the usage of the keys. And the private key won’t be able to decrypt the
information, hence alerting the receiver of manipulation.