|
|
Many of the concepts of cryptographic security stem from the mind of Claude Shannon. His ideas have influenced the field of cryptography greatly, especially the concepts of diffusion and confusion. Although the following concepts of unconditional security, one-time pads, quantum key distribution, and computational security weren't actually conceived by Shannon, his ideas on perfect secrecy and information theory had great influence on the definitions of security.
A cryptographic system is considered to be unconditionally secure if it cannot be broken, even with infinite computational resources. This implies that cryptanalysis is impossible and that even if every possible key were tried in an exhaustive brute-force attack, it would be impossible to determine which key was the correct one.
One example of an unconditionally secure cryptosystem is the one-time pad. A one-time pad is a very simple cryptosystem that uses blocks of random data called pads. The pad must be at least as long as the plaintext message that is to be encoded, and the random data on the pad must be truly random, in the most literal sense of the word. Two identical pads are made: one for the recipient and one for the sender. To encode a message, the sender simply XORs each bit of the plaintext message with each bit of the pad. After the message is encoded, the pad is destroyed to ensure that it is only used once. Then the encrypted message can be sent to the recipient without fear of cryptanalysis, because the encrypted message cannot be broken without the pad. When the recipient receives the encrypted message, he also XORs each bit of the encrypted message with each bit on his pad to produce the original plaintext message.
While the one-time pad is theoretically impossible to break, in practice it's not really all that practical to use. The security of the one-time pad hinges on the security of the pads. When the pads are distributed to the recipient and sender, the assumption is that the pad transmission channel is secure. To be truly secure, this could involve a face-to-face meeting and exchange, but for convenience the pad transmission may be facilitated via yet another cipher. The price of this convenience is that the entire system is now only as strong as the weakest link, which would be the cipher used to transmit the pads. Because the pad consists of random data the same length as the plaintext message, and the security of the whole system is only as good as the method used to transmit the pad, it usually makes more sense in the real world to just send the plaintext message encoded using the cipher that would have been used to transmit the pad.
The advent of quantum computation brings many interesting things to the field of cryptology. One of these is a practical implementation of the one-time pad, made possible by quantum key distribution. The mystery of quantum entanglement can provide a reliable and secret method of distributing a random string of bits that can be used as a key. This is done using nonorthogonal quantum states in photons.
Without going into too much detail, the polarization of a photon is the oscillation direction of its electric field, which in this case can be along either the horizontal, vertical, or one of the two diagonals. Nonorthogonal simply means the states are separated by an angle that isn't 90 degrees. Curiously enough, it's impossible to determine which of these four polarizations a single photon has with certainty. The rectilinear basis of the horizontal and vertical polarizations is incompatible with the diagonal basis of the two diagonal polarizations, so these two sets of polarizations cannot both be measured due to the Heisenberg uncertainty principle. Filters can be used to measure the polarizations — one for the rectilinear basis and one for the diagonal basis. When a photon passes through the correct filter, its polarization won't change, but if it passes through the incorrect filter, its polarization will be randomly modified. This means that any eavesdropping attempt to measure the polarization of a photon has a good chance of scrambling the data, making it apparent that the channel isn't secure.
These strange aspects of quantum mechanics were put to good use by Charles Bennett and Gilles Brassard in the first and probably best-known quantum key distribution scheme, called BB84. First, the sender and receiver agree on bit representations for the four polarizations, such that each basis has both 1 and 0. So 1 could be represented by both vertically polarized photons and one of the diagonally polarized photons (positive 45 degrees) and 0 could be represented by horizontally polarized photons and the other set of diagonally polarized photons (negative 45 degrees). This way, 1s and 0s can exist when the rectilinear polarization is measured and when the diagonal polarization is measured.
Then the sender sends a stream of random photons, each coming from a randomly chosen basis (either rectilinear or diagonal), and these photons are recorded. When the receiver receives a photon, he also randomly chooses to measure it in either the rectilinear basis or the diagonal basis and he records the result. Now the two parties publicly compare which basis each used, and they only keep the data corresponding to the photons they both measured using the same basis. This doesn't reveal the bit values of the photons, because there are both 1s and 0s in each basis. This makes up the key for the one-time pad.
Because an eavesdropper would ultimately end up changing the polarization of some of these photons and thus scramble the data, eavesdropping can be detected by computing the error rate of some random subset of the key. If there are too many errors, someone was probably eavesdropping and the key should be thrown away. If not, the transmission of the key data was secure and private.
A cryptosystem is considered to be computationally secure if the best-known algorithm for breaking it requires an unreasonable amount of computational resources and time. This means that it is theoretically possible for an eavesdropper to break the encryption, but it is practically infeasible to actually do so, because the amount of time and resources necessary would far exceed the value of the encrypted information. Usually the time needed to break a computationally secure cryptosystem is measured in tens of thousands of years, even with the assumption of a vast array of computational resources. Most modern cryptosystems fall into this category.
It's important to note that the best-known algorithms for breaking cryptosystems are always evolving and being improved. Ideally, a cryptosystem would be defined as computationally secure if the best algorithm for breaking it requires an unreasonable amount of computational resources and time, but currently there is no way to prove that a given encryption-breaking algorithm is and always will be the best one. So instead, the current, best-known algorithm is used to measure a cryptosystem's security.
|
|