Tuesday, May 6, 2014

Simple explanation of cryptography

Suppose you want somebody to send you a number $x \in [1,n-1]$ such that any eavesdropper does not know what the message is. The simplest way to do that is have them send $f(x)$ to you, where the function $f(.)$  is injective.

But if the function is easily invertible then anybody who knows what $f(.)$ was used can easily eavesdrop and decode the secret message. So, you can either keep $f(.)$ secret, or you can make the inversion of $f$ really difficult except for you. The latter technique is the one modern crypto-systems use and the former one was used in ancient times starting with Caesar. The problem with Caesar's technique if that sender and the receiver have to agree on what $f(.)$ has to be used and that communication has to be secure, thus the problem remains.

The main idea in modern cryptography is that you should find a function that only you can invert. This is based upon the difficulty of factoring large primes. Suppose that the function $f_n(.)$ can be inverted easily only when the factorization of $n$ is known. Now given such a function $f_n(.)$ you can secretly choose large primes and compute a number $n$ as the product of those primes. Now, since you know the factorization of $n$ the inversion is easy for you, but not for anybody else.

Since the sender does not need to know the factorization of $n$ to encode, your communication becomes secure.