Can you send a secret to Mars?

I’ve been reading a book on cryptography, and playing with encryption of data between two sites, and these got me thinking about the history of cryptography.

Hundreds of years ago cryptography was used to send state secrets. With a lot of data, experts could crack and read your correspondence. You could have a “one time pad” where you used a key just once, which helped. The biggest problem was key distribution. In theory you could send the keys (or the pad of keys) through the post, but if people are intercepting and reading your mail – they get to see the keys!

With computers and mathematicians, sending keys to someone has got easier. It is harder to break, but not impossible.

I saw a document recently which said send your key on paper, in an envelope, by courier and not over the network. If people can read documents wrapped in jars from 2000 years ago in a CAT scanner – reading through an envelope should be easy. Also, there may be no rocket going to Mars to take your letter.

There are two common techniques used today for two ends to get a common secret: RSA and Diffie-Hellman

RSA

With RSA you have a private key (which only you has access to) and a public key – which every one can have access to. If you want to send me some data then you encrypt it with my public key and send the data to me. I use my private key and can then decrypt it.

Is this good enough ?

If you can afford to send someone to Mars, you can afford to have a team of programmers to create every possible private-public key combination and have a look up – if the public key is x then the private key is X. If you advertise a public key then some people can decrypt your message. If we do not advertise which private/public key to use then it makes it harder. But how do we negotiate in secret which private/public key to use?

Diffie-Hellman

From a mathematical perspective I found this is much more interesting. We want to communicate to get a secret key, knowing that people can monitor the network and see what we are sending.

It relies on some number theory properties

• (x **a ) **b = (x**b) **a for example (a**2) **3 = (a* a*) * (a* a) * (a*a) = (a * a * a) * ( a * a * a) = (a**3) **2
• modular arithmetic x mod y is the remainder if you divide x by y. 17 mod 5 is 2
• combining these (x ** a) mod y = (x mod y ) **a mod y. x**a could have hundreds or millions of digits. “x mod y” is less than y, so may fit in 64 bit integers.
• We agree two numbers x and y, which the spy can snoop. I think of a big number a, you think of a big number b.
• I calculate (x **a) mod y = X and send it to you. You take X and calculate X ** b mod y.
• You calculate x **b mod y = Y and send it to me. I take Y and calculate Y**a mod y
• The two numbers are the same, and we can use it as our secret key. The secret agent who does not know a or b cannot calculate the secret.

The secret agents listening on the connection do not know which values of a and b we used, and there could be an infinite number of ‘a’s which all give the same value of (x **a) mod y. Typically people use a and b with thousands of digits.

If you have an x with thousands of digits, and an a with thousands of digits x **a will have millions of digits so you have to have special routines to do the calculations. Fortunately the mod y calculation reduces the size down to a more manageable number – with only thousands of digits.

Who said mathematics was boring?

Is this good enough ?

If you use small numbers then it is easy to crack. Today’s thinking is using more than 2048 bits will be hard to crack.