NTL库中Galois域GF(2^8)的元素表示及算术运算
How to represent the elements of the Galois filed GF(2^8) and perform arithmetic in NTL library
我是 NTL 库的新手,因为它的 GF2X
、GF2E
、GF2EX
等。现在,我想在伽罗华域 GF(2^8)
上执行乘法。问题如下:
Rijndael (standardised as AES) uses the characteristic 2 finite field with 256 elements,
which can also be called the Galois field GF(2^8).
It employs the following reducing polynomial for multiplication:
x^8 + x^4 + x^3 + x^1 + 1.
例如,{53} • {CA} = {01} 在 Rijndael 的字段中,因为
(x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)
= (x^13 + x^12 + x^9 + x^7) + (x^11 + x^10 + x^7 + x^5) + (x^8 + x^7 + x^4 + x^2) + (x^7 + x^6 + x^3 + x)
= x^13 + x^12 + x^9 + x^11 + x^10 + x^5 + x^8 + x^4 + x^2 + x^6 + x^3 + x
= x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x
and
x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x modulo x^8 + x^4 + x^3 + x^1 + 1
= (11111101111110 mod 100011011)
= {3F7E mod 11B} = {01}
= 1 (decimal)
我的问题是如何在NTL
中表示约简多项式x^8 + x^4 + x^3 + x^1 + 1
和多项式x^6 + x^4 + x + 1
和x^7 + x^6 + x^3 + x
。然后对这些多项式进行乘法,得到结果{01}
.
这是我使用这个库的一个很好的例子。
同样,我不懂 NTL,我 运行 Visual Studio 2015 on Windows 7. 我已经下载了我需要的东西,但必须构建一个包含所有提供的源文件的库,这将需要一段时间才能弄清楚。但是,根据另一个答案,这应该可以帮助您入门。首先,初始化 GF(256) 的约简多项式:
GF2X P; // apparently the length doesn't need to be set
SetCoeff(P, 0, 1);
SetCoeff(P, 1, 1);
SetCoeff(P, 3, 1);
SetCoeff(P, 4, 1);
SetCoeff(P, 8, 1);
GF2E::init(P);
接下来,将变量分配为多项式:
GF2X A;
SetCoeff(A, 0, 1);
SetCoeff(A, 1, 1);
SetCoeff(A, 4, 1);
SetCoeff(A, 6, 1);
GF2X B;
SetCoeff(B, 1, 1);
SetCoeff(B, 3, 1);
SetCoeff(B, 6, 1);
SetCoeff(B, 7, 1);
GF2X C;
看起来有一个乘法覆盖,所以假设乘法覆盖基于 GF(2^8) 扩展字段 GF2E::init(P).
C = A * B:
正如问题后的评论,NTL更面向大领域。对于 GF(256),使用字节和查找表会更快。对于高达 GF(2^64),具有无进位乘法的 xmm 寄存器内在函数 (PCLMULQDQ) 可用于在没有表格的情况下快速实现有限域数学(需要一些常数,多项式及其乘法逆)。对于大于 GF(2^64) 的字段,将需要扩展精度数学方法。对于字段 GF(p^n),其中 p != 2 且 n > 1,无符号整数可用于查找表。构建表格将涉及整数和 GF(p) 多项式系数之间的一些映射。
我是 NTL 库的新手,因为它的 GF2X
、GF2E
、GF2EX
等。现在,我想在伽罗华域 GF(2^8)
上执行乘法。问题如下:
Rijndael (standardised as AES) uses the characteristic 2 finite field with 256 elements,
which can also be called the Galois field GF(2^8).
It employs the following reducing polynomial for multiplication:
x^8 + x^4 + x^3 + x^1 + 1.
例如,{53} • {CA} = {01} 在 Rijndael 的字段中,因为
(x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)
= (x^13 + x^12 + x^9 + x^7) + (x^11 + x^10 + x^7 + x^5) + (x^8 + x^7 + x^4 + x^2) + (x^7 + x^6 + x^3 + x)
= x^13 + x^12 + x^9 + x^11 + x^10 + x^5 + x^8 + x^4 + x^2 + x^6 + x^3 + x
= x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x
and
x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x modulo x^8 + x^4 + x^3 + x^1 + 1
= (11111101111110 mod 100011011)
= {3F7E mod 11B} = {01}
= 1 (decimal)
我的问题是如何在NTL
中表示约简多项式x^8 + x^4 + x^3 + x^1 + 1
和多项式x^6 + x^4 + x + 1
和x^7 + x^6 + x^3 + x
。然后对这些多项式进行乘法,得到结果{01}
.
这是我使用这个库的一个很好的例子。
同样,我不懂 NTL,我 运行 Visual Studio 2015 on Windows 7. 我已经下载了我需要的东西,但必须构建一个包含所有提供的源文件的库,这将需要一段时间才能弄清楚。但是,根据另一个答案,这应该可以帮助您入门。首先,初始化 GF(256) 的约简多项式:
GF2X P; // apparently the length doesn't need to be set
SetCoeff(P, 0, 1);
SetCoeff(P, 1, 1);
SetCoeff(P, 3, 1);
SetCoeff(P, 4, 1);
SetCoeff(P, 8, 1);
GF2E::init(P);
接下来,将变量分配为多项式:
GF2X A;
SetCoeff(A, 0, 1);
SetCoeff(A, 1, 1);
SetCoeff(A, 4, 1);
SetCoeff(A, 6, 1);
GF2X B;
SetCoeff(B, 1, 1);
SetCoeff(B, 3, 1);
SetCoeff(B, 6, 1);
SetCoeff(B, 7, 1);
GF2X C;
看起来有一个乘法覆盖,所以假设乘法覆盖基于 GF(2^8) 扩展字段 GF2E::init(P).
C = A * B:
正如问题后的评论,NTL更面向大领域。对于 GF(256),使用字节和查找表会更快。对于高达 GF(2^64),具有无进位乘法的 xmm 寄存器内在函数 (PCLMULQDQ) 可用于在没有表格的情况下快速实现有限域数学(需要一些常数,多项式及其乘法逆)。对于大于 GF(2^64) 的字段,将需要扩展精度数学方法。对于字段 GF(p^n),其中 p != 2 且 n > 1,无符号整数可用于查找表。构建表格将涉及整数和 GF(p) 多项式系数之间的一些映射。