无进位多重重复逆计算误差

Question

下面的帖子提供了如何实现无进位多重应用逆的指导。然而，8位值对的简单实现并不能提供预期的结果。

static uint cl_mul(uint a, uint b)
{
uint r = 0;
while (b != 0)
{
if ((a & 1) != 0)
r ^= b;      // carryless addition is xor
a >>= 1;
b <<= 1;
}
return r;
}
static uint clmulinv(uint x)
{
uint inv = 1;
uint rem = x;
for (int i = 1; i < 32; i++)
{
if (((rem >> i) & 1) != 0)
{
rem ^= x << i;
inv |= 1u << i;
}
}
return inv;
}
int main(int argc, char *argv[])
{

uint16_t cc=0,dd=0;       
uint8_t  c=0,d=0;
uint16_t t=0,e=0, k=0;


for(cc = 0; cc < 256; cc++)  {
for(dd = 0; dd < 256; dd++) {

c = cc;
d = dd;

t = cl_mul(d,c);
e = clmulinv(t);

if((t & 0x1) && ((e == d) || (e == c))) {
printf("k %4llu  c %4hhu    d %4hhu  t  %4llu  e %4hhu   n",k,c,d,t,e);
k++;
}
}
}

}  

对于8位输入[c]和[d]，我获得结果[t]，如果奇数，我将其用作反函数的输入以获得[e]。将[e]与[c]和[d]两者进行比较并不能带来多少快乐。怎么了？

k    0  c    1  d    1          t      1        e    1
k    1  c    5  d  255          t    771        e  255
k    2  c   17  d   85          t   1285        e   85
k    3  c   21  d  219          t   3591        e  219
k    4  c   51  d   85          t   3855        e   51
k    5  c   65  d   73          t   4617        e   73
k    6  c   69  d  151          t   9995        e  151
k    7  c   73  d   65          t   4617        e   73
k    8  c   81  d  157          t   11789       e  157
k    9  c   85  d   17          t   1285        e   85
k   10  c   85  d   51          t   3855        e   51
k   11  c  151  d   69          t   9995        e  151
k   12  c  157  d   81          t   11789       e  157
k   13  c  219  d   21          t   3591        e  219
k   14  c  255  d    5          t    771        e  255

Answer 1

遗憾的是，此代码没有在中正确实现乘法GF(2ⁿ(。我们通过在环中工作得到GF(2ⁿ(GF(2([x]模n次x中的某个不可约多项式。代码这里使用x^p，它不是不可约的。每当争论clmulinv的x是奇数，不存在逆。

对于GF(2⁸(，AES使用多项式x⁸+x⁴+x³+x+1。这意味着，无论何时设置了b的高位，我们需要将b异或2⁴+2³+2¹+2⁰=27。

已修复以下C代码。

#include <assert.h>
#include <stdio.h>
enum { poly = (1 << 8) + (1 << 4) + (1 << 3) + (1 << 1) + (1 << 0) };
unsigned gf2_mul(unsigned a, unsigned b) {
unsigned r = 0;
while (a) {
if (a & 1)
r ^= b;
a >>= 1;
b <<= 1;
if (b & (1 << 8))
b ^= poly;
}
return r;
}
unsigned poly_mul(unsigned a, unsigned b) {
unsigned r = 0;
while (a) {
if (a & 1)
r ^= b;
a >>= 1;
b <<= 1;
}
return r;
}
void poly_divmod(unsigned a, unsigned b, unsigned *q_out, unsigned *r_out) {
unsigned orig_a = a;
unsigned q = 0;
for (int i = __builtin_clz(b) - __builtin_clz(a); 0 <= i; i--) {
assert(orig_a == (poly_mul(q, b) ^ a));
unsigned c = a ^ (b << i);
if (c < a) {
q ^= 1 << i;
a = c;
}
}
*q_out = q;
*r_out = a;
}
// extended Euclid
unsigned gf2_inv(unsigned a) {
unsigned b = poly;
unsigned orig_a = a;
unsigned orig_b = b;
unsigned s = 1, t = 0;
unsigned u = 0, v = 1;
while (a) {
assert(a == (poly_mul(s, orig_a) ^ poly_mul(t, orig_b)));
assert(b == (poly_mul(u, orig_a) ^ poly_mul(v, orig_b)));
unsigned q, r;
poly_divmod(b, a, &q, &r);
assert(b == (poly_mul(q, a) ^ r));
unsigned x = u ^ poly_mul(q, s);
unsigned y = v ^ poly_mul(q, t);
b = a;
u = s;
v = t;
a = r;
s = x;
t = y;
}
return u;
}
int main() {
for (unsigned a = 0; a < (1 << 8); a++) {
assert(gf2_mul(a, 1) == a);
if (a)
assert(gf2_mul(a, gf2_inv(a)) == 1);
for (unsigned b = 0; b < (1 << 8); b++) {
assert(gf2_mul(a, b) == gf2_mul(b, a));
for (unsigned c = 0; c < (1 << 8); c++) {
assert(gf2_mul(a, gf2_mul(b, c)) == gf2_mul(gf2_mul(a, b), c));
assert(gf2_mul(a ^ b, c) == (gf2_mul(a, c) ^ gf2_mul(b, c)));
}
}
}
}