在最近开始研究RFID之后，数据校验成为了必须仔细研究的一个题目。所以借此机会整理一下不同的数据校验方法，以备后来参考。
什么是数据校验
在数据的传输过程中，无论使用什么方法，都无法保证100%的传输正确率，总有发生错误的时候。数据校验就是通过对发送方持有的数据（也就是正确的数据）进行某种运算，对接收方收到的数据也进行同样的运算，并且比较这两个结果。如果结果不一样，肯定是传输过程中发生了错误；而在有的情况下，即使结果一样，也不能认为数据传输是正确的，存在多处错误但是导致校验结果没有变的可能。
个人认为，数据校验是利用了信息的映射方法，试图找到一个映射，让原序列改变的时候它的映射结果也发生改变。当然，如果要做到原序列改变结果一定改变，这表示校验值的信息量和原序列是一样的，就失去了校验的意义，因为一方面成本太高，相当于把原信息再发送一遍；另一方面如果信息量一样，出现错误的可能就一样，如果连校验值在传输中都发生了错误，就没有校验的必要了，肯定得不到正确结果。所以无论什么校验方法，都有可能存在检测不出来错误的情况，但是通过精确的设计算法，可以降低这种可能。
奇偶校验
奇偶校验（Parity Check）是最基础的校验方式，一般用在噪声低或者资源紧缺，而且重发成本不高的地方。
基本算法
奇偶校验的算法非常简单，就是统计数据中出现的1的个数，是奇数个还是偶数个。用软件编程语言可以简单的用比较和取反操作实现，而硬件描述语言则可以将输入信号简单地逐个异或运算。这里比较巧妙，证明如下：
对某一个序列，假设它具有奇性，那么它的奇偶位应该是1。这时在其后面添加0，则1和0异或还是1；如果添加1，那么1和1异或则变成了0。如果它具有偶性也同理，在后面添加0将不会改变其奇偶位，添加1则将变成具有奇性。再看初始情况，只有前两位是1和0异或能获得1，所以逻辑结果正确。
优点
奇偶校验的优点显而易见，就是它非常简单，对资源的消耗量也很低。很适合用在基础的地方，并且单个数据块比较小的地方，或者作为复杂校验协议的基础检查，降低之后的工作量。
缺点
奇偶校验的缺点也相当明显……首先是如果错码是偶数个，比如2个，奇偶校验就不会发现问题。虽然现在一般传输错码率比较低，但是在高噪声或者数据块很大（比如大文件）的情况下还是比较容易出现这种问题的。其次，奇偶校验只能提供基本的反馈：数据有错码，并不能知道具体哪一位出错，所以导致整个数据包被丢弃。
改进
对于简单的单向奇偶校验的基本改进就是双向奇偶校验。双向奇偶校验是对数据块进行的校验。考虑这样一种情况，我要传输一定的数据，按8位一字节传输。我可以使用：
1001010+1
这样的7+1格式，最后一位是校验码。但是如上文所说，有诸多限制，可以按这样的格式改进：
1001010+1
1011100+0
0100100+0
0011101+0
0101100+1
1011111+0
0111000+1
+
1100100 1
7字节一组，第8字节是前7字节的纵向奇偶校验。这样除非横纵同时仅出现偶数位错码才可能导致校验失效，概率非常低。值得一提的是，最后一位不仅是前7字节的校验位的校验，也是第8字节前7位的校验。这一位的存在属于双重冗余，能够进一步降低校验失败的可能。
纵向冗余校验
纵向冗余校验（Longitudinal Redundancy Check），也就是我们平时说的LRC，是对于单向奇偶校验的一个扩展。思路和奇偶校验是一样的，我这次研究的射频卡使用的主要就是LRC。
基本算法
LRC也是奇偶校验的形式，不同的是，它的方向是纵向的，也就是说它在获取全部的字节之后，把每个字节的第一位逐个异或生成校验字节的第一位，每个字节的第二位逐个异或生成校验字节的第二位，以此类推。
10010101
10111000
01001000
00111010
01011001
10111110
01110001
+
11001001
优点
LRC的优点是成本比奇偶校验更低，因为数据与校验的比例更大，所以传输的时候可以传输更多的数据和更少的校验值。在射频卡上使用也是这个原因，射频卡系统的资源非常有限，所以尽量采用低成本的方式。即使一般射频卡的噪声远大于常规有线传输，但是它的重发成本更低，后果也更轻，一次没有刷上大不了再刷一次，所以影响并不大。
缺点
LRC的缺点和单向奇偶校验一样，甚至更明显，因为它的数据与校验的比例更大，出现多重错码的概率更大。
循环冗余校验
循环冗余校验（Cyclic Redundancy Check），也就是我们更常见的CRC。注意CRC与之前提到的两种方法不同，是一种循环校验方式，也叫做多项式校验，是基于除法的操作，用于对数据块而非数据位的校验。
基本算法
CRC是基于GF(2)也就是除以2的余数校验的方式，之所以叫循环，是因为这是一个多项式环。基本实现是这样：
基本要求
首先需要明确一点，在代数编码之中，使用二进制码表示多项式的方法是一位对应一个系数。例如对于\(x^5 + x^2 + 1\)，表示为100101，对应不同次数的系数。但是在CRC规范中有额外规定，最高位和最低位必须是1。
模2除法
第二个需要明确的是，虽然CRC是基于除法，但是为了简化，CRC使用二进制除法，也就是模2除法。模2除法中从左向右扫描，不向高位借位。我们知道普通除法是，进行第一次除，之后判断当前几位余数与除数的大小关系，如果大于除数表示可以商1（二进制只有商1或0），否则商0，再往后面延一位。但是模2除法中不判断余数大小，只要余数与除数首位都是1（因为CRC规定了校验值首位需要是1）就可以商1，之后进行模2减法。模2减法也不借位，直接进行异或。借用网上的图片来说明：
首先是商的起始位，这和普通除法一样，至少要让操作的被除数部分的位数和除数一致。因为一定两者开头都是1，所以按照我们之间讲到的规则，第一位也一定是1。然后对被除数和除数进行模2减法，也就是异或，得到10。位数不够向后面延2位，所以商的第2位是0。之后对于第3位，又是1，第4位同理。可以发现，因为只要余数第一位是1对应位置就可以商1，那么，只要凑够一个同样位数的1开头的就可以商1，结果是会比普通除法大的。
CRC运算方法
CRC校验值的基本获得方式就是利用模2除法。首先约定，有一个生成多项式\(G(x)\)，它是由CRC标准规定的一个式子。将其转换为二进制编码之后，它的长度减去1就是R，也就是CRC校验码的长度。这里减1是因为最高位被省略了，因为一定是1。之后将需要发送的数据左移R位（因为要和长度补齐），用生成多项式进行完整的模2除法直到余数位数小于等于R。此时给余数前置补0，补到R位，就是CRC校验码。
优点
CRC校验码能够保证校验出所有奇数位错码，所有偶数位错码和所有长度小于校验长度R的突发错码。在实际使用中，几乎不可能遇到CRC校验通过而数据实际出错的情况。同时CRC具有纠错能力，因为不同的位数出错的时候，余数状态是不一样的，所以可以通过运算还原正确值，或者仅需重发很小一部分即可。
缺点
虽然作为错误检出机制，CRC校验非常有效，但是它不能防止人为的改变数据。因为CRC算法是线性的，很容易逆运算，而且冗余度很低，所以很容易故意调整数据值，但是保持CRC校验值不变。
整数加法校验和
整数加法校验和（Integer Addition Checksum），也就是最基本的Checksum算法，是很常用的校验方法。整数加法校验和也是一种纵向校验方法，生成一字节的校验码。
基本算法
整数加法校验和的基本算法非常简单，就是直接累加每个要传输的字节。全部累加之后，获得的结果就是校验码。需要注意的是，这里用的是正常的带进位加法，需要进位多少就正常进位。除了最高一位，进位被舍弃，因为校验码无论是由多少个字节生成的，都只有一字节长度。
优点
这一算法的优点是简单，因为是连续加法，所以并行运算也并不难做到，而且加法运算量本身不大，比较好实现。同时，Checksum方法不仅能够检出奇数个错码，还能检出2个错码（因为会由进位把错误传递到下一位），或其他更多的错码，除非错误被直接传递到了省略部分。
缺点
这一算法也有缺点，首先就是因为错误的上浮，不能知道究竟是哪里出现错码，也不能定位是第几个字节出现问题。同时，也存在错码被传递到被忽略部分，也就是最高位进上去的部分而不能检出错码的情况。
md5
相对于之前介绍的校验方法，md5复杂很多。md5（MD5 Message-Digest Algorithm）是一种信息摘要算法，它能够对任意长度的信息生成128位的摘要，抗碰撞性能比较强，主要用在对于校验和防篡改要求比较高的地方。
基本算法
鉴于md5算法的复杂性，在这里就不完全展开讲解了，只解释基本而必要的部分。
首先，md5算法对512位一块的数据进行处理，所以首先要对数据位数进行填充。如果数据长度模512之后不是448，那么就填充一个1和多个0，直到填充至模512之后是448。为什么是448？因为算法使用一个64位的数字来存放填充前的数据长度，这64位将跟在填充后的数据的最后面，这样448+64=512，完成之后正好是512的倍数。
其次，在md5算法中存在幻数的概念。幻数（就是数论里的那个幻数）使用的是标准32位幻数，也就是0123456789ABCDEFFEDCBA9876543210，被分成4组，每组8位按照物理顺序放在寄存器内部（所以根据处理器架构的不同，程序中这个数字可能需要改）。
之后将每个512位的分组数据分成16个32位的部分，对每一部分使用四个标准线性函数进行运算，数据被分成几组就循环几次。
\[F(X,Y,Z)=(X&Y)|((~X)&Z)\] \[G(X,Y,Z)=(X&Z)|(Y&(~Z))\] \[H(X,Y,Z)=X^Y^Z\] \[I(X,Y,Z)=Y^(X|(~Z))\]在经过一定的运算，每次循环分开使用四个不同的函数之后，将获得md5的校验值，128位。
优点
md5的最大的优点就是它的防碰撞能力很强，正常情况下，不人为干预而传输错误导致md5值一样是不可能的，所以一定能够检出传输错误。同时，鉴于它的防碰撞能力很强，也被用来进行脱敏存储，比如数据库中存放的用户密码，或者Windows10离线账户的登陆密码就是以md5形式保存的，避免有人能够直接看到密码。而因为信息在进行摘要的过程中存在损失，所以是不可能精确还原回原来的信息的，再加上对md5没有办法进行逆运算，只能暴力试验，所以一定程度上防止了密码泄露。md5被广泛用在类似的安全认证方面和文件特别是大文件的校验上。
缺点
md5同时也有自己的缺点。首先md5并非理论上防碰撞，只是碰撞率很低，所以通过一定的方法还是可以找到一个序列，md5值和已知的相等。虽然没有办法还原原来的信息，但是对于密码认证方面却非常有效，因为毕竟只验证md5，所以只要能对上，就能通过。所以安全性很高的地方和数字签名方面不能使用md5。另一方面md5验证过程比较复杂，没有硬件实现（因为成本太高了），对于流量很高的系统是一个挑战。
破解
严格来说这一节讲的不是md5的破解而是碰撞，但是鉴于大多数人好像习惯于叫破解，还是沿用这一称呼。
上文中讲到md5可以用特殊的手段在合理的时间内碰撞成功，现在通行的手段就是彩虹表。彩虹表是一种特殊方式生成的查找表，利用的是暴力破解结合查找表的方式对md5进行碰撞。彩虹表使用相关衰减函数代替原来的顺序排列衰减函数，同时特殊排列其顺序，因为如果两个md5值碰撞，在散列链中一定出现在同样的位置并从此重合。所以通过保存哈希链，结合暴力破解（反算和正算）和查找表，允许通过定位哈希链的起点和终点而在运行破解的时候降低碰撞运算次数。
可以想到，这个表越大，那么需要计算和定位逆向初始位置的时间就越短，覆盖面也尽可能地大，但是存储的空间代价越大，目前经过大家的收集和整理，最大的彩虹表接近120G；而用很小的彩虹表也可以达到目标，但是定位的时间会长很多，错误概率也会增加，而定位错误将导致这次运行无法获得需要的结果。目前基本彩虹表大约380M，基础的彩虹表破解工具内置的就是这个彩虹表。
至于具体怎么利用彩虹表破解各种认证，针对不同的情况和不同的工具操作并不一样。这一块在以后的文章中进行讨论。根据我个人对经验来看，大容量彩虹表不一定能够很大的提高破解速度，反而能够提高成功率，换用120G彩虹表之后之前碰撞不出来的Windows离线账户密码可以成功，网上还有专门的md5碰撞服务，我没有试过，不过根据他们自己的描述，应该是比自己运行小规模彩虹表效果好很多。
结语
基本的校验有关的东西就讨论到这里，我会继续研究Proxmark3和RFID的相关内容，并且尽量及时更新我的博客内容以跟进我的进度。