tailieunhanh - ASYMETRIC-KEY CRYPTOGRAPHY

TRAPDOOR ONE-WAY FUNCTIONThe main idea behind asymmetric-key cryptography is the concept of the trapdoor one-way function. TrapdoorOne-WayFunction(TOWF) One-WayFunction(OWF) . 2. f −1 is difficult to compute. 3. Given y and a trapdoor, x can be computed easily. | ASYMETRIC-KEY CRYPTOGRAPHY Le Trong Ngoc letrongngoc@ MODERN CIPHERS 1 TRAPDOOR ONE-WAY FUNCTION 2 FACTORIZATION 3 DISCRETE LOGARITHM 4 RSA CRYPTOSYSTEM 5 ELGAMAL CRYPTOSYSTEM 1 1 TRAPDOOR ONE-WAY FUNCTION The main idea behind asymmetric-key cryptography is the concept of the trapdoor one-way function. One-Way Function OWF 1. f is easy to compute. 2. f -1 is difficult to compute. Trapdoor One-Way Function TOWF 3. Given y and a trapdoor x can be computed easily. 1 TRAPDOOR ONE-WAY FUNCTION factorization problem When n is large n p X q is a one-way function. Given p and q it is always easy to calculate n given n it is very difficult to compute p and q. This is the factorization problem. Discrete logarithm problem When n is large the function y xk mod n is a trapdoor one-way function. Given x k and n it is easy to calculate y. Given y k and n it is very difficult to calculate x. This is the discrete logarithm problem. However if we know the trapdoor k such that k X k 1 mod f n we can use x yk mod n to find x. 2 2 FACTORIZATION 2 FACTORIZATION n X2 - y2 a X b with a X y and b X - y Feramat-Factorization n Il is the number to be factored X 4 Jn while x n smallest integer greater than Jĩi w t-x -n if w is perfect square y X X I 1 1 Jw at x y b x y return a and b