I was away on vacation this week, which explains the near-total silence on the blog. But at least you'll get a FRT from me. And some nice posts on cryptography…
Transposition Ciphers
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-arrangement, which can be reversed if you know the secret to the the permutation.
Friday Random 10, August 22
Solas, "Darkness, Darkness": One of my favorite Irish bands doing a great cover of an old song. A Silver Mt. Zion, "Goodbye Desolate Railyard": a decent ASMZ track, but not…
Astrology and the Olympics
An alert reader sent me link to a stupid
article published by Reuters about the Olympics and Astrology.
It’s a classic kind of crackpot silliness, which I’ve described
in numerous articles before. It’s yet another example of pareidolia – that is, seeing patterns where there aren’t any.
When we look at large quantities of data, there are bound
to be things that look like patterns. In fact, it would be
surprising if there weren’t apparent parents for us to find. That’s
just the nature of large quantities of data.
In this case, it’s an astrologer claiming to have found
astrological correlations in who wins olympic competitions:
Something fishy is happening at the Olympic Games in Beijing. Put it all down to the stars.
Forget training, dedication and determination. An athlete’s star sign could be the secret to Olympic gold.
After comparing the birthdates of every Olympic winner since the modern Games began in 1896, British statistician Kenneth Mitchell discovered gold medals really are written in the stars.
He found athletes born in certain months were more likely to thrive in particular events.
Mitchell dubbed the phenomenon “The Pisces Effect” (pisces is Latin for fish) after finding that athletes born under the sign received around 30 percent more medals than any other star sign in events like swimming and water polo.
The Food Experience Meme
I found a fun meme via Rev. BigDumbChimp, involving food. I'm a sucker for anything involving eating. Venison: Nope. Nettle tea: yes. Didn't like it. Huevos rancheros: Yes, yummy. Steak…
Why is randomness informative? Correcting the Clueless Creationists
Someone sent me some questions about information theory; or actually,
about some questions raised by a bozo creationist arguing about information
theory. But the issues raised are interesting. So while I’m
nominally snarking at a clueless creationist, I’m really using it
as an excuse to talk about one of my favorite mathematical subjects.
The creationist is confused by the information theory idea of information and complexity. That is somewhat confusing.
Intuitively, we think of information in terms of semantics and communication. We think that information is related to semantic content. And our understanding of semantic content comes from language. So we expect
things that are rich in information to be highly structured, like language.
Friday Random 10, August 15
One of the things that I always like to talk about is how a natural expression of randomness will periodically produce something that appears non-random - and in fact, if…
Introducing Cryptanalysis
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 used for
designing cryposystems, because you can only design a successful cryptosystem by
thinking about how it can defeat the ways that it could be broken.
One caveat: I’m going to be describing cryptanalysis in terms of how I understand it, which is sometimes different from classical descriptions by cryptanalysists. My
understanding is strongly rooted in computation and information theory, rather than pure math. So sometimes my presentation will be a bit different, but hopefully by staying in the ground where I’m most comfortable, I can do a better job of making it comprehensible.
Rotating Ciphers
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. For example, two
good easy improvements are:
- Instead of defining substitutions for single characters, define
substitutions for groups (pairs, triplets) of characters. This improves things,
because it allows you to work with groups that will reduce the visibility of
patterns. Still, because there’s so much structure in human language, given
enough data, an encrypted message is still likely to be easy to decode. So this
is great for short messages, but not for anything bigger. - Multiple substitutions: instead of always substituting, say, “x” for “a”,
substitute each letter with a two-digit number. Then for common letters, allow
multiple possible substitutions. By assigning many codes to common letters, and
few codes to uncommon letters, you can make the coded symbols appear with
roughly equal frequency. This can seriously hamper frequency based analyses.
Both of those changes help. They work particularly well when combined. To do
a two-character version of that, you create a list of all possible two-character
sequences. Then you generate a frequency table for how often each two-character
sequence occurs in a large sample of the kind of text you’re going to encode.
Then, finally, you assign a number of substitutions for each pair so that they
occur with approximately equal frequency. That gives you a pretty good
system.
Still, it’s not great. Given enough encoded text, it can be cracked with a
relatively small amount of computational power. If I know the basic idea of the
cipher, and I’ve got a decent amount of encoded text, I can write a program that
will figure it out pretty quickly. Plus, it’s really a lot of work to generate
the cipher – you need to generate frequency tables, and work out the number of
substitions, etc. It’s definitely not trivial to set up, and it’s still pretty
easy to crack.
For that reason, those kinds of solutions aren’t used much – there’s a lot
of prep work, and the secret that you need to share with your partner is large
and complicated. You can get better quality with less effort and a
simple secret using a different scheme called a rotating cipher.
Simple Encryption: Introduction and Substitution Ciphers
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 just one of many kinds of secrets that you can use. The secret that you share with your counterpart can be a password, a number, a textbook, or just about anything else you can imagine.
- 1
- 2