Luhn algoritması - Luhn algorithm

Vikipedi, özgür ansiklopedi

Luhn algoritması veya Luhn formül , aynı zamanda " modülü 10" ya da "mod 10" algoritması yaratıcısı IBM bilim adını, Hans Peter Luhn , basit bir kontrol toplamı , örneğin kimlik numarası, çeşitli doğrulamak için kullanılan formül kredi kart numaraları , IMEI numaraları , Amerika Birleşik Devletleri'ndeki Ulusal Sağlayıcı Kimlik numaraları , Kanada Sosyal Sigorta Numaraları , İsrail Kimlik Numaraları, Güney Afrika Kimlik Numaraları, Yunan Sosyal Güvenlik Numaraları (ΑΜΚΑ) ve McDonald's , Taco Bell ve Tractor Supply'de görünen anket kodları Şti. Makbuzları. 6 Ocak 1954'te dosyalanan ve 23 Ağustos 1960'da verilen ABD Patenti No. 2.950.048'de açıklanmaktadır .

Algoritma kamu malıdır ve günümüzde yaygın olarak kullanılmaktadır. ISO / IEC 7812 -1'de belirtilmiştir . Kriptografik olarak güvenli bir hash işlevi olması amaçlanmamıştır ; kötü niyetli saldırılara değil, yanlışlıkla yapılan hatalara karşı koruma sağlamak için tasarlanmıştır. Çoğu kredi kartı ve birçok resmi kimlik numarası, algoritmayı, geçerli sayıları yanlış yazılmış veya başka şekilde yanlış sayılardan ayırmanın basit bir yöntemi olarak kullanır.

Açıklama

Formül, bir sayıyı , tam hesap numarasını oluşturmak için genellikle kısmi bir hesap numarasına eklenen kontrol basamağına göre doğrular . Bu numara aşağıdaki testi geçmelidir:

  1. En sağdaki basamaktan (kontrol basamağı hariç) ve sola hareket ederek, her ikinci basamağın değerini ikiye katlayın. Kontrol basamağı ne iki katına çıkarılır ne de bu hesaplamaya dahil edilir; iki katına çıkan ilk rakam, kontrol basamağının hemen solunda bulunan rakamdır. Bu ikiye katlama işleminin sonucu 9'dan büyükse (örneğin, 8 × 2 = 16), sonucun rakamlarını ekleyin (örneğin, 16: 1 + 6 = 7, 18: 1 + 8 = 9) veya eşdeğer olarak , sonuçtan 9 çıkarın (örneğin, 16: 16 - 9 = 7, 18: 18 - 9 = 9).
  2. Tüm basamakların toplamını alın (kontrol basamağı dahil).
  3. Toplam modulo 10, 0'a eşitse (toplam sıfırla bitiyorsa), sayı Luhn formülüne göre geçerlidir; aksi takdirde geçerli değildir.

Kontrol basamağının hesaplanması için örnek

7992739871x biçiminde bir kontrol basamağı eklenecek "7992739871" hesap numarası örneğini varsayalım:

7 9 9 2 7 3 9 8 7 1 x
Birbirini ikiye katlayın 7 18 9 4 7 6 9 16 7 2 x
Toplam rakamlar 7 9 (1 + 8) 9 4 7 6 9 7 (1 + 6) 7 2 x

Üçüncü satırdaki tüm rakamların toplamı, yani toplam rakamların toplamı 67'dir.

Kontrol basamağı (x), toplam basamaklarının toplamı hesaplanarak ve ardından modulo 10 değerinin 9 katı hesaplanarak elde edilir (denklem formunda, ((67 × 9) mod 10)). Algoritma biçiminde:

  1. Toplam rakamların toplamını hesaplayın (67).
  2. 9 (603) ile çarpın.
  3. 603 mod 10 daha sonra kontrol basamağı olan 3'tür. Böylece, x = 3 .

(Alternatif yöntem) Kontrol basamağı (x), diğer basamakların (üçüncü sıra) toplamının hesaplanması ve ardından 10'dan birimler basamağının çıkarılmasıyla elde edilir (67 => Birimler basamak 7; 10-7 = kontrol basamağı 3; denklem formunda , 10 - (67 mod 10)). Algoritma biçiminde:

  1. Toplam rakamların toplamını hesaplayın (67).
  2. Birimler rakamını (7) alın.
  3. Birimler basamağını 10'dan çıkarın.
  4. Sonuç (3) kontrol basamağıdır. Rakamların toplamının 0 ile bitmesi durumunda, 0 kontrol basamağıdır.

Bu, tam hesap numarasını 79927398713 olarak okur.

Kontrol basamağını doğrulama örneği

79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 sayılarının her biri aşağıdaki şekilde doğrulanabilir.

  1. En sağdan her saniye hanenin iki katı: (1 × 2) = 2, (8 × 2) = 16, (3 × 2) = 6, (2 × 2) = 4, (9 × 2) = 18
  2. Tüm tek tek basamakları toplayın (parantez içindeki rakamlar Adım 1'deki ürünlerdir): x (kontrol basamağı) + (2) + 7 + (1 + 6) + 9 + (6) + 7 + (4) + 9 + (1 + 8) + 7 = x + 67.
  3. Toplam 10'un katı ise, hesap numarası muhtemelen geçerlidir. Not 3 bir miktar (70) yalnızca geçerli haneli 10 bir çok olmasıdır.
  4. Dolayısıyla bu hesap numaralarının tümü, muhtemelen doğru kontrol basamağına sahip olan 79927398713 dışında geçersizdir.

Alternatif olarak, sanki henüz hesaplanmamış gibi zaten mevcut olan sağlama toplamını yok sayarak aynı sağlama toplamı oluşturma algoritmasını kullanabilirsiniz. Daha sonra sağlama toplamını hesaplayın ve bu hesaplanan sağlama toplamını kredi kartı numarasıyla birlikte verilen orijinal sağlama toplamıyla karşılaştırın. Dahil edilen sağlama toplamı hesaplanan sağlama toplamıyla eşleşiyorsa, sayı geçerlidir.

Güçlülükler ve zayıflıklar

Luhn algoritması, herhangi bir tek basamaklı hatayı ve aynı zamanda bitişik basamakların neredeyse tüm aktarımlarını algılayacaktır. Bununla birlikte, 09 ila 90 arasındaki iki basamaklı dizinin (veya tersi) transpozisyonunu algılamayacaktır . Olası ikiz hataların çoğunu algılayacaktır ( 22 55 , 33 66 veya 44 77'yi algılamayacaktır ).

Diğer, daha karmaşık check-digit algoritmaları ( Verhoeff algoritması ve Damm algoritması gibi ) daha fazla transkripsiyon hatasını tespit edebilir. Luhn mod N algoritması sayısal olmayan dizeleri destekleyen bir uzantısıdır.

Algoritma rakamlar üzerinde sağdan sola bir şekilde çalıştığından ve sıfır basamaklar sonucu yalnızca konumda kaymaya neden olurlarsa etkilediğinden, bir sayı dizisinin başlangıcını sıfır doldurmak hesaplamayı etkilemez. Bu nedenle, belirli sayıda basamağa dolduran sistemler (örneğin 1234'ü 0001234'e dönüştürerek), dolgudan önce veya sonra Luhn doğrulamasını gerçekleştirebilir ve aynı sonucu elde edebilir.

Tek-uzunluklu sayıların başına 0 eklemek, sayıyı sağdan sola değil soldan sağa doğru işlemeyi mümkün kılar ve tek basamaklı basamakları ikiye katlar.

Algoritma, sağlama toplamını hesaplamak için elde tutulan, mekanik bir aygıt için bir Birleşik Devletler Patentinde göründü. Bu nedenle oldukça basit olması gerekiyordu. Cihaz, mod 10 toplamını mekanik yollarla aldı. İkame basamak olan, çift ve azaltmak prosedürü sonuçları, mekanik olarak üretilmemiştir. Aksine, rakamlar makinenin gövdesi üzerinde permütasyon sırasına göre işaretlenmiştir.

Sözde kod uygulaması

function checkLuhn(string purportedCC) {
    int nDigits := length(purportedCC)
    int sum := integer(purportedCC[nDigits-1])
    int parity := nDigits modulus 2
    for i from 0 to nDigits - 2 {
        int digit := integer(purportedCC[i])
        if i modulus 2 = parity
            digit := digit × 2
        if digit > 9
            digit := digit - 9 
        sum := sum + digit
    }
    return (sum modulus 10) = 0
}

Kullanım

Kredi kartı numaralarına ek olarak, bu algoritma aynı zamanda SIM kart numaraları üzerindeki kontrol basamağını hesaplamak için de kullanılır.

Referanslar

Dış bağlantılar