RSA Algorithm in Cryptography and Network Security Tutorial

RSA Algorithm

RSA is an algorithm for public key cryptography RSA (RIvest Shamir Adleman) Algorithm was publicly described in 1977.

Mathematical Background of RSA Algorithm

Extended Euclidean algorithm Given x, find y, such that x.y=1 mod m. The extended Euclidean algorithm can efficiently find the solution to this problem.

Euler’s Theorem For any number, a relatively prime to

N=pq.a(p-1)(q-1)=1modpq

1. Why this is very useful?
2. Let Z = k(p-1)(q-1)+r, we have

a2=ak(p-1)(q-1) x ar …. = ar mod pq

• In other words, If z=r mod (P-1) (q-1), then az = a mod pq

Special case if Z= 1mod (p-1)(q-1),then az = a mod pq

We can use Euler’s theorem  to simplify az mod pq

RSA Algorithm

(i) Let n = pq , where p and q are 2 large primes.

• Public key (e, n), where e is relative prime to

(P-1) (q-1)

• Private key (d, n), such that

ed = 1 mod(p 1)•(q –1)

d can calculated using extended Euclidean Al

Encryption c = me mod n

Decryption cd = (me )d = med mod n

Security of RSA depends on the hardness of factoring.

factoring n = p x q is hard when n is large.

DES Data Encryption Standard)

The data encryption standard was developed in IBM. DES is a symmetric key system which has a 56 bit key and encrypts 64 bit plain-text to 64 bit cipher texts improve DES, the concept of 3 DES was introduced.