a monochromatic oeuvre

Bhargav and I had a short discussion regarding Fibonacci number generating functions over winter break and I recently answered an interview question along the same vein, so I guess its a question worth looking at:

The recursive formula for the generation of the nth Fibonacci number F_n is F_n = F_n-1 + F_n-2, where F₁ = F₂ = 1. How then, do we write a function that generates the nth Fibonacci number? The simplest approach is to convert this formula directly into code (all sample code given in python):

def F(n):
    if n == 1 or n == 2:
         return 1
    else:
         return F(n-1) + F(n-2)

This works, but there’s a minor problem. When we run it for small numbers, it seems fine, but it slows down rapidly for large values of n. On my computer (which, admittedly, isn’t very fast, but it’s still a reasonably nice computer), F₃₀ takes about half a second to run, F₃₅ takes about 6 seconds, and I don’t even want to know when F₅₀ will finish (according to my rough calculations, in about 6 days). This is clearly unacceptable. I could calculate F₅₀ by hand in less than 6 days (or 20 minutes). So what’s wrong?

If we look at the function, we’ll see that when you call F(n), it makes two recursive calls to F(n-1) and F(n-2), each of those makes two more recursive calls, which each make two more, and so on. Furthermore, each additional call only reduces the problem size by a constant factor, one or two. This leads to exponential growth, where a call to F(n) takes almost twice as long as a call to F(n-1). This is bad! The culprit here is we’re doing extra work. Here is the tree of recursive calls for F(6):

As you can see, F(4) is being calculated in both subtrees of F(6), and F(3) is calculated in three different subtrees. As n gets larger, more and more work is being redone in multiple subtrees.

Bhargav’s solution was to use a hash table to save a solution once it’s been calculated, so that future calls can check if the solution has already been found for some n before calculating it again:

fib_results = {1:1, 2:1}
def F(n):
    if n in fib_results:
         return fib_results[n]
    else:
         fib_results[n] = F(n-1) + F(n-2)
         return fib_results[n]

This is in fact much faster and runs in linear time instead of exponential time. Unfortunately, it takes linear space in the form of the hash table, and it is unclear how or whether we can avoid using that space, though it seems like it might be possible since we didn’t use linear space in the naive solution. This approach is called memoization. Memoization is an example of a top-down alternative to dynamic programming. It’s advantage over the bottom-up approach, called dynamic programming, is that it is much easier to convert a naive recursive algorithm to a memoized algorithm. The disadvantage is that dynamic programming is generally somewhat faster in implementation and more powerful, making it clearer how to make optimizations such as getting rid of that linear space hash table.

The idea behind dynamic programming is, once we’ve defined a problem in terms of its subproblems, to solve it by starting from the base cases and solving subsequently larger problems, usually in tabular form. To find F(n), we create an array of n cells, filling cells 1 and 2 with the value 1 (those are the base cases). To fill each cell, we look at the two previous cells and fill it with their sum. Conveniently, this means that the ith cell contains the value of F(i). Hence, by the time we fill the nth cell we will have found the value of F(n).

This algorithm would look like this:

def F(n):
    # Create an array of n cells
    fib_table = [None]*n

    # Initialize base cases
    fib_table[0] = 1
    fib_table[1] = 1

    # Fill table
    for i in range(2, n):
        fib_table[i] = fib_table[i-1] + fib_table[i-2]
    return fib_table[n-1]

Unfortunately, this still takes linear space! It will probably be a little faster than the memoized algorithm, since arrays are a little faster than dictionaries, but we still haven’t got rid of the need for the lookup table. However, if we look at this algorithm, it becomes clear that to fill each cell, we only need to look at the two cells before it. In fact, we can forget the values in every cell before those two, since we’ll never need them again. To save using that space, we can just reuse the same three cells over and over again. In fact, since we only have three cells, we can just use variables instead of creating a table:

def F(n):
    a = 1
    b = 1
    c = 1
    for i in range(2, n):
        c = a + b
        a = b
        b = c
    return c

Mission accomplished. We have a Fibonacci number function that runs in linear time and constant space. Dynamic programming is clearly awesome. A Fibonacci number function is one of the simplest applications of dynamic programming. One could easily imagine coming up with this solution without going through this thought process. However, there are many more complex problems that dynamic programming can solve, without which the best solutions are incredibly difficult to find. Some applications of dynamic programming include RNA folding and seam carving (crazy content aware image resizing)

I stumbled upon a hacker challenge posed by blogger Andy Sloane last night.  He explained how, as a hobby, likes to try to crack or create key generators for commercial programs.  Naturally, he never distributes these cracks, but is only doing it for the intellectual challenge.  Writing a key generator is usually more useful than cracking, since a good keygen typically allows you to receive future updates.  Often, it is also more interesting from an intellectual point of view, as writing a keygen usually requires some knowledge in reverse engineering and number theory.  Andy tries to demonstrate what he means by providing a simple key checker of his own for us to break.  Since I had a lighter workload last night, I figured I’d try it.

For his challenge to the world, he offers the source code of the key checker and three working keys.  The source is available on his blog.  (While a normal keygen writer would not have access to the source code of the key checker, it is usually simple, though tedious, to decompile and interpret the compiled binaries that would be released.)

After downloading and skimming the source, I spent a while trying to understand the custom written (and minimally commented) library he uses for large (125 bit, in this case) integers.  Rather than try to interpret the code itself, I used gdb to inspect the way the library worked, and had soon figured out the inner workings of the key checker:

Each key that it received, it would convert into an integer.  Each key had a unique integer k (with some exceptions: O, Q, and 0; I and 1; and Z and 2 were considered to be interchangeable to lower the change of an misread key) to which it was decoded.

Two magic numbers n = 21967608700894359473408781171922272451 and d=4444901153489723031681183441752517327 were hard-coded into the program.  A new number m ≡ k^d mod n was created.  The key was accepted if m ≡ 12345678 mod c, where c = ⌊n/2³²⌋ (rounded down to the nearest integer).

This was clearly a problem for number theory! This algorithm looked suspiciously similar to the RSA encryption algorithm, which similarly employs two large numbers with special properties.

A quick summary of the steps behind RSA encryption:

1. Pick two large primes p and q.
   
2. Compute n = pq.
3. Compute the totient of n, φ(n) = (p-1)(q-1).
4. Choose an integer e such that e is relatively prime to and less than φ(n).
5. Compute the integer d such that ed ≡ 1 mod φ(n).
6. For your message m, encrypt it by generating ciphertext c ≡ m^e mod n. e is known as the public key and is used to encrypt the message.
7. The person who receives the ciphertext by using d and applying the formula m = c^d mod n.

This works because of Euler’s theorem, which states that a^φ(n) ≡ a mod n for any integers a and n.

From that, c^d =(m^e)^d=m^ed= m^1+kφ(n) ≡ m mod n. (Check out the explanation of RSA on wikipedia for a more in depth explanation.

I quickly used Mathematica to factor n to see if it was the product of two primes. It was!  I checked that d was relatively prime to φ(n) to be sure.  It also was. The only part where this differed from RSA was the final step where it checked to see if m ≡ 12345678 mod c before accepting the key.

I was a little thrown off by c being related to n, but I quickly realized that it didn’t matter what c was.  It was just there to make sure that more than one m (and therefore more than one key) was accepted.  Effectively, what this key checker did was to take RSA generated ciphertext as a key and check to see if it decryped to a message that left a remainder of 12345678 when divided by c.

Therefore, to generate a key, I needed to create a correct message and encrypt it, then convert the ciphertext back to the “key” format.  Creating a message is easy. m is an accepted message if m ≡ 12345678 mod c, so m = ac + 12345678, where a is any natural number.  To encrypt m, I need to find the private key e.  Since n is small enough to factor and ed ≡ 1 mod φ(n), it is easy to find e through modular arithmetic.

Voila! Now I have everything I need to write a keygen for Andy’s example key checker. In fact, here it is.  Now, clearly, I should go do my homework, having wasted several hours on this.