Encryption
jhalper | March 13, 2013Prof. 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…
jhalper | December 14, 2011Is 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…
goodmath | January 8, 2009 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…
goodmath | December 1, 2008Technorati 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…
goodmath | November 20, 2008 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…
goodmath | October 24, 2008 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…
goodmath | October 2, 2008 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…
goodmath | September 15, 2008 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…
goodmath | September 15, 2008 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…
goodmath | September 8, 2008 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…
goodmath | September 4, 2008 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…
goodmath | August 24, 2008 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-…
goodmath | August 15, 2008 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…
goodmath | August 11, 2008 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.…
goodmath | August 8, 2008 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…
goodmath | August 7, 2008 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…