Disclaimer

Many of my essays are quite old. They were, in effect, written by a person who longer exists in that my views, beliefs, and overall philosophy have grown and evolved over the years. Consequently, if I were to write on the same topics again, the resulting essays might differ significantly from their current versions. Rather than edit my essays to remain contemporary with my views, I have chosen to preserve them as a record of my past inclinations and writing style. Thank you for understanding.

April 2001

Unbreakable Encryption

Why aren't people using this stuff yet?

Brief Description

Totally, completely, 100%, perfect, unbreakable encryption is easy, and I mean really easy. It doesn't require an advanced education to understand and it doesn't require powerful computers to calculate. Why isn't anyone concerned about data privacy using it? It has one minor hitch: the two parties exchanging information must meet in person at least once. That one meeting will be enough to ensure a lifetime of unbreakable encryption between the two parties. Of course, if you are just encrypting your own files for protection purposes, this hitch doesn't apply and you can begin today. Even if you are trying to communicate with someone, if that other person is someone who you can meet even once, just briefly for a few minutes (nothing fancy is required here), then you're in business.

Full Description

Sections:

Introduction

Strong encryption gets a fair amount of press. There are weird laws preventing the export of encryption technology using keys longer than a certain length because it's difficult for the US government to break encrypted messages using long keys and that makes strong encryption technology a security threat. Then there was the fiasco with PGP, pretty good privacy, which made it easy for anyone anywhere to use reasonably strong encryption. Quite the legal hullabaloo erupted over that. In order to make fun of the export laws, people started wearing tee-shirts with encryption algorithms on them (and then wearing these shirts onto planes, get it?)

Here's what's so silly about this. Perfect encryption is easy, and widely known. When I say perfect, I mean perfect. It isn't just really really really hard to break. It's absoluteley impossible. The most powerful government with the most advanced technology and unlimited resources couldn't break it. Aliens that are millions or years more advanced than us and can push stars around at will couldn't break it.

The basic cipher

So, how's it work? This kind of encryption is called the one-time pad. The first way to introduce it is to remember the silly little cipher that we all learned when we were kids. Choose a letter of the alphabet, say 'F'. Now 'F' has the numerical value of 6 because it is the sixth letter of the alphabet. To encrypt a message you simply shift every letter forward 6 spaces (wrapping around at the end). To decipher the message just shift each letter back 6 spaces. The "key" is the letter 'F'. A slightly harder version of this cipher consists of mapping each letter of the alphabet to a different letter using a random mixup of letters.

Now, these are both pretty stupid ciphers. Assuming someone knows you're using the original cipher all you have to do is try shifting the message back 25 times at 25 different distances. One of them will hit the original message perfectly. This wouldn't work very easily for the second cipher however. But it's still pretty easy to break. You can pull all kinds of data out of the encrypted message that can be used to break the cipher. For example, the most common letter in the English language is 'E' and the most common letter in an encrypted message (assuming the message is long enough to exhibit probabilistic patterns) will probably be coded to the letter E. Certain letter patterns are common, for example 'THE'. Bottom line, these ciphers are stupid and pointless.

The perfect cipher

What's cool is that you can turn this almost useless cipher into an unbreakable form of encryption with just one tiny little change. It's based more on the original cipher, where each letter shifts forward by a certain numerical distance. A key is generated where each letter in the message if shifted by a different amount instead of using the same shift for every letter in the message. The key is simply a random stream of letters, for example, 'EIBHAKDJBL'. So, using this key, the first letter of the message would be shifted forward 5 spaced because of the 'E' in the first space of the key, and so on down the line.

That's it. No one can break this cipher. Since each letter is shifted by a different amount and the key is essentially random, there are no patterns to be discerned.

Now, let me show you how this same method can be adapted for any general kind of data. Letters are pretty limiting. For example, a picture isn't made out of letters, a sound file isn't made out of letters. Every kind of data stored on a computer is stored as a stream of bits, 0s and 1s. This is essentially an alphabet of 2 letters if you think about it. If a 0 gets a shift value of 0 and a 1 gets a shift value 1, then there are four possible occurrences when encrypting a given bit in the message:

Message bitKey bit, shift distanceEncrypted bit
00, 00
01, 1 forward1
10, 01
11, 1 forward0 (after wrapping
the 1 back to 0)

There is a more formal way to specify this kind of relationship. This is a XOR bitwise operator, which stands for "exclusive or". Given a message bit and a key bit, the encrypted bit will be a 0 if the message bit and the key bit are the same (either 0 or 1), and the encrypted bit will be a 1 if the message bit and the key bit are different:

Message bitKey bitXOR of the two bits
000
011
101
110

To decrypt an encrypted bit, you simply reverse the process. You can either think of this using the shift distances or the XOR operator, they'll both work. Using the XOR method (since it's more formal and all), you simply XOR the encrypted bit with the key bit to get the original message bit back. Look at the table above again and you'll notice that it works both forward and backward.

So now you can encrypt not only text messages but any kind of digital data, that is, any data that you store on your computer, text, pictures, sound, video, take your pick. The key is a stream of bits, the encryption algorithm is simply an XOR of the data and the key, and the decryption is identical. Writing this as a computer program would probably require about ten lines of code, and most of that would be opening and closing files. Pretty cool, eh? The reason that this is called a one-time pad is that repeated uses of the same key on different data sets will reveal patterns in the encrypted data that can be used to break the key, so you must generate a new key as long as the data set for every data set that you want to encrypt (in reality, a few repeated uses probably wouldn't reveal enough information to break the key, but there is no guarantee of this). This may be something of a hassle, but generating a stream of pseudo-random bits is pretty easy, and that's the price you pay for perfect, totally unbreakable encryption.

If your only goal is to protect your own personal data, you're all set. You can create a key and encrypt any data you want. The data will sit encrypted on your harddrive, totally protected from anyone who may wish to take a peek. When you want to see the data again, you can simply decrypt it. You'll have to store the key somewhere however. Tricky tricky. More on this problem below. Now, if your goal is to communicate with another person, in other words to send encrypted data to another person through the mail or over the internet, you have a problem. Quite simply, the person at the other end won't be able to decrypt the data unless they have the key. The two of you are going to have to have the same key.

What to do with the key

Here's the solution. Say you own some huge mega-bucks business in New York and you want to perform secure data-transfer and communication with an associate in Tokyo. Here's what you do. You meet just once. You're rich, you can afford a plane trip. When you meet, you give your associate a stack of DVDs pressed with random bits. That's it. So long as you can store your key securely and you trust your associate to do the same, you can trade encrypted data with your associate until you run out of key bits, and a stack of DVDs is a hell of a lot of bits.

Of course, having these keys lying around kind of causes a problem doesn't it? Now strictly speaking, there's no solution to this problem. However, I have a partial solution that's pretty good. Since it isn't perfect, it kind of fails the goal of attaining unbreakable encryption. However, since it doesn't entail leaving keys out in the open, it might not be less secure than the original method. What you do is memorize a list of movies, or you could use CDs and memorize albums instead of course. DVDs provide more key data, but there are many more CDs in the world than DVDs, thus providing better security. Even if someone figures out that your trick is to use CDs they have to find the right one out of millions. You could even beef up the unpredictability a touch by using every seventh bit or so. Using this method would require some careful software that skips over various track headers and such that are stored on a CD because these headers aren't random and could even provide information that could identify the appropriate CD to use as the key. Nevertheless, this is pretty good since it doesn't require leaving an obvious key lying around haplessly. The reason this isn't perfect is that CDs don't actually have random bits, they have a stream of bits that represent a fairly organized pattern of bits that encode the waveform of a piece of music. It is possible that these patterns can be identified and the key can be broken. It is extremely unlikely however. Whether this method is better or worse than a key of truly random (well pseudo-random anyway) bits depends on whether you think a key of bits can be stored securely.

So that's it. Go to it. Don't tell them I told you.

I would really like to hear what people think of this. If you prefer private feedback, you can email me at kwiley@keithwiley.com. Alternatively, the following form and comment section is available.

Comments

Name:
Comment: characters left

(Html tags will be intentionally stripped for security reasons, sorry.)
Verification: = (solve the equation, don't just duplicate the text)

Name:Anonymous Date/Time:2016/09/14 09:31:50 GMT
A modification I came up with is to use an unreleased DVD (obtaining this is an exercise for the reader) and encode your message using it as a onetime pad with a key K being the ISBN number. Obviously this will only reference one disk so provided that they don't screw up release dates that will do just fine.
Slight problem, the recipient will need a copy of the disk but if you have something so secret that you can't trust anyone (ie damning evidence of alien manipulation of Governments) this is an effective way to make sure it gets released worldwide at the proper time before the authorities have time to react!

Name:Medical Lake Man Date/Time:2014/06/28 22:53:41 GMT
Here is a thought I wonder: If an encryption can be broaken by a high speed computer, how does the computer know when it has broaken it? Let's say it has to read all 100 million, billion trillion possibilities and do a spell check. But you see? How would the computer know it was english? Or was it a bitmap? And if it did do spelling, what if each word had a random letter in front of it so that no word (or few words) would be readable (spellcheckable). It seems to me that it is all just as easy as shuffling a deck of cards. How can the computer (or anyone) know what configuration the cards were in before the shuffle?

Name:Anonymous Date/Time:2013/10/10 17:28:04 GMT
hello there

Name:Keith Date/Time:2012/06/05 16:19:34 GMT
Good point Don. Like I said in the article, one could use a familiar data source, such a music file or an image, just as you pointed out. The tricky part is that if the key isn't actually random, then it isn't perfectly unbreakable. A key that contains a pattern can potentially be broken. There are things one could do to mitigate the obvious patterns, such as sampling the music/image at widely spaced (or better yet, disparate) intervals (which just means you remove high frequency patterns but still suffer low-frequency patterns). Ultimately, only a truly random key is sufficient. Practically, however, whether an imperfect key is imperfect enough to actually break is a difficult question to answer. I think I would solve this by using multiple key sources (albums/images/etc.) and sampling from each of them in some strange fashion so that patterns in one would not necessarily be exhibited by all of the key bits. I don't know, it would require a deeper analysis to really answer this question.

Cheers!

Name:Don Date/Time:2012/02/22 19:51:51 GMT
Very entertaining and understandable. Thank you for that.
Just wondering, could you use the bits that make up, say, a picture of a car or something as a key?
I guess if you were CIA or KGB you might use the desktop wallpaper picture that is built into Windows. That way it would be available on almost any computer you log onto. All you'd need would be the program on a thumb drive and point it at the right JPG file.
Sound a bit Hollywood, doesn't it?

Name:Anonymous Date/Time:2012/02/08 13:26:20 GMT
You can do perfect encryption without ANY meet, or password exchange...

Name:Anonymous Date/Time:2012/02/08 13:22:57 GMT
There is a very simple and 100% unbreakable encryption possible, WITHOUT ANY meetings,
any keys being swapped, nothing...

Name:Anonymous Date/Time:2011/11/25 11:59:49 GMT
The answer is: CRYPTRA

Name:Anonymous Date/Time:2011/10/02 14:23:36 GMT
123

Name:Keith Date/Time:2011/09/19 20:36:55 GMT
Hey, thanks 'Anonymous' for writing. As a matter of fact, one time pads have been mathematically proven to be unbreakable when applied correctly. They are only compromised by perhaps practical concerns of a specific situation. For example, if the key is shorter than the message and is therefore reused, or if the key is not truly random (such as in my idea of using an existing music CD, even when sampled at some sporadic and even prime spacing). Each such compromise weakens the encryption...but is also not necessarily a requirement (one *could* produce a key as long as the message and *could* use a randomly generated key).

Cheers!

Name:Anonymous Date/Time:2011/09/19 20:17:37 GMT
your perfect encryption is flawed.

Name:Keith Date/Time:2011/08/25
NOTE THAT ALL COMMENTS OLDER THAN THIS ONE PREDATE THE COMMENT SYSTEM. They originated as email feedback and have been retroactively converted to public comments to seed the new comment system. As such I have redacted them where appropriate for the purpose of preserving their anonymity.

Name:Anonymous Date/Time:2010/03/15
Hello, i was reading a john sandford murder mystery book about encryption and it mentioned the fact that nowadays the nsa has a very difficult time breaking encryptions and is on the wane, which surprised me. I thought the reason pgp had all the government lawsuits dropped quite suddenly was that they had indeed broken it. But then again, it was hearsay, and im afraid i didnt look into it too much to see. but i am simultaneously alarmed that our government cannot break encryptions that could pose a threat to the united states's security, but also relieved at the idea of being free from big brother's prying eyes, since im a fan of personal freedom and responsibility.
[...]

Name:Anonymous Date/Time:2004/09/27
Greetings Keith,
As you still musing on unbreakable codes? I saw your article on the web and I'd be interested in having a discussion if that's still of interest to you.

Name:Anonymous Date/Time:2002/05/16
Hi,
I work at a very powerful company that developes
encryption software,. I would really be interested
to see what you had posted prior to 9/11.

Not by accusation or any other cause but for research
to see just how readily available a product like this
is to the public, not to mention uses or logic,.

Thanks

I am curious to hear what you think of stuff like
Virtual Matrix E , or DEs, or current RSA products.

Name:Anonymous Date/Time:1999/02/20
Hello,
I am currently researching unbreakable ciphers and I found your page, after it was taken down. I was you could tell me if the encryption you were publishing was based on the one-time pad.
I would like to know this because I'm trying to find any encryption systems other than the one time pad that are truly unbreakable. I think I could be on to something which very well could be.