Programming Praxis

It is generally accepted wisdom that people should use different passwords for each of their online accounts. Unfortunately, few people do that because of the difficulty of remembering so many passwords.

Manuel Blum — he’s the guy in the middle of the Blum Blum Shub sandwich — suggests an algorithm that hashes a web site name into a password. Further, his algorithm is cryptographically secure, so no one else can determine your password, and can be worked mentally, without a computer or even pencil and paper.

Blum’s algorithm works in two steps. A function f maps letters to digits, and a permutation g transposes the digits. The two, taken together, form your personal key, and so must be kept secret.

The first step maps letters to digits; since there are more letters than digits, some of the digits are used more than once. If, for instance, f(a) = 8, f(b) = 3, and f(c) = 7, then the first step would map the input “abc” to the digits [8, 3, 7].

The second step uses the permutation g to calculate the output. Begin with the first and last digits, adding them mod 10; in the example, (8 + 7) % 10 = 5. If the permutation g = 0298736514, then the next digit after 5 is 1, so the first output digit is 1.

After that, each remaining input digit is the basis of an output digit. Calculate the sum of the next input digit and the previous output digit, mod 10, and take the next digit of the permutation, repeating for each remaining input digit. In the example, the second input digit and the first output digit are summed mod 10, (3 + 1) % 10 = 4, and the next digit in the permutation is 0 (wrapping around), so the second output digit is 0. In the same way, the third output digit takes the third input digit and the second output digit, sums them mod 10, and computes the permutation, so (7 + 0) % 10 = 7, which permutes to 3. So the final password produced from an input of “abc” is “103”.

Your task today is to implement Manuel Blum’s mental hashing algorithm for mapping a web site name to a password. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2