刘巍然-学酥，Ph.D/公钥加密/数据隐私保护/Java/听译 阅读原文 我本来计划把身份证号的校验码算法的分析放在我正在撰写的知乎电子书《质数了不起》的纸质扩展版书籍中的，但不曾想类似的问题推到了时间线上。思前想后，还是准备优先以解答问题为主。本答案部分内容的修改版本将会放在纸质扩展版书籍中。 本答案写的有点乱，并且有点偏数学。所以还是等我纸质版书写完，再看纸质版上的原理解释吧… 需要的数学知识 身份证验证码需要这样一个数学原理：如果两个正整数 、 互质，则一定存在两个整数 、（不一定是正整数），使得： 在此我就不严格证明这个性质了，据说现在参加奥林匹克数学竞赛的初中生似乎就要学习这个数学原理。我们接下来要了解，从这个数学原理出发，能得到哪些有意思的性质。 我们假设 ，现在，令上式左右两边同时取模 （简单来说，对一个整数取模 ，是指求这个整数除以 后所得到的余数），得到： 前面提到，模运算就是求余数。注意到由于 都是整数，所以 除以 的余数一定为 0，即有：。所以我们可以得到： 虽然不太直观，但我们可以得到这样一个有趣的性质：如果 互质，则一定存在一个 的数，使得在模 条件下，这个数和 相乘的结果为 1。注意到这个性质和我们一般情况下认为的「倒数」概念很像。本来嘛，倒数的定义就是和原数相乘等于 1 的数，只不过这里是在模 的条件下等于 1 的。在模 的条件下，一般会把 写成 。 身份证号校验算法 先来看看身份证号的校验算法。首先，对身份证号的各个位设置一个对应的「权重值」。这个所谓的权重值对于所有的身份证号都是一样的。根据《中华人民共和国国家标准 GB11643-1999》，每一位对应的「权重值」如下表所示： 序号 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 权重 07 09 10 05 08 04 02 01 06 03 07 09 10 05 08 04 02 01 随后，把身份证号的各个位乘以对应的权重值后（如果末位是 X，则对应位为 10），把结果相加模 11，如果余数为 1，则身份证号验证通过。用数学公式表示为：令身份证号从前至后的 18 位分别为 ，身份证号对应位的权重分别为 ，则校验算法验证下述等式是否成立： （为了论述方便，后面的公式中会略去 mod 11 符号）我们用《中华人民共和国国家标准 GB11643-1999》中给出的例子来验证一下。例子中给出的居民身份证号为 11010519491231002X。各个位的序号、权重、号码如下表所示： 序号 18 17 16 15 14 13 12 11 10 09 08 07 06 05 04 03 02 01 权重 07 09 10 05 08 04 02 01 06 03 07 09 10 05 08 04 02 01 号码 01 01 00 01 00 05 01 09 04 09 01 02 03 01 00 00 02 10 验证式为： 身份证号校验算法的功能 前面的很多答主也提到了，身份证号校验算法的功能有 3 个： 如果身份证号码的其中一位填错了（包括最后一个校验位），则校验算法可以检测出来。 如果我们知道身份证号码的哪一位填错了，应用校验算法可以快速得知填错那一位正确的值应该是多少。（感谢 @刘天任 指出，这条性质实际上是第 1 条性质的推论。从编码理论角度，身份证号校验码并不是纠错码，纠错码应该可以「不知道具体哪位错了的条件下纠正错误」。不过，末尾「扩展」部分会用到这个推论，所以这里仍然保留。） （ @刘天任 给出）如果身份证号的相邻 2 位填反了，则校验算法可以检测出来。 下面，我们用前面提到的原理分析一下为何有上述 3 个性质。 身份证号验证算法背后的数学原理 如果身份证号码的其中一位填错了（包括最后一个校验位），则校验算法可以检测出来 相信大家很容易了理解第一个功能：如果身份证号中有一位输入错误，则校验等式左边的结果一定会发生变化，校验等式就不成立了。 如果我们知道身份证号码的哪一位填错了，应用校验算法可以快速得知填错那一位正确的值应该是多少 第二个功能需要稍微分析一下。假定我们已经知道第 位输入错误了，而其它位都是正确的，实际上我们需要求解一个模 11 下的方程： 整理一下，有： 注意前面的性质，由于 11 是个质数，而根据设置的权重值，，因此我们一定能够找到一个 ，使得 。因此，我们在方程两边同时乘以 ，得到： 根据这个公式，我们可以把所有对应的数字代入到等式右边，从而得到输入错误位所对应的正确结果是多少。 如果身份证号的相邻 2 位填反了，则校验算法可以检测出来。 我们来看看，如果填反了会发生什么情况。假设两个相邻位为 ，如果填反了且校验等式仍然验证通过，则一定有： 整理一下，得到： 我们来观察一下《中华人民共和国国家标准 GB11643-1999》的规范。仔细观察会发现，从后到前，对应的权重分别是 ，，，，，......，。也就是说，。代入上式，有： 两边同时除以 ，得到：。也就是说：，即只有当相邻位上的数相等时，填反了验证等式才会通过。但是相邻位上的数如果都相等了，填反了也没关系嘛。 实际上，如果有抽象代数基础的话会知道 2 是 下的生成元。而且，不难证明，只要权重是根据生成元的指数幂选取的，都可以解决相邻位填反验证等式不通过的功能。 模 10 是不是更好？ 模 10 可以满足身份证号前面的两个性质。观察公式： 如果要满足身份证验证算法的功能，我们实际上只需要要求 与模数互质就可以了。 @刘天任 给出的模 10 算法中，权重值分别为 1、3、7、9，都是与 10 互质的数。 但是，模 10 比模 11 缺少了第三个功能：模 10 不能防止身份证的相邻 2 位填反了。这本质原因是模 10 下形成的有限域 只包含与 10 互质的整数 1、3、7、9。这导致的一个后果是：当存在 2 个及以上位错误时，模 10 不能保证 90% 的检测概率。这个结论讨论起来就有点复杂了，感兴趣的知友们可以简单思考一下为什么。 总结 从理论上看，选择模 11 的本质原因是尽可能允许验证算法可以覆盖到常见的身份证填错情况。而身份证填错的常见情况就是： 有一个数填错了。 相邻两位填反了。 注意，技术不是万能的，对于更多可能的情况，身份证校验算法大多数是无法校验出来的。不过，理论分析可以得到这样一个结论：如果有 2 个以上的位填写错误，而填写错误不是刻意而为之，而是随机填错了的话，则身份证校验算法能够检测出错误的概率为 90%。 如果以数学为武器，看清身份证号验证原理的话，怎么设置都会绕不开基本问题的… 扩展 知友们可以思考这样一个问题：如果某个平台公开了一部分身份证号码，但是身份证号码只隐藏了出生年份，例如：110105????1231002X。这样隐藏是对的吗？会带来什么风险？进一步，如果我们仅能隐藏 4 位的话，隐藏哪 4 位会更安全一些呢？ 以上。 阅读原文
