3
$\begingroup$

I'm currently trying to optimise the finite field multiplication in $ \operatorname{GF}(2)[x]/(p)$, where $p = x^8 ⊕ x^7 ⊕ x^6 ⊕ x ⊕1 ∈ \operatorname{GF}(2)[x] $.

The thing is that I have to multiply by $ 16,32,133,148,192,194 \ \ and \ \ 251 $. Actually, what I do is that I declare 7 arrays (one for each multiplication; length 256) which contains every result. for example, when i want to multiply $ i = 145 $ by 32, i just assign $ array_{16}[i] $ to the result.

Is there an other way to do the multiplication, in order to reduce the memory used by my algorithm for example?

$\endgroup$
  • $\begingroup$ "Look Up Table" is by far the fastest. Do you need to decrease the memory usage? Are you limited by it? There is no point of doing memory optimisation if you will run it on a PC with 4GB of RAM. $\endgroup$ – Filip Franik Jul 13 '18 at 14:56
  • $\begingroup$ What are ‘16’, ‘32’, ‘133’, etc.? Do you mean $x^4$, $x^5$, and $x^7 + x^2 + 1$, respectively? The fastest way may be to precompute a 65536-byte lookup table, but of course if the factors are meant to be secret this will leak secrets through timing. Modern Intel CPUs have CPU instructions for carryless multiplication and polynomial reduction. For any fixed multiplier, you can write shift-and-xor logic. $\endgroup$ – Squeamish Ossifrage Jul 14 '18 at 0:30
  • 1
    $\begingroup$ What are your performance constraints? What is your budget for computation and memory? $\endgroup$ – Squeamish Ossifrage Jul 14 '18 at 0:39
  • $\begingroup$ Actually I'm programming for FPGA. I just wanted to know if there was a mathematical concept behind the multiplication I would have missed. For the moment my design works well and in view of all the answers given I think I will leave it like that. $\endgroup$ – Cedric Jul 16 '18 at 6:48
3
$\begingroup$

a better way to optimize the code is to use multiplication by 2 concept(xtime).

xtime(x) is multiplication by 2 which is left-shift modulo irreducible polynomial ($x^8\oplus x^7\oplus x^6\oplus x\oplus1$ = 0x1C3)

xtime is implemented in c code with irreducible polynomial (0x1c3) as following

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3))
  • = addition modulo 2(xor in code)

The binary representation of your values is as following:

16 : 00010000

32 : 00100000

133: 10000101

148: 10010100

192: 11000000

194: 11000010

251: 11111011

16*x (mul16) is as following 16 is $2^4$ (4 times left shift)-> mul16(x)=xtime(xtime(xtime(xtime(x)))). it can be rewritten as of mul8 as following xtime(mul8(x)). mul8 is defined as nested triple time

32*x (mul32) is as following 32 is $2^5$-> mul32(x)=xtime(xtime(xtime(xtime(xtime (x)))))= xtime(mul16(x)).

133*x = (128+4+1)x = 128*x+ 4*x + x; = ($2^7 + 2^2 +1$)x = (mul128(x)^xtime(xtime(x))^x) = (mul128(x)^mul4(x))^x)

192= (128+64)x = mul128(x)^mul64(x) 194= (192+2)x = mul192(x)^xtime(x)

I will let you do the 148 and 251 multiplication, you can use the following code for assistance:

#include <stdio.h>
#include <stdint.h>

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3)) //P: x8⊕x7⊕x6⊕x⊕1
#define mul4(x)    (xtime(xtime(x)))
#define mul8(x)    (xtime(mul4(x)))
#define mul16(x)   (xtime(mul8(x)))

#define mul32(x)      (xtime(mul16(x)))
#define mul64(x)      (xtime(mul32(x)))
#define mul128(x)     (xtime(mul64(x)))&0xFF
#define mul133(x)  (mul128(x)^xtime(xtime(x))^x)&0xFF
#define mul192(x)  mul128(x)^mul64(x)&0xFF
#define mul194(x)  mul192(x)^xtime(x)&0xFF



uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0; /* the product of the multiplication */
    while (a && b) {
            if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
                p ^= a; /* since we're in GF(2^m), addition is an XOR */

            if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
                a = (a << 1) ^ 0x1c3; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
            else
                a <<= 1; /* equivalent to a*2 */
            b >>= 1; /* equivalent to b // 2 */
    }
    return p;
}

int main(){
    // printf("%x\n",mul16(0x06)&0xFF);
    // printf("%x\n",mul32(0x06)&0xFF);


    // printf("%x\n",mul32(0x22)&0xFF);
    // printf("%x\n",gmul(0x22,32)&0xFF);

    printf("---------\n");
    printf("%x\n",mul128(0xf5)&0xFF);
    printf("%x\n",gmul(0xf5,128)&0xFF);

        printf("---------\n");
    printf("%x\n",mul64(0xf5)&0xFF);
    printf("%x\n",gmul(64,0xf5)&0xFF);

        printf("---------\n");
    printf("%x\n",mul192(0x35)&0xFF);
    printf("%x\n",gmul(192,0x35)&0xFF);

        printf("---------\n");
    printf("%x\n",mul133(0x35)&0xFF);
    printf("%x\n",gmul(133,0x35)&0xFF);

            printf("---------\n");
    printf("%x\n",mul194(0xe5)&0xFF);
    printf("%x\n",gmul(194,0xe5)&0xFF);


    return 0;
}
| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer. I'm coding in VHDL, but your C code will be extremely useful to me. $\endgroup$ – Cedric Jul 16 '18 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.