5

I was attempting to explain public key cryptography to a layman the other day which requires an explanation of a trap door function. While I do know in principle what a trap door function is, I have to admit the specific mathematical properties behind the prime factorization problem and the ECC problem are beyond me.

Is there a simple example that can be used to exemplify a trap door function? I was thinking of squares and square roots, since squares are easily computed but square roots, in a way, require guided brute force.

6

The most basic answer is simply factorization. It's easy to compute the product of two prime numbers. It would take a minute or two, but you can calculate on pen and paper that 1093*1039=1,135,627. Going the other way is much harder. If I just gave you the number 1,135,627 and asked you what two numbers I multiplied to get that number, it might take you hours of trial factorization with pen and paper to factor it. To do it quickly you'd need a computer.

But if I asked you to factor 15, you'd quickly answer 5 and 3. So the difficulty of factoring goes up as the primes go up in value. If the two primes are chosen sufficiently large even a computer, or even thousands of computers aren't sufficient to arrive at the two factors.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.