跳转至

Galois Field in Cryptography

Official Document

https://sites.math.washington.edu/~morrow/336_12/papers/juan.pdf

Explanations

多项式模的计算方法(Example1)

We take the irreducible polynomial modulo m(p) to be p^8+p^6+p^5+p^1+p^0.

To calculate 84·13\ (mod\ m(p)),we go through the following steps:

\begin{align*} 84 · 13 & = ((2^6 + 2^4 + 2^2 ) · (2^3 + 2^2 + 2^0 ))\ (mod\ m(p))\\ & = (2^9 + 2^8 + 2^7 + 2 · 2^6 + 2^5 + 2 · 2^4 + 2^2 )\ (mod\ m(p))\\ & = (2^9 + 2^8 + 2^7 + 2^5 + 2^2 )\ (mod\ m(p)) \end{align*}

Take 2^9 + 2^8 + 2^7 + 2^5 + 2^2 's coefficients out as 1110100100 , p^8+p^6+p^5+p^1+p^0 's as 101100011, then we use long division to compute the reduced polynomial as follows:

\require{enclose} \begin{array}{rll} 11 && \hbox{$...Quotient$ ($2^1+2^0$) } \\[-3pt] 101100011 \enclose{longdiv}{1110100100}\kern-.2ex \\[-3pt] \underline{101100011\phantom{0}} && \hbox{$Apply\ XOR\ Operation$} \\[-3pt] {101100010}\kern.2ex \\[-3pt] \underline{\phantom{0}101100011} \\[-3pt] \phantom{0}1 && \hbox{$...Remainder$ ($2^0$)} \\[-3pt] \end{array}

which denotes that 84·13\ \div m(p) = 2^1+2^0 ··· 2^0. This also indicates that 84 and 13 are multiplicative inverse pairs to m(p).

求逆(Example2)

Suppose we don't know the multiplicative inverse of 84 to m(p)​. Then to calculate the multiplicative inverse we will use Extended Euclidean Algorithm. Unlike long division, we need to keep track of the auxiliary when we work with Extended Euclidean Algorithm as follows:

Remainder Quotient Auxiliary
2^8+2^6+2^5+2^1+2^0 / 0
2^6+2^4+2^2 / 1
2^5+2^4+2^1+2^0 2^2 2^2
2^0 2^1+2^0 2^3+2^2+2^1

The first two rows in the Remainder column are always the modulo polynomial followed by the polynomial we wish to invert. The first two rows in the Auxiliary are always 0 and 2^0 . The remainder and the quotient in row n is then calculated from the division of the remainders in row n − 1 and n − 2 while the auxiliary in row n is given by the sum of the auxiliary in row n − 2 and the product of the quotient in row n and the auxiliary in row n − 1 until the last remainder equals to 2^0. The final entry in Auxiliary happens to be the multiplicative inverse of the product, thus the multiplicative inverse of 84 is 2^3 + 2^2 + 2^0 = 13 which agrees with the preceding example.


2018/8/16