RSA Algorithm in Cryptography and Network Security Tutorial
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
- 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
(i) Let n = pq , where p and q are 2 large primes.
- Public key (e, n), where e is relative prime to
- 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.
Sorting in Design and Analysis of Algorithm Study Notes with Example
Learn Sorting in Handbook Series: Click here