## Blum’s Mental Hash

### September 26, 2014

We begin by defining the key as in the example, with extra digits added to complete the mapping for letters *d* to *z*:

`(define f (vector 8 3 7 1 8 5 6 3 0`

1 2 7 2 8 4 1 0 4 9 2 5 5 6 7 3 9))

`(define g (vector 0 2 9 8 7 3 6 5 1 4))`

The hash function is a little bit complicated:

(define (hash f g str) (let* ((len (string-length str)) (vec (make-vector len 0)) (out (make-vector len 0)) (next (make-vector 10 0)) (gg (append (vector->list g) (vector->list g)))) ; compute next array (do ((i 0 (+ i 1))) ((= i 10)) (vector-set! next i (cadr (member i gg)))) ; map f over the input string (do ((i 0 (+ i 1))) ((= i len)) (vector-set! vec i (vector-ref f (- (char->integer (char-upcase (string-ref str i))) 65)))) ; initialize hash (vector-set! out 0 (vector-ref next (modulo (+ (vector-ref vec 0) (vector-ref vec (- len 1))) 10))) ; compute remainder of hash (do ((i 1 (+ i 1))) ((= i len)) (vector-set! out i (vector-ref next (modulo (+ (vector-ref vec i) (vector-ref out (- i 1))) 10)))) ; return result (list->string (map (lambda (d) (integer->char (+ d 48))) (vector->list out)))))

The first `do`

converts the permutation into a *next* array, the second `do`

maps *f* over the input string, then the first output character is computed, the third `do`

computes the remainder of the output, one character at a time, and finally the result is returned as a string. Here are some examples:

`> (hash f g "abc")`

"103"

> (hash f g "ProgrammingPraxis")

"25800782938893297"

You can run the program at http://programmingpraxis.codepad.org/gCnPCUUb.

Although Blum’s crypto is good, I think that’s a little bit more work than I would like to do each time I need a password. Bruce Schneier suggests that most people have learned how to safeguard the wallets that hold their cash money, so it is reasonable to write down passwords on a piece of paper that you keep in your wallet, an approach I find perfectly sensible.

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 […]