## 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

; 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.

Pages: 1 2

### 7 Responses to “Blum’s Mental Hash”

1. Andras said

Java:

```package eu.eyan.programmingpraxis.blumhash;

import org.fest.assertions.Assertions;
import org.junit.Test;

/**
* https://programmingpraxis.com/2014/09/26/blums-mental-hash/
*
* Blum’s Mental Hash
*
* Your task today is to implement Manuel Blum's mental hashing algorithm, available here, for mapping a web site name to a password.
*
*/
public class BlumHash {

private static final String EXAMPLE_MAP = "83712345678901234567890123";
private static final String EXAMPLE_PERMUTATION = "0298736514";

@Test
public void testBlumHash() throws Exception {
System.out.println(blumHash("Programmingpraxis A to z", EXAMPLE_MAP, EXAMPLE_PERMUTATION));
Assertions.assertThat(blumHash("abc", EXAMPLE_MAP, EXAMPLE_PERMUTATION)).isEqualTo("103");
}

public static String blumHash(String siteInput, String map, String permutation) {
String hash = "";
String site = siteInput.replaceAll("[^a-zA-Z]", "").toLowerCase();
int bi = -1;
for (int i = 1; i <= site.length(); i++) {
if (i == 1) {
bi = g((f(site.charAt(i - 1), map) + f(site.charAt(site.length() - 1), map)) % 10, permutation);
} else {
bi = g((bi + f(site.charAt(i - 1), map)) % 10, permutation);
}
hash += bi;
}
System.out.println(siteInput);
System.out.println(hash);
return hash;
}

private static int g(int number, String permutation) {
return Integer.valueOf((permutation + permutation.charAt(0)).substring(
(permutation).indexOf("" + number) + 1,
(permutation).indexOf("" + number) + 2));
}

private static int f(Character c, String map) {
return Integer.valueOf(map.substring((int) c - (int) 'a', (int) c - (int) 'a' + 1));
}
}
```
2. Francesco said
```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'

```
3. Francesco said

Ok, I apparently can’t grok WordPress.

4. Another Java (8) solution:

```import java.util.function.Function;

public class BlumHash {

private Function<Character, Integer> f;
private int[] g;

public BlumHash(Function<Character, Integer> f, int[] g) {
this.f = f;
this.g = g;
}

public String hash(final String s) {
int n = s.length();
int[] d = new int[n];
for (int i = 0; i < n; i++) {
d[i] = f.apply(s.charAt(i));
}
int[] h = new int[n];
h[0] = next((d[0] + d[n - 1]) % 10);
for (int i = 1; i < n; i++) {
h[i] = next((h[i - 1] + d[i]) % 10);
}
StringBuilder sb = new StringBuilder(n);
for (int i = 0; i < n; i++) {
sb.append(h[i]);
}
return sb.toString();
}

private int next(int n) {
for (int i = 0; i < g.length; i++) {
if (g[i] == n) {
return g[(i+1) % g.length];
}
}
}

public static void main(String[] args) {
BlumHash hasher = new BlumHash(c -> {
switch (c) {
case 'a': return 8;
case 'b': return 3;
case 'c': return 7;
default:
return c % 10;
}
}, new int[]{0,2,9,8,7,3,6,5,1,4});
System.out.println(hasher.hash("abc"));
}
}
```
5. Claire said

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;
}

6. Claire said

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;
}

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