チェックデジットを比較してみた

チェックデジットは、バーコード・ISBN・クレジット番号と様々なものに使われている。少し前マイナンバーカードのチェックデジットは性能が悪い、という話もあったらしい。
チェックデジットにはどのような方式が有るのかを調べ、それぞれの性能差を比較してみた。

比較対象のチェックデジット方式

単純な足し算
Luhnアルゴリズム
ISBN-10
ISBN-13
マイナンバー
Verhoeffアルゴリズム
DAMMアルゴリズム

各方式のPHP実装

比較テストのためPHPで各方式を実装した。フォーマットをそろえるため以下の仕様とした

1つの方式を1つの関数で実装する
入力はN桁の数字(0-9)で構成された文字列型
出力は数値型。入力文字列を処理した結果で主に0-9の数値が返る

正しく動作すれば良いので最適化はしていない。

単純な足し算

function sum1($str) {
	$cs = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$cs += intval($str[$i]);
		$cs %= 10; //1の位だけ足せばいい
	}
	return $cs;
}

Luhnアルゴリズム

クレジットカード番号など。偶数桁を2倍して足す

function luhn($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n % 2 ? 2 : 1;
		$c = intval($str[$i]) * $w;
		$c -= $c > 9 ? 9 : 0; // 2倍して10以上になる数(5*2..9*2)の一と十の位の和は、9との差と等しい
		$cd += $c;
	}
	$cd = (10 - ($cd % 10)) % 10;
	return $cd;
}

ISBN-10

旧規格の10桁ISBN。ISSN(8桁)、共通取引先コード(6桁)も桁数は違うが同じ処理。モジュラス11 ウェイト10-2というらしい。結果が10になることもあり、ISBN,ISSNではその場合は'X'と表記される。共通取引先コードでは結果が10になるコードは廃番

function isbn10($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n + 1;
		$cd += intval($str[$i]) * $w;
	}
	$cd = (11 - ($cd % 11)) % 11;
	return $cd;
}

ISBN-13

JANコード(8・13桁)や集合包装用商品コード(GTIN-14)、UPCコード(12桁)、出荷梱包シリアル番号(SSCC,14桁)も同様。モジュラス10 ウェイト3・1 というらしい

function isbn13($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n % 2 ? 3 : 1;
		$cd += intval($str[$i]) * $w;
	}
	$cd = (10 - ($cd % 10)) % 10;
	return $cd;
}

マイナンバー

正式名称は不明。以下を参考に実装

マイナンバーはチェックデジット込みで12桁で固定なので、本来は任意の長さの数字列に対応する必要は無い

function mynumber($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n + ($n >= 7 ? -5 : 1);
		$cd += intval($str[$i]) * $w;
	}
	$cd = 11 - ($cd % 11);
	$cd = $cd >= 10 ? 0 : $cd;
	return $cd;
}

Verhoeffアルゴリズム

全ての1桁誤りと隣接する2桁の入れ替わり誤りを検出できる最初の十進チェックデジットアルゴリズム

function verhoeff($str) {
	$str .= "0";
	$d = array(
		array(0,1,2,3,4,5,6,7,8,9),
		array(1,2,3,4,0,6,7,8,9,5),
		array(2,3,4,0,1,7,8,9,5,6),
		array(3,4,0,1,2,8,9,5,6,7),
		array(4,0,1,2,3,9,5,6,7,8),
		array(5,9,8,7,6,0,4,3,2,1),
		array(6,5,9,8,7,1,0,4,3,2),
		array(7,6,5,9,8,2,1,0,4,3),
		array(8,7,6,5,9,3,2,1,0,4),
		array(9,8,7,6,5,4,3,2,1,0)
	);
	$inv = array(0,4,3,2,1,5,6,7,8,9);
	$p = array(
		array(0,1,2,3,4,5,6,7,8,9),
		array(1,5,7,6,2,8,3,0,9,4),
		array(5,8,0,3,7,9,6,1,4,2),
		array(8,9,1,6,0,4,3,5,2,7),
		array(9,4,5,3,1,2,6,8,7,0),
		array(4,2,8,6,5,7,3,9,0,1),
		array(2,7,9,3,8,0,6,4,1,5),
		array(7,0,4,6,9,1,3,2,5,8)
	);
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i - 1;
		$cd = $d[$cd][$p[$i % 8][intval($str[$n])]];
	}
	$cd = $inv[$cd];
	return $cd;
}

Dammアルゴリズム

Dammアルゴリズムは、Verhoeffアルゴリズムと同様に、最も頻繁に起こる2種類の誤り、すなわち1桁の入力誤りと、（末尾に付け足されたチェックディジットとその直前の数字の入れ値替えを含む）隣り合う2桁の入れ違えの、2種類の誤りを検出できる

さらにDammアルゴリズムはテーブルを入れ替えれば数字以外の入力にも対応可能だとか。
今回は http://www.md-software.de/math/DAMM_Quasigruppen.txt にある
『Ordnung 10: Computer-Suche, erkennt alle phonetischen Fehler』 (Order 10: コンピューター検索、全ての音声エラーを検出)のテーブルを利用した。

function damm($str) {
	$tbl = array(
		array(0,3,1,7,5,9,8,6,4,2),
		array(7,0,9,2,1,5,4,8,6,3),
		array(4,2,0,6,8,7,1,3,5,9),
		array(1,7,5,0,9,8,3,4,2,6),
		array(6,1,2,3,0,4,5,9,7,8),
		array(3,6,7,4,2,0,9,5,8,1),
		array(5,8,6,9,7,2,0,1,3,4),
		array(8,9,4,5,3,6,2,0,1,7),
		array(9,4,3,8,6,1,7,2,0,5),
		array(2,5,8,1,4,3,6,7,9,0)
	);
	$cd = 0;
	for($i=0; $i<strlen($str); $i++) {
		$cd = $tbl[$cd][$str[$i]];
	}
	return $cd;
}

各方式の検証

テストデータとしてランダムな11桁の数字を用意し、(例: 12345678901)

ランダムな1桁を違う数字に書き換える(例: 92345678901)
ランダムな連続する2桁を違う数字に書き換える(例: 19945678901)
ランダムな連続する2桁を交換する(例: 21345678901)
ランダムな箇所に数字を挿入する(例: 192345678901)
ランダムな1桁を削除する(例: 2345678901)

という5パターンの書き換えを行う。
それぞれのチェックデジットを計算し、どの程度エラーを検出できるかを比較した。

検証結果

結果は以下の表のとおり。テストデータ数は100,000件。表の数字はエラー検出の失敗数(%)である。少ないほど良い

＼	足し算	Luhn	ISBN10	ISBN13	マイナンバー	Verhoeff	Damm
#1 1桁変更	0	0	8952(9.0%)	0	1777(1.8%)	0	0
#2 2桁変更	11136(11%)	11026(11%)	7997(8.0%)	11038(11%)	11485(11%)	10916(11%)	10927(11%)
#3 入れ替え	100000(100%)	2149(2.0%)	0	11254(11%)	1836(1.8%)	0	0
#4 1桁追加	9989(10%)	10010(10%)	8968(9.0%)	9978(10%)	10755(11%)	10008(10%)	9878(9.9%)
#5 1桁削除	10231(10%)	9182(9.0%)	7610(7.6%)	9291(9.3%)	10015(10%)	10210(10%)	9151(9.2%)

「足し算」の結果を基準に考えると、

テスト1:1桁の変更は、マイナンバーはたまにエラー検出失敗することが分かる。mod11なのに0-9に丸めている影響か
テスト1:1桁の変更、ISBN10もたまに失敗しているが、これは本来9桁の数字までしか想定されていないから
テスト3:2桁の入れ替えに対しては、ISBN10・Verhoeff・Dammには完璧な耐性があり、次いでLuhn・マイナンバーがかなり良い
テスト2:2桁の変更、テスト4:1桁追加、テスト5:1桁削除に対しては、どの方式も同様の耐性か

方式別に評価すると

足し算も悪くない。入れ替え耐性が全くないのが欠点
Luhn は全体的に良い
ISBN10 は入力が9桁以下ならば良い。ただ出力が11パターン(0-10)あってズルい
ISBN13 は2桁の入れ替え耐性が多少弱い
マイナンバーは1桁変更の検出漏れが欠点
Verhoeff, Dammはほぼ同等の性能。今回比較した中では一番良い

Verhoeff＝Damm＞Luhn＞ISBN13＞マイナンバー＞足し算

という感じだろうか。

まとめ

様々なチェックデジット方式を実装・検証してみて違いを確認できた。
今回検証した範囲では、評判の悪いマイナンバーのチェックデジットは本当に性能が悪かった。他と比べて何もメリットがないように思える。
余り見かけないVerhoeff,Dammアルゴリズムは同程度に優秀であること、そして世界で一番使われているであろうLuhnアルゴリズムもかなり優秀であるとわかった。

検証スクリプト

最後に検証に使ったPHPスクリプトをそのまま載せておく。

php checkdigits.php random 100000 11

とすれば検証結果が出力される

checkdigits.php

<?php

// 単純に足し算する
function sum1($str) {
	$cs = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$cs += intval($str[$i]);
		$cs %= 10; //1の位だけを足せばいい
	}
	return $cs;
}

// 旧規格の10桁ISBN
// https://ja.wikipedia.org/wiki/ISBN#%E3%83%81%E3%82%A7%E3%83%83%E3%82%AF%E3%83%87%E3%82%A3%E3%82%B8%E3%83%83%E3%83%88%EF%BC%882006%E5%B9%B4%E3%81%BE%E3%81%A7%EF%BC%89
// ISSN(8桁)、共通取引先コード(6桁)も桁数は違うが同じ処理。モジュラス11 ウェイト10-2というらしい
// 結果が10になることもあり、ISBN,ISSNではその場合は'X'と表記される。共通取引先コードでは結果が10になるコードは廃番
function isbn10($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n + 1;
		$cd += intval($str[$i]) * $w;
	}
	$cd = (11 - ($cd % 11)) % 11;
	return $cd;
}

// 現規格の13桁のISBN
// https://ja.wikipedia.org/wiki/ISBN#%E3%83%81%E3%82%A7%E3%83%83%E3%82%AF%E3%83%87%E3%82%A3%E3%82%B8%E3%83%83%E3%83%88%EF%BC%882007%E5%B9%B4%E4%BB%A5%E9%99%8D%EF%BC%89
// JANコード(8・13桁)や集合包装用商品コード(GTIN-14)、UPCコード(12桁)、出荷梱包シリアル番号(SSCC,14桁)も同様。モジュラス10 ウェイト3・1 というらしい
function isbn13($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n % 2 ? 3 : 1;
		$cd += intval($str[$i]) * $w;
	}
	$cd = (10 - ($cd % 10)) % 10;
	return $cd;
}

// マイナンバー
// https://qiita.com/ytkhs/items/fa6ef94d3c8615b0ce64
// https://www.soumu.go.jp/main_content/000327387.pdf
// 12345_678901 => 1*2 + 0*3 + 9*4 + 8*5 + 7*6 + 6*7 + 5*2 + 4*3 + 3*4 + 2*5 + 1*6 (nの位の数値に 1<=n<=6 なら n+1, 7<=n<=11 なら n-5 をかける)
//              => 212 mod 11 = 3 (11でわった余りを求め)
//              => 11 - 3 = 8 (11から引いたものがチェックデジット。10,11なら0とする)
function mynumber($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n + ($n >= 7 ? -5 : 1);
		$cd += intval($str[$i]) * $w;
	}
	$cd = 11 - ($cd % 11);
	$cd = $cd >= 10 ? 0 : $cd;
	return $cd;
}

// Verhoeffアルゴリズム
// https://ja.wikipedia.org/wiki/%E3%83%B4%E3%82%A1%E3%83%BC%E3%83%98%E3%83%95%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
function verhoeff($str) {
	$str .= "0";
	$d = array(
		array(0,1,2,3,4,5,6,7,8,9),
		array(1,2,3,4,0,6,7,8,9,5),
		array(2,3,4,0,1,7,8,9,5,6),
		array(3,4,0,1,2,8,9,5,6,7),
		array(4,0,1,2,3,9,5,6,7,8),
		array(5,9,8,7,6,0,4,3,2,1),
		array(6,5,9,8,7,1,0,4,3,2),
		array(7,6,5,9,8,2,1,0,4,3),
		array(8,7,6,5,9,3,2,1,0,4),
		array(9,8,7,6,5,4,3,2,1,0)
	);
	$inv = array(0,4,3,2,1,5,6,7,8,9);
	$p = array(
		array(0,1,2,3,4,5,6,7,8,9),
		array(1,5,7,6,2,8,3,0,9,4),
		array(5,8,0,3,7,9,6,1,4,2),
		array(8,9,1,6,0,4,3,5,2,7),
		array(9,4,5,3,1,2,6,8,7,0),
		array(4,2,8,6,5,7,3,9,0,1),
		array(2,7,9,3,8,0,6,4,1,5),
		array(7,0,4,6,9,1,3,2,5,8)
	);
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i - 1;
		$cd = $d[$cd][$p[$i % 8][intval($str[$n])]];
		//echo " i:{$i}, n:{$n}, chr:".$str[$n].", cd:{$cd}\n";
	}
	$cd = $inv[$cd];
	return $cd;
}

// DAMMアルゴリズム
// https://ja.wikipedia.org/wiki/Damm%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
function damm($str) {
	// http://www.md-software.de/math/DAMM_Quasigruppen.txt 
	//  Ordnung 10: Computer-Suche, erkennt alle phonetischen Fehler (Order 10: コンピューター検索、全ての音声エラーを検出)
	$tbl = array(
		array(0,3,1,7,5,9,8,6,4,2),
		array(7,0,9,2,1,5,4,8,6,3),
		array(4,2,0,6,8,7,1,3,5,9),
		array(1,7,5,0,9,8,3,4,2,6),
		array(6,1,2,3,0,4,5,9,7,8),
		array(3,6,7,4,2,0,9,5,8,1),
		array(5,8,6,9,7,2,0,1,3,4),
		array(8,9,4,5,3,6,2,0,1,7),
		array(9,4,3,8,6,1,7,2,0,5),
		array(2,5,8,1,4,3,6,7,9,0)
	);
	$cd = 0;
	for($i=0; $i<strlen($str); $i++) {
		$n = $str[$i];
		$cd = $tbl[$cd][$n];
	}
	return $cd;
}

// ルーン・アルゴリズム
// https://ja.wikipedia.org/wiki/Luhn%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
// クレジットカードなど
function luhn($str) {
	$cd = 0;
	for($i=0,$len=strlen($str); $i<$len; $i++) {
		$n = $len - $i;
		$w = $n % 2 ? 2 : 1;
		$c = intval($str[$i]) * $w;
		$c -= $c > 9 ? 9 : 0; // 2倍して10以上になる数(5*2..9*2)の一と十の位の和は、9との差と等しい
		$cd += $c;
	}
	$cd = (10 - ($cd % 10)) % 10;
	return $cd;
}

function test() {
	$testdata = array(
		array("luhn", "4992739871", 6),
		array("verhoeff", "236", 3),
		array("damm", "572", 4),
		array("isbn10", "410109205", 2),
		array("isbn13", "978410109205", 8),
		array("isbn13", "456995111617", 9),  //JAN13
		array("isbn13", "4996871", 2),       //JAN8
		array("isbn13", "1456995111617", 6), //GTIN14
		array("isbn13", "01234567890", 5), //UPC12
		array("isbn13", "04569951110000001", 6), //SSCC18
		array("mynumber", "12345678901", 8),
		array("sum1", "572", 4)
	);
	foreach($testdata as $d) {
		$m = $d[0];
		$input = $d[1];
		$output = $d[2];
		$result = $m($input);
		$ok = $output === $result;
		echo ($ok ? " ok " : "!NG!" ) . " {$m}('{$input}') => {$result} (expect: {$output})\n";
	}
}

function help() {
	$script =  basename(__FILE__);
	echo "> php {$script} [help]                            - Show help message\n";
	echo "> php {$script} test                              - Run method test\n";
	echo "> php {$script} random [\$num_sample] [\$num_digit] - Run random test\n";
	echo "\t\t\$num_sample: number of sample data(default: 10000)\n";
	echo "\t\t\$num_digit: number of digit(default: 11)\n";
}

if (isset($argv[0]) && $argv[0] === basename(__FILE__)) {
	$cmd = $argv[1];
	if ($cmd === 'test') {
		return test();
	}
	if ($cmd === 'help' || !isset($cmd)) {
		return help();
	}
	if ($cmd !== 'random') {
		echo "Invalid command: {$cmd}\n";
		return help();
	}
	// $digit 桁のランダムな数字列を $sample 個生成する
	$sample = isset($argv[2]) && is_numeric($argv[2]) ? intval($argv[2]) : 10000;
	if ($sample < 10) {$sample = 10000;}
	$digit = isset($argv[3]) && is_numeric($argv[3]) ? intval($argv[3]) : 11;
	if ($digit < 2) {$digit = 2;}
	// 桁数がサンプル数に比べて小さすぎる場合エラー(例:2桁の数字ではサンプルを100個以上作れない)
	$min_digit = floor(log($sample, 10));
	if ($digit <= $min_digit) {
		echo "!! BAD Parameter. \$num_digit:{$digit} is too small !!\n";
		echo " \$num_digit must be greater than " . ($min_digit+1) . " [= log10({$sample})]\n";
		return;
	}
	$nums = array();
	echo "Creating {$sample} samples(digit: {$digit})\n";
	$len = $total = 0;
	$testnames = array("?1", "?2", "<>", "+1", "-1");
	while($len < $sample) {
		// 先頭は0以外
		$num = "" . rand(10000, 999999);
		while(strlen($num) < $digit) {
			$num .= sprintf('%08d', rand(0, 99999999));
		}
		$num = substr($num, 0, $digit);
		if (isset($nums[$num])) {continue;}
		$nums[$num] = array();
		// Test1: 1カ所だけランダムに書き換える
		$n = rand(0, $digit-1);
		$s = rand(1, 9);
		$r = (intval($num[$n]) + $s) % 10;
		$nums[$num][] = substr_replace($num, $r, $n, 1);
		// Test2: 連続した2カ所をランダムに書き換える
		$n = rand(0, $digit-2);
		$s1 = rand(1, 9);
		$s2 = rand(1, 9);
		$r1 = (intval($num[$n])   + $s1) % 10;
		$r2 = (intval($num[$n+1]) + $s2) % 10;
		$nums[$num][] = substr_replace($num, $r1.$r2, $n, 2);
		// Test3: 連続した2カ所を入れ替える
		$nums[$num][] = substr_replace($num, $num[$n+1].$num[$n], $n, 2);
		if ($num === $nums[$num][2]) {
			// 入れ替えた数字が元の数字と同じだった場合、この番号は廃番にする
			unset($nums[$num]);
			continue;
		}
		// Test4: 1桁増やす
		$n = rand(0, $digit);
		$r = rand(0, 9);
		$nums[$num][] = substr_replace($num, $r, $n, 0);
		// Test5: ランダムに1桁削除
		$n = rand(0, $digit-1);
		$nums[$num][] = substr_replace($num, "", $n, 1);
		
		$len++;
		$total+= count($nums[$num]);
		if ($len < 5) {
			echo "  [{$len}]: {$num} => ".implode(",", $nums[$num]) . "\n";
		}
	}
	
	echo "Processing...\n";
	$methods = array("luhn", "isbn10", "isbn13", "verhoeff", "damm", "mynumber", "sum1");
	$stat = array();
	foreach($methods as $m) {
		$time_start = hrtime(true);
		$stat[$m] = array("ok" => 0, "ng" => 0, "time" => 0);
		foreach($nums as $num => $testnums) {
			$cd = $m(strval($num));
			$i=0;
			foreach($testnums as $tnum) {
				$tcd = $m(strval($tnum));
				if (!isset($stat[$m]["test".($i+1)."ng"])) {$stat[$m]["test".($i+1)."ng"] = 0;}
				if ($cd !== $tcd) {
					// チェックデジットが違う(正しく異常検知)
					$stat[$m]["ok"]++;
				} else {
					// 異常検知できなかった
					$stat[$m]["ng"]++;
					$stat[$m]["test".($i+1)."ng"]++;
				}
				$i++;
			}
		}
		$a = strlen("{$len}");
		$stat[$m]["time"] = hrtime(true) - $time_start;
		echo "[{$m}]: " . $stat[$m]["time"] . "ns (" . sprintf('%8.4f', $stat[$m]["time"]/1000000) . "msec)\n";
		for($i=1; $i<=count($testnames); $i++) {
			echo "   #{$i} {$testnames[$i-1]} NG: " . sprintf("%{$a}d", $stat[$m]["test{$i}ng"]) . "/" . $len . "\t(" . sprintf('%8.4f', $stat[$m]["test{$i}ng"]*100/$len) . "%)\n";
		}
		echo "   Total NG: " . sprintf("%{$a}d", $stat[$m]["ng"]) . "/" . ($total) . "\t(" . sprintf('%8.4f', $stat[$m]["ng"]*100/$total) . "%)\n";
	}
}