How to compute the inverse of a polynomial under GF(2^8)?

2.2k Views Asked by At

It's well known that AES cryptography algorithm uses Galois Field GF(2^8) multiplication to process the step MixColumn, and each column of the 4*4 matrix on encrypting should multiply the polynomial 3X^3 + X^2 + X + 2 which is usually notated as an array {0x03, 0x01, 0x01, 0x02}, while on decrypting, the matrix should multiply the inverse of the polynominal mentioned above, namely 0x0BX^3 + 0x0DX^2 + 0x09*X + 0x0E which can also notated as an array {0x0B, 0x0D, 0x09, 0x0E}.

Now I wonder If only one polynomial is known, e.g. {0x03, 0x01, 0x01, 0x02}, how can I compute its inverse mod (X^4 + 1), namely {0x0B, 0x0D, 0x09, 0x0E}, and vice versa.

1

There are 1 best solutions below

1
On

The usual method is to apply the extended Euclidean algorithm to your polynomial $p(x)$ and $x^4+1=(x+1)^4$.

Observe that $$p(1)=0\text{x}03\operatorname{XOR} 0\text{x}01 \operatorname{XOR} 0\text{x}01 \operatorname{XOR} 0\text{x}02=0\text{x}01=1\neq0,$$ so we know that there are no common factors. Therefore the extended Euclidean algorithm will produce polynomials $u(x)$ and $v(x)$ with coefficients in $GF(2^8)$ such that $$ u(x)p(x)+v(x)(x^4+1)=1. $$ And from this you can read that the polynomial $u(x)$ (you can reduce it modulo $x^4+1$ to get a unique result) is the inverse you are looking for.