check digitを使った誤り検出

概要

クレジットカード・シリアルナンバーなど、長くなるほど入力ミスはしやすくなります。

そんな時に毎回DBに問い合わせて正しい値かをチェックするのではなくアルゴリズムによって正しいものかどうかチェックする仕組みがcheck digit（チェックディジット）です。

具体例

例えば

全桁を足し合わせて10で割った値をcheck digitとする

という計算式でcheck digitを算出するとします。
元の値を1234 5678 901とするとcheck digitは

となります。
よってcheck digitを付加した最終的なコードは1234 5678 9016となります。

元の値	check digit	最終的な値
1234 5678 901	6	1234 5678 9016

入力ミスすると

仮に入力ミスして1234 5678 0016となった場合、check digitである最後尾6を除いてからcheck digitを計算すると

となり、本来check digitを満たすコードであれば1234 5678 0017であるのに、1234 5678 0016となっているのでこの時点で入力したコードが間違っていることが分かります。

元の値	check digit	最終的な値
1234 5678 901	6	1234 5678 9016
1234 5678 001	7	1234 5678 0017

このように正しいコード1234 5678 9016と一致するか確認する前に、1234 5678 0016は存在しないコードとして弾くことが可能な訳です。

check digitのメリット

大きく２つあります。

• ユーザの入力ミスの検知
• 計算式を非公表とすることで不正な値を検知

先程の例から分かるように、そのコードが存在するかどうかの前にそもそも正しいかどうかをアルゴリズムでチェックできるので、入力ミスをチェックできます。

またcheck digitを算出する計算式は自由に選択できるので、公表しなければ不正な値の検知にも使用できます。

アルゴリズムでチェックできるので無駄なDB参照も無くなり良いこと尽くめですね。

アルゴリズム

有名なアルゴリズムを紹介します。

Luhnアルゴリズム

Luhnアルゴリズムはクレジットカードの誤り検知に利用されています。

特徴

Luhnアルゴリズムは以下の特徴があります。

• 任意の1桁の間違いや隣接する桁の数字の順序間違いを検出できる
• 09 から 90 （または逆）という間違いは検出できない
• 同じ数字が2つ連続する場合の間違いも10種類のうち4種類までは検出できる（22 ⇔ 55、33 ⇔ 66、44 ⇔ 77 は検出できない）

このように基本的な入力ミスはチェックできますが、一部検出漏れも存在します。

以下のサイトでチェックできます。

Check Credit Card Numbers | Validate your credit card number with our free online checker

正しい値のとき

間違った値のとき

Dammアルゴリズム

Dammアルゴリズムはラテン方格 （擬群の積表） を用いたcheck digitのアルゴリズムです。

ラテン方格とは n x n 行列に n 個の異なる要素が各行・各列に１回だけ現れるように配置された行列です。

$$ \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix} $$

この例では1, 2, 3が各行・各列に１回だけ現れています。

特徴

Dammアルゴリズムは以下の特徴があります。

• 全ての1桁入力誤りを検出できる
• 全ての隣り合う2桁の入れ替え誤りを検出できる

なので入力ミスはほぼ検出できます。

サンプルコード

サンプルコードを以下に記します。jsなのでディベロッパーモードのコンソールで簡単に確認できます。

var table = [
  [0, 3, 1, 7, 5, 9, 8, 6, 4, 2],
  [7, 0, 9, 2, 1, 5, 4, 8, 6, 3],
  [4, 2, 0, 6, 8, 7, 1, 3, 5, 9],
  [1, 7, 5, 0, 9, 8, 3, 4, 2, 6],
  [6, 1, 2, 3, 0, 4, 5, 9, 7, 8],
  [3, 6, 7, 4, 2, 0, 9, 5, 8, 1],
  [5, 8, 6, 9, 7, 2, 0, 1, 3, 4],
  [8, 9, 4, 5, 3, 6, 2, 0, 1, 7],
  [9, 4, 3, 8, 6, 1, 7, 2, 0, 5],
  [2, 5, 8, 1, 4, 3, 6, 7, 9, 0]
];

// Dammアルゴリズム
function calcDamm(basenumber) {
  var s,damm;
  damm = 0;
  s = String(basenumber); 
  for (var i=0; i<s.length; ++i) {
    damm = table[damm][s.charAt(i)];
  }
  return damm;
}

function checkDamm(number) {
  return calcDamm(number) == 0;
}

応用

紹介したアルゴリズムは数字を対象にしていますが、計算式に使用されている数字を以下のように文字に変換すれば、文字列でのcheck digitも生成できます。

数字	0	1	2	3	4	5	6	7	8	9
文字	a	b	c	d	e	f	g	h	i	j

特にDammアルゴリズムのラテン方格は位数3~64まで利用可能＝3~64文字までの表が作成可能です。

http://www.md-software.de/math/DAMM_Quasigruppen.txt

なのでシリアルナンバーやクーポンコードで利用する場合、

文字列	利用する表
数字	10 x 10の表
アルファベット	26 x 26の表
アルファベット＋数字	36 x 36の表
アルファベット（大文字小文字）＋数字	62 x 62の表

といった形で使えば良いわけです。

まとめ

バーコードやマイナンバーにもcheck digitが使われており、実は身近なところで活用されています。

ユーザが入力するタイプのサービスとしては

• クレジットカード入力
• クーポンコード
• シリアルナンバー

などの入力ミスチェック・不正値チェックに活用できると思います。

ソース

• Luhnアルゴリズム - Wikipedia
• Dammアルゴリズム - Wikipedia