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.

Advertisements

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

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

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: