Luhnアルゴリズム

Luhnアルゴリズム（Luhn algorithm, ルーン・アルゴリズム）は、様々な識別番号の認証に使われている単純なチェックサム方式。MOD-10アルゴリズムとも。クレジットカード番号、IMEI番号、en:National Provider Identifier（アメリカでの医療機関の識別番号）、カナダ社会保険番号（Social Insurance Number）などで使われている。IBMの科学者ハンス・ピーター・ルーン（英語版）が1954年 1月6日に特許を申請し、1960年 8月23日に発効した^[1]。

アルゴリズムはパブリックドメインになっており、今日では広く利用されている。ISO/IEC 7812-1^[2] に詳細に記されている。暗号学的ハッシュ関数としては使えない。

記入ミスやタイプミスを検出するためのもので、クレジットマスターによる悪意ある攻撃を防ぐものではない。多くのクレジットカードや各国政府が発行する識別番号で、ランダムな数値群から正しい番号を区別するチェックディジットとして、単純な手法としてこのアルゴリズムを使っている。

利点と欠点

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

他のもっと複雑なチェックディジットアルゴリズム（たとえばDammアルゴリズムやヴァーヘフアルゴリズム）では、より多くの転記ミスを検出できる。また、Luhnアルゴリズムを数字以外の文字列を扱えるよう拡張した Luhn mod N algorithm もある。

このアルゴリズムは右から左に数字を操作していき、ゼロは途中にある場合だけ結果に影響するため、番号の桁数が足りない場合に先頭にゼロを補完しても影響は生じない。したがって、ある数が番号の規定桁数になるように、例えば 1234 を 00001234 としても、Luhnアルゴリズムはこのどちらについても同じ結果となる。

アメリカ合衆国の特許は、このアルゴリズムにしたがってチェックサムを計算する装置を対象としていた。その装置は各桁の10を法とする総和を機械的手段で計算しており、より単純な方法が求められた。特許では偶数番目の数字を2倍して置き換えるという部分を機械で行っていない。その代わりに桁に印をつけて順序を入れ替えるという方法を取っている。

非形式的解説

Luhnアルゴリズムは、チェックディジットを含む数が正しいかどうかを検証する。チェックディジットは通常、一意な番号に付与され、チェックディジットを含めた全体を認証番号などに使う。この番号は以下のようにして検証できる。

右端のチェックディジットを1番目として、偶数番目の桁を2倍にする。
2倍にしていない桁も含め、各数字の総和を求める（2倍にした桁が2桁になった場合は、それぞれを別々の数字として加える）。
この総和の下1桁が0なら（つまり、10で割り切れる場合）、この番号はLuhnアルゴリズムでは正しく、そうでない場合は正しくない。

例として、49927398716 という番号を検証する場合を考える。

右端から偶数番目の桁をそれぞれ2倍する: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
それぞれの数字の総和を計算する（括弧で囲まれた数字は上のステップで2倍した桁）: 6 + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 4 = 70
10で割りきれるか調べる: 70 mod 10 = 0 なので、この番号は正しい。

実装例

下記のPythonの関数はLuhnアルゴリズムを実装したもので、入力された数字の配列がLuhn番号として正しければ True を返し、さもなくば False を返す。入力配列の各要素は数字1桁で表せる必要があり 0 以上 9 以下の整数でなければならない。この実装では配列を逆転させ（reversed）、ブーリアン変数 alt をループするごとに反転させて奇数番目か偶数番目かを判定している。

def check_number(digits):
    _sum = 0
    alt = False
    for d in reversed(digits):
        assert 0 <= d <= 9
        if alt:
            d *= 2
            if d > 9:
                d -= 9
        _sum += d
        alt = not alt
    return (_sum % 10) == 0

他の実装例

PostgreSQL、Transact-SQL
C言語、C#、VB.Net
Java、Java
Actionscript2、JavaScript、Prototype JavaScript、JavaScript
Perl、Perl
Python、Python
Ruby、Ruby
ColdFusion
FileMaker Pro
F#
Common Lisp
Haskell
MS Excel
PowerShell
ProvideX
PHP
PureBasic
VBScript (ASP)
XSLT
C, awk and Python

脚注

^ アメリカ合衆国特許第 2,950,048号, Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.
^ ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system

[1] アメリカ合衆国特許第 2,950,048号, Computer for Verifying Numbers, Hans P. Luhn, August 23, 1960.

[2] ISO/IEC 7812-1:2006 Identification cards -- Identification of issuers -- Part 1: Numbering system

[1]

[2]