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 log_{2} (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

_{m}kФ(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.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security : RSA Algorithm |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.