Definition: A prime number is a natural number that has exactly two
distinct divisors: 1 and itself.
Examples: 3, 5, 7, 11, 13, 17, etc.
Run the algorithm on an example: Find all primes from 2 to 24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
2 3 5 7 9 11 13 15 17 19 21 23
2 3 5 7 11 13 17 19 23
2 3 5 7 11 13 17 19 23
How long should we go? When can we stop this process? The remaining numbers in the list are the primes from 2 to 24.
Animated GIF of the sieve of Eratosthenes from Wikipedia.
Check out Mathematician Terry Tao on The Colbert Show explaining primes and why they're special!
An example:
Alice
a
, say 761
A
as the product of prime a
and another prime q1: Bob
b
, say 269
B
as the product of b
and another prime q2:
Alice computes key k as the product of a (her own *private* key) and
B (Bob's *public* key): k = a*B
= 363,762,893
Bobs computes key k as the product of b (his own *private* key) and
A (Alice's *public* key): k = b*A
= 363,762,893
So, Alice and Bob have *computed* a common key k
to use for encryption.
Notice that they didn't need to exchange any secret information in order to do so!
Eve
knows A and B, since they are public. But she does not know a, b, neither k.
Can Eve break the system? Yes, if she can compute key k.
How can she compute key k? She needs to find out what a or b are. In other words, Eve needs to factor A and B to their prime factors.
Let's deal with B (478,013), just because it is smaller than A and therefore easier for
us to try to factor.
Eve would have to try each one of the following primes (from 2 to the square root of B), to see what are
indeed the factors of B:
(We use this list of prime numbers upto 691)
Prime numbers from 2 to 691 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
At this point, we can start one division after the other, on the board. But, wait... can we do any better (faster)? We are 10(+) of us in this room.... Let's assign each student a column of the prime numbers above. For each one of them (p), the student tries the division B/p. This way we all work in parallel, like a parallel computer. At the end of the task, each student-processor comes up and reports the results.
At some point we will be able to break B to its prime factors.
Applying the same process, A can be factored as well.
Then, Eve has all she needs to break the system!
In the RSA or the Diffie-Hellman system, the "multiplications" and "divisions" above, are operations that involve powers and mod arithmetic. It is "extremely hard" to do the "operation" that corresponds to our "division" operation, and that's what makes it revolutionary and practical.
HTTPS uses public-key encryption to arrive at a common session key, this is then used as a key for private-key encryption. The chicken and egg problem has been solved!
But how do we trust that A
is indeed Alice's public key. Alice certifies it by getting it signed (digitally) from
a certifying authority. Check your browser!