posted
People like hiding things, sometimes because what the information they have is truly vital, and can not be known by others (like government secrets or personal information), and sometimes because they’re paranoid. Whatever the cause, when someone wants to share that information with someone else, they want to make sure that no one but the intended recipient can read it. Of course there are many ways of doing this, like just making sure no one else receives or hears your message, but the most common way of keeping something secret is to encrypt it
Encrypting data is taking that data and changing it into some other data that is some how correlated to the original data in a way that can be reversed. For instance changing the phrase “John walked around the room” into “1” is not true cryptography unless the recipient of the message “1” knows that it represents “John walked around the room”. Perhaps the best, non-traditional example of cryptography is compression. Compressing data changes it into a different data set that, if the compression method is known, can be reconverted back into the original data. Encryption is normally something done with the specific idea of secrecy, so compression wouldn’t fit the bill in that case, but compression is a form of encryption.
The simplest, and original version of encryption was “Caesar’s Encryption”. If A is 1, B is 2, C is 3 and so on, then you would simply shift the numbers up by 3. So ‘A’ would turn into ‘D’, B to ‘E’ and so on. The last three letters at the end of the alphabet (‘X, Y, Z’) would be the first three of the alphabet (‘A, B, C’). Then, to “decrypt” the message (take the new data and turn it back into the original) is as simple as subtracting three from it. So ‘D’ would turn back into ‘A’, ‘E’ back to ‘B’ and so on.
This is a very simple encryption method, very simple and easy to crack, but it is a very good example of encryption, just bad for keeping actual secret data, you’ll be happy to know that your data is not encrypted this way!
All right, hopefully now you understand what encryption is, so let’s move on to some more complicated examples, and after those, we’ll get into RSA, the way your most secure data is encrypted, and maybe talk about some of the encryption ideas of the future. This wont be even approaching a complete or comprehensive look at encryption “algorithms” (the methods used to encrypt data are called algorithms), whole books can, and have been written on the subject, but by the end of this hopefully you’ll know something about how your data is encrypted, and heck, some of the simpler ones you can put into action yourself!
The first one is very similar to our original example, but to understand it, you have to understand modular arithmetic (don’t worry, it’s really easy, at least the amount you have to know to understand this algorithm ).
The “Mod function” is simple enough, take a number, say 17, and divide it by 5, what do you get? 3 with a remainder of 2 (3*5 + 2 = 17). 17 mod 5 = 2. That’s it! It’s the remainder of a division of two integers.
All right, so our first technique is adding, like in out first example, only it doesn’t just have to be letters, say a byte in a computer, that runs from 0 to 255. Add any number to it, say 130, and then mod it by 256. 234 will turn into (234+130) mod (256) which is (364) mod (256), which is 108. Apply this to any byte and you’ll get a unique result, also a byte wide. The benefits of this method are that it has “unique mapping” (if you don’t know what that means, don’t worry), it’s very simple and thus easy to use (and fast). The downsides are that it’s easy to decrypt, an the person decrypting it has to have some private information. Now this isn’t much of a problem for some stuff, you want to send something to a friend from class, you can just tell them private information (the number to add onto the data) and then they can use that later. But it’s not general enough for commercial use.
There’s another ancient type of encryption, a message would be written down when the paper (or whatever) was wrapped around a baton, then when it was unrolled, it didn’t spell anything meaningful, the letters had been rearranged, and the only way (supposedly) to read it was to have a baton of exactly the same radius. Basically the idea is to move around the letters, so “ANNIE” might go to “NEANI”. Of course some formula must be used to do this transposition, so that there’s a known way to turn it back into the original data. There’s a lot of possible formulas to do this, the specifics of which aren’t very important, the idea is simply moving around the data (letters just being an example of such data). Of course this has both the same benefits and problems with the previous crypto-formal.
A third algorithm (the last simple one we’ll go over) is specific to computers, bitwise encryption. As we all probably know computers store things in binary, 10110100 would be a good example of a byte. The first kind most people try to do is called “compliment”, basically switch all the ones to zeros, and zeros to ones. The binary number a few sentences ago would become “01001011”. This is fine as far as it goes, except that it’s the easiest encryption to break, there’s no hiding, simply taking the compliment of the new number will result in the original, so there’s really no significant security, no information is missing for anyone to decrypt it.
A better form of bitwise encryption is something called “XOR”, or “Exclusive OR”. The way this works is to take two binary numbers, say 1101 and 0110, then compare each digit to the corresponding one in the other number, if only one of them is a ‘1’ then the result for that digit is a ‘1’, otherwise it’s a ‘0’. So the “XOR” of those two numbers is 1011. The good thing about this method is that it creates a much more random looking data, so the method is better hidden, and it requires some other information to decrypt it.
Those are three of the most basic forms of encryptions, and I’ve written a little program (a while ago, I didn’t do it for this, I’m pathetic but not that pathetic ) that makes use of all of these. Feel free to check it out.
Of course professionally done ciphers are not based on any of these, these are too easy to crack, and have too many draw backs. So let’s describe the ideal cipher, and see how it was realized.
The ideal cipher can not be reversed (decrypted) by anyone who is not supposed to be able to, and anyone can encrypt a message. This seems impossible, it means creating an equation that is “one-way solvable”. Say 2*x = y, then 3 will be encrypted as 6, 5 as 10 and so on. The problem is that of course the only way to encrypt this way is to know the equation, and thus, know how to turn the encrypted data back to the original, anyone can figure out 10 is in fact 5. So what is desired is an equation that you can solve one side of it, but not the other side. Impossible? Well it wasn’t until 1970 that someone found it (side note: one man claims he discovered this equation earlier, but was working for the government and wasn’t allowed to reveal it). It’s called “The RSA Algorithm”, RSA being the initials of the three men who discovered it.
I can actually prove the results I’ll show you here, but it would take a lot of equations and explaining, and I can’t begin to prove some of the theorems that we would need, so instead I’ll just explain the equations. It ties back to the “modular arithmetic” we talked about earlier.
C = M^(e) mod (n)
Where ‘C’ is the cipher data (the encrypted value) and ‘M’ is the original data. ‘n’ is the product of p and q (product being p*q), where p and q are both prime numbers. I’ll just say what ‘e’ is, it’s a number that’s relatively prime with a number ‘fi’, where ‘fi’ is (p-1)*(q-1), if you have no clue what I’m talking about, don’t worry.
‘p’ and ‘q’ being prime is the absolute key to this, it means that n has a prime factorization that is p and q, if you don’t know what this means, the important part is that factoring primes is very, very, very difficult. Typically p and q are about 100 or more digits long, meaning n is about 200 digits long. Knowing only ‘n’, finding the prime factors p and q is almost impossible given our current computing power. Why is this important? Well you can find ‘C’ given ‘M’ only knowing ‘e’ and ‘n’, not p or q. Now, the decryption equation:
C^(d)=M mod (n)
Where d is based on that number fi we discussed (d*e = 1 mod (fi), for those who care). What this means is that to turn M into C only requires knowing only ‘e’ and ‘n’, but to decrypt one must know ‘p’ and ‘q’, which are basically impossible to find even knowing ‘n’. This RSA cipher is the base for everything you do securely online, from e-mail to e-banking. In fact, you can reverse this encryption in such a way as to prove who you are (this is how “certificates” work).
The one problem with this method is that if an easy way of factoring a number is ever found, it will become useless, but so far no method is known. That doesn’t mean people have stopped looking for new ways of keeping data secure. Perhaps the most exciting idea is using quantum spin and filters.
An atom has a certain “spin” associated with it, I’m not even going to try and explain what this is, seeing as this isn’t a physics article, but basically you can filter based on this spin. Say there’s four different ways to spin (up, down, left, right), if you put up a filter that only let in atoms that had an ‘up’ spin, then you would know that if an atom had an up spin or not, same for any of the three other filters.
Now let’s say some user wants to send an encrypted message to someone else, let’s call them A and B (A sending, B receiving). Before the message is sent, person A sends off a few thousand atoms which have a spin that only A knows. B puts up filters at random for each of the atoms separately (probably photons actually, but I really don’t want to get into it ). Whenever one of the atoms gets through the filter, then person B knows what those atom’s spin were. B then tells A which atoms it figured out, they can then use these spins to send the message. The reason this works is that no one else can figure out what those spins are unless they know the filters B uses, and so long B keeps they’re filters random, no one can. And even then, when someone tries to intercept the message, they, by definition, change it, so there’s no way to intercept the message without the two people A and B, knowing that someone’s listening in! This has actually been done, and is perfectly feasible theoretically, but the infrastructure to send and receive these messages, while it exists, is not available outside of a laboratory, where as the current internet infrastructure provides an incredibly easy way of sending traditional computer information (binary).
Well there you have it, some basics on cryptography, now you have some idea about what’s going on when you transfer money, read an e-mail, or verify someone’s identity, as well as an idea where we’re going in this field in the future.
posted
I posted the code to the program here, but it was long and had the potential to screw up the page format, so now it's gone. Unfortunatly my website is down so I can't host it myslef.
posted
Good essay, Hobbes. I can never explain math half as clearly as you.
I hadn't heard of using quantum spin for cryptography before, very interesting.
As far as breaking RSA encryption, my money is on a hardware breakthrough, perhaps via quantum computing, rather than any drastically more effective algorithm, but that's just speculative.
As a follow up, could you please define steganography for your eager fans. It was used in two recent novels I read, Quicksilver by Neal Stephenson and Pattern Recognition by William Gibson.
Posts: 6316 | Registered: Jun 2003
| IP: Logged |
quote: my money is on a hardware breakthrough, perhaps via quantum computing, rather than any drastically more effective algorithm
Completely agree, espeicially if we get light-frequency processors half as soon as some of the people who are working on them claim (20 years would be half as fast btw ).
Though someone at my university (Purdue) claims to have solved the Reiman Sum Hypothesis, which would lead to easier prime factoring, no one is convinced he has (he solved another really big one years ago, he's pretty well respected, but still ... ) and even if he has, it doesn't make it insentaneous or easy to implment so I'd still put my money on the hardware. Hardware in computing is advancing exponentialy faster than software improvments.
quote:As a follow up, could you please define steganography for your eager fans
Never heard of it before, so I'm doing some research, this looks great, thanks!
posted
My first exposure to cryptography was "The Case of the Dancing Men" when I was a boy. Since the code was broken because of the frequencies of letters in the messages, I came up with an alternative. Each letter was randomly assigned a number of cypher equivalents based on the number of times it appeared in a thousand letters of "normal" English. Then, each time a letter was used, one of the corresponding cypher equivalents was randomly chosen.
Over large samples, the frequency of each cypher equivalent would approach 1 per thousand. I actually started writing it out in a notebook but got bored.
The big weakness is that numbers would appear in combinations in non-random patterns, although a LOT of coded text would be needed to figure that out. But hey, I was 11.
posted
The only way in which hardware would lead to sufficiently fast prime factorization is if it were a quantum computer. Incremental speed increases in current technology, even to many orders of magnitude faster than we possess today, might reduce the processing time for computing a particular prime factorization at the number of bits we currently worked at to a few years, hardly a practical number in almost all instances.
Quantum computing, however, factors primes much, much easier (mmmm, partial states).
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
Steganography, it’s like cryptography only different. Basically, cryptography is masking a message, making it impossible to tell what the message actually means, steganography is hiding a message, making it so that no one even knows information was sent. If you’ve read Shadow of the Hegemon then you’ve seen an example of steganography in Petra’s communication. But instead of wading into spoilers for that book, I’ll give another example, very common in detective literature.
So, today, enough garish and nostalgic oratories grated repeated against plush houses in Concord.
This is a terrible example, since it’s not really a very meaningful sentence, no one would believe that’s what it was intended to be, but imagine if it made more sense if I put more effort into it. It’s a sentence, it has some pre-assigned meeting, in this case apparently there were some annoying speeches given in Concord. However, the real message isn’t about talking, it’s found somewhere else in the message. Take the first letter of every word in the sentence, you’ll get “steganographic”.
It’s a way of hiding a message, disguising it as some totally benign message that no one would take any interest in. In reality, the message is stored in some way of reading it that a person normally wouldn’t think of. That’s steganography in a nutshell.
How is it applied today? Well many people use it just as it has always been, simple methods, like the one illustrated above, handwritten notes, drawing that mean something besides what they look like to the casual observer. But of course, like everything else, steganography has been improved on and utilized by computers. The main way of doing this is in complex files, particularly, image files, where small deviations won’t be noticed (as opposed to a text document, where it would be picked up on if ‘a’ changed to ‘c’ or something of the kind). Let’s look at how this is done.
As I’m sure we’re all aware of, computers store information in “bytes” or “words”, a word being a certain number of bytes, today that’s normally 4 bytes. These are comprised of “bits” that are either ‘0’ or ‘1’.
Now an image stored in the computer is typically (no one much uses vector images these days) stored as “pixels”, or as a certain color for every little dot on the screen. An all red picture would have a series of pixels stored in bytes on the computer, each one containing the computer code for red.
Now the way the computer code works is as a continuum, so that the color code for red would be closely related to the color code for slightly white red, as you would imagine. Why is this important? Because by changing the number around a little, the color, and thus the whole image, only gets changed a very little.
Any pixel will have “significant bits” and insignificant bits. The significant bits are like the digit ‘3’ in the number 31254, change that to ‘4’ and the number just got 10,000 bigger. However, change the digit ‘4’ to ‘5’ and the number’s only bigger by one. This is how steganography works in images, it’ll change the least-significant, insignificant bits and leave the more important ones alone. So a message can be hidden in these bits, like a whole other image hidden inside one main image, by only using the last couple of bits or so to store the other image.
This is a very common practice, and there are many computer programs out there that can do this for you. One of the benefits of using images is that they tend to have a pretty random assortment of least-significant bytes, so that even if the aberration to the original image is noticed, picking out that it’s systematic is almost impossible unless you already know that it is.
This is the type of thing that the NSA looks for in terrorist web sites, hidden messages, secreted away somewhere in the vast complexities of the data stored there. It doesn’t have to be in images, it can be in sound files, movies, anything really. Or it can be just plain disguised lettering.
Printer-friendly view of this topic
![[Smile]](smile.gif)
).![[Wink]](wink.gif)
) that makes use of all of these. Feel free to check it out. 
![[Dont Know]](graemlins/dontknow.gif)
![[Cool]](cool.gif)
