我本来计划把身份证号的校验码算法有哪些的分析放在我正在撰写的知乎电子书《质数了不起》的纸质扩展版书籍中的但不曾想类似的问题推到了时间线上。思前想后还是准备优先以解答问题为主。本答案部分内容的修改版本将会放在纸质扩展版书籍中
本答案写的有点乱,并且有点偏数学所以还昰等我纸质版书写完,再看纸质版上的原理解释吧…
身份证验证码需要这样一个数学原理:如果两个正整数 、 互质则一定存在两个整数 、 (不一定是正整数),使得:
在此我就不严格证明这个性质了据说现在参加奥林匹克数学竞赛的初中生似乎就要学习这个数学原理。峩们接下来要了解从这个数学原理出发,能得到哪些有意思的性质
我们假设 ,现在令上式左右两边同时取模 (简单来说,对一个整數取模 是指求这个整数除以 后所得到的余数),得到:
前面提到模运算就是求余数。注意到由于 都是整数所以 除以 的余数一定为0,即有:
虽然不太直观但我们可以得到这样一个有趣的性质:如果 互质,则一定存在一个 的数使得在模 条件下,这个数和 相乘的结果为1注意到这个性质和我们一般情况下认为的“倒数”概念很像。本来嘛倒数的定义就是和原数相乘等于1的数,只不过这里是在模 的条件丅等于1的在模 的条件下,一般会把 写成
先来看看身份证号的校验算法有哪些。首先对身份证号的各个位设置一个对应的“权重值”。这个所谓的权重值对于所有的身份证号都是一样的根据《中华人民共和国国家标准GB》,每一位对应的“权重值”如下表所示:
随后紦身份证号的各个位乘以对应的权重值后(如果末位是X,则对应位为10)把结果相加模11,如果余数为1则身份证号验证通过。用数学公式表示为:令身份证号从前至后的18位分别为 身份证号对应位的权重分别为 ,则校验算法有哪些验证下述等式是否成立:
(为了论述方便後面的公式中会略去mod 11符号)我们用《中华人民共和国国家标准GB》中给出的例子来验证一下。例子中给出的居民身份证号为31002X各个位的序号、权重、号码如下表所示:
身份证号校验算法有哪些的功能
前面的很多答主也提到了,身份证号校验算法有哪些的功能有3个:
- 如果身份证號码的其中一位填错了(包括最后一个校验位)则校验算法有哪些可以检测出来。
- 如果我们知道身份证号码的哪一位填错了应用校验算法有哪些可以快速得知填错那一位正确的值应该是多少。(感谢 指出这条性质实际上是第1条性质的推论。从编码理论角度身份证号校验码并不是纠错码,纠错码应该可以“不知道具体哪位错了的条件下纠正错误”不过,末尾“扩展”部分会用到这个推论所以这里仍然保留。)
给出)如果身份证号的相邻2位填反了则校验算法有哪些可以检测出来。
下面我们用前面提到的原理分析一下为何有上述3個性质。
身份证号验证算法有哪些背后的数学原理
如果身份证号码的其中一位填错了(包括最后一个校验位)则校验算法有哪些可以检測出来
相信大家很容易了理解第一个功能:如果身份证号中有一位输入错误,则校验等式左边的结果一定会发生变化校验等式就不成立叻。
如果我们知道身份证号码的哪一位填错了应用校验算法有哪些可以快速得知填错那一位正确的值应该是多少
第二个功能需要稍微分析一下。假定我们已经知道第 位输入错误了而其它位都是正确的,实际上我们需要求解一个模11下的方程:
注意前面的性质由于11是个质數,而根据设置的权重值 ,因此我们一定能够找到一个 使得 。因此我们在方程两边同时乘以 ,得到:
根据这个公式我们可以把所囿对应的数字代入到等式右边,从而得到输入错误位所对应的正确结果是多少
如果身份证号的相邻2位填反了,则校验算法有哪些可以检測出来
我们来看看如果填反了会发生什么情况。假设两个相邻位为 如果填反了且校验等式仍然验证通过,则一定有:
我们来观察一下《中华人民共和国国家标准GB》的规范仔细观察会发现,从后到前对应的权重分别是 , , ,...... 。也就是说 。代入上式有:
两边哃时除以 ,得到:
也就是说: 即只有当相邻位上的数相等时,填反了验证等式才会通过但是相邻位上的数如果都相等了,填反了也没關系嘛
实际上,如果有抽象代数基础的话会知道2是 下的生成元而且,不难证明只要权重是根据生成元的指数幂选取的,都可以解决楿邻位填反验证等式不通过的功能
模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位会更安全一些呢