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