Because it is just based on the idea of "same" or "different", exclusive-or doesn't mind what order operations are performed in, so all of these equivalences are always true:
Every number is the same as itself, and the difference between a number and zero is the number itself, so we also know that:
These two sets of rules tell us that exclusive-or is reversible in useful ways:
Encryption is performed by simply exclusive-orring the message and the key together. The fact that ((m xor k) xor k) = m means that encrypting and decrypting are exactly the same thing (so long as you use the same key k for each). "m" is the message you start with, "k" is the first key in your pad. You encrypt by computing (m xor k) which you send to your friend. Eventually your friend receives a completely unreadable bunch of numbers, which is of course (m xor k). He, she, or it decrypts the message by exclusive-orring it with the first key in his, her, or its pad, which will also be "k", computing ((m xor k) xor k) which is equal to "m" the original message. If your two pads got "out of synch" with each other, the two "k"s in the formula would be different, and you'd get ((m xor k1) xor k2) which is just rubbish.
If someone intercepts your encrypted message, what could they
possibly do
to crack the code? Nothing. Even the "brute force" approach doesn't work.
In cryptanalysis, the brute force approach means trying out every possible
key and finding the one that gives meaningful results. The reasoning being
that decrypting with the wrong key just produces gibberish, which even a
stupid computer can easily distinguish from real English.
(aside:
One of the many things
that makes computer-based cryptanalysis so useful is that real human
languages (and even programming languages for that matter) never use all
possible characters equally. In English, spaces, "E"s, "T"s, "S"s and "A"s
appear much more frequently than other letters, so a brute force approach
can be entirely computerised. The computer can try millions of possible
keys in a second, just seeing if the results of the attempted encryption
have a reasonable letter-distribution for a real language.)
With a one-time pad,
you can find a key that results in any intercepted message being decrypted
as any piece of text you care to choose. For example, suppose that I want to
send you the secret message "CAT" (kept short so that we can work through
the whole example quickly), and the first key in our shared pad is
(in hexadecimal) 39E1A6. Converting both to 8-bit binary (using ASCII for
the message) we have m = 01000011,01000001,01010100 and
k = 00111001,11100001,10100110, so the encrypted message
(m xor k) = 01111010,10100000,11110010. I would probably
convert that to hexadecimal (or something else) for convenience, getting
7AA0F2, which I send to you, and which is intercepted by the enemy agent.
You know that our first
key is 39E1A6, so you have no trouble decrypting the message, but the
German, trying the brute force approach will try all possible keys. At some
point, he will try the key 39E1A6 and see the message "CAT" as a possible
decryption, but at some other point, he will also try the key 3EEFD5, and
calculate 3EEFD5 xor 7AA0F2 = 444F47, which
converts by ascii to
the message "DOG". At some other point he will try the possible key
38F5DF, and calculate 38F5DF xor 7AA0F2 = 42554D,
which converts by ascii to the message "BUM".
So, although at some
point the Germans do try a key that reveals our secret message, they will
also try keys that reveal every possible three-letter message, and they will
have no possible way of knowing which is the correct one. Without the key,
every possible original message is equally likely.
Why must you never re-use a key? If you use the same key
more than once, you have to absolutely ensure that nobody ever gets to see
the decrypted (or plain-text) version of one of your messages. If anyone
ever gets hold of a decrypted message, and they happen to have intercepted
the encrypted version of that same message, they can simply exclusive-or the
two together, and the result will be your key.
If you hadn't reused your
keys, an old key would be useless information; the Germans could only use it
to decrypt the one message that they have already seen the decryption of.
If you did re-use that key, they would now be able to decrypt every other
message that you used that same key for.
It is usually impossible to
keep things secret for ever (sometimes what was a secret once becomes public
knowledge in the future), so reusing keys is always wrong.
Why is this not equally
a problem of all other encryption techniques? Simply because it is not
normally possible to reconstruct the key given a message and the encryption
of it. For the one-time pad scheme, if the message is "m" and the key is
"k", then the encrypted message is (m xor k). If the
Germans intercept this, and later find out what the original message was,
they will have both m and (m xor k). They will simply
put the two parts together and
compute (m xor (m xor k)) which is equal
to k. This complete reversibility and swappability is a peculiarity of
exclusive-or that does not apply to other encryption schemes.
Cracking it: The bytes that make up the repeated key should
be random; exclusive-orring a byte with a random byte makes another random
byte. No matter what the distribution of letters is in the original message
(e.g. 25% spaces, 10% "T"s, etc.) the distribution of different letters (and
in fact all 256 possible one byte values) in the encrypted message will
always be even. This is very important. If you take two random bytes, the
chance of them being the same will be 1 in 256. If you take two
characters from an encrypted message, they will be effectively random, so
the chance of them being the same will also be 1 in 256. However, if you
take two random bytes from the plain-text message, no matter what language
it is written in, the chance of them being the same will be a lot higher.
We'll make use of that fact in a little while.
Take an abstract example
of a message and a key. The message is 9 bytes long, and we'll call the
plain-text unencrypted bytes:
Once we know the key length (3 in this example) the rest is easy. We now
know that the key is repeated every 3 bytes. That means that the
1st, 4th, 7th, 10th, etc. bytes
of the message were all exclusive-orred with the same byte (the first byte
of the key). We don't yet know what that byte is, but we do know everywhere
that it was used. There are only 256 possible values that byte could have,
so we simply try them one by one.
Having established that
the key length is 3, we attack the first byte of the key first. We only look
at bytes 1, 4, 7, 10, 13, 16, ... of the intercepted message. We first
exclusive-or them all with 0 and measure the distribution of the results.
If the expected peaks (spaces very common, control-W's very rare, etc) we
know we have found the correct byte of the key. If the distributions are all
wrong, just move on to the next possible value (that is 1) for this byte.
We just run through all possible values for the byte until we find one that
gives a reasonable distribution of the decrypted bytes. If we get all the
way up to trying 255 without success, something is really wrong. The first
step (finding the key length) would not have found any peaks if no value for
the key gave a good distribution.
In exactly the same way,
we get each byte of the key, one-by-one. The only
clever trick here is
finding the length of the key. Without that we wouldn't be able to get any
further.
If you feel like looking at a program, here are two relevant ones. The first (xorstream.c) does the encryption and decryption using repeated exclusive-or once you know the key. Its very simple. All it does is show you that there's really nothing to it. You run the program by giving it a key in hexadecimal on the command line; it reads from standard input and writes to standard output, so if you want to encrypt the contents of file "plain.txt", storing the result in the file "hidden.txt" you would type xorstream 3AE791B9 <plain.txt >hidden.txt If you look at the program you'll notice that it would be very easy to modify it to take file names from the command line too.
The second program (crackxor.c) does the cracking. If you make up a random key, and use it to encrypt a large-enough text file with xorstream, this program should be able to decrypt it without knowing the key. It isn't a very pretty program, because I was in a bit of a hurry (that's the excuse I'm sticking with for now anyway), but if you really want to, you should be able to see what's going on.
DES, like the one-time pad and the exclusive-or scheme, is an example of
a symmetric algorithm. That means that you nly need one key; the same
key is used for both encrypting and decrypting. This sounds like a
convenience (only needing one key) but it really means that for practical
uses you may well need lots and lots of keys. if A and B want to communicate
privately, they must have a shared key that nobody else in the world knows.
If B and C want to communicate privately too, they must also have a shared
key that nobody else in the world knows. B can't use the same key for
communicating with both A and C, because then A would be able to read things
meant for C and vice-versa.
If
you have a group of just four people, who want to be able to communicate
with each other privately, you need a separate key for A and B to share,
one for A and C, one for A and D, one for B and C, one for B and D, and one
for C and D, giving a total of 6 different keys. In general, a group of N
people will need approximately ½N2 keys, with each person
having to remember (N-1) of them. Not much of a convenience at all.
DES works by dividing your message up into 64 bit blocks, and encoding
each block separately. The encoding is just a matter of combining the 64
bits of message with the 56 bits of the key in strange and confusing ways.
The only real operations involved are permuting (rearranging bits in a
different order) and exclusive-orring, but these operations are performed so
many times that there is (claimed to be) no known way to unjiggle the bits
without knowing the key.
Because DES is just a
sequence of permutations and exclusive-ors, it is very easy to implement in
hardware. You can buy a chip that can do literally Gigabytes of DES
encryption in a second, for just a few dollars. That is the reason for its
popularity. Vast amounts of data can be encrypted and decrypted at virtually
no cost. You could easily encrypt real-time high-resolution video streams.
Unfortunately, there is a down-side. The original design of DES specified a 128 bit key, but as a result of government (National Security Agency) insistence, it was reduced to 56 bits, and if you want to import encryption software to foreign countries you are only allowed to use 40 bit keys. In a 40 bit key, there are only 240 or approximately 1,000,000,000,000 different possibilities. With hardware that can try over 1,000,000,000 per second, the "brute force" attack, trying every possible key and seeing which produces a readable result, is guaranteed to succeed in just a few minutes. A 56 bit key would take 65,000 times as long, but it could still be done, and if you buy 65,000 of the chips, you could even crack the 56 bit keys in just a few minutes. A normal person couldn't afford to buy tens of thousands of those chips, but a government or large corporation could easily. I think we can be confident that government agencies can crack DES encryption in a matter of seconds. It would be irresponsible for them not to have that ability once they know that it can be done.
If DES had been allowed to keep its originally specified 128 bit keys, it
would
take about 4,000,000,000,000,000,000,000 times as long to crack as a 40 bit
key, which would make cracking a practical impossibility throughout the
foreseeable future. If your chip could try 1,000,000,000,000 keys per
second (far beyound our abilities now), and you had 1,000,000,000 chips
(far beyond our ability even to connect together now), it would still take
a few thousand million million years to crack one message, and that's about
a million times the age of the earth, and is many thousands of times the
expected lifespan of the known universe.
Even worse, the original
design (made by IBM) was "played around with" in Washington. I would not be
surprised if that playing around had added a deliberate flaw to make
cracking by those in the know even easier. The DES operations are so
convoluted that very few people have even a clue as to how to analyse its
security for themselves. I certainly haven't. As a result of all of this, I
would not trust DES with anything really important.
With all that behind us, the relevant facts are:
So, you generate the three numbers n, d, and e; two of them (n,d) are kept secret as your
private key, two of them (n,e) are published in a big directory as your public key, and
you're all set. The calculations involve big (really big) numbers. If the numbers
aren't big enough, you won't have good security. Remember the number n is part of your
public key; n is just p×q, and given p and q and e (the other part of your public key)
it is very easy to calculate d (the secret part of your private key). So how can there be any
security at all? Simply because p and q are really really big numbers, probably around 200 digits
(decimal) each, which means that n will be a 400 digit number, and there is no known method
for efficiently finding the factors of a very big number. Essentially, you'd have to try
a brute force search; given n, test every 200 digit number to see if n is divisible by it.
There are
100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
200 digit numbers to try, so nobody is going to be able to factorise n in any reasonable amount of
time. However, if anyone ever invents a good algorithm for factoring huge numbers, RSA
will instantly become useless.
Because RSA relies on doing calculations with
huge numbers with perfect accuracy, it takes a lot longer than DES or most other encryption schemes,
but if you don't need to encrypt huge amounts of data, it is probably a really good bet. The theory
behind it is so well known and thoroughly examined that we can be absolutely certain that neither
the NSA nor the KGB nor MI5 or anyone else has been able to put any "trap doors" in the algorithm.
The
only thing that can go wrong is someone discovering a factoring algorithm, and opinion seems
to be that no such algorithm exists.
One potential problem is that you have to
come up with very large random prime numbers. The only way to be absolutely sure that a number is
prime is again by a brute force search of all possible factors, which takes an impossible amount
of time. Probabilistic methods are used instead. You pick a very big random number, and test it
against enough randomly selected possible factors to be virtually (but not quite absolutely)
certain that it is prime. You can very easily get a 200 digit number that has only a 1 in
1,000,000,000,000 chance of not being prime.
One way hash functions provide a way of "locking" a document. If you are concerned that somebody might change a document after you've checked it, just calculate its hash value and remember that (the hash value is much much much smaller than the original document, you could easily store thousands of hash values in a "smart card" carried in your wallet (or purse)). Every time you lok at that document, just recompute the hash value; if it has changed, you know that the document must have changed. If the hash value has not changed, how certain can you be that the document also has not changed? Very certain but not absolutely certain. If you are computing 64 bit hash values, there are two to the power of 64 (which as approximately 20,000,000,000,000,000,000 possible results, all more-or-less equally likely. If somebody made any change to the document, there is only a 1 in 20,000,000,000,000,000,000 chance that the hash value would remain the same. I'd be happy to live with those odds. A really malicious person could have a computer automatically make many trivial changes to the altered document, just waiting for one to turn up with the same hash value as the unaltered document. If their computer could rehash a document 1,000,000 times a second, it would still be expected to take about 300,000 years for them to succeed in their fiendish plot. Of course, if you only used 32 bit hash values there are only 4,000,000,000 possible values, and at 1,000,000 rehashes per second, success would come after an average of 2,000 seconds, or just half an hour. A million rehashes per second is a bit too fast to take seriously now, but before too many years, it will certainly be possible.
Passwords in unix are managed this way. Your actual password isn't recorded anywhere in the
system, just its hash value. When you type your password to log in, the system calculates the hash
value of what you type, and compares that with what's stored. This means that nobody can find your
password even if they do berak in and get root access to the computer.