Thuật toán Luhn

Thuật toán Luhn hoặc công thức Luhn, cũng được biết là thuật toán "modulus 10" hay "mod 10", nó được đặt theo tên người sáng tạo ra nó, nhà khoa học của IBM Hans Peter Luhn, là một công thức tổng kiểm đơn giản được sử dụng để xác thực nhiều loại số nhận dạng, chẳng hạn như số thẻ tín dụng, IMEI, National Provider Identifier tại Mỹ, mã Social Insurance Numbers tại Canada, Số ID tại Israel, Nam Phi, Số an sinh xã hội Hy Lạp (ΑΜΚΑ), và các mã khảo sát xuất hiện trên biên lai của McDonald's, Taco Bell, và Tractor Supply Co. Nó được mô tả trong bằng sáng chế tại Mỹ số 2,950,048, nộp vào ngày 6 tháng 1 năm 1954 và được cấp vào ngày 23 tháng 8 năm 1960..

Thuật toán này thuộc phạm vi công cộng và được sử dụng rộng rãi ngày nay. Nó được quy định trong ISO/IEC 7812-1. Nó không có ý định là một hàm băm bảo mật bằng mật mã; nó được thiết kế để bảo vệ chống lại các lỗi vô ý, không phải các cuộc tấn công độc hại. Hầu hết các thẻ tín dụng và nhiều số nhận dạng chính phủ sử dụng thuật toán như một phương pháp đơn giản để phân biệt các số hợp lệ với các số bị nhầm hoặc không chính xác.

Mô tả

Thuật toán dùng để tính toán số này như sau:

Bước 1: Nhân đôi giá trị của những số ở vị trí chẵn tính từ phải sang bao gồm cả số Check Digit (là các số ở vị trí 2, 4, 6... 14), trong đó số thứ 1 là số ngoài cùng phía bên phải của chuỗi số IMEI.

Bước 2: Cộng dồn tất cả các chữ số riêng lẻ của các số thu được ở bước 1, cùng với các số ở vị trí lẻ (là các số ở vị trí 1, 3, 5,...,13) trong chuỗi số IMEI.

Bước 3: Nếu kết quả ở bước 2 là một số chia hết cho 10 thì số A sẽ bằng 0. Nếu kết quả ở bước 2 không chia hết cho 10 thì A sẽ bằng số chia hết cho 10 lớn hơn gần nhất trừ đi chính kết quả đó, tức là tổng các số kể cả A phải chia hết cho 10.

Ví dụ: số IMEI là 350880-10-195032-A, trong đó A là số kiểm tra cần phải tính để tổng 3+5*+0+8*+8+0*+1+0*+1+9*+5+0*+3+2*+A chia hết cho 10

Bước 1: 4, 0, 18, 0, 0, 16, 10

Bước 2: (4 + 0 + (1 + 8) + 0 + 0 + (1 + 6) + (1 + 0)) + (3 + 0 + 8 + 1 + 1 + 5 + 3) = 42

Bước 3: A = 50 – 42 = 8

Như vậy số IMEI hợp lệ phải là 350880-10-195032-8.

Điểm mạnh và điểm yếu

Thuật toán Luhn sẽ phát hiện bất kỳ lỗi một chữ số nào, cũng như gần như tất cả các chuyển vị của các chữ số liền kề.Tuy nhiên, nó sẽ không phát hiện chuyển vị của dãy hai chữ số 09 thành 90 (hoặc ngược lại). Nó sẽ phát hiện 7 trong số 10 lỗi số kép có thể xảy ra (nó sẽ không phát hiện ra 22 ↔ 55, 33 ↔ 66 hay 44 ↔ 77).

Các thuật toán kiểm tra số phức tạp khác (giống như thuật toán Verhoeff và thuật toán Damm) có thể phát hiện thêm các lỗi sao chép. Thuật toán Luhn mod N là một phần mở rộng hỗ trợ các chuỗi không có số.

Bởi vì thuật toán hoạt động trên các chữ số theo cách từ phải sang trái và các chữ số 0 chỉ ảnh hưởng đến kết quả nếu chúng gây ra dịch chuyển vị trí, việc đệm số 0 bắt đầu một chuỗi số không ảnh hưởng đến phép tính. Do đó, các hệ thống đệm đến một số chữ số cụ thể (ví dụ bằng cách chuyển đổi 1234 thành 0001234) có thể thực hiện xác thực Luhn trước hoặc sau khi đệm và đạt được kết quả tương tự.

Chuẩn bị một số có độ dài từ 0 đến vị trí lẻ khiến nó xử lý số từ trái sang phải thay vì phải sang trái, nhân đôi các chữ số ở vị trí lẻ. Thuật toán xuất hiện trong United States Patent cho một thiết bị cơ khí cầm tay để tính toán checksum. Do đó, nó được yêu cầu khá đơn giản. Thiết bị lấy mod 10 tổng bằng phương tiện cơ học. Các chữ số thay thế, nghĩa là, kết quả của thủ tục nhân đôi và giảm, không được tạo ra một cách cơ học. Thay vào đó, các chữ số được đánh dấu theo thứ tự hoán vị trên thân máy.

Triển khai giả mã

function luhnAlgorithm(cardNumber) {
  const digits = cardNumber.toString().split('').map(Number);

  let sum = 0;
  let isAlternate = false;

  for (let i = digits.length - 1; i >= 0; i--) {
    let digit = digits[i];

    if (isAlternate) {
      digit *= 2;
      if (digit > 9) {
        digit -= 9;
      }
    }

    sum += digit;
    isAlternate = !isAlternate;
  }

  return sum % 10 === 0;
}
// Ví dụ sử dụng
const cardNumber = '4242424242424242';
const isValid = luhnAlgorithm(cardNumber);

console.log(`Số thẻ ${cardNumber} có hợp lệ: ${isValid}`);

Nơi sử dụng

Ngoài số thẻ tín dụng, thuật toán này cũng được sử dụng để tính toán số kiểm tra trên số thẻ SIM.

Ví dụ. Lấy số sê-ri SIM (còn được gọi là ICCID) 89610195012344000018

Số được in trên thẻ SIM thường là một tập hợp con của chuỗi này.

Hai chữ số cuối cùng là chữ số kiểm tra.

checkLuhn("896101950123440000") sẽ trả về 1 - số kiểm đầu tiên

checkLuhn("950123440000") sẽ trả về 8 - số kiểm thứ hai. Số rút ngắn này, theo sau là số kiểm của nó được in trên chính thẻ SIM.

Xem thêm

• Checksum
• Thuật toán Luhn mod N

Liên kết ngoài

• Implementation in 88 languages on the Rosetta Code project