From http://www.mic-d.com/curriculum/lightandcolor/interference.html
From http://www.physik.unizh.ch/groups/groupfink/science/young.jpg
Toni Smith
24 May 2004
Math 187 Final Project
Modern cryptography relies entirely on the simple fact that large numbers are difficult to factor. Multiplying two prime numbers together to get a larger number is a rather simple task for a computer to perform. Reversing the process - taking the large number and breaking it down into its prime factors - is incredibly time consuming for even the fastest computers. It normally takes weeks or months using supercomputers, or hundreds of computers working in parallel over the Internet, to factor numbers of more than 100 digits. The largest number on record to have been successfully factored, known as RSA-576, was the 174 digit number
1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564 2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573 4031879550 6569962213 0516875930 7650257059 |
which was factored on December 3, 2003, after a massively parallel effort by the German Bundesamt für Sicherheit in der Informationstechnik (Federal Bureau for Information Technology Security). RSA-576 factors into two 87 digit primes,
3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317 |
and
4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527 |
(Interestingly, this factorization was announced on the day after the discovery of the largest known prime number - 6,320,430 digits - by the Great Internet Mersenne Prime Search.)
RSA, the most advanced modern cryptosystem, takes advantage of this difficulty in factoring large numbers to allow public key cryptography. The idea for public key cryptography arose out of the work of the American mathematician Whitfield Diffie, who came up with the concept of an asymmetric key. Premodern cryptography uses symmetric keys, meaning that a message is decrypted simply by reversing the way it was encrypted. For example, with a monoalphabetic substitution cipher, the plaintext "cipher" might be encoded as the ciphertext "ABCDEF", where c was sent to A, y to B, and so on. To decrypt it, the recipient must only know the key that the sender used in order to send A back to c, B back to y, and so on. Asymmetric keys, on the other hand, work by using one key for encryption and a different key for decryption. Alice could publicly release her encryption key so that anyone could encrypt messages to send to her. With Alice's decryption key still private, even if Eve intercepted an encrypted message and looked up Alice's public encryption key, she would still not be able to decrypt the message. Only Alice knows the decryption key, so only Alice can decrypt the message.
RSA, the brainchild of Ronald Rivest, Adi Shamir, and Leonard Adleman, uses an extremely long semiprime number as a person's public key. A semiprime number is the product of two prime numbers, p and q; thus, it can only be factored as p times q. Alice chooses her two primes, p and q, and multiplies them together, yielding the long semiprime N. She then computes size of the set of units between 0 and N, denoted φ(N). (The set of units between 0 and N is the set of all numbers in this range that have no factors in common with the factors of N, i.e. the units are numbers that are relatively prime to N.) Since N has only the prime factors p and q, φ(N) = (p - 1)(q - 1). Alice then chooses a number e and computes its inverse d, so that ed = 1 (mod φ(N)). She publishes N and e, her public (encryption) keys; she keeps d, her private (decryption) key, secret. She throws away p, q, and φ(N) - these values are no longer needed.
If Bob wants to send Alice the message M, he looks up Alice's public keys and uses them to calculate P = Me (mod N). This is the encrypted message that he sends to Alice. Alice decrypts the message with her private key d by raising it to the dth power: Pd = (Me)d = Med = M1 = M.
Alice needn't worry if Eve intercepts the message, because Eve probably could not decrypt it. The only known way for Eve to decrypt the message is to find the number d that is the inverse of Alice's public key e. For Eve to find d, she needs to know φ(N), which can only be obtained by factoring N. (Actually, it has not been proven that there are no other ways to find d, but none have yet been discovered.) Because large numbers are so difficult to factor, it is effectively impossible to determine the two prime factors p and q from the given public key N if the public key is sufficiently large. For high security transactions, the public key N tends to be over 300 digits. "The combined efforts of a hundred million personal computers would take more than one thousand years to crack such a cipher" (Singh).
The RSA cryptosystem would be destroyed if, at some time in the future, someone discovered a fast method of factoring large numbers. It seems doubtful that such a breakthrough would come in the form of a new algorithm or a mathematical formula - mathematicians have been trying to develop a fast factoring method for over two millennia. Many mathematicians believe that factoring is inherently difficult, and that no new mathematics can be developed to make it computationally easy.
The threat to RSA comes not from the possibility of a new factoring algorithm being developed. Instead, it comes in the form of an entirely new class of computers. Silicon chips continue to get faster, approximately doubling in speed every 18 months (according to Moore's Law), but a limit exists on how fast silicon chips can be made to run. Many experts believe that most known technological capabilities will approach or have reached their limits within the next ten to fifteen years. Even the fastest silicon-based computer that will ever be made may not prove fast enough to break RSA. A quantum computer, on the other hand, could factor a 300 digit number in the time it takes an ordinary silicon-based computer to produce that number by multipying its factors together.
Quantum computers utilize the quantum mechanical principle of superposition, according to some theorists, or of parallel universes, according to other theorists, in order to perform certain operations in a fraction of the time required by silicon-based computers. The principle of superposition/parallel universes is best illustrated through a classic physics experiment known as the Double Slit Experiment, first performed by the English physicist/physician/Egyptologist Thomas Young in 1799. After making a tiny hole in a window shutter through which sunlight could enter an otherwise dark room, Young positioned a screen with two tiny slits cut into it directly in the path of the light, dividing the incoming light into two streams (Figure 1). Rather than observing two patches of light on the facing wall, he observed several patches (Figure 2). Young realized that the light waves in each beam were interfering with the light waves in the other beam. The multiple patches of light resulted from two peaks or two troughs in the light waves overlapping ("in step" waves), giving rise to more intense light, while the dark areas separating the patches resulted from a peak and a trough overlapping ("out of step" waves), thereby cancelling each other out.
| |
| Figure 1: Setup for Young's Double Slit Experiment From http://www.mic-d.com/curriculum/lightandcolor/interference.html | Figure 2: What Young might have observed From http://www.physik.unizh.ch/groups/groupfink/science/young.jpg |
Modern versions of the Double Slit Experiment have proven that there is more mystery to these interacting light beams than meets the eye. Physicists now know that light exists not only as waves, but also as particles - photons. Even when repeating the Double Slit Experiment using a filament that emits single photons at a known rate, say one photon per minute, results identical to Young's are obtained. A single photon travels towards two tiny slits in a wall. Since the filament emits one photon per minute, no other photons are present to possibly interfere with this single photon that is approaching the slits. To enter the chamber on the other side of the wall, the photon must pass through either the left slit or the right slit. If it passes through the left slit, it will hit a detector in the chamber slightly on the left side; if it passes through the right slit, it will hit the detector on the right side. The experiment continues for several hours, so that many photons have passed through the slits one by one. Without any other photons present to interfere with each individual photon as it approaches the slits, one would expect precisely two regions of impact where the photons have hit over the course of the experiment - a left region and a right region. Instead, several regions are observed (Figure 3). The only conclusion to be drawn is that somehow, each photon interferes with itself.
 | |
| After 28 particles | |
 | |
| After 1,000 particles | |
 | |
| After 10,000 particles | |
|
Variations on the Double Slit Experiment have used electrons, protons, and other particles in place of photons, and the results remain the same. This is because, in accordance with quantum mechanics, matter itself exists as both particles and waves.
The ability of a photon (or proton, or electron, or any other particle) to interfere with itself cannot be explained by classical physics. Quantum physics explains the phenomenon in either of two ways. Most mainstream physics tends to explain the interference by stating that particles, including photons, exist in a "quantum superposition of states" until they are observed. This means that from the time the photon leaves the light source until the time it reaches the detector, i.e. the entire time it is not being measured or detected in any way, it exists in both a leftwardly-inclined form (the first "state," or possibility) and a rightwardly-inclined form (the second state). One single photon goes through both slits simultaneously, interfering with itself after passing into the chamber. The alternative explanation, held most notably by the originator of the concept of quantum computers, David Deutsch, is known as the "many worlds" or parallel universe explanation. This theory posits that when a particle is not being measured or detected and has the potential to do one of many possible things, the universe splits into many universes, at least one for each possible scenario. The particle then encounters each possible scenario and so does every possible thing it could do - in different universes. Thus, in a certain number of universes, the photon goes through the left slit; in a certain number of alternate universes, the photon goes through the right slit. Under specific circumstances, most notably the lack of any observer or detecting agent, these universes can interfere with each other. The universe that we see - the universe in which our consciousness resides - is just one of the many universes that have been branching off of each other since time began.
Significantly, when the Double Slit Experiment is repeated with detectors affixed near the two slits, recording which slit the particle went through, the classically expected results are obtained: the particle is seen to have gone through either the left or the right slit (not both), and the detector on the inner wall of the chamber, facing the two slits, records only two regions of impact. The quantum interference is nowhere to be found. This unexpected property can be attributed to the Heisenberg Uncertainty Principle: the act of observing the particle fundamentally alters its "behavior." Therefore, if a quantum computer is to create a superposition of states (or to initiate a branching of universes), it is of the utmost importance that the particles are not observed until after the quantum calculation has taken place. When it has completed, the act of observing the particles causes them to "fall out" of their superposition (or causes the data obtained from performing the calculation in each parallel universe to collapse into one universe). The particles are then in the "answer state," the state that represents the final results of the quantum calculation.
The principle of superposition or of parallel universes allows quantum computers to solve numerous problems in the amount of time that it takes an ordinary computer to solve a single problem. Suppose a mathematician wants the answer to two mathematical problems. With an ordinary computer, the mathematician would have to write a program to solve the first problem, input the data, and wait for the output, then repeat the process for the second problem. An ordinary computer must address questions sequentially. If the mathematician had a quantum computer, on the other hand, s/he could combine the two questions and input them simultaneously. According to which interpretation of quantum theory you prefer, the computer would then either interpret the input as a superposition of two states (one for each question) and would itself enter a superposition of two states, or the universe would branch off into two other universes so that the first question could be addressed in one universe and the second question could be addressed in the other. Since the laws of quantum mechanics allow many different states (questions) to exist (be answered) at the same time, the end result is that both questions could be answered "in parallel" on a quantum computer faster than they could be answered "in serial" on a silicon computer.
To illustrate how a quantum computer could be used to break RSA encryption, imagine that Eve intercepts a message, encrypted using RSA, that Alice was trying to send to Bob. Eve looks up Bob's RSA public key N (the key that Alice used to encrypt the message), and has only to factor it in order to obtain enough information to calculate Bob's private decryption key d. Suppose further that Eve does not know about the latest algorithms that have been developed for factoring large numbers (not that they would help very much anyway, since the number that Eve needs to factor is extremely long), so she decides to use a brute force algorithm to factor Bob's public key. She obtains a list of prime numbers between 1 and the largest integer that is less than the square root of Bob's public key. She then writes a program that selects two numbers from her list and multiplies them together, checking after each multiplication to see whether the product is equal to Bob's public key. If equality holds, Eve knows that the two primes that had just been multiplied together are the factors of N. We know that if Eve were to run this program on a silicon-based computer, even the fastest computers in the world would take many, many years to find the answer. However, if Eve has access to a quantum computer, she could represent the primes as two sets of spinning particles, multiply the two sets together only once, and come up with the answer in the amount of time that it would take a silicon chip to perform a single multiplication.
As you may remember if you have taken general chemistry, electrons have one of two possible orientations: spin up or spin down. An electron is described by four values called "quantum numbers," where no two electrons in an atom or molecule can have the exact same set of quantum numbers. Spin is the fourth quantum number, and can equal either +½ (spin up) or -½ (spin down). Just as silicon computers manipulate bits (binary digits - 0's and 1's), quantum computers manipulate qubits (quantum bits - particles that can take on two possible spins). Eve could represent a single number by a set of spinning electrons in the same way that numbers in binary are represented by a series of 0's and 1's. Adding energy to an electron, such as by zapping it with a laser, can change the spin from +½ to -½ or vice versa. Eve can take advantage of this fact in order to put her set of electrons (which represent a number) into superposition (or, depending on which interpretation of quantum theory you prefer, Eve can take advantage of this fact in order to cause the universe to branch off into many universes in which each possible computation can take place). The amount of energy needed to enact a change in spin must exceed a certain threshold value. Eve zaps her set of electrons with a minimal amount of energy very near the threshold value and - very importantly - does not observe the results. Maybe the minimal amount exceeded the required threshold, and therefore changed the electrons' spins; maybe it was below the threshold, and therefore the spins remain the same as they were. Eve does not know which is true, so according to quantum theory, both are true (or, either is true depending on which universe Eve is in). Eve then does this with a second set of spinning electrons. She now has two sets of electrons whose spin states represent a number, but she does not know what numbers they are currently representing; therefore, the two sets represent every possible number that could be represented by the electrons in the sets. The quantum computer then multiplies the two sets of spinning electrons together, so that every possible combination of numbers is multiplied together. When the quantum computer checks for equality with Bob's public key, the superposition collapses (or the data from the multiple universes comes together), and Eve is left with her two sets of particles having spins corresponding to a qubit representation of the factors of N.
If quantum theory could be used to take away our security by allowing anyone to decrypt messages that are currently too difficult to break, it could also be used to give us back our security in a form that is completely unbreakable. Assuming that scientists' knowledge of the laws of quantum physics is accurate, quantum cryptography could be used to create a cryptosystem that is unbreakable not just in practice, but in theory as well.
Quantum cryptography utilizes the polarization of light to transmit a message. The polarization of light refers to the angle of oscillation of a light wave. If you imagine light as a sine wave oscillating in a plane, the polarization of the light refers to the angle that the plane is rotated relative to another object, say the ground. Light can oscillate vertically, horizontally, and everywhere in between. Polaroid lenses serve as detectors for polarized light: vertically oriented Polariod lenses filter out horizontally polarized light, which cannot pass through the lens. Light that was polarized in some sort of diagonal fashion may or may not be blocked out by the lens. If a beam of diagonally polarized light did get through the lens, it would become reoriented as vertically polarized light. Each possibility - either blocking the light or reorienting the light - occurs to about 50% of the light waves.
For simplicity's sake, imagine that light can be polarized in one of four possible directions: vertical, horizontal, diagonal left, and diagonal right (represented as |, -, \, and /, respectively). Suppose further that there are two types of Polaroid-style detectors for this light: a "+" and a "x".The + detects vertically and horizontally polarized light; any diagonally polarized light that hits this detector will either be blocked or be reoriented with a vertical or horizontal polarization. The x detector detects diagonally polarized light; any vertically or horizontally polarized light will either be blocked or be reoriented with one of the two possible diagonal polarizations.
If Alice wants to send a message to Bob, she could use the following scheme: with the + detector, | polarized light represents a "1" and - polarized light represents a "0", while with the x detector, / represents "1" and \ represents "0". Alice then sends her binary message to Bob, switching unpredictably between the two possible ways of representing "1"s and the two possible ways of representing "0"s. For example, the message 1101101001 could be sent as:
| Message | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| Scheme | + | x | + | x | x | x | + | + | x | x |
| Transmission | | | / | - | / | / | \ | | | - | \ | / |
If Bob knows what scheme Alice used to transmit the polarized light, he can set up his detectors in the same order as Alice's scheme. For the first beam of light, he knows to use the + detector, so he correctly sees a | polarized beam and realizes that the first digit in Alice's message is "1". For the second beam of light, he switches to his x detector and sees a / polarized beam, which tells him that the second digit is also "1". Bob continues switching detectors in accordance with Alice's scheme until he receives her entire message.
If Eve does not know the correct detecting scheme, even if she could intercept the light, she could not read the message. This is because by random chance, Eve will probably guess the correct detecting scheme only 50% of the time. The times she guesses correctly, she will be able to read the correct digits, but when she guesses incorrectly, the light that she sees passing through the detector would be randomly repolarized as either a "0" or a "1". Eve would have no way of knowing which detectors she used correctly (hence which digits she got right) and which she used incorrectly (which digits she got wrong), because either detector would show a polarized beam of light pass through. At best, Eve would receive a garbled, nonsensical message.
The problem then becomes one of key distribution: How does Alice tell Bob which sequence of detectors to use beforehand? In practice, quantum cryptography as described here would never be used because Alice has no way of telling Bob which detectors to use without the possibility of being overheard by Eve. She couldn't call him on the phone and tell him; Eve could have a wiretap in place. She couldn't encrypt the detection scheme with RSA and send it to Bob, because in the world of quantum computers, RSA has already been broken. She couldn't transmit the detection scheme using quantum cryptography, because then they're back to their original problem again. Instead, quantum cryptography would be used in practice to produce one time pads that could be used to securely encrypt any message.
To create a quantum cryptography one time pad, Alice transmits a random sequence of binary digits using randomly chosen detector schemes. She keeps track of what digits she's sending and what scheme she used for each digit. Bob, in receiving the light waves, can only guess at which detectors to use. He uses a randomly chosen detector scheme himself, and keeps track of which detectors he has used and what type of polarized light he received. After continuing this process for a sufficiently long time, Alice can call Bob on an ordinary insecure phone line and tell him which polarization scheme she used for each digit. She does not tell him how she polarized each beam of light. (She might tell Bob, "I used + then x then + then x then x..." but she does not say, "I sent | then / then - then /...") Bob then tells Alice which detector schemes he guessed correctly. Alice and Bob agree to use only the information sent using the detectors that Bob guessed correctly, so the string of digits that they agree to use is a subset of the complete set of digits that Alice sent. This substring is their new key, a one time pad that either one of them could use to securely encrypt a message.
Even if Eve were spying on Alice and Bob, and had intercepted the light waves that were being sent between them, she could not obtain the key. This is because Eve would never guess all of the same detectors that Bob would guess, so when Alice calls Bob on the phone after the transmission is complete, Eve would overhear that Alice and Bob had agreed to throw out half of the data that she had collected - the half that did not agree with Bob's own guesses about which detector to use. Eve could not use her incomplete, garbled key to decrypt a message encoded with the one time pad that Alice and Bob established together.
Quantum cryptography not only allows for the creation of an unbreakable cryptosystem, it also reduces the possible harm that could result from a "man in the middle" attack. All forms of encryption are vulnerable to a "man in the middle" attack, which occurs when Eve intercepts a communication that Alice is trying to send to Bob, takes the message for herself, and sends a fake message to Bob in its place. Even though with quantum cryptography, Eve could never hope to decrypt Alice's message, she could still interfere with communication between the two parties. Quantum cryptography cannot prevent these "man in the middle" attacks, but it does allow Alice and Bob to know after the fact that an eavesdropper had been intercepting their communications. If Eve had been intercepting the light waves that Alice was sending to Bob, her act of intercepting or detecting them would alter their polarization whenever she used the wrong detector (statistically, 50% of the time). If she then let the light waves continue on their course to Bob, or if she sent her own light waves to Bob in their place, Bob wouldn't know it at the time. When Alice calls Bob to compare detector schemes, thereby obtaining their one time pad, they agree to use all the digits for which their detector schemes agreed. Since they exchanged no information about the actual polarization of the light that Bob detected, they still do not know that Eve's interference caused some of the polarizations to deviate from what Alice sent to Bob, even when Bob chose the right detector. Alice's version of the one time pad will then be different from Bob's version. After Bob uses his version of the one time pad to encrypt a message and sends it to Alice, Alice decrypts it using her version of the one time pad. Since the one time pads were different, the message comes out garbled and nonsensical. A nonsensical message would warn Alice and Bob that something interfered with their original communication. Quantum cryptography can then be thought of as superior to other cryptosystems in its detection - if not prevention - of "man in the middle" attacks. Eve can only frustrate Alice and Bob by garbling their key; she cannot read the messages they have sent or send false messages in their place.
The technology behind quantum cryptography exists today. In fact, you can purchase your own quantum cryptography system today from a company called MagiQ for a mere $50,000. The current problem that prevents quantum cryptography from being implemented on a large scale is rooted in the same laws of quantum mechanics that make it an unbreakable cryptosystem in the first place. Eve's detectors alter the polarization of the light waves that Alice and Bob are using to communicate. In reality, many factors besides Eve exist that could alter the polarization of the light waves. Even simple physical occurrences like water vapor in the air could alter the polarizations. For this reason, it is very difficult to transmit the light over long distances. A year and a half ago, MagiQ announced that its commercially available quantum cryptosystem could transmit messages "an unprecedented 120 km distance." That's a far cry from the many thousands of miles that would need to be traversed between, say, Washington DC and Moscow. Over distances that long, the curvature of the earth becomes a limiting factor. Currently, a straight path is required to limit unwanted changes in polarization.
An even more severe restriction on the power of quantum cryptography also arises from the need to eliminate unwanted changes in polarization. All of the quantum cryptography systems in existence today require a direct connection between two machines in order to transmit data. This is because there is no currently known way to develop "quantum routers" or "quantum gateways" analogous to the routers and gateways of the Internet. The act of routing a polarized light wave from one line to another would alter its polarization. For this reason, quantum encryption might never come into personal use - there is no way that one person's home computer could be directly connected to every Internet server that the person could ever be interested in. Commerce over the Internet may continue to be based on RSA and similar cryptosystems far into the future, even if or when a quantum computer was built to crack RSA. Quantum cryptography might become a tool solely of governments and large banking institutions.
The use of one time pads allows for completely unbreakable encryption (provided that, as the name implies, they are used only once!). The use of quantum cryptography allows for a limited but unbreakable means of distributing these one time pads. Despite its limitations, quantum cryptography may be the only completely secure encryption system that the world will ever know.
Check these out for further information.
General books that cover a variety of the topics touched upon here:
1. Deutsch, David. The Fabric of Reality. New York: Penguin Books, 1997.
2. Singh, Simon. The Code Book. New York: Doubleday Publishing, 1999.
Articles on RSA:
1. Mathworld: RSA-576 Factored, 5 December 2003
2. Mathworld: RSA Number
3. Wikipedia: RSA
Article on the Largest Known Prime / Mersenne Primes:
1. Mathworld: 40th Mersenne Prime Announced, 2 December 2003
Articles on Moore's Law:
1. Wikipedia: Moore's Law
2. Tuomi, Ilkka. "The Lives and Death of Moore's Law"
Articles on the Double Slit Experiment:
1. PhysicsWeb: The double-slit experiment, September 2002 editorial
2. Wikipedia: Double-slit experiment
Article on the Heisenberg Uncertainty Principle:
1. Wikipedia: Uncertainty principle
Article on Quantum Computers:
1. Wikipedia: Quantum computing
Articles on Quantum Cryptography:
1. Bennett, Brassard, and Ekert. "Quantum Cryptography." Scientific American, vol. 269 (October 1992), pp. 26-33.
2. Wikipedia: Quantum cryptography
3. Slashdot: Quantum Cryptography Leaving the Lab, 12 April 2004.
Commercial Quantum Cryptography Dealers:
1. MagiQ Technologies: Quantum Information Solutions for the Real World
Picture credits:
