Handbook of Computer Science(cs) and IT

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 Eucledian algorithm Given x, find y, such that x.y=1 mod m. The extended Eucledian 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

a²=a^k(p-1)(q-1) x a^r …. = a^r mod pq

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

 

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

 

We can use Euler’s theorem  to simplify a^z 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 Euculidian Al

Encryption c = m^e mod n

Decryption c^d = (m^e )^d = m^ed mod n

Security of RSA dependes 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 plaintext to 64 bit cipher texts improve DES, the concept of 3 DES was introduced.