Encryption

Prof. Shafi Goldwasser, who is at both the Weizmann Institute and MIT, will receive the 2012 A.M. Turing Award, together with Prof. Silvio Micali of MIT. Goldwasser is only the third woman to receive the Award since its inception in 1966, and she is the third faculty member of the Weizmann Institute to receive what is considered to be the “Nobel Prize in computing.” Goldwasser and Micali’s work in the 1980s laid the foundations of modern cryptography – the science that, among other things, keeps your electronic transactions secure. The basis of their work is a series of riffs on the…
Is it possible to perform operations on encrypted data, while keeping it secure from all prying eyes (or circuits), even if that data is stored remotely, in the "cloud?" Will our end result still be encrypted, and when we decode it with our private decryption key, will our result be correct? To put it another way, could we allow sensitive data - say private medical information - to be monitored on-line and feel completely secure in the knowledge that no one can access it without our express permission? Can we use a cloud service to store our encrypted data and perform a search on that data…
Ok, away from politics, and back to the good stuff. When I left off talking about encryption, we were href="http://scienceblogs.com/goodmath/2008/12/public_key_cryptography_using.php">looking at RSA, as an example of an asymmetric encryption system. Since it's been a while, I'll start off with a quick review of RSA. Asymmetric encryption systems like RSA are based on computations that are easy to perform if you know the keys, and incredibly hard to perform if you don't. In the specific case of RSA, everything is based on a pair of very large prime numbers. If you know those two primes…
Technorati Tags: cryptography, public-key, encryption, RSA, asymmetric encryption The most successful public key cryptosystem in use today is RSA - named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd, who was one of Ron Rivest's students. Errol is without a doubt the best teacher I've ever had (and also a thoroughly nice guy). If you want to go to grad school to study algorithms, you frankly couldn't do better than heading to Delaware to work with Errol. I have very fond memories of Errol's class where we talked…
I've been trying for a couple of weeks to put together a couple of interesting posts on the cryptographic modes of operation for confidentiality and integrity, and I just can't do it. I'm finding it boring to write about, and if it bores me to write it, I know there's no way that it's going to be engaging to readers! So, I'm going to move on. I've explained the basic idea of the message authentication code as an integrity check, and I've described one simple way of integrating it into a common mode of operation. If you're really interested in learning more, I recommend Bruce Schnier's book…
In my last cryptography post, I wrote about using message authentication codes (MACs) as a way of guaranteeing message integrity. To review briefly, most ciphers are designed to provide message confidentiality - which means that no one but the sender and the intended receiver can see the plain-text of the message. But ciphers that provide confidentiality don't necessarily make any guarantees that the message received is exactly the message that was sent. There are a good number of cryptographic attacks that work by altering the message in transit, and depending on the cipher, that can result…
Now, we're finally reaching the point where the block-cipher stuff gets really fun: block cryptanalysis. As I've explained before, the key properties of a really good encryption system are: It's easy to compute the ciphertext given the plaintext and the key; It's easy to compute the plaintext given the ciphertext and the key; It's hard to compute the plaintext given the ciphertext but not the key; It's hard to compute the key. That last property is actually a bit of a weasel. There are really a wide variety of attacks that try to crack an encryption system - meaning, basically, to…
So, as it turned out, I made a major screwup in my post earlier today on modes of operation. Rather than just edit the post, I'm adding a new post with the corrected description of the counter mode, and a bit of explanation. I figure that if I screw up badly, it's more honest to make a second post explaining the error than it is to just correct it and pretend that all was well. What I got wrong was the order in which things happen. In the counter mode, you encrypt the counter using the key, and then you exclusive-or the result of that with the plaintext to get the ciphertext. The plaintext…
Sorry for the slow pace of the blog lately. I've been sick with a horrible sinus infection for the last month, and I've also been particularly busy with work, which have left me with neither the time nor the energy to do the research necessary to put together a decent blog post. After seeing an ENT a couple of days ago, I'm on a batch of new antibiotics plus some steroids, and together, those should knock the infection out. With that out of the way: we're going to look at how to get from simple block ciphers to stream ciphers, using the oh-so-imaginatively named modes of operation! As a…
As promised, now we're going to look at the first major block cipher: the DES. DES stands for "data encryption standard"; DES was the first encryption system standardized by the US government for official use. It's an excellent example of a strong encryption system; to this day, while there are several theoretical attacks, there's no feasible attack on a single DES-encrypted message that's better than brute force. The main problem with DES is the shortness of its key: only 56 bits, which makes it downright practical to implement brute-force attacks against it using today's hardware. DES…
Where encryption starts getting really interesting, in my opinion, is block ciphers. Block ciphers are a general category of ciphers that are sort of a combination of substitution and transposition ciphers, and sort of something entirely different. They're really fascinating things, but they're pretty complicated. The basic core of block ciphers is encryption of blocks. A block is a fixed-length series of bits. The basic cipher is a pair of functions (E,E-1), where E (the encryption function) takes a block B and a key K, and generates a new block B'=E(K,B), which is the encrypted form of…
The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be rather dull; in their pure form, they're very simple, and not very difficult to crack, even without computers. But some of the most sophisticated modern ciphers can be looked at as a sort of strange combination of substitution and transposition, so it's worth looking at. A transposition cipher doesn't change the characters in the plain-text when it generates the cipher-text - it just re-arranges them. It applies some kind of permutation function to the text to produce a re-…
To understand why serious encryption algorithms are so complex, and why it's so important to be careful with the critical secrets that make an encryption system work, it's useful to understand something about how people break encryption systems. The study of this is called cryptanalysis, and it's an amazingly fascinating field of applied mathematics. I'm going to be interspersing information about cryptanalysis with my cryptography posts. One thing to remember here is that we'll be talking about it mainly in the context of how you can break an encryption system - but cryptanalysis is also…
So, last time, we looked at simple substitution ciphers. In a substitution cipher, you take each letter, and pick a replacement for it. To encrypt a message, you just substitute the replacement for each instance of each letter. As I explained, it's typically pretty each to break that encryption - the basic secret of the encryption is the substitution system, and it's pretty easy to figure that out, because the underlying information being encrypted still has a lot of structure. There are a couple of easy improvements on a simple substitution cipher, some of which came up in the comments.…
The starting point talking about encryption is to understand what the point of it is; what it's supposed to do, what problems it's supposed to avoid. Encryption is fundamentally about communication: you've got two parties who want to communicate, but don't want anyone else to be able to listen in. They way that you do that is by sharing a secret. You use that secret to somehow modify the information that you're going to send, so that it can't be read by someone who doesn't have the secret. People often think of encryption as a way of using a password to hide information, but a password is…
As you've probably heard, the US customs service has, recently, asserted the right to confiscate any and all computers and/or digital storage carried by anyone crossing the US border. They further assert the right to demand all passwords, encryption keys, etc., from the owners. They even further assert the right to keep or make copies of any data that they find, and to share it without limit with anyone they choose. I don't think I really need to stress how insane this is. Back when I worked for IBM, I frequently travelled to Canada, because I worked with development labs in Toronto and…