错误检测(Error Detection) 是计算机科学和通信应用中一个非常基础的技术,它可以被用来校验信息传输过程中的完整性和可靠性。今天介绍一个非常基础的校验算法:Luhn 算法。该算法被广泛的应用于美国的信用卡以及金融产品中的证券代码当中。

Luhn 算法是以他的发明者 Hans Peter Luhn 命名而来,Luhn 算法是他的 80 余种专利中的一个。Luhn 同时也是哈希算法改进成现今这样分 bucket 存储的首批倡导者之一。

由于应用的广泛性,这种算法被设计的非常简单高效。最原始的 Luhn 算法只能被作用于数字(0~9)的任意组合。

假设有一串这样的数字 592648,我们需要计算它的校验位数字 592648x 中的 x

  1. 从这串数字的最后一位开始算起(比如例子中的最后一位 8),每隔一位将其数字乘以 2。
  2. 把得到的新的数字相加。如果由于上一步得到了超过 10 的数字,那么就将其十位与个位相加。
  3. 用 10 减去上一步得到的和的个位数,这就是我们所要求的 x
原始数字 5 9 2 6 4 8
隔一位乘以 2 5 18 2 12 4 16
超过 10 的十位与个位相加 5 9 2 3 4 7

将上述最终得到的数字相加得到 30,用 10 减去个位数 0 得到 10,那么 x = 0

这么做的好处是,如果我得到了一串包含校验码的数字 5916480,我可以根据算法得到最后一位不应该是 0,那么很有可能这串数字在传输过程中出现了错误。

不考虑性能以及完整性,一个简单的 C# 演示代码可以写成:

private static char GetForDigits(string digits)
{
	var index = 0;
	var sum = 0;
	for (var i = digits.Length - 1; i >= 0; i--)
	{
		var c = Convert.ToInt32(char.GetNumericValue(digits[i]));
		c = index % 2 == 0 ? c * 2 : c;
		sum += c / 10 + c % 10;
		index++;
	}

	var result = 10 - sum % 10;
	if (result == 10)
	{
		result = 0;
	}

	return char.Parse($"{result}");
}

如果需要检测一串包含校验码的数字是否完整,可以

private static bool CheckDigits(string digits)
{
	return GetForDigits(new string(digits.Take(digits.Length - 1).ToArray())) == digits[digits.Length - 1];
}

Luhn 算法在日常生活中被广泛应用,然而它也有很多的缺陷。

比如有几种特殊的 case 它是检测不出来的。一串数字中这样的组合被另外一种组合篡改,是不影响最终的校验码的:09-9022-5533-6644-77。以及以 0 开头的数字其 0 是被忽略的,也就是无论多少个 0 都是同样的校验码。

当然,只能针对数字是不够的,所以它也产生了一些变种以及改进算法,这里不做展开了。

需要指出的是,Luhn 算法并不是用来保证信息是否被篡改,比如被恶意修改之类的,它是一种非常简单的对于不经意或者说是无意的信息丢失进行检验的算法。

(本文完)