Internet 校验和的数学性质

时间:2021-12-12 15:12:13

Internet 校验和(Checksum)仅计算头部的正确性,这一点很重要,这意味着 IP 协议不检查 IPv4 packet 有效载荷部分的数据正确性。为了保证有效载荷部分的正常传输,其他协议必须通过自己的协议数据完整性检测机制来保护重要数据。我们可以看到在封装在 IP 的几乎所有协议(UDP、TCP、ICMP、IGMP)在自己头部中都有一个涵盖头部数据的校验和。

IPv6 放弃了校验和字段。原因如下:位错误带来的后果一般是数据被投递到错误的目的地、数据的来源显示错误、有效载荷中的位错误。由于位错误比较少见,而且其他上层协议的字段提供了对有效载荷部分的更有力的确保正确性的机制,因此IPV6删除了这个字段。

特别的,当 IPv4 的数据包经过一台路由器时,TTL 字段减一会导致头部校验和的重新计算,即每一跳路由都会导致校验和的重新计算。

校验和检测失败时 IPv4 将直接丢弃接收到有误的数据包不会生成差错信息,更高层需要以某种方式检测丢失的数据报并在必要时重新传输。

internet校验和的内容

Internet 校验和的内容如下

  1. 将校验和的字段设置为零。
  2. 将整个头部(仅有 header 部分)认为是一个 16 bits integer 的一个序列。计算这一系列的 16 位整数的反码和。将运算结果存放到校验和字段内。
  3. 收到 IPv4 packet 时,对整个 header (校验和字段不是 0 而是有填充)进行相同的计算。反码和结果应该为 0 ,代表数据无误。若非 0 ,则代表数据有误

实例

例如要发送的 packet 内容是 :E3 4F 23 96 44 27 99 F3 【00 00】 (checksum 字段清零)

将整个序列看成 16 位的整数,一个十六进制数是 4 bits,所以要看成 4 个十六进制数为一个整数。

二进制反码求和:从低位到高位逐列进行和计算,如果最高位(16位)进位,则得到的结果加1,一直循环到最高位没有进位为止.最后把得到的结果取反.

可以用如下的简单方法求反码和:对几个数进行补码和,也就是我们通常所用的加法,然后将进位的数字加到最低位。

最后把结果取反。

  • 补码和:E34F + 2396 + 4427 + 99F3 = 1E4FF
  • 反码和:进位的数字加到最低位:E4FF + 1 = E500
  • 取反:checksum = ~(E500) = 1AFF

则填充 checksum 之后发送的 packet 内容变成:E3 4F 23 96 44 27 99 F3 【1A FF】

接收方检测过程:计算包括 checksum 在内的整个 packet 的反码和,再取反。

  • 补码和:E34F + 2396 + 4427 + 99F3 + 1AFF = 1FFFE
  • 反码和:进位的数字加到最低位:FFFE + 1 = FFFF
  • 取反结果 = ~(FFFF) = 0

若结果为 0 ,说明数据在传输过程中没有发生变动。若结果不为 0 ,则数据在传输过程中有变动、受损。

数学性质

这里运用到离散数学中关于群论的知识点。

集合 G 不为空集,在 G 上的二元运算满足封闭性、结合律、存在单位元、每个元素都有逆元,则称<G, +> 为群,若满足交换律,则称群 G 为阿贝尔群。

可以通过观察发现,16 位整数的一个十六进制值序列集合 V = {0001,0002,...,FFFF} ,定义 + 为二进制反码和运算,<V, +> 构成阿贝尔群

  • 对于任意的 X,Y in V, (X + Y) in V [封闭]
  • 对于任意的 X,Y,Z in V, X + (Y + Z) = (X + Y) + Z [可结合]
  • 对于任意的 X in V, e + X = X + e = X ,e = FFFF [单位元 e 是 FFFF]
  • 对于任意的 X in V, 存在 X′ in V 使 X + X′ = e [每个元素都存在逆元]
  • 对于任意的 X,Y in V, (X + Y) = (Y + X) [交换律]

事实上,观察构造 checksum 的过程我们可以得知:checksum 其实是前面 4 个 16 bit integer 做二进制反码和运算(下文用 ‘+’ 代替)的结果的取反取反这个操作特别的有意思,因为你对任何一段长度为 n 的二进制数据取反,与原来的数据相加,结果一定是长度为 n 的 1 串。

例如:1011,取反是 0100。1011 + 0100 = 1111

所以,对于 16 bit integer,这个结果一定是 FFFF。FFFF 在我们前面的分析中,就是阿贝尔群<V, +>单位元!所以我们可以得出一个结论:在构造 packet checksum 时,checksum 其实就是其余数据在群<V, +>中的逆元!!

当收到 packet 的一方,在做验证的时候,因为前面的 4 个 16 bit integer 和后面这 2 个字节的 checksum 是互为逆元的,所以对它们进行 + 的运算结果一定是单位元 FFFF。而由于整个运算集合构成了一个群,因此确保了每一个元素都有一个对应的逆元,也就证明了:如果检验和检测正确,意味着数据完好,如果出错,意味着数据受损。

关于这个十六位整数的十六进制值序列集合,非常让人感兴趣的一点是 其中没有 0000。这是为什么呢?我们考虑一下,如果将数字0000放入集合,则 <V, +> 不再是一个阿贝尔群。

0000 显然可以作为单位元 e。对于群,每个元素都要有一个逆元,取随意的元素 AB12 来说,需要有一个逆元 X′ + AB12 = 0000,这样的 X′ 在<V, +>是不存在的。因此,我们需要排除 0000 ,使得<V, +> 构成阿贝尔群。

那么排除 0000的道理又何在呢?首先,排除 0000 使得<V, +>是一个阿贝尔群,之前已经说过了。第二条理由是,任何一个合法的 IPv4 包,不可能所有的字节都为 0 。如果要将 0000 纳入群众,则是考虑存在一个合法的 IPv4 包,除了 checksum 之外的字节都为 0 的情况,而这种情况

  1. 会导致<V, +> 不再是一个阿贝尔群。
  2. 实际是不存在的,不存在任何一个合法的 IPv4 头部全是 0 的情况。

因此我们可以排除 0000,由此推断出 Internet 校验和的群属性。


参考链接:http://blog.csdn.net/qq_34369618/article/details/60603867