^[ÂSV‹ñW�...½�...'ÇU-???

Published Date
01 - Feb - 2006
| Last Updated
01 - Feb - 2006
 
^[ÂSV‹ñWŽŒÇU-???
This is a story about people with secrets. Through the ages, they have been plagued by the incurable tendency of other people to try whatever they can to find out what these secrets are. We are, after all, but human. Keeping everything hush-hush has been a constant battle of wits. Cryptography-the art of writing messages so that only the intended recipient can understand it-was soon born.

Alice, Bob... Aur Woh
We can't journey into the world of secret communication without some seasoned players, so we've recruited Alice and Bob-two veterans of the game who have been secretly chatting with each other under the watchful eyes of cryptography researchers for years. The villain here is played by Eve, whose sole purpose is to eavesdrop on Alice and Bob's conversation without them finding out.

Nyah Nyah Nyah!
To foil Eve's dastardly schemes, Alice and Bob turn to mathematics. Before sending out her message, Alice gives it to an encryption program, which performs its mathematical magic on it, turning an otherwise readable plaintext message into what looks like gibberish, or ciphertext. Bob then uses a decryption program to turn that gibberish back into plaintext. Of course, Eve's case isn't entirely hopeless. If she manages to get her hands on how either Alice's encryption or Bob's decryption program works, she's back in the game-all she has to do is reverse-engineer their methods.

So plain old gibberish-ing won't work for Alice and Bob-they need a key to lock their message. The key is basically a string of numbers that the encryption program uses when it's turning messages into ciphertext. All mathematical operations rest on this key, and so even though Eve can still access the ciphertext and know exactly how the encryption and decryption programs work, she is still baffled without it.

Today's computers would take ages to crack an encrypted message, but what about tomorrow's computers?

Protect The Key, You Must
Even though Alice and Bob have keys that they can now mockingly wave in Eve's face, the big question for Alice is, "If I write my message using a key, how do I send the key to Bob so he can read it?" Obviously, sharing the key should be done in complete secret, but they really can't plan for Eve's creativity when it comes to new and improved methods to eavesdrop.

The first idea is the Public key and Private Key system. This way, Alice and Bob don't need to hunt for secure ways to distribute their keys. Instead, they each have a Private Key which they use to decrypt messages, and a Public Key which is used to encrypt the message. Think of it as a box with two keys-anyone with the public key can lock it, but only the person with the private key can unlock it. The public key/private key system relies on the fact that there are some mathematical operations that take longer to undo than do-for example, you could go all calc-happy and keep multiplying numbers to get a 1000-digit number, but factorising that number into all the numbers you started with is a pain even for supercomputers! Say Alice wants to send a message to Bob:

Alice: Oi! I need to send you something. Give me your public key.
Bob: Sure; it's 12I94732
Eve [with evil grin]: Hee hee, now I know the key!
Alice will then use Bob's public key to encrypt her message and send it to Bob.
Alice: *S*&(?"{|?O%%&
Bob: Aha! Now that the message has been locked with my public key, I can use my own private key to unlock it.
Eve: What the…? I can't decrypt this!

Another method is the terribly secret One-Time Pad (OTP). The OTP is a random key, the same length as the message, which is applied once, and only once. Theoretically, there is no way of deciphering an OTP-encrypted message without knowing the pad itself. There is, of course, the fact that this pad has to be guarded with great care. Out of sheer paranoia, this pad also needs to be: (a) completely random so that Eve can't detect patterns and figure out the pad herself, and (b) used only once, so it's useless even if Eve finds it out-keeping her safely out of the conversation.

Attack! 
There are many methods that dedicated hackers can use to eavesdrop on your information.
The Brute-Force Attack is the most basic of them all. It runs through all possible combinations of numbers and letters to figure out the key to decrypt messages. Naturally, it's really inefficient and can actually take thousands of years to crack today's codes.
In a Man-in-the-middle Attack, the hacker intercepts messages between both parties, maybe even sending out wrong information to them without being detected. For example, in the public/private key system, Eve could intercept a message from Alice to Bob which contains Alice's public key. She could then send Bob her own public key. Bob would then use Eve's public key to send his secret message to who he thinks is Alice, but in reality, he's making it for Eve! Eve could then use Alice's public key to encrypt anything she wants Bob to read. Through all this, Alice and Bob don't know that Eve is listening in, so they think that they are talking to each other.
Sitting Pretty?
It all sounds really safe, doesn't it? To be dead honest, cryptography as it exists today is quite sufficient for our causes. Breaking into current systems is quite tough; that people have enough faith to carry out billions of dollars worth of transactions over the Internet speaks for itself.

But safety now doesn't mean safety forever. True, today's computers would take ages to crack an encrypted message (see box Attack!), but what about tomorrow's computers? Quantum computing is going to turn complex mathematics into child's play. Think of the 1000-digit number problem-a quantum computer would actually be able to give all the factors to the number in a single shot!

The first to succumb will be the public key/private key system. Nobody can deny that there is a relationship between the public and private keys of a person-after all, it is because of this relationship that enables people to tell whether a message is meant for them. It still hasn't been proven that Eve can't 'pick' Alice's lock just by knowing her public key and using math to figure out the private key. As computers become more powerful, scientists will have to keep refining this technique to keep private keys private.

The One-time pad is quite secure-in fact, it has been proven that even if Eve had infinite computing power, she wouldn't be able to break it. The trouble is, the key needs to be shared in a way that is perfectly secure, otherwise the entire effort is pointless.

Everything else aside, there is still no way to tell if your communication line is being monitored or not. So apart from guarding against the computers of the future, we need to figure out a way to prevent eavesdroppers getting out ciphertext at all.

Thankfully, before quantum computing arrives and exposes all our embarrassing secrets, there will be Quantum Cryptography, which will ensure that the Alices and Bobs of the future can still chat without Eve ruining the party.

Light In Shining Armour
Rather than using mathematics to encrypt messages, scientists have been working on quantum cryptography, which uses the quantum-physical properties of light to aid in securing communications. The purpose of quantum cryptography is to provide a secure way to transfer keys between Alice and Bob without Eve being able to find them out.

Light behaves strangely in the sub-atomic world. Sometimes it's a wave, and sometimes it's a stream of particles called photons. It is these photons that will be used to carry our data in the future.

Jargon Buster 
Encryption: Performing mathematical operations on messages to hide their content.
Decryption: The reverse process of encryption-getting the original message back from the encrypted version.
Plaintext: A clear, un-encrypted message, like "Hello."
Cipher: An algorithm used to encrypt plaintext and convert it into seemingly nonsensical ciphertext.
Key: A string of numbers that is given to the cipher along with the message. The cipher's resulting output depends on the key.
Ciphertext: The final result of plaintext fed to the cipher along with the key, for example, ‹ñWŽŒÇ^[Â.

In the world of classical physics, a bit is a bit is a bit. It's tangible-either as an electrical signal in a wire or the intensity of a light beam in a fibre-optic cable. And because it's tangible, it can be measured. Measuring something like the electrical current through a wire doesn't affect the current itself-it just passes through unchanged. This means that someone could tap a communication line without either party ever finding out.

In the quantum world, though, things are a little different. There are properties of photons that are tied together so tightly that measuring one property will cause a change in the others, disturbing the entire system. This way, any attempt to eavesdrop would easily be detected.

The Crazy, Crazy Quantum World
Suppose you have a friend behind you. You can't see him, so he could be standing, sitting, running, jumping, anything. Of course, you could just turn around and take a look, but do you really know what he was doing the instant before you looked? If you lived in the sub-atomic world, he was actually doing everything till you observed him; once seen, he settled into the state you saw him in. What state? Well, you could see him in any state at all-it's random. Why random? Ah, well, Einstein himself couldn't figure it out in his lifetime, so don't expect an explanation from us.

Even though quantum randomness gives scientists sleepless nights, it actually helps cryptographers sleep better. The problem with the one-time pad is that in computers, nothing is really random-programs are written that simulate randomness, but are actually predictable.

Er…
At the core of quantum physics is the concept of Uncertainty. Two properties of a photon can be related in such a way that the more certain you get about one, the less certain you get about another. Heisenberg's Uncertainty Principle describes the relationship between the position and momentum of particles. Basically, if you know the position of a photon, you will never know its momentum unless you are prepared to give up your knowledge of its position.

Stand Me Up, Lie Me Down, Turn Me Around
The property of photons that is used in quantum cryptography is Polarisation. Light waves move in different planes-vertical, horizontal, and everything in between. Linear Polarisation is the act of selecting only those light waves that move in one particular plane. Light could either be vertically or horizontally polarised. There is also the special case of polarisation called Circular Polarisation, where the light wave is made to move in a circular fashion rather than the classical up-and-down in one plane. Circular polarisation could happen in the right or left direction. Each photon carries with it information about its polarisation. Linear and Circular polarisations are bound by uncertainty-your measurement of linear polarisation will destroy your measurement of circular polarisation, and vice versa.

Much to our relief, quantum cryptography can be understood even if you don't understand polarisation.

1                               4                                               2                               3 

                                            
Setting The Scene-Artur Ekert's Card Tricks
In 1991, Artur Ekert came up with an interesting analogy to help us lesser mortals understand quantum cryptography.

Suppose we have a whole bunch of sealed envelopes with either blue or red cards in them. Each card has either 0 or 1 written on it. Blue cards can only be read using a special "blue machine," and red cards can only be read using a "red machine." If we put a blue card in a red machine, the machine will throw out a random guess as to whether there was a 0 or 1 written on the card, and vice versa.



The colour of the card (the photon) represents its polarisation-let's say red for linear and blue for circular. A 0 on a red card would mean that the photon is horizontally polarised, and a 1 would mean it is vertically polarised. Similarly, a 0 on a blue card would mean left-circular polarisation and a 1 would mean right-circular polarisation.

Somewhere in these observations comes the whole craziness of the quantum world. If we put an envelope with a blue card that says "1" into the red machine, it will make a guess at what's on the card-say 0. But now, if this card is put back into the red machine, it will still read 0. But wasn't it supposed to give a random answer each time? What has happened is that the card has now taken on the properties of a red card with 0 written on it, and its ever being blue with 1 is now a distant memory. This is a manifestation of uncertainty: observing a card as blue automatically destroys the assumption that it was ever red, and vice versa.

Quantum Weirdness And Spooky Happenings
If you thought all this was bizarre, read on to find out what even the greatest of scientists call weird. It's called Quantum Entanglement, and had been billed by Einstein himself as "spooky."

The concept of quantum entanglement talks about photons that are so closely related that it's impossible to describe one without describing the other, no matter how far apart they are. And the really spooky part is that any attempt to measure the properties of one photon will immediately affect the other one-photons talking to each other in no time at all.

Coming back to the cards: suppose, now, that we hand one sealed envelope each to Alice and Bob. We find that if both of them use the same colour machine, their outputs are the same-either both 0 or both 1. But if they use different machines, the outputs may or may not be the same. But how? There is no way for both of them to know what colour card they are receiving. Let's try to guess what the card could be before either of them checks it in their respective machines. What if both cards were blue? That would surely get them the same answer if they both put the cards in their blue machines, but that doesn't mean that they would get the same if they put the card in their red machines. By similar reasoning, we can also discount that they were both red.

What if both were different colours? Even that wouldn't explain why both in a blue machine would give the same outcome-what happened to the logic of having random outcomes when the colours didn't match? The only option left is that there was no colour or data on those cards before they were put in the machine.

What we didn't tell you is that the cards we gave Alice and Bob were really entangled-so if Alice's blue machine said that the card has 1 written on it, then both cards are blue with 1 written on it. Now, if Bob puts the card in his blue machine, it will (correctly) tell him that its value is 1, but if he puts it in his red machine, he will get either a 0 or 1 randomly-just as expected.

Why Won't You Talk To Me?
Finally, now, we are in a position to discuss how keys are exchanged in the quantum cryptography scenario.

We have our old favourites-Alice, Bob and Eve; joining them is a source of entangled photons-let's call him Sam. We can use the card analogy here as well.

Sam sends out pairs of entangled cards to both Alice and Bob, who decide, independently of each other, which machine to use to read it. Suppose Alice starts with her red machine and gets a reading of 0, and Bob uses his blue machine and gets the same reading. This goes on for a long while. After a set number of such trials, they start to compare notes. They discuss the measurements (but not the data they got from them) over a public channel-something like:
Alice: "I used my red machine."
Bob: "Hey so did I!"
OR, Bob: "Nah, I used blue."

This continues for all the cards that were sent out by Sam. Finally, they keep only the data they got from those cards for which they made the same measurement, and discard the rest. Thanks to Quantum Weirdness, they know that they now have the same string of data. To make doubly sure, though, they share some of this data, again over the public channel, to see if everything matches. Once this is verified, this shared data is then discarded. What they are left with is a shorter string of data that only the two of them know-the Key!

But wait, didn't we say that Alice and Bob discuss all this in public? What happened about all that secrecy that was promised? Let's take a look at what information Eve has if she was listening in on all of this (and of course she was):
1. She knows which machines both Alice and Bob used, and
2. She knows a few selected bits of the key.
Our response:
1. So what if she knows which machines were used? She doesn't know what answers the machines gave Alice and Bob, does she?
2. Again, so what? Remember, the bits that are discussed in public are discarded and are no longer part of the key.
Take That, Eve!
Our concern here is a man-in-the-middle attack (see box Attack!). How can Eve find out the key without both Alice and Bob knowing she's there? She needs to send them her own cards, and make sure that both Alice and Bob get the result that Eve wants them to. Suppose she sends out a pair of cards with 1 on them, and both Alice and Bob use the blue machine (Eve can find this out because Alice and Bob are going to discuss what machines they used). So because both Alice and Bob used the blue machine, they got 1 as their output-exactly what Eve wanted. If this continued this way, Alice and Bob would end up agreeing on a key that Eve created. Bye bye, privacy!

Isn't there a possibility that Alice and Bob could end up using different machines? Their output wouldn't tally, and Eve can't know what the outcome will be. True, but these results are discarded anyway-they didn't use the same machine! So all Eve needs to do is skip this part in the key she's trying to send Alice and Bob, and see what they got for the next bit. She'd still know the part of the key that has been agreed upon, so she's still a threat. Could it be that a quantum cryptography system is not immune to attacks?

Wait! What if Eve sent out blue cards, and Alice and Bob used their red machines? Would they get the same result then? Now this is where Eve's dirty little secret is revealed-you see, she didn't send out entangled cards-just identical cards to fool Alice and Bob into believing they are entangled. So there's a 50 per cent chance that even though Alice and Bob use the same machine, they will get different answers. When they do their final check and reveal parts of the key to each other, they are going to end up in a situation where they both used red, but got different answers. "Something's wrong!" they'd say, "let's shut up for now." And that's the end of Eve's game.

Reality Check
The concept of quantum cryptography has been around since the late 1970s, and working systems have been set up in educational institutions as early as the 90s. However, it will take a while before we see it in more places. For one thing, quantum cryptography is possible only over fiber-optic lines. Before we see it in our daily lives, we still need to see a world where fiber-optics has penetrated to a much greater degree. Entanglement is a fun concept to read about, but it is a really difficult thing to do, and even once it's done, controlling that entanglement is possible only over small distances-around 60 km or so.

Most importantly, quantum cryptography hasn't evolved to suit a network scenario-point-to-point connections are all there is. Even so, there are real-life applications where it is already starting to become practical.

My Preciousssss…
The infrastructure for a quantum cryptography system is a massive expense; whose information could possibly be so secret that they wouldn't mind shelling out obscene amounts of money to protect it? Why, the military, of course! We don't want our national secrets being bandied about on public forums, do we?

Think: ten years from now, you're making a withdrawal from your ATM. You need to punch in your PIN, don't you? Would you really be comfortable with the idea that there could be a hacker tapping the line, waiting to make his quantum computer decipher your PIN?

Companies such as New York's MagiQ and Geneva's idQuantique are already providing quantum cryptography solutions to banks and the military-obviously the first people who would want such ironclad protection. Research is underway to use quantum cryptography in communication with satellites as well.

Billions of dollars are spent in credit card transactions on the Internet today. Sure, the cryptography used is really secure-the time it would take to decrypt your credit card number is much, much longer than the actual validity of your card. For example, it is estimated that it would take around a thousand years to break current techniques using today's computers. Who cares, then, if you're going to be long gone before your credit card number is found out? But then again, there is the looming threat of quantum computers. As we move on, and quantum cryptography can be used on the Internet, we should see an almost total stop to things like credit-card theft; almost every financial transaction could be carried out over the Net without any worries.

Another Reality Check
Quantum cryptography may be the ultimate safeguard against eavesdroppers-even eavesdroppers with quantum computers. There
is still the matter of encryption on your hard drive-if a hacker with a quantum computer gets into your system, nothing says that he can't break any kind of file encryption you have used. Secrets-especially military secrets-need to be kept hidden for decades, and we still need a system for encryption in storage media before everything is truly under lock and key.



Team DigitTeam Digit

All of us are better than one of us.