Here's an excellent video:
 that gives clearly and simply the intuition of how public key  private key cryptography works using painting colors,
 and then explains how this can be implemented for computers.
Outline of its explanations:
colors
How could Alice and Bob agree on a secret color without Eve finding it out ?
We assume:
 it's easy to mix two colors together to make a third color.
 given a mix of two colors and one of those two colors, it's hard to reverse it to get the other original color.
This is a oneway fonction.
 1 : puc: public color. Alice and Bob agree publicly on a starting color. So Eve gets it too.
 2 : Alice randomly selects a private color: Ac, and mixes it with the public color: mix(puc, Ac). Bob randomly selects an private color: Bc, and mixes it with the public color: mix(puc, Bc).
 3 : Alice sends mix(puc, Ac) to Bob. Bob sends mix(puc, Bc) to Alice. These exchanges are intercepted by Eve.
 4 : Alice does: mix(Ac, mix(puc, Bc)). Bob does mix(Bc, mix(puc, Ac)). Assuming the mixing color operation is associative, they now both share the following color: mix(puc, Ac, Bc).
Eve cannot perform this last operation. Knowing only puc and mix(puc, Ac), she cannot reverse the mixing operation and extract Ac, Alice's private key. Same for Bc, Bob's private key.
maths
This idea can be applied to the exchange of numbers by computers: how could Alice and Bob agree on a secret random number without Eve finding it out ?
We need a oneway function similar to color mixing.

Given two positive numbers, a (the dividend) and n (the divisor), a modulo n (abbreviated as a mod n) is the remainder of the euclidean division of a by n. If \(\mathbf{a = q \times n + r}\), euclidian division, we note \(\mathbf{a = r \mod n}\) or \(\mathbf{a mod n = r }\)

Let \(\mathbf{p}\) be a prime number, e.g. : \(\mathbf{p=17}\). The number \(\mathbf{g=3}\), for example, is a primitive root of \(\mathbf{17}\) : which means that we have the following property: \(3^x = 0,...,16 \mod{17}\) in such a way that for \(x\) randomly varying, \(0,...,16\) are equally likely as an output of this operation. (Algebra: \(g\) is a generator of the finite field : \( <g> = \mathbb{F}_p $, where : $\mathbb{F}_p= \mathbb{Z}/p\mathbb{Z}\) )

oneway fonction: \(\mathbf{x \mapsto 3^x \pmod{17}}\)
 $ 3^{29} \pmod{17} = 12 $ easy
 $ 12 = 3^? \pmod{17} $ hard, discrete logarithm problem.
Let's draw the same diagram as the one illustrating the color exchanges:
 1 : Alice and Bob agree publicly on a couple \(\mathbf{(g=3, p=17)}\). This is the public key. Eve gets it too.
 2 : Alice selects a private random number (private key), e.g. \(\mathbf{15}\), and computes: \(\mathbf{3^{15} \pmod{17} = 6}\). Bob selects a private random number, e.g. \(\mathbf{13}\), and computes: \(\mathbf{3^{13} \pmod{17} = 12}\).
 3 : Alice sends \(\mathbf{6}\) to Bob. Bob sends \(\mathbf{12}\) to Alice. These exchanges are intercepted by Eve.
 4 : Alice computes: \(\mathbf{12^{15} \pmod{17} = 10}\). Bob computes: \(\mathbf{6^{13} \pmod{17} = 10}\). They now both share a number, \(\mathbf{10}\), that Eve can't compute, even though she could intercept all messages.
This works because:
 on Alice's side: \(12^{15} \pmod{17} = {(3^{13} \pmod{17})}^{15} \pmod{17} = {(3^{13})}^{15} \pmod{17}\)
 on Bob's side: \(6^{13} \pmod{17} = {(3^{15} \pmod{17})}^{13} \pmod{17} = {(3^{15})}^{13} \pmod{17}\)
 and : \(\mathbf{ {(3^{15})}^{13} = 3^{15 \times 13} = {(3^{13})}^{15} }\)
 Exactly like we had : mix(Ac, mix(puc, Bc)) = mix(Bc, mix(puc, Ac)) = mix(puc, Ac, Bc) in the illustration with painting colors.
Eve cannot perform this last operation:
 to compute Alice's private key she'd have to solve: \(\mathbf{3^{?} \pmod{17} = 6}\)
 or to compute Bob's private key she'd have to solve: \(\mathbf{3^{?} \pmod{17} = 12}\)
Both are instances of the same discrete logarithm problem, namely calculating the inverse function of the initial oneway function \(\mathbf{x \mapsto 3^x \pmod{17}}\). Eve can't do it just like knowing only puc and mix(puc, Ac), she could not inverse the mixing operation and extract Ac, Alice's private key, or similarly could not extract Bc, Bob's private key.
biblio
 complete video, including historical background: http://youtu.be/YEBfamv_do
 Credits: Art of the Problem
 https://www.youtube.com/user/ArtOfTheProblem/about
 Each episode presents a problem and follows its journey from prehistoric through modern times.
 Creator: Brit Cruise
 Music: Cameron Murray
 Illustration: Mark Phillips
 Female Narrator: Lyndsay Simmons
 original paper, Whitfield Diffie and Martin E. Hellman: http://wwwee.stanford.edu/~hellman/publications/24.pdf
 same paper, contemporary fonts: http://cs.unc.edu/~fabian/course_papers/diffie.hellman.pdf
 https://en.wikipedia.org/wiki/Euclidean_division
 https://en.wikipedia.org/wiki/Modulo_operation
 https://en.wikipedia.org/wiki/Modulo_operation
 https://en.wikipedia.org/wiki/Finite_field
Comments
comments powered by Disqus