|
Title: . Post by: nimda on June 02, 2012, 07:40:51 PM .
Title: Re: How do two large primes make (public key) cryptography possible? Post by: Meni Rosenfeld on June 02, 2012, 08:23:25 PM The most well-known PKC algorithm is RSA (http://en.wikipedia.org/wiki/RSA_%28algorithm%29); the basic idea is moderately simple and you can read about it in the linked Wikipedia article, but you need to understand a bit of number theory, starting with modular arithmetic (if you don't, that should be your first step). There's also a numeric example.
If the secret prime numbers are p and q and their public product is n=pq, then to encrypt a message you take its representation as an integer and raise it to some power, modulo n. Anyone can do that, but most can't take a power and figure out what the base was. The recipient who knows p and q can find the totient phi(n) = (p-1)(q-1) and with some number theory magic use it to invert the power operation. Cryptology is a word not used very often and usually only by crypto pros. And for those who use it, it's not synonymous with cryptography; rather, they use cryptography to refer to developing and using cryptographic techniques, cryptanalysis to breaking them, and cryptology to both.(is cryptology a word?) If P=NP then there's a polynomial-time algorithm to break PKC. Whether this has practical relevance is not clear; if the best polynomial has order 20, then it's still impossible.Edit: a little offtopic... does PKC prove, or at least rely on, P!=NP? |