OMAC:有限域中的乘法 - 我如何计算正确的多项式

信息安全 密码学 加密
2021-08-19 16:44:35

EAX 操作模式

我们解释了 OMAC 定义中使用的符号。iL 的值(第 40 行:i 是 {2, 4} 和 L ∈ {0, 1} n 中的整数)是通过将 L 乘以表示数字 i 的 n 位字符串得到的 n 位字符串. 乘法是在有限域 GF(2 n ) 中使用规范多项式来表示域点的。我们选择的规范多项式是具有最小数量非零系数的 n 次不可约多项式中按字典顺序排列的第一个多项式。对于 n = 128,指示的多项式为 x 128 + x 7 + x 2 + x + 1。在这种情况下,如果 L 的第一位为 0 且 2L = (L << 1) ⊕ 0,则 2L = L << 1 12010000111 否则,其中 L << 1 表示 L 左移一个位置(第一位消失,零进入最后一位)。4L 的值就是 2(2L)。我们警告说,为了避免侧信道攻击,必须以恒定时间的方式实现加倍操作。

我基本上只是给出了在 n = 128 的有限乘法中使用的多项式是 x 128 + x 7 + x 2 + x + 1。我希望我的实现是抽象的,因为它不依赖于正在使用的密码。为了允许块大小 n 是任意数字而不是硬编码 128 或其他几个,我怎样才能让我的软件计算正确的多项式?

2个回答

别。对于大多数人来说,没有理由实现自己的加密库。获取具有 CMAC(又名 AES-OMAC1)实现的现有加密库,并使用该代码。自己实现它很容易出错(存在安全问题的风险),并且经常错过标准库中的性能优化。对于大多数目的,没有理由自己实现它,也没有理由使用除 AES 之外的任何其他密码,或者特别是具有 128 位块大小以外的任何其他密码的块密码。

当然,@DW 给出了重要且正确的答案。不要重新实现你自己的密码库(或者,至少,为了学习和乐趣而这样做,但不要相信它!)。

现在,对于细节,你引用的文本实际上给出了所有需要的细节,尽管是以一种相当简洁的数学方式。重要的一句话是:

我们选择的规范多项式是具有最小数量非零系数的 n 次不可约多项式中按字典顺序排列的第一个多项式。

当您使用二进制多项式以n次多项式P为模进行计算时,仅当P不可时,您才会得到一个有限域(表示为GF(2 n ) ) 。

2 n 个 n二进制多项式它们都可以写成:

P = p 0 + p 1 X + p 2 X 2 + ... + p n-1 X n-1 + X n

其中每个p i是 0 或 1。请注意,对于二进制多项式,我们计算GF(2)中的所有值,因此加法是 XOR,乘法是 AND。

对于更快的实现,当非零p i 的数量最少时,我们更喜欢它如果非零p i用于较小的i值,那也更好这是很容易看出,对于P是不可约,p 0必须等于1,并且必须有奇数个非零的p之间1n-1个正如 EAX 规范所说,我们尝试所有多项式,直到我们找到一个不可约的;我们从只有一个非零p i的多项式开始(有n-1其中),并且,如果没有一个是不可约的,那么我们尝试具有三个非零p i值的多项式(其中有(n-1)(n-2)(n-3)/6个)。我们从那些p i代表可能的最低值i开始,即我们从1+X+X 2 +X 3 +X n开始。

因此,您所要做的就是枚举n次的二进制多项式,其中非零系数的数量最少,按字典顺序,并测试它们的不可约性。有关该测试,请参阅《应用密码学手册》第 4 章第 4.5.1 节。