RSA Algorithm

1. The RSA algorithm 2. Security of RSA

RSA Algorithm

It was developed by Rivest, Shamir and Adleman. This algorithm makes use of an expression with exponentials. Plaintext is encrypted in blocks, with each block having a binary value less than some number n. That is, the block size must be less than or equal to log2 (n); in practice, the block size is k-bits, where 2k < n < 2k+1. Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C:

C = Me mod n

= Cd mod n = (Me mod n) mod n

(Me) d mod n

= Med mod n

Both the sender and receiver know the value of n. the sender knows the value of e and only the receiver knows the value of d. thus, this is a public key encryption algorithm with a public key of KU = {e, n} and a private key of KR = {d, n}. For this algorithm to be satisfactory for public key encryption, the following requirements must be met:

·        It is possible to find values of e, d, n such that Med = M mod n for all M<n.

·        It is relatively easy to calculate Me and Cd for all values of M<n.

·        It is infeasible to determine d given e and n.

Let us focus on the first requirement. We need to find the relationship of the form:

Med = M mod n

A corollary to Euler‟s theorem fits t0068e bill: Given two prime numbers p and q and two integers, n and m, such that n=pq and 0<m<n, and arbitrary integer k, the following relationship holds

mkФ(n) +1 = mk(p-1)(q-1) +1 = m mod n

where Ф(n) – Euler totient function, which is the number of positive integers less than n and relatively prime to n. we can achieve the desired relationship, if ed=kФ(n)+1

This is equivalent to saying:

ed ≡ 1 mod Ф(n) d = e-1 mod Ф(n)

That is, e and d are multiplicative inverses mod Ф(n). According to the rule of modular arithmetic, this is true only if d (and therefore e) is relatively prime to Ф(n). Equivalently,

gcd(Ф(n), d) = 1.

The steps involved in RSA algorithm for generating the key are

·        Select two prime numbers, p = 17 and q = 11.

·        Calculate n = p*q = 17*11 = 187

·        Calculate Ф(n) = (p-1)(q-1) = 16*10 = 160.

·        Select e such that e is relatively prime to Ф(n) = 160 and less than Ф(n); we choose e = 7.

·        Determine d such that ed ≡ 1 mod Ф(n) and d<160. the correct value is d = 23, because

23*7 = 161 = 1 mod 160.

1. The RSA algorithm:

Key Generation

2. Security of RSA

There are three approaches to attack the RSA:

·        brute force key search (infeasible given size of numbers)

·        mathematical attacks (based on difficulty of computing ø(N), by factoring modulus N)

·    timing attacks (on running time of decryption)

Factoring Problem

Mathematical approach takes 3 forms:

·        Factor n = p*q, hence find Ф(n) and then d.

·        Determine Ф(n)directly without determining p and q and find d.

·        Find d directly, without first determination Ф(n).

Timing attacks

It has been proved that the opponent can determine a private key by keeping track of how long a computer takes to decipher messages. Although the timing attack is a serious threat, there are simple countermeasures that can be used:

·        Constant exponentiation time – ensures that all exponentiations take the same amount of time before returning a result.

·        Random delay – better performance could be achieved by adding a random delay to the exponentiation algorithm to confuse the timing attack.

·        Blinding – multiply the ciphertext by a random number before performing exponentiation.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Cryptography and Network Security : RSA Algorithm |