正则表达式能否匹配有效的信用卡号？

# 正则表达式能否匹配有效的卡号？ 来源：https://abstractnonsense.xyz/blog/2025-08-31-can-a-regex-match-valid-card-numbers/ 2025年8月31日 我们构建了一个确定性有限自动机（https://en.wikipedia.org/wiki/Deterministic_finite_automaton），用于识别符合卢恩校验位算法（https://en.wikipedia.org/wiki/Luhn_algorithm）的任意长度有效卡号集合，并通过“扭曲现实”的方法推导出了一个包含数百万字符的可执行正则表达式。 有时，仅仅一个问题的存在就足以令人着迷。最近，一位同事问我（https://abstractnonsense.xyz/microblog/2025-03-11-irregular-expressions/）是否可能使用卢恩算法（https://en.wikipedia.org/wiki/Luhn_algorithm）在正则表达式中验证信用卡号码，嗯，这彻底让我“上头”了（https://xkcd.com/356/）。我将简要概述这个问题，然后我们一起来探讨解决方案。 为了理解下文，如果你之前接触过确定性有限自动机（DFA）（https://en.wikipedia.org/wiki/Deterministic_finite_automaton）、正则语言（https://en.wikipedia.org/wiki/Regular_language）和模运算（https://en.wikipedia.org/wiki/Modular_arithmetic）等概念，会很有帮助。如果没有，快速浏览一下维基百科页面应该就足以跟上进度。在阐述过程中，我也会用Python代码来配合数学形式化描述，以便更容易理解。 ## 卡号中包含什么？ 信用卡号并非一串无结构的数字。ISO标准（https://en.wikipedia.org/wiki/ISO/IEC_7812）规定了卡号的格式如下： - 一个6位或8位的数字前缀：发卡行识别码（IIN）（https://en.wikipedia.org/wiki/Payment_card_number#Issuer_identification_number_%28IIN%29）。这串数字通常用于在支付界面动态显示对应的卡组织图标。 - 除最后一位外的所有数字代表个人账户ID。这连同CVV和有效期，是支付卡信息中极其敏感的部分，绝对不应在互联网上泄露。本文中的所有示例，我们将使用由Stripe（https://docs.stripe.com/testing#cards）慷慨提供的虚拟卡号。 - 而我们最感兴趣的最后一位是**校验位**，它根据卡号的其他数字通过卢恩算法计算得出，用于检测输入错误。这个校验位就是支付界面在无需向支付网关发送API请求验证卡号是否有效的情况下，就能捕获输入错误的方式。 如果你之前没见过校验位，可以将其视为一种*哈希函数*。其思想是改变一个数字（例如，意外打错）应改变校验位，从而标记出发生了错误。 ## 卢恩算法是什么？ 卢恩算法的一种典型表述（https://rosettacode.org/wiki/Luhn_test_of_credit_card_numbers）如下：从*右向左*遍历数字，交替将数字本身或该数字的“卢恩双倍值”加到一个累加和中。最后，我们检查这个和是否能被10整除。 Python中的卢恩算法如下： ```python def validate_luhn_checkdigit(number: int) -> bool: digits: list[int] = [int(d) for d in reversed(str(number))] luhn_sum = 0 for i, d in enumerate(digits): if i % 2 == 1: luhn_sum += luhn_double(d) else: luhn_sum += d return luhn_sum % 10 == 0 ``` 然而，由于DFA无法*反向*遍历字符串（正则语言在反转操作下是封闭的，但这不足以反转字符串来构建我们的DFA。例如，没有DFA能够识别回文字符串的语言），我们将使用基于数字长度奇偶性的等效*从左到右*表述： ```python def validate_luhn_checkdigit(number: int) -> bool: digits: list[int] = [int(d) for d in str(number)] parity = len(digits) % 2 luhn_sum = 0 for i, d in enumerate(digits): if i % 2 == parity: luhn_sum += luhn_double(d) else: luhn_sum += d return luhn_sum % 10 == 0 ``` “卢恩双倍”函数 $\ell: \texttt{[0-9]} \to \texttt{[0-9]}$ 定义如下： $$ \ell(d) = \begin{cases} 2d & 2d < 10 \\ 2d - 9 & 2d \ge 10 \end{cases} $$ 其中 $\texttt{[0-9]}$ 是整数集合 $\{0, 1, \dots, 9\}$ 的简写。 在Python中这等价于： ```python def luhn_double(d: int) -> int: return 2*d if 2*d < 10 else 2*d - 9 >>> [(d, luhn_double(d)) for d in range(10)] [(0, 0), (1, 2), (2, 4), (3, 6), (4, 8), (5, 1), (6, 3), (7, 5), (8, 7), (9, 9)] ``` 请注意，我们使用“卢恩双倍”函数来防止错误的易位，原因在于它是数字 $\{0, \dots, 9\}$ 的一个*置换*函数。这意味着两个不同的数字输入保证会映射到不同的输出，从而对累加和产生不同的贡献，从而改变校验位。 请注意，尽管DFA是定义在字母表和*字符串*上的，但我们这里的实现是接受一个*整数*。没关系，我们将不那么严格，将整数视为数字字符串。你可能会注意到这忽略了前导零填充（例如，`02` 在Python中不是有效的十进制字面量）或空字符串等退化情况。 ## 我们为什么关心卡号？ 这里的问题是：是否存在一个**正则表达式**，它能在数字序列上计算卢恩算法以匹配*有效*的卡号？ 如果你搜索“*验证信用卡号的正则表达式*”，你会遇到StackOverflow答案（https://stackoverflow.com/a/23231321），这些答案聚合了一系列匹配主要卡组织前缀和长度要求的模式。但这很无聊！那里没有任何保证*校验位是正确的*！ > *关于**有效性**的简短说明。*从现在起，当我提及有效性或正确性时，我纯粹是指一个数字是否满足卢恩校验位算法。我们不考虑卡号是否对应一个真实、活跃且适合支付的账户，我们将此视为一个正交的问题。 现在，在深入探讨这个问题的核心之前，让我们稍作停顿，思考一下为什么考虑这样一项工作是有意义的。首先，这是一个纯粹*有趣*的问题。我认为这是在任何问题上花费时间的必要且充分条件。 但如果这还不够：当权者（https://en.wikipedia.org/wiki/Payment_Card_Industry_Security_Standards_Council）强制推行一项标准（PCI DSS）（https://en.wikipedia.org/wiki/Payment_Card_Industry_Data_Security_Standard），要求你庄严宣誓以正确方式处理卡号详情。许多金融机构会有经过批准的特殊系统来存储和处理卡号详情，而更多系统则不允许。两者绝不应混淆。但你如何确保你的日志没有意外且偷偷地泄露敏感的支付详情？嗯，你绝对、绝对**不应**依赖正则表达式来检测或清除这些公然的违规行为。但如果你想*知道*，你*能*做到吗？ ## 迈向解决方案 我们可以做出一个简单的观察：根据规范，支付卡号有最大长度。由于所有*有限语言*都是*正则*的，这意味着可以简单地枚举所有可能的有效卡号，并用 `|` 将它们合并成一个庞大的正则表达式。对于那些跃跃欲试的人，值得体会一下这项工作的规模。如果我们假设卡号有16位数字，那么有 $10^{15}$ 种序列在末尾具有有效的校验和（我们将忽略前导零或前缀是小集合中可能的IIN之一的情况）。 但更普遍的问题是那个让我夜不能寐的问题： > 是否存在一个DFA，它能识别满足卢恩校验位算法的、以10为基数书写的数字语言 $L$？ 请注意，这个语言是无限的，因为我们不限制数字的长度。如果这样的DFA存在，那么该语言就是正则的（根据克林定理（我提议将此重命名为`Kl(e|n)*'s`定理）），因此*必须*存在一个正则表达式匹配该语言中的所有字符串（对于程序员请注意：遵循将这些集合称为*语言*的术语，语言的元素通常称为*单词*——这与*字符串*可互换使用）。 距离我接触DFA或语言理论已经几年了，起初，我认为这个问题是无法解决的。直到我偶然发现了出色的Arithmancia Automatorum (https://iagoleal.com/posts/automata-divisibility/)，其中呈现了*“为整除性构建最小DFA的极其显式构造”*。理解如何为识别以 $b$ 为基数书写的能被 $m$ 整除的数字语言的DFA构建转移函数，让我看到了希望，即存在一个类似的转移函数可以将卢恩算法表示为DFA。 有趣的是，卢恩发明了一个*机械*装置（卢恩算法的原始出处是一项专利（*US patent 2950048A*），幸运的是，它已被扫描并通过Google Patents (https://patentimages.storage.googleapis.com/ec/2a/f7/b9af046ed26128/US2950048.pdf) 提供为PDF）。来计算校验位。如果我们能机械地实现，那它显然就是为被实现为离散有限自动机而生的！ ## 用于识别卢恩算法的DFA的构造 首先我们注意到，*先验地*，DFA无法知道字符串的奇偶性。但没关系！这只是意味着我们需要将处理*偶数*和*奇数*长度字符串的逻辑编码到DFA的状态中。转移函数必须在DFA消耗每个数字时以某种方式“更新”奇偶性。 这启发了以下的状态构造。我们可以定义两个识别卢恩算法的DFA：一个识别偶数长度字符串的语言，另一个识别奇数长度字符串的语言。由于正则语言在并集下封闭，我们可以将这两个DFA合并成一个DFA。并集构造涉及取每个状态集的笛卡尔积，并创建一个代表并集状态的元组。 第二个观察是，模加法运算分配律良好。这意味着我们可以沿着转移计算模10的部分卢恩和，而不用担心最终答案无效。 让我们现在形式化以上内容。接下来会涉及一些数学——如果你愿意，可以跳到最终的构造和随附代码部分。 令字母表 $\Sigma = \texttt{[0-9]}$ 表示十进制数字集合，状态集 $\mathcal{S} = (E, O) = \texttt{[0-9]} \times \texttt{[0-9]}$ 分别表示偶数长度和奇数长度字符串的模10部分卢恩和。 我们从状态 $s_0 = (0, 0)$ 开始，并接受任何状态 $\{(E, O) \in \mathcal{S} \mid E = 0 \}$。为了在字符串长度奇偶性交替时跟踪我们交替的部分卢恩和，我们定义转移函数 $\delta: \mathcal{S}\times\Sigma \to\mathcal{S}$，从当前状态和新数字 $d$ 到下一个状态如下： $$ \boxed{ \delta((E, O), d) = ((O+d) \bmod 10, \, (E + \ell(d)) \bmod 10) } $$ 其中 $\ell$ 是如上定义的*卢恩双倍*函数。请注意，在每次转移中，$E$ 和 $O$ 部分和会在对中交换！ 为了直观理解其工作原理，请注意转移是*提前*计算的。我们正在定义计算，并将其烘焙到DFA中，作为一种计算图。我认为这是一个极其强大的概念——它表明一个盲目的自动机（或一个非常忙碌的河狸）可以通过简单地遵循“如果在状态 `X` 且下一个符号是 `Y`，则转到状态 `Z`”的规则手册来进行非平凡（但不是任意的！Damnit, Busy Beavers 不能做*所有*事）的计算。毕竟，这不正是计算机所做的吗？在如此深层次上看到数学与计算机科学之间的对应关系，有些深刻的东西。 在Python中，我们可以简洁地定义DFA： ```python def luhn_dfa(number: int) -> bool: word: list[int] = [int(d) for d in str(number)] def transition(state: tuple[int, int], d: int) -> tuple[int, int]: (E, O) = state return ((O + d) % 10, (E + luhn_double(d)) % 10) state = (0, 0) for d in word: state = transition(state, d) return state[0] == 0 ``` 这就是我们得到的！一个拥有100个状态和1000次转移的DFA，它能识别有效的卢恩校验位字符串！ ## 如何为这个DFA构建正则表达式？ 我有点本末倒置了。你点进来可能期望看到一个可以复制粘贴到PII扫描器中立即使用的巨型正则表达式。毕竟，在识别语言的DFA和匹配同一语言中所有字符串的正则表达式之间进行转换在数学上是有保证的。而且我们已经构建了DFA！不幸的是，DFA和相应正则表达式之间的转换过程通常会导致*指数级*的组合爆炸。 现在，本文的早期版本认为这种转换在计算上是不可行的。但是，我还没有放弃与风车搏斗！在与非常乐于助人的Alok Menghrajani (https://www.quaxio.com/) 通过电子邮件和代码交流后，他向我指出了正则表达式操作库 greenery (https://github.com/qntm/greenery)，我现在有了一个正则表达式！ 或者更准确地说，以下代码定义了一个针对偶数和奇数长度卢恩有效字符串的DFA（当然，一旦你有了这两个正则表达式，你可以用 `|` 将它们合并成一个），并使用 greenery 的实现（https://github.com/qntm/greenery/blob/e55c96712677d56ef14664a1595a47fb7f26bc01/greenery/rxelems.py#L260C4-L260C4）将DFA转换为正则表达式。 对于勇敢探索到此的读者，请注意最终生成的正则表达式对*极其庞大*。在我的M1 Air上，每个偶/奇表达式的计算大约需要20分钟，生成的正则表达式分别长达`32,461,605`和`48,236,673`个字符。 ```python # /// script # requires-python = ">=3.11" # dependencies = [ # "greenery", # ] # /// import time from pathlib import Path import greenery def build_luhn_dfa(parity: int) -> greenery.fsm.Fsm: def luhn_double(d: int) -> int: return 2*d if 2*d < 10 else 2*d - 9 def transition(state: tuple[int, int], d: int) -> tuple[int, int]: (E, O) = state return ((O + d) % 10, (E + luhn_double(d)) % 10) states = {(E, O) for E in range(10) for O in range(10)} alphabet = {str(d) for d in range(10)} initial = (0, 0) finals = {(E, 0) for E in range(10)} if parity == 0 else {(0, O) for O in range(10)} transitions = { state: {d: transition(state, int(d)) for d in alphabet} for state in states } return greenery.fsm.Fsm( alphabet=alphabet, states=states, initial=initial, finals=finals, map=transitions, ) start = time.time() dfa_even = build_luhn_dfa(0) dfa_odd = build_luhn_dfa(1) re_even = dfa_even.to_regex() re_odd = dfa_odd.to_regex() total = time.time() - start print(f"Even regex length: {len(re_even)}") print(f"Odd regex length: {len(re_odd)}") print(f"Total computation time: {total:.2f} seconds") Path("re_even.txt").write_text(re_even) Path("re_odd.txt").write_text(re_odd) ```