时间戳

首页 > 解决方案 > 关于AES不可约多项式的问题

encryption - 关于AES不可约多项式的问题

问题描述

对于伽罗瓦域 GF(2^8)，多项式的格式为 a7x^7+a6x^6+...+a0。

对于 AES，不可约多项式是 x^8+x^4+x^3+x+1。

显然，GF(2^8) 的最大幂是 x^7，但为什么不可约多项式的最大幂是 x^8？

不可约多项式的最大幂将如何影响 GF 的逆结果？

我可以将不可约多项式的最大幂设置为 x^9 吗？

标签： encryptionaesgalois-field

解决方案

要理解为什么 GF(2⁸) 的模数必须是 8 阶（即以 8 作为其最大指数），您必须知道如何使用 GF(2) 中的系数执行多项式除法，这意味着您必须知道如何执行一般的多项式除法。我会假设你知道如何做这些事情。如果你不知道怎么做，网上有很多教程可以学习。

请记住，如果r = a mod m，则意味着存在q这样的情况a = q m + r。要进行有效的 GF(2⁸) 算术，我们需要保证r对于任何aand是 GF(2⁸) 的元素q（即使aandq不需要是 GF(2⁸) 的元素）。此外，如果我们从 GF(2⁸) 中选择右边，我们需要确保它可以是GF(2⁸) 的任何元素。ra

所以我们必须选择一个模数（the m）来保证这些。我们通过选择一个m正好为 8 的顺序来做到这一点。

如果除法的分子 (the ain a = q m + r) 是 8 阶或更高阶，我们可以找到一些东西放入商 (the q) 中，当它乘以 x⁸ 时，可以抵消更高阶。但是我们不能将商放入可以乘以 x⁸ 来给出阶数小于8 的项，因此余数 (the r) 可以是不超过 7 的任何阶数。

让我们尝试几个模数（或除数）为 x⁸+x⁴+x³+x+1 的多项式除法示例，看看我的意思。首先让我们计算 x⁸+1 mod x⁸+x⁴+x³+x+1：

                1            <- quotient
             ┌──────────────
x⁸+x⁴+x³+x+1 │ x⁸        +1
             -(x⁸+x⁴+x³+x+1)
             ───────────────
                  x⁴+x³+x    <- remainder

所以 x⁸+1 mod x⁸+x⁴+x³+x+1 = x⁴+x³+x。

接下来让我们计算 x¹²+x⁹+x⁷+x⁵+x² mod x⁸+x⁴+x³+x+1。

               x⁴ +x +1                      <- quotient
             ┌──────────────────────────────
x⁸+x⁴+x³+x+1 │ x¹²+x⁹   +x⁷+x⁵      +x²
             -(x¹²   +x⁸+x⁷+x⁵+x⁴      )
             ───────────────────────────
                   x⁹+x⁸      +x⁴   +x²
                 -(x⁹      +x⁵+x⁴   +x²+x)
                 ─────────────────────────
                      x⁸   +x⁵         +x
                    -(x⁸      +x⁴+x³   +x+1)
                    ────────────────────────
                            x⁵+x⁴+x³     +1  <- remainder

所以 x¹²+x⁹+x⁷+x⁵+x² mod x⁸+x⁴+x³+x+1 = x⁵+x⁴+x³+1，其阶数 < 8。

最后，让我们尝试一个更高的顺序：x¹⁰⁰+x⁹⁶⁺x⁹⁵+x⁹³+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x mod x⁸+x⁴+x³+x+1怎么样？

               x⁹²             +x⁸⁴                    <- quotient
             ┌────────────────────────────────────────
x⁸+x⁴+x³+x+1 │ x¹⁰⁰+x⁹⁶⁺x⁹⁵+x⁹³    +x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x
             -(x¹⁰⁰+x⁹⁶+x⁹⁵+x⁹³+x⁹²                  )
             ─────────────────────────────────────────
                                x⁹²+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x
                              -(x⁹²+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴  )
                              ────────────────────────
                                                    x  <- remainder

所以x¹⁰⁰+x⁹⁶⁺x⁹⁵+x⁹³+x⁸⁸+x⁸⁷+x⁸⁵+x⁸⁴+x mod x⁸+x⁴+x³+x+1 = x。请注意，我仔细选择了分子，以免计算时间过长。如果您想要一些痛苦，请尝试手动执行 x¹⁰⁰ mod x⁸+x⁴+x³+x+1。

推荐阅读