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
- Why this is very useful?
- 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 Euculidian Al
Encryption c = me mod n
Decryption cd = (me )d = med 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.