Regular and Efficient doubling in $GF(2^n)$

Question

A naive approach to compute a multiplication $a \cdot b$ in a Galois field of the form $GF(2^n)$ is the russian peasant algorithm. However, it does not run in constant time and therefore is not safe against timing attack.

Does there exist optimization techniques to implement $2 \cdot a$ for $a \in GF(2^n)$ in a regular way ?

If we consider $GF(2^4)$ defined by the polynomial $X^4 + X + 1$ (represented by 0x13 in hexadecimal), the most efficient solution I found is to compute $2 \cdot a$ as described below (in C code)

 (a<<1) ^ (0x20 - ((a & 0x8) >> 3)) & 0x13

Can we do better in terms of efficiency without precomputations?

Answer 1

Yes, the principle in the question can be generalized and slightly simplified, as long at there is support for wide-enough arithmetic. In $\text{GF}(2^k)$ represented as integers in range $[0,2^k)$ with a initially in this range, we can double a as:

( P & -( a >> S ) ) ^ ( a + a )

with S defined to $k-1$, and P the constant obtained by evaluating for integer $x=2$ the polynomial $P(x)$ characteristic of the representation of $\text{GF}(2^k)$ as integers.

The expression assumes either the arithmetic rules of C99, or the ubiquitous two's-complement representation of signed integers. It works in most languages ignoring arithmetic overflow. The left operand of the bitwise XOR ^ evaluates to P or to zero depending on if bit S of quantity a is set or clear (under the assumption that no higher-order bit of ais set). The XOR thus performs the reduction modulo $P(x)$ of the right term a + a (equivalent to a << 1 ).

For example, in $\text{GF}(2^8)$ with polynomial $x^8+x^4+x^3+x+1$, we set P to $2^8+2^4+2^3+2+1$ . The expression is:

( 0x11B & -( a >> 7 ) ) ^ ( a + a )

If the result is truncated to $k$ bits (e.g. because it is stored in a variable of that size), then the value of P can (and should) be similarly truncated. This allows all $k\le64$ using 64-bit registers (rather than $k\le63$ if we did not use this truncation technique).

On most modern computers and languages (even interpreted) that represent the quantities involved as a fixed number of computer words, evaluation time is independent of the value of a. That might not hold for integers represented as variable size structure, including long in Python and BigInteger in Java, especially when $k$ is a multiple of the word size.

One compiler is known to emit an "unary minus operator applied to unsigned type" warning, even though the C99 standard explicitly defines the behavior of applying the unary minus operator to an unsigned quantity. Complain to the supplier, and in the meantime squelch the warning with #pragma warning (disable : 4146). Alternately, bow and write

( 0x11B & ( 0 - ( a >> 7 ) ) ) ^ ( a + a )

Answer 2

TL;DR; The general formula is;

$x := deg(primitive \;\; polynomial) -1 $

$$(a \ll 1) \oplus ((1 \ll (x +3)) - [(a \wedge (1 \ll x)) \gg x]) \wedge \{p.p\}$$

A simplification by Dave's comment;

$((a\gg deg) \wedge 1) = ((a\wedge (1 \ll deg)) \gg deg)$

$$\{2\}* a = (a \ll 1) \oplus ((1 \ll (x +3)) - [(a\gg (x-1)) \wedge 1) ] \wedge \{p.p\}$$

---

In the comment, I said that "for the general case, there is no generic algorithm". I was completely wrong. This algorithm indeed generic.

1. case: Why works in $GF(2^4)$ with the primitive polynomial (p.p.) $x^4+x+1 = \{0x13\}$

(a<<1) ^ (0x20 - ((a & 0x8) >> 3)) & 0x13

represent the $a$ as letters in binary $a=\{x_3,x_2,x_1,x_0\}$ let see how the calculation really works.

1. $b = a \ll 1 = \{x_3,x_2,x_1,x_0,0\}$
2. $c = a \;\&\; 0x8= \{x_3,0,0,0\}$
3. $d = c \gg 3 = \{x_3\}$

4. $e = 0x20 - \{x_3\}$ this is the tricky part.

   1. if $\{x_3\} = 0$ than $e = \{1,0,0,0,0,0\} = 0x20$

      1. $b = \{y,z,t,0\}$ //since $x_3=0$
      2. $f = e \;\&\; 0x13 = \{1,0,0,0,0,0\} \;\&\; \{1,0,0,1,1\} = \{0,0,0,0\}$
      3. $2\cdot A= b \oplus e = \{x_2,x_1,x_0,0\} \oplus \{0,0,0,0\} = \{x_2,x_1,x_0,0\} $

   2. if $\{x_3\} = 1$ than $e = \{x_3,x_3,x_3,x_3,x_3\}$

      1. $f = e \;\&\; 0x13 = \{x_3,x_3,x_3,x_3,x_3\} \;\&\; \{1,0,0,1,1\} = \{x_3,0,0,x_3,x_3\}$
      2. $2 \cdot A= b \oplus e = \{x_3,x_2,x_1,x_0,0\} \oplus \{x_3,0,0,x_3,x_3\} = \{x_2,x_1,x_0 \oplus x_3, x_3\} $

2. case: AES $GF(2^8)$ with the primitive polynomial $x^8 + x^4 + x^3 + x + 1 = \{0x11b\}$

(a<<1) ^ (0x200 - ((a & 0x80) >> 7)) & 0x11b

This is exactly same steps only with different size and primitive polynomial;

represent the $a$ as letters in binary $a=\{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0\}$

1. $b = a \ll 1 = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}$
2. $c = a \;\&\; 0x8= \{x_7,0,0,0,0,0,0,0\}$
3. $d = c \gg 7 = \{x_7\}$

4. $e = 0x200 - \{x_7\}$

   1. if $\{x_7\} = 0$ than $e = \{1,0,0,0,0,0,0,0,0,0\} = 0x200$

      1. $b = \{x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}$ //since $x_7=0$
      2. $f = e \;\&\; 0x11b = \{1,0,0,0,0,0,0,0,0,0\} \;\&\; \{1,0,0,0,1,1,0,1,1\} = \{0,0,0,0,0,0,0,0\}$
      3. $\{2\}\cdot A= b \oplus f = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\} \oplus \{0,0,0,0,0,0,0,0\} = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\} $

   2. if $\{x_7\} = 1$ than $e = \{x_7,x_7,x_7,x_7,x_7,x_7,x_7,x_7,x_7\}$

      1. $f = e \;\&\; 0x11b = \{x,x,x,x,x\} \;\&\; \{1,0,0,0,1,1,0,1,1\} = \{x_7,0,0,0,x_7,x_7,0,x_7,x_7\}$
      2. $\{2\} \cdot A= b \oplus f = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\} \oplus \{x_7,0,0,0,x_7,x_7,0,x_7,x_7\} = \\ \{x_6,x_5,x_4,x_3 \oplus x_7,x_2 \oplus x_7,x_1 ,x_0 \oplus x_7,x_7\} $

3. General formula

$x := deg(primitive \;\; polynomial) -1 $

$$(a \ll 1) \oplus ((1 \ll (x +3)) - [(a \wedge (1 \ll x)) \gg x]) \wedge \{p.p\}$$

sketch of proof;

Normally we use primitive polynomial $p = \{x_n,\ldots,x_0\}$ of degree $n$ to represent $x^n = p -x_n$ to replace the $x^n$ as;

let $a=\{a_n,\ldots,a_0\}$ than $\{2\}a=\{a_n,\ldots,a_0,0\}$

if $a_n = 0$ there is nothing to do, $\{2\}a=\{a_{n-1},\ldots,a_0,0\}$

if $a_n = 1$, we add the $x^n = p -x_n$ to the polynomial

$$\{2\}a=\{a_{n-1},\ldots,a_0,0\} + p$$

The algorithm cleverly combines the two cases $a_n =0$ and $a_n=1$. if $a_n =0$ the $\oplus$ part is just $\{0,\ldots,0\}$ with masked the p.p. If not; then it is exactly $x_n-p$.