RSA Algorithm in cryptography | RSA Algorithm

 RSA Algorithm — Putting to Use the Basic Idea

• The basic idea described in the previous subsection can be used to create a confidential communication channel in the manner described here.

• An individual A who wishes to receive messages confidentially will use the pair of integers {e,n} as his/her public key. At the same time, this individual can use the pair of integers {d,n} as the private key. The definitions of n, e, and d are as in the previous subsection.

• Another party B wishing to send a message M to A confidentially will encrypt M using A’s public key {e,n} to create ciphertext C. Subsequently, only A will be able to decrypt C using his/her private key {d,n}.

• If the plaintext message M is too long, B may choose to use RSA as a block cipher for encrypting the message meant for A. As explained by our toy example in Section 12.4, when RSA is used as a block cipher, the block size is likely to be half the number of bits required to represent the modulus n. If the modulus required, say, 1024 bits for its representation, message encryption would be

based on 512-bit blocks. [While, in principle, RSA can certainly be used as a

block cipher, in practice, on account of its excessive computational overhead, it is more

likely to be used just for server authentication and for exchanging a secret session key.

A session key generated with the help of RSA-based encryption can subsequently be used for content encryption using symmetric-key cryptography based on, say, AES.]

• The important theoretical question here is as to what conditions if any must be satisfied by the 

How to Choose the Modulus for the RSA Algorithm

• With the definitions of d and e  the modulus n must be selected in such a manner that the following is guaranteed: Me)d ≡ Med ≡ M (mod n) We want this guarantee because C = Me mod m is the encrypted form of the message integer M and decryption is carried out by Cd mod n.

• It was shown by Rivest, Shamir, and Adleman that we have this guarantee when n is a product of two prime numbers:

n = p×q for some prime p and prime q ......(1)

• The above factorization is needed because the proof of the algorithm, presented in the next subsection, depends on the following two properties of primes and coprimes:

1. If two integers p and q are coprimes (meaning, relatively prime to each other), the following equivalence holds for any two integers a and b:

{a ≡ b (mod p) and a ≡ b (mod q)} ⇔ {a ≡ b (mod pq)} .....(2) 

This equivalence follows from the fact a ≡ b (mod p) implies a−b = k1p for some integer k1. But since we also have a ≡ b (mod q) implying a−b = k2q, it must be the case that k1 = k3 ×q for some k3. Therefore, we can write a−b = k3×p×q, which establishes the equivalence. (Note that this argument breaks down if p and q have common factors other than 1.).

2. In addition to needing p and q to be coprimes, we also want p and q to be individually primes. It is only when p and q are individually prime that we can decompose the totient of n into the product of the totients of p and q. 

That is

φ(n) = φ(p)×φ(q) = (p−1)×(q−1)..... (3)

• So that the cipher cannot be broken by an exhaustive search for the prime factors of the modulus n, it is important that both p and q be very large primes. Finding the prime factors of a large integer is computationally harder than determining its primality.

• We also need to ensure that n is not factorizable by one of the modern integer factorization algorithms. 

 Proof of the RSA Algorithm

 We need to prove that when n is a product of two primes p and q, then, in arithmetic modulo n, the exponents behave modulo the totient of n. We will prove this assertion indirectly by establishing that when an exponent d is chosen as a mod φ(n) multiplicative inverse of another exponent e, then the following will always be true Me×d ≡ M (modn).

 Using the definitions of d and e ,since the integer d is the multiplicative inverse of the integer e modulo the totient φ(n), we obviously have

e×d ≡ 1 (mod φ(n)) (4) 

This implies that there must exist an integer k so that

e×d − 1 ≡ 0 (mod φ(n)) = k×φ(n)..... (5)

• It must then obviously be the case that φ(n) is a divisor of the expression e×d − 1. But since φ(n) = φ(p)×φ(q), the totients

φ(p) and φ(q) must also individually be divisors of e×d − 1. That is

φ(p) | (e×d − 1) and φ(q) | (e×d − 1) ...........(6)

• Focusing on the first of these assertions, since φ(p) is a divisor of e×d − 1, we can write

e×d − 1 = k1φ(p) = k1(p − 1)...... (7)

for some integer k1.

• Therefore, we can write for any integer M:

Me×d mod p = Me×d − 1 + 1 mod p = Mk1(p − 1)×M mod p ......(8)

• Now we have two possibilities to consider: Since p is a prime, it must be the case that either M and p are coprimes or that M is a multiple of p.

 Let’s first consider the case when M and p are coprimes. By Fermat’s Little Theorem 

 since p is a prime, we have

Mp − 1 ≡ 1 (mod p)

Since this conclusion obviously extends to any power of the left hand side, we can write

Mk1(p − 1) ≡ 1 (mod p)

Substituting this result in Equation (8), we get  Me×d mod p = M mod p (9)

 Now let’s consider the case when the integer M is a multiple of the prime p. Now obviously, M mod p = 0. This will also be true for M raised to any power. That is, Mk mod p = 0 for any integer k. Therefore, Equation (9) will continue to be true even in this case.

• From the second assertion in Equation (6), we can draw an identical conclusion regarding the other factor q of the modulus n:

Me×d mod q = M mod q..... (10)

 when p and q are coprimes, for any integers a and b if we have a ≡ b (mod p) and a ≡ b (mod q), then it must also be the case that a ≡ b (mod pq). Applying this conclusion to the partial results shown in Equations (9) and (10), we get

Me×d mod n = M mod n (11)