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.
- 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.
- $b = a \ll 1 = \{x_3,x_2,x_1,x_0,0\}$
- $c = a \;\&\; 0x8= \{x_3,0,0,0\}$
- $d = c \gg 3 = \{x_3\}$
$e = 0x20 - \{x_3\}$ this is the tricky part.
if $\{x_3\} = 0$ than $e = \{1,0,0,0,0,0\} = 0x20$
- $b = \{y,z,t,0\}$ //since $x_3=0$
- $f = e \;\&\; 0x13 = \{1,0,0,0,0,0\} \;\&\; \{1,0,0,1,1\} = \{0,0,0,0\}$
- $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\} $
if $\{x_3\} = 1$ than $e = \{x_3,x_3,x_3,x_3,x_3\}$
- $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 \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\} $
- 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\}$
- $b = a \ll 1 = \{x_7,x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}$
- $c = a \;\&\; 0x8= \{x_7,0,0,0,0,0,0,0\}$
- $d = c \gg 7 = \{x_7\}$
$e = 0x200 - \{x_7\}$
if $\{x_7\} = 0$ than $e = \{1,0,0,0,0,0,0,0,0,0\} = 0x200$
- $b = \{x_6,x_5,x_4,x_3,x_2,x_1,x_0,0\}$ //since $x_7=0$
- $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\}$
- $\{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\} $
if $\{x_7\} = 1$ than $e = \{x_7,x_7,x_7,x_7,x_7,x_7,x_7,x_7,x_7\}$
- $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\} \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\} $
- 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$.
10
... $\endgroup$ – fkraiem Oct 19 '18 at 10:21