## Key exchange overview

*July 15, 2011 at 7:46 pm* *
Leave a comment *

Warning: This is me using the internet as an entity to explain things to. Any of this could be a lie.

Go read a text book.

=== Scenario ===

Alice and Bob and trying to communicate in a world where all their messages can be intercepted. What can they do.

=== The key exchange problem ===

Idea: If alice and bob have a symmetric encryption algorithm all the need to do is share one secret. Is it possible for alive and bob to create a shared secret by exchanging functions of private secrets that no one else will know.

=== Formalisation ===

The extremely optimistic formalisation looks like this.

A: has a secret a

B: has as secret b

A publishes f(a)

B publishes f(b)

A uses f(b) to calculate g(f(b), a) privately.

B uses f(b) to calculate g(f(a), b) privately.

[ Here we are optimistic because:

A and B use the same functions. Only one message is send from each party. The messages don’t depend upon one another]

=== Stupid approach ===

Have f(a) = ca, g(x, y) = xy. Hurrah everything works by associativity and commutativity! The only problem is that c is common knowledge, so since we can do division moderately easily be lose.

=== Fixing this ===

Exponentiation is a nice operation

(a^b)^c = a^(bc) = (a^c)^b

since taking logarithms modulo some number is hard we can use this, giving us key exchange.

Entry filed under: Uncategorized.

Trackback this post | Subscribe to the comments via RSS Feed