7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For $GF(2^4)$ this seems optimal. I think for the general case, there is no generic algorithm. $\endgroup$ – kelalaka Oct 16 '18 at 15:39
  • 1
    $\begingroup$ sage: [2*x for x in GF(2^4)] gives [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. Maybe there is a simpler algorithm... $\endgroup$ – LeoDucas Oct 16 '18 at 22:08
  • 1
    $\begingroup$ Have a look at the GHASH Section of this $\endgroup$ – Ruggero Oct 17 '18 at 7:20
  • $\begingroup$ @LeoDucas OP actually asking multiplying by $\{2\}$, not the base field element 2. $\endgroup$ – kelalaka Oct 19 '18 at 8:06
  • 1
    $\begingroup$ @LeoDucas Some cryptographers have this weird notation where by $2$ they mean the coset of $X$ (in the quotient ring $\mathbf F_2[X]/(p(X))$), apparently because it can be represented by the binary string 10... $\endgroup$ – fkraiem Oct 19 '18 at 10:21
3
$\begingroup$

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 )
$\endgroup$
4
$\begingroup$

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\} $
  1. 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\} $
  1. 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$.

$\endgroup$
  • $\begingroup$ Nit: (1<<(x+2))-(0or1) or equivalently (1<<(deg+1))-(0or1) is sufficient and what you actually used: deg(0x13)=4,x=3,1<<5=0x20; deg(0x11B)=8,x=7,1<<9=0x200. Also the 0or1 can be done more simply as (a>>x)&1. $\endgroup$ – dave_thompson_085 Oct 20 '18 at 4:12
  • $\begingroup$ @dave_thompson_085 I didn't get the point of $0 \vee 1$ it is already 1 $\endgroup$ – kelalaka Oct 21 '18 at 7:51
  • 1
    $\begingroup$ That's shorthand. The formula is 2a = (a<<1) xor (mask & poly) where mask is ( (1<<(deg+1)) - (if a has highbit set then 1 else 0) ) -- I'm referring to the second part of the mask expression, which is a value that is sometimes 0 and sometimes 1 depending on a, as 0or1. Using ((a>>deg)&1) is a simpler way of computing that subexpression than ((a&(1<<deg))>>deg) . $\endgroup$ – dave_thompson_085 Oct 22 '18 at 9:13

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.