I understand the basics behind public key cryptography, in that each party has two keys - the public one encrypts, and the private one decrypts. What I cannot figure out is, How does the public key encrypt and not decrypt, but yet the private key can decrypt?
I do understand the possibilities of this, but, does anyone know what cipher can do this, and how does this practically operate?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
How it works depends on the cipher, but the basic idea is that of a trapdoor function.
A trapdoor function is a function that is easy to compute in one direction, yet believed to be difficult to compute in the opposite direction (finding its inverse) without special information, called the "trapdoor".
Many number theoretic problems have been used in the past successfully to build such functions, and the wikipedia article is fairly good.
Let's take one as an example, lets say the problem of factoring a number into it's prime factors. Every number can be uniquely broken up into a product of primes. It turns out though, that breaking a number up into its prime factors is difficult if the number is large enough and the factors are large enough, but give me a few large prime numbers and I can easily compute the composite that those numbers make up.
So, how can this be leveraged with cryptography? I choose say two large prime numbers called $p,q$ and set $n=p\cdot q$. I then set $e=65567$ and give you $e,n$. I then use my extra information ($p,q$) to compute $d$ such that $ed\equiv 1\pmod{\phi(n)}$. This can only be efficiently computed if you know $p$ and $q$.
You have $e,n$, so to send me a message $m$ you compute $c=m^e\bmod{n}$ and send $c$ to me. For me to get $m$ back, I must know $d$, I can only know $d$ if I know $p,q$ and you knowing only $n$ and $e$ cannot compute $d$.
To get $m$ back I compute $c^d\equiv (m^e)^d \equiv m^{ed} \equiv m^1 \equiv m\pmod{n}$, so I have successfully used my extra information to recover $m$, something you cannot do without the extra information.
The public key can encrypt (it is the forward direction of the "one-way function"), but cannot decrypt because it does not know the trapdoor information to go in the reverse direction.
The cipher described here is RSA. There are others, but RSA is pretty simplistic.
-
$\begingroup$ quote: "such that ed ≡ 1 mod n. This can only be efficiently computed if you know p and q." Is that: ed ≡ 1 (mod n)? $\endgroup$ Dec 8, 2012 at 21:21
-
1$\begingroup$ +1 nice explanation. ArtOfTheProblem uses a similar but possibly easier-to-understand explanation in their "Public Key Cryptography: RSA Encryption Algorithm" youtube video. $\endgroup$ Dec 9, 2012 at 1:27
$\begingroup$
$\endgroup$
1
If you are talking about RSA public key encryption the albebraic structure of the construction and some number theory will clear your puzzled situation. There is no meaning to write down how RSA works.Have a look here here
"$d$ is the multiplicative inverse of $e$: $ed\equiv1 \pmod{n}$. That's why $(m^e)^d \pmod{n}=m$
-
1