Breaking Caesar’s Cipher (part III)

In the last installment of this series, we looked at Markov chains as a mean of estimating the likelihood of a given piece of text of actually being a message, written in English, rather than mere gibberish.

This week, we finally piece everything together to obtain a program to crack Caesar’s cipher without (much) human intervention.

Suggested Reading: Lost Cat

Caroline Paul, Wendy MacNaughton — Lost Cat: A True Story of Love, Desperation, and GPS Technology — Bloomsburt, 2013, 176 pp. ISBN 1608199770

(Buy at Amazon.com)

This is a story of Tibia the cat that suddenly vanishes for five weeks before coming back. In full health, shiny coat, happy. Then vanishes again. Quickly, Caroline Paul catlover, couchridden following a plane crash, worries about Tibby, wondering where he was and why he didn’t come back sooner. Then begins a detective story: will a GPS and a camera attached to the cat reveal its whereabouts?

Breaking Caesar’s Cipher (Caesar’s Cipher, part II)

In the last installment of this series, we had a look at Caesar’s cipher, an absurdly simple encryption technique where the symmetric encryption only consists in shifting symbols places.

While it’s ridiculously easy to break the cipher, even with pen-and-paper techniques, we ended up, last time, surmising that we should be able to crack the cipher automatically, without human intervention, if only we had a reasonable language model. This week, let us have a look at how we could build a very simple language model that does just that.

Building a Tree from a List in Linear Time (II)

Quite a while ago, I proposed a linear time algorithm to construct trees from sorted lists. The algorithm relied on the segregation of data and internal nodes. This meant that for a list of data items, nodes were allocated (but only contained data; the others just contained pointers.

While segregating structure and data makes sense in some cases (say, the index resides in memory but the leaves/data reside on disk), I found the solution somewhat unsatisfactory (but not unacceptable). So I gave the problem a little more thinking and I arrived at an algorithm that produces a tree with optimal average depth, with data in every node, in linear time and using at most extra memory.

Caesar’s Cipher

Julius Caesar, presumably sometimes during the war in Gaul, according to Suetonius, used a simple cipher to ensure the privacy of his communications.

Caesar’s method can hardly be considered anything close to secure, but it’s still worthwhile to have a look at how you can implement it, and break it, mostly because it’s one of the simplest substitution ciphers.

A Special Case…

Expressions with floors and ceilings ( and ) are usually troublesome to work with. There are cases where you can essentially remove them by a change of variables.

Turns out, one form that regularly comes up in my calculations is , and it bugged me a while before I figured out the right way of getting rid of them (sometimes).

Shallow Constitude

In programming languages, there are constructs that are of little pragmatic importance (that is, they do not really affect how code behaves or what code is generated by the compiler) but are of great “social” importance as they instruct the programmer as to what contract the code complies to.

One of those constructs in C++ is the const (and other access modifiers) that explicitly states to the programmer that this function argument will be treated as read-only, and that it’s safe to pass your data to it, it won’t be modified. But is it all but security theater?

Compressed Series (Part II)

Last week we looked at an alternative series to compute , and this week we will have a look at the computation of . The usual series we learn in calculus textbook is given by

We can factorize the expression as

Compressed Series (Part I)

Numerical methods are generally rather hard to get right because of error propagation due to the limited precision of floats (or even doubles). This seems to be especially true with methods involving series, where a usually large number of ever diminishing terms must added to attain something that looks like convergence. Even fairly simple sequences such as

may be complex to evaluate. First, is cumbersome, and becomes small exceedingly rapidly.

Zenmap

I recently discovered a cute little front-end to nmap called zenmap.

Zenmap is installed by default in distributions such as Backtrack Linux, but is also found in Ubuntu’s repositories.