## Blum’s Mental Hash

### September 26, 2014

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.

Java:

lk x xs = maybe undefined id (lookup x xs)

lf l = lk l $ zip [‘a’..’z’] (cycle [8,3,7])

nf n = lk n $ zip ls (tail ls ++ [head ls])

where ls = [0,2,9,8,7,3,6,5,1,4]

gen cs = let is = map lf cs

fd = nf $ mod (head is + last is) 10

in f (tail is) fd

where f [] l = [l]

f (a:as) l = let l’ = nf (mod (l+a) 10)

in [l] ++ f as l’

Ok, I apparently can’t grok WordPress.

Here is a solution in Haskell: http://codepad.org/y4LrYRX7

Another Java (8) solution:

C++:

//blumhash.h

#include

#include

#include

#include

using namespace std;

class BlumHash

{

public:

BlumHash();

string BlumHashMethod(string& siteName,string& map, string& permutation);

private:

int f(char c, string& map);

int g(int number, string& permutation);

};

//blumhash.cpp

BlumHash::BlumHash()

{

}

string BlumHash::BlumHashMethod(string& siteName, string& map, string& permutation)

{

int input = -1;

int number = -1;

string hash = “”;

transform(siteName.begin(),siteName.end(),siteName.begin(),::tolower);

for (int i = 0; i=’a’ && siteName.at(i)<='z'))

{

continue;

}

if(i == 0)

{

int first = f(siteName.at(i),map);

int last = f(siteName.at(siteName.length()-1),map);

input = (first + last)%10;

}

else

{

int bi = f(siteName.at(i),map);

input = (bi + number)%10;

}

number = g(input,permutation);

char a[10];

itoa(number,a,10);

hash +=a;

}

return hash;

}

int BlumHash::f(char c, string& map)

{

char tmp = map[c-'a'];

return(atoi(&tmp));

}

int BlumHash::g(int number, string& permutation)

{

int length = permutation.length();

char tmp;

char a[10];

itoa(number,a,10);

int position = permutation.find(a);

if(position == length – 1)

{

tmp = permutation.at(0);

}

else

{

tmp = permutation.at(position+1);

}

return atoi(&tmp);

}

//main.cpp

#include "blumhash.h"

int main(int argc, char *argv[])

{

BlumHash blumHash;

string map = "83701234567890123456789789";

//string map = "837";

string permutation = "0298736514";

string siteName = "A(B*c";

string siteName2 = "This is my programming.";

string hash;

hash = blumHash.BlumHashMethod(siteName,map,permutation);

cout<< siteName<<" : "<<hash<<endl;

string hash2;

hash2 = blumHash.BlumHashMethod(siteName2,map,permutation);

cout<< siteName2<<" : "<<hash2<<endl;

return 0;

}

I missed some code lines in the last comment, so here I posted again.

C++:

//bluhash.h

#include

#include

#include

#include

using namespace std;

class BlumHash

{

public:

BlumHash();

string BlumHashMethod(string siteName, string& map, string& permutation);

private:

int f(char c, string& map);

int g(int number, string& permutation);

};

//blumhash.cpp

BlumHash::BlumHash()

{

}

string BlumHash::BlumHashMethod(string siteName, string& map, string& permutation)

{

int input = -1;

int number = -1;

string hash = “”;

transform(siteName.begin(),siteName.end(),siteName.begin(),::tolower);

for (int i = 0; i=’a’ && siteName.at(i)<='z'))

{

continue;

}

if(i == 0)

{

int first = f(siteName.at(i),map);

int last = f(siteName.at(siteName.length()-1),map);

input = (first + last)%10;

}

else

{

int bi = f(siteName.at(i),map);

input = (bi + number)%10;

}

number = g(input,permutation);

char a[10];

itoa(number,a,10);

hash +=a;

}

return hash;

}

int BlumHash::f(char c, string& map)

{

char tmp = map[c-'a'];

return(atoi(&tmp));

}

int BlumHash::g(int number, string& permutation)

{

int length = permutation.length();

char tmp;

char a[10];

itoa(number,a,10);

int position = permutation.find(a);

if(position == length – 1)

{

tmp = permutation.at(0);

}

else

{

tmp = permutation.at(position+1);

}

return atoi(&tmp);

}

// main.cpp

#include "blumhash.h"

int main(int argc, char *argv[])

{

BlumHash blumHash;

string map = "83701234567890123456789789";

//string map = "837";

string permutation = "0298736514";

string siteName = "A(B*c";

string siteName2 = "This is my programming.";

string hash;

hash = blumHash.BlumHashMethod(siteName,map,permutation);

cout<< siteName<<" : "<<hash<<endl;

string hash2;

hash2 = blumHash.BlumHashMethod(siteName2,map,permutation);

cout<< siteName2<<" : "<<hash2<<endl;

return 0;

}

[…] saw an “in-your-head” random number generator in a previous exercise, but I found it hard to operate. Today’s exercise, due to George Marsaglia is a random number […]