The Lagrange interpolation polynomial of the AES S-box has degree 254 and 9 terms in it. How about the DES S-boxes? How can we calculate the interpolation polynomial for S-boxes having a different number of input and output bits?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can use any finite field $\mathbb F_{2^n}$ with $2^n$ elements as long as $n$ is at least the maximum of the bitlengths of the in- and output. If in- or output is too short, one can simply extend it with zeros. For the DES one often takes simply $n=6$.
If you define $\mathbb F_{64}$ as $\mathbb F_2[X]/(X^6+X+1)$ (i.e., use $0x43$ where $0x11b$ is used in the definition of the field for the AES), you'll get for the first S-box
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]
the polynomial
$$0x31\cdot X^{62} + 0x19\cdot X^{61} + 0x29\cdot X^{60} + 0x09\cdot X^{59} + 0x0d\cdot X^{58} + 0x02\cdot X^{57} + 0x2f\cdot X^{56} + 0x15\cdot X^{55} + 0x3e\cdot X^{54} + 0x05\cdot X^{53} + 0x3d\cdot X^{52} + 0x27\cdot X^{51} + 0x18\cdot X^{50} + 0x35\cdot X^{49} + 0x39\cdot X^{48} + 0x3e\cdot X^{47} + 0x15\cdot X^{46} + 0x37\cdot X^{45} + 0x19\cdot X^{44} + 0x2c\cdot X^{43} + 0x21\cdot X^{42} + 0x32\cdot X^{41} + 0x21\cdot X^{40} + 0x06\cdot X^{39} + 0x17\cdot X^{38} + 0x1b\cdot X^{37} + 0x1d\cdot X^{36} + 0x1a\cdot X^{35} + 0x18\cdot X^{34} + 0x38\cdot X^{33} + 0x23\cdot X^{32} + 0x0a\cdot X^{31} + 0x0f\cdot X^{30} + 0x23\cdot X^{29} + 0x06\cdot X^{27} + 0x1e\cdot X^{26} + 0x3a\cdot X^{25} + 0x38\cdot X^{24} + 0x1e\cdot X^{23} + 0x3c\cdot X^{22} + 0x2b\cdot X^{21} + 0x31\cdot X^{20} + 0x2f\cdot X^{19} + 0x21\cdot X^{17} + 0x20\cdot X^{16} + 0x0b\cdot X^{15} + 0x18\cdot X^{14} + 0x2b\cdot X^{13} + 0x04\cdot X^{12} + 0x19\cdot X^{11} + 0x16\cdot X^{10} + 0x11\cdot X^{9} + 0x26\cdot X^{8} + 0x1f\cdot X^{7} + 0x0e\cdot X^{6} + 0x36\cdot X^{5} + 0x04\cdot X^{4} + 0x33\cdot X^{3} + 0x17\cdot X^{2} + 0x3e\cdot X + 0x0e$$
