Rosio Pavoris a blog

In which I am bored and write a ridiculously thorough, line-by-line review of a worthless piece of fluff.
Didn’t actually take that long.

As you may remember, my grandfather died a few months ago, and one of the many, many things we inherited was a vast collection of pictures spanning well over a century (the oldest ones are 130 years old). I promised I’d scan some of them and post them, but that never happened, mostly because my uncles made off with them.
They’re back now, though, and I’ve scanned a few of the ones that weren’t glued down. That doesn’t, unfortunately, include the very oldest ones, but it still goes back quite a way.

Click pictures for bigger, though some bigger ones are missing because I fucked up while resizing. I’ll fix it later tomorrow eventually.
I’ve resized and cropped, but made no effort to fix the colors. This is the state these pictures are in.

One of the older ones to start off. Presumably these people are related to me.
I think the guy with the beard on the left is Baron de Buisseret, my grandmother’s grandfather. I’m not sure what his first name is, but he had a bunch of kids, including a daughter named Marie-Louise, who married some guy named Stouffs and gave birth to my grandmother. So unfortunately, no noble title for me.¹

Read the rest of this entry »

Specifically, a small classical cryptography library.
None of these things are very hard to implement (in fact, two of the hardest bits I haven’t even implemented myself), but it’s good practice for me and some people might hypothetically have a use for it.
I’ve taken a stab at documenting it, but I don’t know how Python documentation works, so forgive me if it’s useless.

Included functions are:

• atbash: The Atbash cipher. Optionally allows you to pass your own alphabet.
• bifid: Delastelle’s bifid cipher.
• caesar: The Caesar cipher. Optionally allows you to pass your own alphabet, preserves case and letters not in the alphabet.
• foursquare: The four-square cipher.
• hill: The Hill cipher, sans decryption function, because I honestly couldn’t figure out how to invert a matrix in a way that preserves integers (protip: it’s not the usual way; I wrote a Gauss-Jordan reduction function before realising that couldn’t work for most key matrices). If you know how to invert it yourself, you can do that and pass it as the key along with the ciphertext, and it’ll decrypt normally. Alternatively, you could tell me how to do it and I’ll fix it.
• keyword: The keyword cipher. Optionally allows you to pass your own alphabet, preserves case and letters not in the alphabet.
• playfair: The Playfair cipher. Note that the decryption doesn’t have a way to tell which characters were added during encryption and which were there in the plaintext (though it should be obvious unless your plaintext has a lot of Xs and Qs).
• railfence: The rail fence cipher. Encryption only, because it gave me a headache. Never mind, I added decryption. It’s not as elegant as I’d like, but it works.
• rot13: ROT13. Special case of the Caesar cipher.
• solitaire: Bruce Schneier’s solitaire cipher.
• solitaire_prng: The key generator for same.
• vigenere: The Vigenère cipher previously discussed.
• vigenere_autokey: Vigenère’s autokey cipher, also previously discussed.

Basically, everything in Wikipedia’s “classical ciphers” for which an algorithm was described, minus a few of the more boring ones.
There’s also a Polybius class, which allows for easy construction of Polybius squares, and methods for looking up things in them. It’s just a wrapper around a square matrix and a reverse look-up of the same.

The general principle behind these functions is that they take a message (which is a string) and a key appropriate to the cipher. To decrypt, you use the same function and pass an additional boolean decrypt, set to True.
Preservation of case and punctuation characters and the like is inconsistent, so if that’s important, you’re going to have to look at the code itself. This is because I am nothing if not easily bored.

Anyway, enjoy. I may add to this over time, so if there are ciphers you would like me to implement, let me know.

Memes evolve, and even creationist memes are no exception. It used to be that they denied things like antibiotic resistance in bacteria and pesticide resistance in insects even existed, but now most of the ones that actually end up “debating” sane people seem to agree that “micro-evolution” happens, but “macro-evolution” doesn’t.
The distinction is meaningless, of course, and the argument amounts to nothing more than “I believe in small changes over a small period of time, but not large changes over a large one”. The implication that there is some invisible barrier to speciation, though, still tends to stump many of the people they’re debating, because it’s not necessarily easy to come up with an example that’s simple enough for the wilfully ignorant to understand, and examples of observed speciation in bacteria doesn’t tend to impress people who only barely believe bacteria even exist, much less that it’s meaningful to speak of different species of them.

Ring species, however, are such an example. They demonstrate a gradual process of speciation, and they manage to do it in a way that’s observable in real time.

Put simply, with ring species you have a series of populations along a line or open ring (often a coastline or a river bank, actually). Each of these populations can breed with itself (obviously) and with its slightly different neighboring populations. Perhaps some populations are classified as different subspecies of some overarching species; it’s difficult to point down where one subspecies ends and the next begins, though: the populations basically form a continuum.
The punchline, though: though each population can breed with its neighbors and produce fertile offspring (which, according to a popular definition, makes them the same species), the populations at the ends of the line cannot. They are, in effect, different species.

The canonical example is the herring gull complex around the north pole.¹

The ring starts on the shores of the northern North Atlantic with the herring gull Larus argentatus. It can interbreed freely with the American herring gull Larus smithsonianus,² which occurs, surprisingly, across North America.
The North American herring gull can interbreed with the Vega gull Larus vegae, which is a subspecies of the East Siberian gull (the only other subspecies is the Larus vegae mongolicus, which isn’t relevant to our story). That in turn can interbreed with Heuglin’s gull, Larus heuglini, which can interbreed with the Siberian lesser black-backed gull Larus fuscus heuglini, concluding our trip across northern Siberia.
The Siberian lesser black-backed gull can interbreed with the lesser black-backed gull Larus fuscus, which bring us back to Europe, mostly around the Baltic Sea, though they share some territory with the herring gull.³

These gulls form a species continuum, as you can see, but the herring gull cannot interbreed with the lesser black-backed gull.
It’s hard to tell where one species ends and the next begins, but it’s undeniable that the herring gull and the lesser black-backed gull are different species.

This is just one mechanism of speciation (allopatric speciation; these gulls inhabit much the same niches, so this is nearly entirely down to genetic drift, too), but it’s a plainly obvious one.⁴

Of course, most creationists would just reply “but they’re all still birds”, which is a level of ignorance against which little can be done.
Some of the more literate ones might point out that not only are they all birds, they’re all still in the genus Larus, moving their non-existent barrier to speciation to a barrier to “genusiation”, but that’s no more to the point than to point out that all new growth on an old tree seems to happen at the bud level, with only new twigs being born, and that no new massive boughs have been added to it in decades.

(Incidentally, there’s an interesting parallel in linguistics, with the dialect or language continuum. Flanders is a good example of it, with most of its many, many dialects being intelligible to its immediate geographic neighbors, but people on one end of the region not being able to understand a damn thing people on the other are saying. It can probably be argued that the Limburgs dialects make Dutch form a language continuum with German.)

¹ I’m aware of the Liebers/de Knijff/Helbig paper, and I slightly disagree with its conclusion that the Larus species complex does not represent a ring species. Regardless of how it was formed, it’s a ring now. There may be contexts in which it’s not useful to speak of it as a ring species, but that isn’t relevant here.
If you want to argue about this, by all means do.

² And, indeed, is almost indistinguishable from it to the untrained eye. The American herring gull is a bit bigger, though.

³ The taxonomic story is actually a bit more complex than that, obviously. For instance, the gulls in the eastern part of the range of the Heuglin’s gull are often considered a separate subspecies (Larus heuglini taimyrensis, or the Taimyr Gull), but some people believe these to just be the result of interbreeding between Heuglin’s gulls and Vega gulls; and of course most species names are in dispute: the Vega gull is sometimes classified as Larus argentatus vegae, and people seem to be confused over what the Siberian lesser black-backed gull actually is.
This is something for taxonomists to squabble over, though, and I’m not convinced it’s a productive use of anyone’s time.

⁴ If the Liebers paper makes you nervous, there are other, less controversial examples of ring species, including Ensatina salamanders around Central Valley in California, and greenish warblers around the Himalayas.

950 € for something barely bite-sized. Apparently purebreds are expensive.

But yes, we finally went out and bought a new dog. It’s a Cavalier King Charles spaniel, not a cocker, but because it’s purebred and the names of this litter have to start with H, it will still be officially registered as being called Haskell.
Though my mom intends to call him Baziel, apparently.

Born August 10th, so we won’t actually be getting him until mid-October.

Did you know Denmark annexed Germany, the Netherlands, Belgium, Luxembourg, Switzerland, most of Austria (Tyrol and Vorarlberg resisted the foreign invaders), Hungary, and Slovenia, thereby restoring much of the Holy Roman Empire to its former glory?
Because Google did:

As for Chrome itself, it looks promising (more so than most Google projects, at least), though obviously it needs a Linux version. And, I suppose, a FreeBSD version.
The source is available, and a horrific mess. A simple browser shouldn’t have two gigabytes of junk cluttering up its repository (516 DLLs and 218 Windows executables, for the record), or provide its own copy of Cygwin just to have (I’m assuming) a C compiler.

The Javascript engine seems to be holy fuck fast, though, and the fact every tab gets its own thread is neat, and the task manager is definitely handy. The “Omnibar” is a pain in the ass, of course, and they could really use a Firefox-style extension system. They certainly have the Javascript engine for it.
As soon as they release a Linux version, I’ll probably switch away from Iceweasel, though as long as there are no equivalents for TorButton and the 4chon extension, I’ll still keep it around.

(If you still don’t know what this is about, this will help.)

Edit: And even with all that junk, it still doesn’t compile. Fuck it, I’m not troubleshooting that.

The Vigenère cipher is a more interesting cipher, in that it uses an actual key, and isn’t trivial to bruteforce. Central to the Vigenère cipher (and, in fact, most classical substitution ciphers) is the tabula recta:

Suppose that you have a message to encrypt starting with “Proletarians of Europe! The war has lasted more than a year.”, and a key “secret”. To encrypt your message, you line the plaintext and the ciphertext up like this:

And then you just look up vertical pairs in the table. The first letter to encrypt is P, so you go to the row marked P. The first letter to encrypt it with is S, so you look in the column S of the row P. The resulting ciphertext letter is H. You repeat this for the rest of the letters.
The resulting ciphertext will be:

Decrypting is the reverse of this: you go to the column corresponding to the key letter, find the letter H in that column, and then look at what row that letter is in.

Implementing this in Python turns out not to be very hard.
I actually constructed the tabula recta as a lookup table, mostly to see how hard it would be, but you don’t, of course, have to do that. All you need is a way to turn letters into numbers (A = 0, B = 1, &c.) and back, and encryption is as easy as:

ciphertext_letter =
    to_letter((to_number(plaintext_letter) + to_number(key_letter)) % 26)

Decryption just changes the + to a -.
This is also how I constructed the tabula recta. The to_letter function is easily accomplished by treating a string of the letters in alphabetical order as an array, and the for the to_number function I just used a reverse dictionary lookup of the same.
The tabula recta then takes literally three lines of code:

lookup = dict([(a, 0) for a in alpha])
for a in lookup:
    lookup[a] = dict([(b, alpha[(tonum[a] + tonum[b]) % 26]) for b in alpha])

You really don’t want to know how much longer that would be in Java.
A sample session:

$ ./vigenere.py
[E]ncrypt or [D]ecrypt? E
Phrase to encrypt? Proletarians of Europe! The war has lasted more than a year.
Strip whitespace and punctuation? (Y/n) Y
Key? secret
hvqcimsvkrrlgjglvhhivyipsvjrweswvvhfgvgkltfeavek
$ ./vigenere.py
[E]ncrypt or [D]ecrypt? D
Phrase to decrypt? hvqcimsvkrrlgjglvhhivyipsvjrweswvvhfgvg kltfeavek
Key? secret
proletariansofeuropethewarhaslastedmorethanayear

The Vigenère cipher is less easy to crack than the Caesar cipher, but not much.
If you know the length of the key, the ciphertext simply turns into so many Caesar-shifted ciphertexts, which may be subjected to frequency analysis. Though of course, we’ve already seen how great that turns out if you don’t have a massive amount of text to analyse.
If you don’t know the length of the key, but do have a huge ciphertext, you can look for repeating clusters of letters, which are likely to be bits of plaintext that happen to repeat at intervals equal to some multiple of the key length. If you have a bunch of different ones, you can find the largest common factor of the intervals, and this will likely be the key length. After this you can just use frequency analysis again. This method is known as the Kasiski examination, after the Prussian Friedrich Kasiski (though Charles Babbage also came up with it).
These things aren’t that hard to implement, but also not that interesting.

It should be clear, though, that the Vigenère cipher is a pretty weak one (it certainly doesn’t deserve the name «le chiffre indéchiffrable»), which is ironic, given that Blaise de Vigenère never actually came up with it, and the one he did come up with was actually quite a bit stronger.
Vigenère’s autokey cipher uses the same basic principle of the tabula recta, but instead of a repeating key, it’s going to use a short key to start with, and then for the rest of it use the plaintext.¹ Vigenère himself suggested using a single letter of the alphabet for the key, but that’s pretty stupid. Let’s instead use a full word, like so:

Again, not that hard to implement.
Rather than repeating, the key is now just the provided key plus the ciphertext, which saves a modulo operation in the lookup.
Decryption has an extra step, because every deciphered letter has to be added to the key while the decryption is in progress, but on the whole, it’s very similar to the other “Vigenère” cipher.

Breaking it is rather harder than breaking the other one, though. Frequency analysis isn’t really going to work, though if you use a single letter for the key, like Vigenère suggested, bruteforcing is trivial, and our own example is vulnerable to a dictionary attacks. Both of those are attacks against the key, though, not the cipher.
There are some relatively straightforward attacks possible, one of which is described in the Wikipedia article, and I’m working on those now.

More to come.

¹ You’ll remember that this basic principle also returns in a slightly different form in certain block cipher modes of operation in modern cryptography. It’s also used for some types of self-synchronising stream ciphers.