Diffie-Helman key exchange

Pick a large prime p, like 13

Pick any remainder other than 1 or 0 modulo 13 and start to look at its powers

x   "2 to the x modulo 13"
1   2
2   4
3   8
4   3
5   6
6   12
7   11
8   9
9   5
10  10
11  7
12  1

The powers 2^1, 2^2, ..., 2^12 contain every (non-zero) remainder modulo 13 exactly once.

Because of this, we say "2 is a primitive root modulo 13"

x   "3 to the x modulo 13"
1   3
2   9
3   1
4   3
...

In general with respect to any prime, primitive roots do exist (and are not so hard to find)

How would we find x such that

2^x = 9 modulo 13 (even if we know 2 is a primitive root)?

By brute force or something close to it (as far as anyone knows)

Now imagine p really is a large prime (hundreds or thousands of digits long) known to the world.

Imagine we know that 2 is a primitive root modulo p.

Alice: Picks a random a (between 2 and p-2) and computes

A = 2^a (modulo p)

She knows that she can announce A to the world at large and yet no one will (feasibly, in any reasonable length of time) be able to compute a.

Bob: Picks a random b and announces B = 2^b (modulo p).

Now Alice and Bob can each compute the value of X = 2^(a*b) modulo p because Alice can compute this as

(B)^a = (2^b)^a = 2^(b*a) = X  (modulo p)

Bob can compute it as

(A)^b = (2^a)^b = 2^(a*b) = X

So Alice and Bob both can compute X easily and "know" that no one else can.

[Because there is no known algorithm, given A = 2^a and B = 2^b to compute X without the knowledge of a or b]

Known to the world we have some hash function

H: <Integers> -> strings of 128 bits

and Alice and Bob can use H(X) as a private key for a symmetric cryptosystem.

----

Lab 1 task 5

Every character is actually a short binary string (for the purposes of this exercise we're using straight ASCII so every character is one byte)

We imagine encoding a character by taking its exlusive or with another (random) byte

a --> a + r

If someone use the same byte to encode a different character 

b --> b + r

and we "overhear" (a+r) and (b+r)

We can work out

(a+r) + (b+r) = a+b

So we overhear the exclusive or of the 

First character of message 1 with the first character of message 2
Second character of message 1 with the second character of message 2
...

The question that the task is meant to address is how much do we learn about the characters from that?


In Cryptologian

12345
54321
66666