RSA Algorithm

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 log₂ (n); in practice, the block size is k-bits, where 2^k < n < 2^k+1_. Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C:

C = M^e mod n

= C^{d mod} n = (M^e mod n) mod n

(M^e) ^d mod n

= M^ed 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 M^{ed =} M mod n for all M<n.  

·        It is relatively easy to calculate M^e and C^d 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:

M^{ed =} 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 _{= m}k(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.