The Laws of Cryptography:
Digression: Verhoeff's Error Detection

by Neal R. Wagner

Copyright © 2001 by Neal R. Wagner. All rights reserved.

NOTE: This site is obsolete. See book draft (in PDF):

Here is Verhoeff's scheme using the dihedral group using special permutations. Notice that all adjacent transpositions are detected.


// ErrorDetection.java: base class for single-digit error detection
public class ErrorDetection {

   public static void printArray(int[] a) {
      for (int i = 0; i < a.length; i++) {
      	 if (a[i] == 10)
      	    System.out.print("X ");
      	 else
      	    System.out.print(a[i]);
      	 if (i%5 == 0) System.out.print(" ");
      }
      System.out.println();
   }
   
   public static void printUnchecked(int[] a) {
   	  System.out.print("? ");
      for (int i = 1; i < a.length; i++) {
      	 System.out.print(a[i]);
      	 if (i%5 == 0) System.out.print(" ");
      }
      System.out.println();
   }
}

// VerhoeffErrorDetection.java: Implement Verhoeff's decimal error detection public class VerhoeffErrorDetection extends ErrorDetection { private static int[][] op= { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 0, 6, 7, 8, 9, 5}, {2, 3, 4, 0, 1, 7, 8, 9, 5, 6}, {3, 4, 0, 1, 2, 8, 9, 5, 6, 7}, {4, 0, 1, 2, 3, 9, 5, 6, 7, 8}, {5, 9, 8, 7, 6, 0, 4, 3, 2 ,1}, {6, 5, 9, 8, 7, 1, 0, 4, 3, 2}, {7, 6, 5, 9, 8, 2, 1, 0, 4, 3}, {8, 7, 6, 5, 9, 3, 2, 1, 0, 4}, {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} }; private static int[] inv = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9}; private static int[][] F = new int[8][]; private static int[] F0 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; private static int[] F1 = {1, 5, 7, 6, 2, 8, 3, 0, 9, 4}; public VerhoeffErrorDetection() { F[0] = F0; F[1] = F1; for (int i = 2; i < 8; i++) { F[i] = new int[10]; for (int j = 0; j < 10; j++) F[i][j] = F[i-1] [F[1][j]]; } } public static int insertCheck(int[] a) { int check = 0; for (int i = 1; i < a.length; i++) check = op[check][ F[i % 8][a[i]] ]; a[0] = inv[check]; return a[0]; } public static boolean doCheck(int[] a) { int check = 0; for (int i = 0; i < a.length; i++) check = op[check][ F[i % 8][a[i]] ]; if (check != 0) return false; else return true; } // main function public static void main (String[] args) { VerhoeffErrorDetection v = new VerhoeffErrorDetection(); int[] a = new int[15]; boolean checkFlag = false; for (int i = 1; i < a.length; i++) a[i] = (int)(Math.random() * 10.0); VerhoeffErrorDetection.printUnchecked(a); VerhoeffErrorDetection.insertCheck(a); VerhoeffErrorDetection.printArray(a); System.out.println(VerhoeffErrorDetection.doCheck(a)); a[4] = (a[4] + 1)%10; VerhoeffErrorDetection.printArray(a); System.out.println(VerhoeffErrorDetection.doCheck(a)); // test all adjacent transpositions System.out.println("\nTest all adjacent transpositions"); for (int p1 = 0; p1 < 10; p1++) for (int p2 = 0; p2 < 10; p2++) { if (p1 != p2) { a[8] = p1; a[9] = p2; VerhoeffErrorDetection.insertCheck(a); // interchange a[8] ^= a[9]; a[9] ^= a[8]; a[8] ^= a[9]; if (VerhoeffErrorDetection.doCheck(a)) { System.out.println("Warning: Interchange of " + p1 + " and " + p2 + " not detected"); checkFlag = true; } } } if (checkFlag) System.out.println("At least one transposition undetected"); else System.out.println("All transpositions detected"); } // end of main }
Here is the output, showing a simple test, and a test of all adjacent interchanges. All interchange errors are detected.
? 75787 12372 9429
1 75787 12372 9429
true
1 75797 12372 9429
false

Test all adjacent transpositions
All transpositions detected


Revision date: 2001-12-31. (Please use ISO 8601, the International Standard.)