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.

Pages: 1 2

6 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. 
     * 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));
        }
    }
    
  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.
    Here is a solution in Haskell: http://codepad.org/y4LrYRX7

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: