盧恩算法
外觀
盧恩算法(英語:Luhn algorithm),也稱為「模10」(Mod 10)算法,是一種簡單的校驗和算法,一般用於驗證身份識別碼,例如發卡行識別碼、國際行動裝置識別碼,美國國家提供商標識號碼,或是加拿大社會保險號碼。該算法由IBM科學家漢斯·彼得·盧恩創造,專利於1954年1月6日申請,1960年8月23日頒證,美國專利號2950048[1]。
該算法現已屬於公有領域並得到了廣泛的應用,例如ISO/IEC 7812-1[2]。它不是一種安全的加密哈希函數,設計它的目的只是防止意外出錯而不是惡意攻擊。
描述
[編輯]盧恩算法會通過校驗碼對一串數字進行驗證,校驗碼通常會被加到這串數字的末尾處,從而得到一個完整的身份識別碼。
我們以數字「7992739871」為例,計算其校驗位,設校驗位為X並添加至數列末位,即7992739871X:
- 從校驗位開始,從右往左,偶數位乘2(例如,7*2=14),然後將兩位數字的個位與十位相加(例如,10:1+0=1,14:1+4=5);
- 把得到的數字加在一起(本例中得到67);
- 將數字的和取模10(本例中得到7),再用10去減(本例中得到3),得到校驗位。
原始數字 | 7 | 9 | 9 | 2 | 7 | 3 | 9 | 8 | 7 | 1 | x |
---|---|---|---|---|---|---|---|---|---|---|---|
偶數位乘2 | 7 | 18 | 9 | 4 | 7 | 6 | 9 | 16 | 7 | 2 | x |
將數字相加 | 7 | 9 | 9 | 4 | 7 | 6 | 9 | 7 | 7 | 2 | =67 |
再用10去減得到校驗位 | 3 |
另一種方法是:
- 從校驗位開始,從右往左,偶數位乘2,然後將兩位數字的個位與十位相加;
- 計算所有數字的和(67);
- 乘以9(603);
- 取其個位數字(3),得到校驗位。
優缺點
[編輯]盧恩算法可以發現某一位的錯誤。 盧恩算法幾乎可以發現所有由於鄰位上數字被交換產生的錯誤。 但是,它只能發現數字交換產生的錯誤中的7/10,不會發現22 ↔ 55, 33 ↔ 66 或 44 ↔ 77。
代碼實現
[編輯]Java
[編輯]/**
* 校验位字符集
*/
private static char[] CHECKS = "0987654321".toCharArray();
public static boolean isValidLuhn(String number) {
if (number == null) {
return false;
}
char[] chs = number.toCharArray();
int count = 0;
for (int i = chs.length - 2, k = 1; i >= 0; i--, k++) {
// 不是数字字符时直接返回 false
if (chs[i] < '0' || chs[i] > '9') {
return false;
}
// 偶位数字 * 2,奇位不乘
int num = (chs[i] - '0') << (k & 1);
// 累加
count += num % 10 + num / 10;
}
// 对校验位进行比对
return (chs[chs.length - 1] == CHECKS[count % 10]);
}