19th June 2007

Posted in

Blog :: Books and Movies

I haven't done much non-tech blogging lately. Perhaps a movie recommendation and a book (dis-)recommendation will help fill out the personal side of my blog...

For Fathers' Day we had my Dad over for supper - one brother is still in Paraguay and Mom and the other brother were attending a family reunion back East. I fixed Chinese food semi-successfully (the stir fry was good, the chow mein was lousy and it's hard to mess up home made egg rolls) and we watched a movie Dad brought over.

Deja Vu was excellent - Denzel Washington delivers a typically human performance and the central sci-fi conceit was well done and produced several interesting scenes (like a temporal car chase. You'd have to see it to understand...) Anyways, for anybody in the mood for a reasonably clean intelligent thriller with real people, Deja Vu delivers the goods.

In the book world I most recently read some Dan Brown. I finally got The Da Vinci Code just to see if it was any good.  Short story is it wasn't (Angel's and Demons was better) but I actually wanted to write about the other Dan Brown novel I picked up at the same time.

Digital Fortress is a painful book to read for anybody remotely clueful about computer science in general and encryption specifically. It's bad to the degree that's it's obvious Dan Brown not only does not understand much about computers, he didn't get anybody qualified to proof the book... I won't bother to give you the plot except to say that it involves the NSA and a potentially "unbreakable" algorithm. There are so many whopper's in the book that it's pointless to nitpick the main point - never the less: in the book the NSA has a super computer that can "brute force" any encryption algorithm. This is not only likely, it's a near certainty - many standard encryption algorithm's (say DES) use 128 bit keys - the password is 128 binary digits long and the NSA almost certainly has the computing power to try every number until it finds the correct key for messages encrypted in this fashion.

In Digital Fortress, however, a former NSA employee has invented an "unbreakable" algorithm that alarms the NSA, inspires a bidding frenzy and generally drives the plot forward. This is somewhat silly since "unbreakable encryption" already exists. "One-time pads" are a very old encryption system that is theoretically unbreakable - the idea is that the algorithm might be very simple (say a simple rotation) but the key that is used to encrypt the plaintext is as long as the text itself is and the key is never used repeatedly. This is a theoretically unbreakable system that Digital Fortress ignores.

Of course no one uses this system (except perhaps embassies or spies). The reason is that the system is clunky - in order for two people to share an encrypted message they must both have the same key source (usually a very long stream of randomly generated numbers). The Government can do this sort of thing - physically and securely ship keys to remote destinations like embassies for future use - but everybody else needs to use systems that are more convenient.

This is where public key cryptography comes in. Public key cryptography was a huge theoretical breakthrough that solved the centuries-old problem of "key exchange". If Alice and Bob (the two classic names used in discussing encryption) want to communicate but know that an eavesdropper (Eve) is listening, how can they communicate securely? By encrypting their conversation, of course. But encryption schemes require a password - if Alice and Bob haven't already securely agreed on a password how can they agree upon a password without Eve hearing it and being able to decrypt their conversations as easily as they can themselves? Well most encryption schemes are symmetric - you use a single password to encrypt and decrypt a text. (Skip the next paragraph of explanation if your eyes are already starting to roll back in your head and keep reading further down).

Consider a simple "Caesar Cipher" (so called because allegedly invented by Julius Caesar; encryption is not a new problem). It uses simple letter rotation where Alice and Bob pick a number as a password and then use it to rotate every letter in the text. If the password is "2" then the plaintext letter A goes up two places to the become the encrypted letter C. Alice's name encrypts to "CNKEG". And if you know the algorithm and the password you can decode as well: C goes down two places to become A, N goes down two places to become L, etc. A Caesar cipher can be made more complicated with a longer key: consider the key "4,11" which would rotate the first letter in the text 4 places, the second 11, the third by 4 again, and so on. The principle is the same, however, one key is used by the algorithm to either encrypt plaintext or decrypt the generated ciphertext.

Public Key encryption was a major theoretical breakthrough because it uses asymmetric algorithm's. The key that encrypts plaintext is not the same as the key that decrypts and knowing one doesn't help you guess the other. With such an algorithm Bob can tell Alice freely his "public key" knowing that Eve will get it too. But Alice can then encrypt a message and send it to Bob knowing that even though Eve has the encrypted message and the encryption key, she won't be able to figure out the message without the "private key" that Bob is keeping a secret. That such an algorithm exists was a subject of debate for quite some time and is kind of mind blowing when you think about it. Understanding the importance of public key encryption, however, isn't that difficult: I just explained it in a blog post.

Dan Brown wrote a whole novel involving cryptography and never got that far. Here's what he said about public cryptography:

Public Key encryption was a concept as simple as it was brilliant. It consisted of easy-to-use, home-computer software that scrambled personal E-mail messages in such a way that they were totally unreadable. A user could write a letter and run it through the encryption software and the text would come out the other side looking like random nonsense - totally illegible - a code. Anyone intercepting the transmission found only an unreadable garble on the screen.

This, of course, is a description of how computerized encryption - any kind of encryption - works and misses the whole point of the only major theoretical advance in Encryption in the last 40 years. This sort of mistake was emblematic of the whole book, however, with well defined terms like virus and worm redefined and ideas like "email tracer programs" that demonstrate profound ignorance of how email actually works. Oh, and the unbreakable algorithm isn't susceptible to brute-force attacks because it uses "rotating cleartext". Yes, that means that successfully decoding the message results in a different cleartext each time!

Well. I realise that even my personal blogging sort of slips in the direction of technology. There is, however, a point to all this. The Da Vinci Code has been debated to death - google and you'll find lots of people criticizing it's history, theology, symbology (I loved how pretty much everything apparently is a hidden reference to the feminine divine). For anyone tempted to take the Da Vinci Code seriously, however, look at Digital Fortress. Not only does it contain error - it is written without much effort to understand the ostensible backdrop of the book so as to avoid ridiculous and ludicrous statements. It is probably not wise to believe, unverified, anything the author has to say about other fields of knowledge.

Posted on June 19th 2007, 01:19 AM