Thuật toán Luhn là gì? Chi tiết về Thuật toán Luhn mới nhất 2022

Thuật toán Luhn là gì?

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.[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 Luhn

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 (Check Digit).

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ả đó.
Ví dụ: số IMEI là 350880-10-195032-A, trong đó A là số kiểm tra cần phải tính toán. Bước 1: 10, 16, 0, 0, 18, 0, 4 Bước 2: (1 + 0 + 1 + 6 + 0 + 0 + 1 + 8 + 0 + 4) + (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.

Có thể bạn quan tâm  Vẻ đẹp cuộc sống là gì? Chi tiết về Vẻ đẹp cuộc sống mới nhất 2021

Điểm mạnh và điểm yếu của Thuật toán Luhn

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[2] 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.

Cách hoạt động của thuật toán Luhn

Thuật toán công thức LUHN được phát triển bởi một Nhà Khoa học Máy tính người Đức tên là Hans Peter Luhn vào năm 1954 khi đang làm việc với tư cách là một nhà nghiên cứu tại IBM. Các hoạt động chính xác của thuật toán dựa trên số học mô-đun, một kỹ thuật toán học được phát triển bởi Carl Friedrich Gauss vào đầu thế kỷ 19. Mặc dù các hoạt động chi tiết của nó khá phức tạp, nó được biết đến nhiều nhất vì cho phép máy tính nhanh chóng đánh giá xem số thẻ tín dụng mà khách hàng cung cấp có chính xác hay không.

Có thể bạn quan tâm  Nhà thờ chính tòa là gì? Chi tiết về Nhà thờ chính tòa mới nhất 2021

Cách thức hoạt động là áp dụng một loạt phép tính cho số thẻ tín dụng đã cho, cộng kết quả của những phép tính đó và kiểm tra xem số kết quả có khớp với kết quả mong đợi hay không. Nếu đúng, thì số tín dụng được coi là hợp lệ. Nếu không, thuật toán sẽ từ chối số thẻ tín dụng, cho biết rằng người dùng đã mắc lỗi khi nhập số.

Từ quan điểm của khách hàng, chúng tôi sử dụng Thuật toán Luhn mọi lúc mà không hề nhận ra. Khi đặt hàng trực tuyến hoặc sử dụng thiết bị đầu cuối tại điểm bán hàng (POS) của người bán, hệ thống máy tính có thể nhanh chóng cho biết khi nào chúng tôi nhập sai thông tin của mình. Điều này là do Thuật toán Luhn đã được kết hợp vào lập trình của các hệ thống đó. Nếu không có nó, chúng tôi sẽ cần phải đợi cho đến khi toàn bộ đơn đặt hàng được gửi trước khi nhận ra liệu giao dịch có được chấp thuận hay không. Nói cách khác, Thuật toán Luhn giúp chúng tôi nhanh chóng xác định lỗi của người dùng và từ đó đẩy nhanh tốc độ giao dịch.

Ví dụ trong thế giới thực về thuật toán Luhn

Một trong những khái niệm trọng tâm trong Thuật toán Luhn là việc sử dụng cái gọi là “số kiểm tra”. Các chữ số này bao gồm các số được chèn vào dãy số rộng hơn để giúp xác minh hoặc “kiểm tra” xem toàn bộ số có xác thực hay không.

Có thể bạn quan tâm  Linh Ẩn tự là gì? Chi tiết về Linh Ẩn tự mới nhất 2021

Đối với thẻ tín dụng, số kiểm tra bao gồm một chữ số duy nhất được in ở cuối số thẻ tín dụng. Thay vì được chọn cụ thể bởi công ty phát hành thẻ tín dụng, thay vào đó, số kiểm tra được tự động xác định bởi Thuật toán Luhn, dựa trên các số đứng trước trong dãy số. Khi người dùng nhập số thẻ tín dụng của họ để hoàn tất giao dịch, phần mềm xử lý thanh toán có thể sử dụng Thuật toán Luhn để phát hiện xem số được chỉ định có chính xác hay không, một phần dựa trên số kiểm tra của nó.

Ngày nay, Thuật toán Luhn được tích hợp vào các ngôn ngữ lập trình và thư viện mã phổ biến, nên việc đưa xác minh số nhận dạng dựa trên Luhn vào các ứng dụng phần mềm mới là tương đối dễ dàng.

Triển khai giả mã

function checkLuhn(string purportedCC) {
    int sum := integer(purportedCC[length(purportedCC)-1])
    int nDigits := length(purportedCC)
    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
}

Nơi sử dụng Thuật toán Luhn

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.

Tham khảo

  1. ^ ISO/IEC 7812-1:2017 Identification cards — Identification of issuers — Part 1: Numbering system
  2. ^ US Patent 2,950,048 – Computer for Verifying Numbers, Hans P Luhn, August 23, 1960

Từ khóa:

thuật toán luhn
giải thuật luhn
luhn
check digit là gì
luhn check
check luhn

LADIGI – Công ty dịch vụ SEO LADIGI giá rẻ, SEO từ khóa, SEO tổng thể cam kết lên Top Google uy tín chuyên nghiệp, an toàn, hiệu quả.

Nguồn: Wikipedia

Scores: 4.1 (110 votes)

100 lần tự tìm hiểu cũng không bằng 1 lần được tư vấn