# 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.