如何在伽罗华域中进行多项式减法和除法

Question

在我的加密课程中，我得到了两个紧凑形式的多项式和一个不可约多项式，并被要求在 GF(2^8) 中执行 4 个基本算术运算。完成了加法和乘法，我现在想知道如何处理减法和除法。为了方便起见，我们假设输入按位序列始终为 8 位

1st bit sequence: 11001100
2nd bit sequence: 11110000
irreducible polynomial(fixed): x^8 + x^4 + x^3 + x^1

如何进行减法/除法？

Answer 1

多项式x^8 + x^4 + x^3 + x^1不是不可约的：x显然是一个因子！。我的赌注是与 混淆x^8 + x^4 + x^3 + x + 1，这是字典顺序上第一个 8 次不可约多项式。

当我们修正多项式后，GF(2 ⁸ ) 是一个域，其中每个元素都是它自己的相反数。这意味着减法与加法相同。

该字段中的乘法 * 减去零形成一组 255 个元素。因此，对于任何非零B，它保持B ²⁵⁵ = 1。因此，该B的乘法逆元是B ²⁵⁴。

因此，当 B 不为零时，可以将 A / B 计算为 B ^{254 * A。}如果除以零结果为零，则该公式在没有特殊情况的情况下有效。

B ²⁵⁴可以通过标准二进制求幂方法（平方和乘法）进行 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}的模逆计算是恒定时间的（正如密码学中所希望的那样，以防止侧信道定时攻击），主要条件是乘法，而其他方法几乎不可能确保这一点，包括现代硬件上的表和大多数计算机语言，也许除了汇编语言。