Snake Oil - Encryption that Sucks

The Future of Cryptography - Quantum Machines

Quantum computing will prove to be a revolutionary way of solving very large (and currently infeasible) problems. The underlying imlication is that a machine can calculate and test a virtual infinity of possibilities in parallel, where traditional machines would have to try each possibility serially, one at a time. This is great news for the algorithmics community, but may foretell a rather unpleasant fate for cryptography, at least as we know it. For now, this technology is in its early stages, and will certainly not become widespread for some time.

For single-key encryption systems, quantum machines would be able to perform brute-force attacks in constant time, no matter how large the key space, simply by trying all possible keys in parallel. The more interesting use of these machines is to analyse public-key systems, such as RSA. To get a basic understanding of how RSA works, have a look at our theory section.

Finding Prime Factors on Traditional Computers
Certain problems seem to be extremely hard to solve using traditional deterministic sequential computers. Finding the prime factors of integers is one of these problems, and has particular relevecce to public-key encyption. The difficulty of factoring should be obvious if one considers the brute-force approach to tackling this problem. If a number n is to be decomposed into it's prime factors then the numbers from 2 up to the square root of n must be considered as a possible factor (if it is prime). If there are p prime numbers less than or equal to the square root of n that are factors of n, then there are C(2,p)+C(3,p)+...+C(p,p) possible formal products that could describe the prime factors of n, where C(i,j) is the binomial coefficient defined to be i! / j!(j-i)!. If n is large then the brute-force approach is not computationally feasible [Shor01].

Quantum Computing
To solve a problem, a traditional computer considers some specific string of 0s and 1s as input and produces some specific sequence of bits as output. Units involved in the quantum computation are the direction of spin of individual atoms. Instead of the single bit representation, the qubit or quantum bit can represent many different values simultaneously. In this way a quantum computer can consider multiple bit strings at once. If a classical computer operates on n bits (including bits for stack pointers and variables used in computation) for a specific problem P, then there are 2ⁿ states that the computer could be in. A quantum computer working on problem P could consider all 2ⁿ states at once. All 2ⁿ states would be superimposed over the n qubits. Thus there is an exponential increase in parallelism given by a liner increase in number of qubits. The drawback to the qubit representation is that when they are measured they will exhibit the properties of classical bit representations (i.e. they will be in some specific configuration). This means that if the result of the quantum computation on some specific bit string B is required then there is a probability associated with the observer actually getting the result of the computation on B. Luckily there are methods to increase the probabilty of getting the desired answer [Hogg96].

It is essential to note that it is not currently known how to build a quantum computer. Despite this fact, algorithms are presently being developed which use a quantum computer for the computational model. It is arguable whether a qauantum computer will ever be built. Many models have been proposed which seem feasible; moreover, the laws of quantum mechanics suggest that it is possible to build a quantum computing device [Shor01].

Factoring Integers on Quantum Computers
In 1994 when Peter Shor, a scientist working for Bell Labs devised a polynomial time algorithm for factoring large numbers on a quantum computer. This discovery drew great attention to the field of quantum computing. The technique Peter Shor describes is directly applicable to the RSA encryption algorithm; the value of p and q can be obtained and hence the algorithm can be comprimised [Shor01].

Quantum Encryption
Many strong encryption techniques have been developed that require the use of a secret key (see the section on one-time-pads for example). The problem with these techniques is that they require both parties to be aware of the secret key. The problem becomes circular: how do we transmit the secret key such that only the two parties involved know the key. The encryption techinques that require secret keys could still be useful if there was a way that both parties could be aware of the secret key and be sure that nobody else knew the key. In the early 1980's, Gilles Brassard and Charles Bennett proposed a solution to this problem that exploited the properties of quantum mechanics.

Brassard and Bennett proposed a method for encoding and recieving information such that if a person reads the encoded message then some unrecoverable properties of the message change. First off the secret key is encoded using a normal bit representation, but is transmitted using a non-traditional method: bits are actualized by photons that have different polarisations depending on whether they represent a 0 or a 1. If a someone, say Eve, attempts to intercept the key exchange between Alice and Bob, for example, then Eve would have to observe the photons. Due to the strange properties of quantum mechanics, just viewing the key would alter the polarisation of the photons. Eve would then have to retransmit the key to Bob and presumably Bob and Alice could detect that there was an intruder and would discard the key. But if just observing the photons changes the polarisation then how can Bob get the key even if Eve isn't listening in?

The solution to this problem takes advantage of the quantum mechanics. Alice begins by sending randomly generated bits to Bob at regular intervals (the bits sent would have to be remembered by Alice). Alice uses two polarising filters: one orientated at 0 degrees and one at +45 degrees. A 0 bit is encoded using the 0 degree filter and 1 bit is encoded using the +45 degree filter. In order to recieve the photons, Bob has two filters: one orientated at 90 degrees and one at -45 degrees. The properties of quantum mechanics give us the following facts:

A photon that strikes a filter that is orientated in the same direction of it's polarisation will always pass through the filter

A photon that strikes a filter that is orientated orthogonally to the direction of it's polarisation will never pass through the filter

A photon that strikes a filter that is orientated diagonally to it's polarisation has a 50% chance of passing through the filter and a 50% chance of being blocked

Bob can use these properties to gain knowledge of some of the random bits that Alice is sending him. If Bob is monitoring his -45 degree filter then there are two possibilites:

No photon passes through: Bob doesn't know what Alice sent since it could have been and +45 degree photon, which will always pass through
the filter, or it could have been a 0 degree, which is sometimes blocked
A photon passes through the filter: Alice sent a 0 degree polarised photon

Using this information, Bob can be sure if Alice sent a 0 degree polarised photon if a photon passes through the -45 filter. Likewise, Bob can be sure that Alice sent a +45 degree polarised photon if one passes through his 90 degree filter. Bob will be able to correctly identify a portion of the photons that Alice is sending. He can use this information to decide upon a key with Alice: since Alice is recording all the bits she sends, Bob can call her on the phone and tell her which bits he recieved. Bob would not have to tell her the value of the bits he recieved, but rather he would just have to tell which bits he got (ex. Bob might say I got bits 4, 7, 9, 15, etc...). If Eve is listening to this conversation, the data is useless, since the values of the bits being used are not revealed. The bits that Bob correctly recieved form the key that will be used for encryption and decryption.

Conclusion
The power of quantum computers seems to be quite obvious. If we are able to build them then many problems that are currently infeasible become feasible. Cracking the RSA encryption scheme is one of these problems. Although quantum computers may be only speculation at this point in time, they still have repercussions for computer users today. If a quantum computer is eventually built then any RSA encrypted data that still exists can be decrypted. It is also important to note that RSA has become a standard encryption technique and is used in a lot of communiction software. If a quantum computer was suddenly developed then much of the encryption software that is at the heart of internet applications would need to be updated. Quantum encryption seems to provide a way of getting around the power of quantum computing. The quantum encryption techniques described by Brassard and Bennett are virtually unbreakable. A quatum computing device would prove useless against a message encrypted using a one-time-pad technique. It is true that the quantum computer could consider all possible keys, but it would never know when it was right. A simple example will show why this is the case. Suppose a one-time-pad encrypted message is found and a quantum computer tries to decode it by cycling through all the possible keys. Lets say it tries some key k_j and decodes the message to be HELLO THERE BOB. Lets say it tries some key k_i and gets the message SECRET MESSAGE!. There is no way to tell which key is the correct one. Since quantum encryption guarentees that the key will not be known, the encrypted message is safe. This suggests that quantum encryption is a solution to the problem that quantum computers raise for more traditional encryption techniques such as RSA.

Back to the top.