Blum’s Mental Hash
September 26, 2014
It is generally accepted wisdom that people should use different passwords for each of their online accounts. Unfortunately, few people do that because of the difficulty of remembering so many passwords.
Manuel Blum — he’s the guy in the middle of the Blum Blum Shub sandwich — suggests an algorithm that hashes a web site name into a password. Further, his algorithm is cryptographically secure, so no one else can determine your password, and can be worked mentally, without a computer or even pencil and paper.
Blum’s algorithm works in two steps. A function f maps letters to digits, and a permutation g transposes the digits. The two, taken together, form your personal key, and so must be kept secret.
The first step maps letters to digits; since there are more letters than digits, some of the digits are used more than once. If, for instance, f(a) = 8, f(b) = 3, and f(c) = 7, then the first step would map the input “abc” to the digits [8, 3, 7].
The second step uses the permutation g to calculate the output. Begin with the first and last digits, adding them mod 10; in the example, (8 + 7) % 10 = 5. If the permutation g = 0298736514, then the next digit after 5 is 1, so the first output digit is 1.
After that, each remaining input digit is the basis of an output digit. Calculate the sum of the next input digit and the previous output digit, mod 10, and take the next digit of the permutation, repeating for each remaining input digit. In the example, the second input digit and the first output digit are summed mod 10, (3 + 1) % 10 = 4, and the next digit in the permutation is 0 (wrapping around), so the second output digit is 0. In the same way, the third output digit takes the third input digit and the second output digit, sums them mod 10, and computes the permutation, so (7 + 0) % 10 = 7, which permutes to 3. So the final password produced from an input of “abc” is “103”.
Your task today is to implement Manuel Blum’s mental hashing algorithm for mapping a web site name to a password. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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 […]