Quantum cryptography

A pretty cool book I just read is Simon Singh's Code Book about cryptography. As my blog title suggests I'll mostly talk about the quantum part. Just a short summary.

Today's standard is the RSA cipher. Its speciality is that you need a different key for enciphering and deciphering. In other words: everyone can a encipher a message intended for you, but only you can read it. This is possible because exponentiating and subsequent modulo taking is in principle bijective (with an appropriate domain) but it is difficult to find the inverse function. At the heart of this method are two (large) prime numbers p and q. Their product N is made public and can be used for encrypting. For decrypting you need p and q. If p and q are large enough (and well chosen so that a few other mathematical tricks don't work), it is in principle impossible to deduce p and q out of N and only the person that initially multiplied p and q will be able to read the message.

Apparently quantum computers might be spefically suited for the task of factorising N. A regular computer would check numbers one at a time. The input for a quantum computer is a superposition of all the numbers to be checked. The computation can be carried out on this whole set. If done correctly the measurement at the end will lead the correct result with a high probability.

The way to escape from every decryption even quantum computers is quantum cryptography. It relies either on the uncertainty principle or on quantum entanglement. According to modern understanding of science it is in principle unbreakable. Unless of course some physicist eventually finds some of those hidden variables, how you can hop back and forth between parallel universes or some more realistic way of life beyond quantum theory.

P.S. There may be some quantum computers around already and people that know every dirty bit of secret about you.