Monthly Archives: October 2008

Differential Cryptanalysis

Leave a reply

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:

  1. It’s easy to compute the ciphertext given the plaintext and the key;
  2. It’s easy to compute the plaintext given the ciphertext and the key;
  3. It’s hard to compute the plaintext given the ciphertext
    but not the key;
  4. 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 discover the key. What makes that
statement of the property so weasely is that it omits the information available to the person trying to crack it. In the first three properties, I clearly stated what information you had available to produce a result. In the last, I didn’t.

There’s a reason that I weaseled that. Partly, it’s because a correct statement of it would be ridiculously long and incomprehensible; and partly because it’s often deliberately set up differently for different encryption systems. You can design systems that are extremely strong against certain attacks, but not so good against others. There’s no universally ideal encryption system: it’s always a matter of tradeoffs, where you can handle some scenarios better than others.

Today we’re going to look at one particularly fascinating attack that’s used against block ciphers. It’s called differential cryptanalysis.

Continue reading →

ScienceBlogs DonorsChoose Drive 2008

Leave a reply

Every year at ScienceBlogs, we do a charity drive for
DonorsChoose.org. If you haven’t heard of them, DonorsChoose is a charity that takes proposals from schoolteachers, and lets people pick specific proposals to donate money to. We run our charity challenge through the month of October.

For personal reasons, I couldn’t participate last year. The year before that, Good Math/Bad Math readers donated just over two thousand dollars to support math education in impoverished New York area schools.

This year, I’m still focusing on the NYC area, because with where I live and work, I get to directly see how these schools and students are treated, and how desperately they need help. I’ve selected a number of projects that fit into two main categories:

  1. Basic Supplies: These are proposals to buy very
    basic classroom essentials, like pencils and paper. It’s
    pathetic that teachers need to come to a charity asking for this
    kind of stuff. But the unfortunate fact is, there are schools in
    NYC where the school can’t even provide paper and pencils for their
    students. How can you possibly expect a student to learn math, when
    they don’t even have blank paper to work problems on? I guess we all too busy trying to figure out
    cool toys for two year old boys to care about the future.
  2. Math Manipulatives: manipulatives are much more
    interesting. They’re things like shaped pattern blocks blocks,
    which can be used to provide a direct, tactile tool for
    understanding math. I live in an excellent school district, and my
    children’s classrooms have enormous supplies of manipulatives of
    several different kinds. I’ve seen very directly how these simple
    things make basic mathematical concepts concrete and understandable
    for elementary school children. Manipulatives can be used to help
    develop the intuitions behind shapes, numbers, addition,
    multiplication, patterns, areas, fractions, angles, and basic
    geometry. They’re an amazing tool for elementary education, and I
    think every school should have boxes of manipulatives in every
    elementary classroom. They’re not terribly expensive, and they’re
    wonderful.

To me, there’s a bit of a personal element to this stuff. The work that I’m most proud of in my life is several summers that I spent working for something called the New Jersey Discovery program. Discovery took children from some of the worst schools in the state of New Jersey, and set out to help them. The kids spent their weekends all year in tutoring. Then during the summer, they came to Rutgers, and spend the summer at the university. Three days a week, they took classes; the other two days, they worked for the university. If the kids did this for the two full years, then they got scholarships to get their bachelors degree at Rutgers.

I got to teach the Discovery kids computers and math. They were great kids: smart, hard-working, and motivated. I got to hear from them what their schools were like: places where they didn’t have basic essentials. In 1990, they were using math textbooks from 1960 – books that were falling apart, with missing pages. And that was one of the better equipped classes. They had english classes where they had no books at all. They didn’t have paper. They had classrooms where the blackboard were cracked and broken, and couldn’t be written on.

Before that experience, I had no idea that poor schools
were anything remotely close to that bad. It astonished me, and
opened my eyes. It’s easy to not realize, to not notice
how bad things can be for people who are less fortunate that you.

It’s a bad time in the economy, so I understand that a lot of us have a lot less money available to donate to things like this. But at the same time, it’s important to realize that inner city
impoverished school systems will generally be hurt much worse by economic troubles than the schools of those of us are better off.

So please: go to Donors Choose, and find some good proposals, and help
fund them!

Of course, I’ll throw in some goodies. If you throw in over $100, you can pick a topic for me to write an article about. I’ll probably also set up something at Cafepress to make some Good Math/Bad Math goodies for donors. Don’t wait though – I’ll still send you the goodies even if you donate before I decide what they are.