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:
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)); } }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:
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")); } }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 […]