crc128生成多项式怎么计算得到的？

[badmonkey7]

常见的crc32,crc16的生成多项式都是约定好的，不过这次中间人攻击的那道题里面有一个crc128，针对这种位数较多，且不常见的crc(如crc128，crc256等)，他们的生成多项式是如何生成的呢？

[zzh1996]

是 SageMath 中 GF(2^128) 不指定 variable name 时默认使用的多项式

生成题目中那个数字的 Sage 代码：

m = 0
for i, c in enumerate(GF(2 ^ 128).modulus().coefficients(sparse=False)[:-1]):
    m += ZZ(c) * 2 ^ (127 - i)
print(hex(m))

输出：

0xb595cf9c8d708e2166d545cf7cfdd4f9

注意这里需要把二进制位的顺序逆序一下。

在搜索引擎搜索这个数字可以发现 0CTF Quals 2019 的 fixed point 一题也使用了这个数字，应该是巧合。

[badmonkey7]

sage中GF(2^128)默认返回的多项式为primitive polynomial(本原多项式),而crc恰好要求生成多项式为本原多项式详见wiki,所以对于任意位数的crc其实我们只要选择mod(2^bits)下的任意一个本原多项式就行了，而本原多项式的数量为phi((2^bits)-1)/bits。至于crc为什么选择本原多项式，大概是因为性质良好叭？？