对于我的加密课程，我得到了两个多项式，紧凑形式和一个不可约多项式，并被要求在 GF(2^8) 中执行 4 个基本算术运算。完成了加法和乘法，我现在想知道如何处理减法和除法。为方便起见，假设输入按位顺序始终为 8 位
1st bit sequence: 11001100
2nd bit sequence: 11110000
irreducible polynomial(fixed): x^8 + x^4 + x^3 + x^1
如何执行减法/除法？
问问题
1000 次
1 回答
4
多项式x^8 + x^4 + x^3 + x^1不是不可约的：x显然是一个因素！。我的赌注是与 混淆x^8 + x^4 + x^3 + x + 1，它是字典上第一个 8 次不可约多项式。
在我们修正多项式之后，GF(2 8 ) 是一个场，其中每个元素都是它自己的对立面。这意味着减法与加法相同。
该字段中的乘法 * 减去零形成一组 255 个元素。因此，对于任何非零 B，它保持 B 255 = 1。因此，这种 B 的乘法逆元是 B 254。
因此，当 B 不为零时，可以将 A / B 计算为 B 254 * A。如果认为除以零产生零，则公式在没有特殊情况的情况下有效。
B 254可以通过标准二进制求幂方法（平方和乘法）使用 13 次乘法计算，依次将 B 提高到 2、3、6、7、14、15、30、31、62、63、126、127、254权力。在 crypto.SE这个答案中的 C 代码。可以减少到 11 次乘法，并用 255 次乘法构建一个完整的逆表；在线试用！.
获得（一个）模逆的其他稍快的方法包括扩展欧几里得 GCD 算法和对数/反对数表，请参阅crypto.SE 上的这个其他答案。然而：
- 当速度是一个问题时，我们可以预先列出模逆。
- 那更复杂。
- 作为 B 254的模逆的计算是恒定时间的（在密码学中可用于防止侧信道定时攻击），主要条件是乘法，当用其他方法几乎不可能保证时，包括现代硬件上的表和大多数计算机语言，也许保存汇编。
于 2020-02-21T06:57:11.357 回答