Luhnアルゴリズムについて学んだのでまとめた

概要

Webアプリ開発をしていると招待コードやクーポンコード等の文字列を作成するという機能が必要になるケースが有るかと思います。
こういったケースでは、打ち間違いによって想定外のコードが入力される(悪意のある入力は除きます)のはできる限り避けたいと思うのですが、
そういったケースに適した誤入力検知アルゴリズムがLuhnアルゴリズムです。

先にアルゴリズムの特徴をまとめます。

• 1桁の誤入力を検知できる
• 隣り合う桁の順番を誤った場合も一部検出できる
• 実装がシンプル
• 実際に、クレジットカード番号や海外の社会保険番号等の作成・検証に利用されている

また、PHPにてコードの作成・検証の実装もしました。
特に作成に関する実装はあまりなかったように思えたためコードを記載しました。

今回は簡単のため、作成する文字列は数値だけとしますが、
これは簡単に拡張できて、文字列に対しても適用することができます(Luhn mod Nアルゴリズム)。

Luhnアルゴリズムって？

Luhnアルゴリズムはチェックサム方式で誤入力を検知するアルゴリズムです。
1桁の打ち間違いと、それ以外のいくつかの誤入力を検知することができます。

例えば、正しいコードが5637なとき、ユーザに5631という文字列を入力されると(7と1の見間違いによる誤入力)、これは誤入力だと検知することができます。

実際の検査の手順は以下の流れになります。

1. コードを右から数えて奇数番目、偶数番目と分類する
2. 偶数番目の数をそれぞれ2倍する
3. 2.にて数値が2桁になった場合、それぞれ別々の数字とする(9*2=18の場合、18でなく1と8とする)
4. それぞれの数をすべて加える
5. その数が10で割り切れれば正しく、そうでない場合は誤っている

先程の例を実際に検討すると、5637では、

奇数番目の数は7,6
偶数番目の数は3,5
2倍すると6,1,0です。
足し合わせると7+6+6+1+0=20で、10で割り切れるため正しいです。
ですが、5631では
奇数番目の数は1,6
偶数番目の数は3,5
2倍すると6,1,0です。
足し合わせると1+6+6+1+0=14で、10で割り切れないため誤りです。

チェックディジット生成＆検証(PHP)

実際に実装しました。
言語はPHPです。

###検査

function check_luhn(string $code) :bool
{
    $len = strlen($code);
    $even = false;
    $sum = 0;
    for ($i = 0; $i < $len; $i++) {
        $c = $code[$len - 1 - $i];
        $d = intval($c); // *
        if ($even) {
            $sum += intdiv(2 * $d, 10) + 2 * $d % 10;
        } else {
            $sum += $d;
        }
        $even = !$even;
    }
    return ($sum % 10 == 0);
}

$test_code = trim(fgets(STDIN));
echo 'code: ' . $test_code . "\n";
if (check_luhn($test_code)) {
    echo 'OK';
} else {
    echo 'NG';
}

###生成

はじめ付加する数を考慮せずに飛ばし、もとの文字列の各桁の総和を10で割ったあまりが0になるような数を付加しました。

function createCode(string $src) :string
{
    $len = strlen($src) + 1; // チェックディジットを含む
    $even = true;
    $sum = 0;
    for ($i = 1; $i < $len; $i++) {
        $c = $src[$len - 1 - $i];
        $d = intval($c); // *

        if ($even) {
            $sum += intdiv(2 * $d, 10) + 2 * $d % 10;
        } else {
            $sum += $d;
        }
        $even = !$even;
    }

    $check_digit = (10 - ($sum % 10));
    return $src . strval($check_digit);
}

$test_src = trim(fgets(STDIN));
echo 'code: ' . $test_src . "\n";
echo createCode($test_src);

ソースコードに多々現れる10という数字を$Nという変数に置き換え、
数値の取り出し(コメントの*の部分)の箇所を少し工夫すれば、
数字以外の文字列にも拡張できそうです。

なぜ検知できるのか

まず、2倍する処理を一旦忘れた場合について考えます。
各桁の総和を10で割った余りが0のコードがあるとします。
このうち、一桁を変更して同じく総和の余りを0にすることを考えますが、
これが可能な数値は0から9までのなかで元の数値以外ありません。
よって、一桁の変更までは誤入力を検知できます。

次に、2倍する処理を考慮することにします。
実は、0から9までのどの数を2倍し、二桁になった場合は各桁を足す
という処理を行っても、0から9にそれぞれ個別の結果が得られます。

元の数	1	2	3	4	5	6	7	8	9
2倍	2	4	6	8	10	12	14	16	18
各桁を足す	2	4	6	8	1	3	5	7	9

結局、2倍して各桁を足す処理は数字を一部入れ替えているだけで、
各数字は1対1対応しているので、1桁の誤入力検知ができるという仕組みです。

そこで、そもそも各桁を普通に足し合わせるだけで1桁の誤検知は可能なのに、
なぜ2倍する必要があるのか、と疑問に思われるかもしれません。
実は偶数のみを2倍することで、順番の入力ミスを防ぐことができます。
具体的には、5637というコードを5367と入力した際、
2倍する処理を行わない場合では誤入力を検知できませんが、
2倍する処理を行うことで誤入力検知ができます。

しかし、一組だけ検知できないケースがあります。

0と9の入れ替わりは区別できない？

実はこのアルゴリズム、0と9が入れ替わった誤入力を検知できません。
例えば109と190はどちらも正しいです。

実は、数字以外にも拡張したluhn mod Nアルゴリズムにおいても、
0とN-1の数が入れ替わっても検知ができません。
(数字のみを扱う場合はN=10となります。)

以下のように数学的に検知不可能だとわかります。

0とN-1が入れ替わったときに、
入れ替わった0の桁とN-1の桁が両方偶数の場合、
0→N-1, N-1→0となっているだけなので総和は変化がないことがわかります。

さて、上記に該当しない、すなわち奇数番目の桁が絡んだものについて考えます。
奇数が絡んだ場合は2倍し、2桁の場合は各桁を足し合わせるということですが、これは数式として以下のように表せます。(上の桁と下の桁の和を足し合わせています)

(2 (N - 1) - (2 (N - 1)) \% N) \div N + (2 (N - 1) )\%N

これを変形すると

\begin{align}
&= (2 N  - 2 - (N + N - 2) \% N) \div N + (N + N - 2) \% N \\
&= (2 N - 2 - (N - 2)) \div N + N - 2 \\
&= N \div N + N - 2 \\
&= N - 1
\end{align}

となり、結局N-1の桁は2倍する処理を経てもN-1です。

以上より、0とN-1の入れ替えが発生しても、N-1増えてN-1減るだけで総和は変わりません。

すなわち、Luhnアルゴリズムにおいて、0と9の入れ替わりは検知できないということになります。