|
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アルゴリズムは、チェックディジットを含む数が正しいかどうかを検証する。チェックディジットは通常、一意な番号に付与され、チェックディジットを含めた全体を認証番号などに使う。この番号は以下のようにして検証できる。
例として、49927398716 という番号を検証する場合を考える。
実装例下記のPythonの関数はLuhnアルゴリズムを実装したもので、入力された数字の配列がLuhn番号として正しければ 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
他の実装例
脚注
|