Something to try over the weekend: cryptography by hand

For about three and a half hours tonight, I awaited essays from next month’s tutorial students in the MCR. Having exhausted what scaps of newspaper were available, I fell back to reading a copy of Dan Brown’s Da Vinci Code, abandoned by some departed grad student.

Two hundred and sixty pages in, and unlikely to proceed enormously further, I note somewhat pedantically that there have been no codes presented. At best, there have been a series of riddles. The book would be interesting for its historical asides, if I could consider them credible.

Rather than go on about that, I thought I would write an incredibly brief primer on how to actually encrypt a message:

Crypto by hand

In the next few paragraphs, I will show you how to use a simple cryptographic device called a transposition cipher. If you really want to learn it, follow along with a pen and paper. As ciphers go, it is very weak – but it is easy to understand and learn. For starters, we need a secret message. The following is hardly secret, but it will do for a demonstration:

“DAN BROWN IS A DUBIOUS HISTORIAN”

Next, we need an encryption key. For this type of cipher, we need two or more English words that do not use any letter more than once. It is quicker if they have the same number of letters, but I will use two with different numbers of letters to demonstrate the process:

“DUBLIN PINT”

Write the first word of the key onto a piece of paper, with a bit of space between each letter and plenty of space below:

“D U B L I N”

Now, add numbers above the letters, corresponding to their order in the alphabet:

“2 6 1 4 3 5
D U B L I N”

Now, add your message (hereafter called the plaintext) in a block under. If necessary, fill out the box with garble or the alphabet in order:

“2 6 1 4 3 5
D U B L I N
D A N B R O
W N I S A D
U B I O U S
H I S T O R
I A N A B C”

Note how each word of the first keyword now has a column of text underneath it. Starting with the first column in the alphabetical ordering (B, in this case) copy out the column, starting at the top, as a string of text. Make sure you understand what is happening here before you go on. The first column, read downwards is:

NIISN

Now, add to that string the other columns, read from top to bottom, in alphabetical order. You can leave spaces to make it easier to check:

NIISN DWUHI RAUOB BSOTA ODSRC ANBIA

Clearly, each column section should have the same number of letters in it. Make sure you’ve got the transcription right before going on. Note that the string above is the same letters as are in the original message, just jumbled. As such, this system isn’t smart to use for very short messages. People will realize fairly quickly that “MKLLINAIL” could mean “KILL MILAN.”

Moving right along…

Take the strong you generated a moment ago, and put it into a block just like the one you made with the first keyword, except with the second keyword. This time, if you need letters to fill out the rectangle, make sure to use the alphabet in order. You will need to remove the excess letters when working backwards to decrypt, so you may as well make it easier.

“3 1 2 4
P I N T
N I I S
N D W U
H I R A
U O B B
S O T A
O D S R
C A N B
I A A B”

Now we have the message even more jumbled. The final encryption step is simply to copy each column in that grid out, from top to bottom, in alphabetical order according to the second keyword:

IDIOODAA IWRBTSNA NNHUSOCI SUABARBB

Note: the shorter the key, the longer each column will be. The above string is your encrypted text (called cyphertext). This final version is a jumble of the letters in the original message. Remove the spaces to make it harder to work out how long the last keyword is. If you like, you can use that put that string through a grid with another word. Each time you do that, you make the message somewhat harder to crack, though it obviously takes longer to either encode or decode.

To pass on the message, you need to give someone both the cyphertext and the key. This should be done by separate means, because anyone who has both can work out what kind of cipher you used and break your code. The mechanisms of key exchange and key security are critical parts of designing cryptographic systems – the weakest components of which are rarely the algorithms used to encrypt and decrypt.

To decode it, just make grids based on your keywords and fill them in by reversing the transcription process described above. I am not going to go through it step by step, because it is exactly the same, only backwards.

If anyone finds out about the credibility of Mr. Brown’s historical credentials, it won’t be my fault.

One word of warning: this system will not keep your secrets secure from the CIA, Mossad, or even Audrey Tautou. This cipher is more about teaching the basics of cryptography. If you want something enormously more durable that can still be done by hand, have a look at the Vignere Cipher.

PS. It is rumored that this very blog may contain a tool that automates one form of Vignere encryption and decryption. Not that it is linked in the sidebar or anything…

[Update: 27 July] Those who think they have learned the above ciper can try decrypting the following message:

BNTAFREEHOOI-LTOSIRISOTWD-FTNWAOEYSOXT-ERASEAAAKGVE

The segment breaks should make it a bit easier. The key is:

SCOTLAND HIKE

Good luck, and please don’t post the plaintext as a comment. Let others who want to figure it out do so.

Off to Scotland – goodbye until Monday

Train tracks south of Oxford

One advantage of not having all of your gear with you (particularly large backpacks) is that it forces a certain parsimony in packing. Given that we are only going for four days and that we will be spending a lot time crushed in a minibus, that is probably for the better. As such, I am reduced to standard hiking gear, wet weather gear, cold weather gear, and basic camping equipment. One important thing coming along with my is my Dublin book, so that I can plan where I want to go for my excursion beyond the city and generally plot out what I want to see. Suggestions are still very welcome.

My brothers are parents are making their annual trek to Oregon this coming week. It is something my family has been doing for more than a decade now: always going to the Lagoon Campground near Florence, Oregon by driving down the gorgeous Oregon coastline. I’ve gone at least six times: twice with my friend Jonathan, twice with Kate, and several times with just my family. Once, we went as far south as the Redwood Forest in California, but Florence is generally our terminus. Several times, the drive back has included Mount Saint Helens, and it always manages to encompass the Tillamook Cheese Factory. I hope they have a safe drive and enjoy themselves.

A full account of the hiking trip in Scotland, along with photos, will appear here upon my return.

South Hinksey

Bridge near South Hinksey

Happy Birthday Bilyana

While walking with Kelly this evening, we found an unusually nice bit of Oxfordshire, accessible through a park near their new flat. If you carry on down St. Aldates and across the Folly Bridge, then farther on down Abingdon Road, you will eventually see a park on the right. There is a small waterpark and a pool. Beyond that is a reasonably large lake, which can be crossed using the bridge in the photo above. Farther on are a set of train tracks likewise crossed by that bridge and then fields and the village of South Hinksey. It is all very attractive and photogenic, and I am glad to have discovered it in such good company.

Tomorrow, I need to tie up final loose ends before the Scotland trip. Now that it has become clear that we will be driving more than thirteen hours each way, I am a bit daunted by this four day excursion. Hopefully, the drive will be pleasant and the two days of hiking will be spectacular. My fingers are crossed incredibly tightly that I will get both papers from my August tutorial students in time to print them before leaving. If not, I will have a very hectic period of work to be completed immediately upon my return.

If I am to get my paper into the next issue of MITIR, I need to have it submitted by the 31st. Since I will be in Scotland after the 27th, that means finishing it tomorrow. They haven’t been entirely clear on whether they just want a few stylistic changes and a few specific statistics, or if they are serious about the 4000 word maximum. If so, I need to boil away more than a third of the existing paper. Hardly something I can do in the day that remains to me. All that can be done is for me to revise the paper as well as can be managed, send it off before I leave, and then return home to find out what they have decided. It seems increasingly likely that I will also return home to finally find my new headphones.

Warped wheel

I have discovered why the rear wheel of my bike keeps going out of alignment and rubbing against the frame: the wheel itself is somewhat bent. No matter how I line it up, there is a warp that causes it to rub against the brake pad once or twice per revolution. Over time, I guess it drifts more and more, to the point where the side of the tire is rubbing against the back portion of the frame.

When I get back from Scotland, I will have to go to Beeline Cycles and learn how much it will cost to have repaired. Until then, I will ride with a spanner so that I can reset things when they go too badly out of whack for me to easily maintain forward momentum.

[Update: 5 August 2006] I brought the bike in to Beeline Cycles, where I bought it back in March, and they fixed it for free under the warranty. Yet another case in which they have exceeded my expectations for good customer service.

500 miles by minibus

Google Maps predicts that the drive from Oxford to Shiel Bridge, near the Isle of Skye, will take almost thirteen hours. That seems an excessively long time to traverse less than 550 miles, but they may know things about the character of the roads that I do not. We leave at 8:15am on Thursday.

The weather is predicted to range between highs around 22 degrees Celsius and lows of about 12. Cloudy days are predicted, which is welcome. I much prefer to climb mountains under an overcast sky than under the glare of the sun. I have a spray bottle of 50% DEET to repel midges.

Since the whole trip is only four days, and I don’t need to carry a tent, stove, or sleeping bag, I will just be taking a day pack. Naturally, I will include items necessary if real rain or real cold emerge – Gore-Tex and wool respectively. On the photographic side, I am bringing both my A510 and my EOS Elan 7N (with 28-105mm zoom). On the latter, I will be shooting the roll of Velvia that Tristan sent me. As with so much other gear left behind in Vancouver, I wish I had my 50mm prime lens and my Manfrotto tripod with me for the trip.

While it’s a bit of a shame that we won’t get much chance to see any Scottish cities or towns, it is really the mountains that are drawing me up there. Nice as the countryside around Oxford can be, it has no wildness to it. It’s all marked off and manicured. I expect Scotland to be more vital.

The moral choices in assigning rights

Tree at St. Hugh's College

The best piece of writing I have come across in the last week or so is a chapter from the Bromley and Paavola book on environmental economics that I have been reading. By A. Allan Schmid, it is called “All Environmental Policy Instruments Require a Moral Choice as to Whose Interests Count.” The argument is that the idea of solving environmental problems in a purely technical way (internalizing externalities, to borrow from the economics lingo) is impossible. When a policy is represented that way, there is always a moral choice being concealed. In tort law, this becomes explicit through an instrument called nuisance.

If my neighbours are making homemade beer and the process produces a constant cloud of nasty smelling gas that wafts into my yard and through my windows, I could seek remedy in court. It would then be decided whether or not the smell constitutes nuisance. If not, the court effectively grants a right to produce the smell to my neighbours. I would then be free to try to convince them to use that right differently, for instance by paying them not to make beer.

If the court rules in my favour one of two things can take place. They can grant an injunction, forbidding my neighbours to make beer without my permission. This is great for me, since I can effectively sell them the right to make beer if the amount they are willing to pay exceeds the amount the smell bothers me. This is what Coase is alluding to in his argument that it doesn’t matter who you assign rights to, as long as bargaining can occur (See: Coase Theorem). Of course, he ignores the distributional consequences of assigning the rights one way or another. As an alternative to an injunction, the court can fix a set amount of damages to be paid. This relieves the nuisance, but gives me less scope to take advantage of the court’s decision.

What the example illustrates is that in creating policies to deal with externalities, the rights in question must be effectively assigned to one party or another. We either assign companies the right to pollute, which people around them can negotiate for them not to do, or we assign those people the right not to live in a polluted place, in which case the company has to go to them with an offer. The assigning of rights, then, isn’t a mere technical instrument for achieving an environmental end, but a matter of distributive justice.

Consider the case of fisheries access agreements in West Africa. West African governments have the sovereign right to exploit the waters in their Exclusive Economic Zones (EEZs). They can also choose to sell that right, as many have done, to the EU. The governments end up getting about 10% of the value of the fish that are caught, while suffering the loss of future revenue that is associated with the depletion of the fisheries (since they are exploited at an unsustainable level). In this case, the distributional consequences of West African governments being rights holders are fairly adverse. The incentives generated inflict harm on the life prospects of those whose protein intake previously came from fish caught by artisinal fisheries now rendered less productive due to EU industrial fishing. Likewise, the life prospects of future generations of citizens are harmed.

One of the best bits of the Schmid piece is the following:

A popular phrase contrasts “command and control” with voluntary choice. Another contrasts “coercive” regulations with “free” markets. This is mischievous, if not devious. At least, it is certainly selective perception. First of all, the market is not a single unique thing. There are as many markets as there are starting place ownership structures. I personally love markets, but of course I always want to be a seller of opportunities and not a buyer. Equally mischievous is the idea that externalities are a special case where markets fail. Indeed, externalities are the ubiquitous stuff of scarcity and interdependence.

He puts to paid the idea that there is a tradeoff between economic efficiency and moral principles. That is simple enough when you realize there is an infinite set of economically efficient outcomes, given different possible preferences and starting distributions.

Those wanting to read the entire piece should see: Schmid, A. Allen. “All Environmental Policy Instruments Require a Moral Choice as to Whose Interests Count.” in Bromley, Daniel and Jouni Paavola (eds). Economics, Ethics, and Environmental Policy: Contested Choices. Oxford : Blackwell Publishing. 2002. pp. 133-147.

Strange and annoying WordPress bug

I am abandoning the What You See is What You Get (WYSIWYG) editor that is built into WordPress (they call it the ‘visual rich editor’). It has the extremely nasty habit of randomly inserting literally hundreds of [em] tags and [/em] tags into pages with complex formatting, such as my academic C.V. Usually, it closes every tag that it randomly opens, so the formatting isn’t visibly affected. As soon as you try to change some small thing, however, everything goes insane. Going back through and fixing all of these mangled pages is a big pain.

WordPress also has serious trouble dealing with [p] tags and line breaks.

I hope the cause behind this was identified in the recent bug hunt and will not trouble people after the next major release.

Essential free Mac software

After a year of using a Mac primarily, I have come to appreciate this excellent operating system. I have also come to understand some of the gaps in it, particularly insofar as the software and tools that it includes are concerned. The following, then, is my short list of essential (free) Mac programs. Naturally, they are geared towards the kinds of things I personally do all the time.

1) Adium – instant messaging program

The MSN Messenger client for Mac is quite terrible. It is unstable and badly out of date. The freeware program Adium talks not only to MSN, but to AIM, ICQ, Google Talk, and many other instant messenger services. You see one contact list for people on all the services you’ve listed and the software works well and in a stable fashion.

Make sure to get the Hobbes icons. The one of him dancing, to indicate the presence of a new message, is especially endearing.

One word of warning, all the different preferences can be a bit daunting when you start out. Leave them on the defaults and don’t worry about them.

2) Fetch – FTP client

An FTP program essential to anyone who runs websites. This one is much less temperamental than Cyberduck, which I used for many months before being introduced to this superior alternative. You can apply for a free educational license on the Fetch homepage.

3) Firefox – web browser

Hands down the best web browser for any platform, the Mac version of Firefox is an essential item. I hang on to Safari because it sometimes runs complex Java more reliably than Firefox does (I am thinking specifically of the photo upload script for Facebook). I hang onto Opera because the built in bittorrent support is very useful. With those caveats, Firefox is what I use 99% of the time. At a later point, I should write a list like this of the essential Firefox extensions (SessionSaver, AdBlock with Filerterset.G, and Flashblock come to mind instantly).

4) Google Earth – interactive atlas

Not essential, perhaps, but free and definitely great fun. The built in demonstration tour is worth a look. It shows off the terrain mapping nicely with Mount Saint Helens.

5) jEdit – text editor

Even with MS Office installed, there is no program in Mac OS that can cleanly edit files that must be text only, without formatting. I am talking about things like manually editing HTML files, PHP scripts, htaccess files, and the like.

6) KisMAC – wireless network detector

Particularly if you are running Tiger (OS 10.4), this free utility is helpful for dealing with wireless networks in more sophisticated ways than are possible using the WiFi implementation built into the OS.

7) MacJanitor – maintenance program

If you have a laptop that you leave closed or in sleep mode when you are not using it, chances are some of the timed maintenance scripts that are meant to run under Mac OS are never doing so. By default, they run in the early morning, but that will only happen if your computer is on. This program lets you run them manually, a good idea for maintaining system performance.

8) Password Safe – password utility

The Java version runs under Mac OS and is very helpful for keeping track of the passwords of things you use quite rarely. It is better than Keychain because you can install the Java version on a USB key and then use it on Macs, PCs, and Linux machines.

9) Remote Desktop Connection – system tool

I have no idea why this is not included by default in the operating system. Either this or one of the open source equivalents is necessary to connect to Windows based terminal servers.

10) Skype – VOIP program

Particularly if you have a Mac laptop with a built-in mic, Skype is an exceptionally convenient way to keep in touch with people inexpensively. I really wish more of my friends used it.

11) VideoLAN – media player

This open source video player can deal with the widest range of file types of anything I have used on the Mac. DivX files that simply will not play in Quicktime or Windows Media Player open without trouble, and it has fullscreen mode – a feature that is bizarrely lacking in other Mac video software.

One item that I won’t put on the official list is a third party MD5 hash checker. Only people who need to check the integrity of downloaded files will need one and it doesn’t really matter which one you choose. Just don’t trust the one built into Disk Utility (at least not for .iso files).

PS. The essential non-free software is basically MS Office (OpenOffice does not cut it when you need to collaborate with people using Office) and Photoshop 7, CS, or CS2.

Ten weeks of summer remain

Bridge over the Oxford canal

Happy Birthday Kelly Kilpatrick

About ten weeks now remain before the start of Michaelmas 2006. Of the major things I wanted to do over the summer – namely, travel, earn some money, and work on the thesis – I have done at least a bit of each. Hopefully, all three will be boosted in August as I instruct two more students, complete more additional batches of work for Dr. Hurrell, and travel to Ireland.

One thing I need to develop is a filing system for thesis related materials. Books are easy enough to deal with, whether they are mine or borrowed from the library. What I really need an organizational system for are my own notes on readings (which I have generally put into a succession of notebooks, ordered chronologically) and printed or photocopied articles. For the fish paper, I just put that stuff into one big binder, but I doubt that will be adequate for a 30,000 word project.

Speaking of the fish paper, I really must get back to editing it. It is now anybody’s guess whether I will be able to complete the desired revisions before leaving for Scotland, and thus whether it will appear in the next issue of the MIT International Review or the one subsequent.

PS. Still no Etymotics. With bated breath, I wait.