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.

Posted by programmingpraxis

Filed in Exercises

7 Comments »

7 Responses to “Blum’s Mental Hash”

Andras said

September 26, 2014 at 10:08 AM

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. 
 * http://www.scilogs.com/hlf/mental-cryptography-and-good-passwords/
 * 
 */
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));
    }
}

Francesco said

September 26, 2014 at 12:47 PM

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'

Francesco said
September 26, 2014 at 12:49 PM
Ok, I apparently can’t grok WordPress.
Here is a solution in Haskell: http://codepad.org/y4LrYRX7

Catalin Cristu (@catalin_c) said

September 30, 2014 at 8:23 PM

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];
            }
        }
        throw new IllegalArgumentException(n + " not found");
    }

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

Claire said
October 2, 2014 at 4:37 AM
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;
}
Claire said
October 2, 2014 at 4:54 AM
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;
}
Marsaglia’s Mental RNG | Programming Praxis said
January 29, 2019 at 10:01 AM
[…] 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 […]

S	M	T	W	T	F	S
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

Programming Praxis