CS114 Lab 10: on Cryprography

Public Key Cryptography

Prime Numbers

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.

How to find prime numbers: Sieve of Eratosthenes

Run the algorithm on an example: Find all primes from 2 to 24

  1. List all numbers, 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. Cross out all multiples of 2:
    2 3   5   7   9    11    13    15    17    19    21    23
    
  3. The first number after 2 in the remaining list is 3. Cross out all multiples of 3:
    2 3   5   7        11    13          17    19          23
    
  4. The first number after 3 in the remaining list is 5. Cross out all multiples of 5:
    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!

Encryption using Public Key Cryptography

An example:

Alice

Bob

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

Parallel Computing

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 and Digitial Signatures

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!