GF(2^8)->GF((2^4)^2)の変換

質問

ガロア体の逆数演算で、
GF(2^8)->GF((2^4)^2)
に変換して計算しようとしています。
それで、GF(2^8)元aより、GF((2^4)^2)の元bへの変換、
b=A*aがうまく行きません。

GF(2^8)では、生成多項式
X^8=p7*X^7+p6*X^6---
で元を順次つくります。1ビット単位のシフトレジスタを使って、
α^0=1h
α^1=2h
α^2=4h

と言う風になります。

GF((2^4)^2)では、生成多項式
Y^2=q1*Y+q0
で元をつくります。ここで、q1,q2は、GF(2^4)の元です。
したがって、4ビット単位のシフトレジスタを使って、
β^0=1h
β^1=10h
となります、ここでわからないのは、b=A*aの変換手順です。
a=α^0=1h
の場合は、
b=β^0=1h
に対応します。
問題は次で、
a=α^1=2hの場合は、
b=β^1=10hに変換するように、Aを設計しています。
つまり、
10h=A*2h
の関係を成立させています。
これでは、b=3h、つまり、
A*3h
がうまく行きません。
多分、α^1とβ^1を直接変換するのが、間違いだと思いますが、
どうすればいいでしょう？

回答No.10

reiman · ベストアンサー

ω∈GF(2^8)
の逆数を求めてみる。
No.9の前段の変換により
ω=pγ+q　p,q∈GF(2^4)
とする。
δ=p^2b+pqa+q^2 (∈GF(2^4))
と置くと
ω^-1=δ^-1pγ+δ^-1(pa+q)
ただし、a,bはそれぞれNo.9の前段のa,bである。
よってω^-1を求めるためにはGF(2^4)の元δの逆数が求まれば良い。
次に
δ∈GF(2^4)
の逆数を求めてみる。
No.9の後段の変換により
δ=p'β+q'　(p',q'∈GF(2^2))
とする。
η=p'^2b'+p'q'a'+q'^2 (∈GF(2^2))
と置くと
δ^-1=η^-1p'β+η^-1(p'a'+q')
ただし、a',b'はそれぞれNo.9の後段のa,bである。
よってδ^-1を求めるためにはGF(2^2)の元ηの逆数が求まれば良い。
以上まとめて
ω^-1を求めるためにはGF(2^2)の元ηの逆数が求まれば良い。
GF(2^2)の非零元は3個しかないのでω^-1を求めるためにたった3個の小さな逆数テーブルを使えばよい。

おまけ：
γ^8=1+γ^2+γ^3+γ^4
γ^9=γ+γ^3+γ^4+γ^5
γ^10=γ^2+γ^4+γ^5+γ^6
γ^11=γ^3+γ^5+γ^6+γ^7
γ^12=1+γ^2+γ^3+γ^6+γ^7
γ^13=1+γ+γ^2+γ^7
γ^14=1+γ+γ^4
γ^15=γ+γ^2+γ^5
γ^16=γ^2+γ^3+γ^6
γ^17=γ^3+γ^4+γ^7
γ^18=1+γ^2+γ^3+γ^5
γ^19=γ+γ^3+γ^4+γ^6
γ^20=γ^2+γ^4+γ^5+γ^7
γ^21=1+γ^2+γ^4+γ^5+γ^6
γ^22=γ+γ^3+γ^5+γ^6+γ^7
γ^23=1+γ^3+γ^6+γ^7
γ^24=1+γ+γ^2+γ^3+γ^7
γ^25=1+γ
γ^26=γ+γ^2
γ^27=γ^2+γ^3
γ^28=γ^3+γ^4
γ^29=γ^4+γ^5
γ^30=γ^5+γ^6
γ^31=γ^6+γ^7

お礼

ありがとうございます。
お陰さまで、線形変換行列は求まりました。
またよろしく。

回答No.9

reiman

【GF(2^4)→GF(2^8)】
GF(2)→GF(2^8)の生成多項式として
x^8+x^4+x^3+x^2+1
を使い
GF(2)→GF(2^4)の生成多項式として
x^4+x+1
を使い
GF(2^4)→GF(2^8)の生成多項式として
x^2+ax+b　(a,b∈GF(2^4))
を使うとし
GF(2^4)の生成元をβとし
GF(2^8)の生成元をγとする。
すると以下が成立する。
γ^8+γ^4+γ^3+γ^2+1=0…(1)
β^4+β+1=0…(2)
γ^2+aγ+b=0…(3)
β=β[0]+β[1]γ+β[2]γ^2+β[3]γ^3+β[4]γ^4+β[5]γ^5+β[6]γ^6+β[7]γ^7
(β[0],β[1],β[2],β[3],β[4],β[5],β[6],β[7]∈GF(2))
とし
(2)に代入して(1)を使って7次以下のγの多項式にして
γのべき乗の係数を0としてβをγの式として求める。
β[1]=β[2]=β[5]=β[6]=0
β[3]=β[4]=β[7]=1
なおβ[0]=0とおく。(β[0]は任意に設定できる。)
よって
β=γ^3+γ^4+γ^7…(4)
同様に
a=a[0]+a[1]β+a[2]β^2+a[3]β^3　(a[0],a[1],a[2],a[3]∈GF(2))
b=b[0]+b[1]β+b[2]β^2+b[3]β^3　(b[0],b[1],b[2],b[3]∈GF(2))
とおき(1),(3),(4)に代入して
a[0],a[1],a[2],a[3],b[0],b[1],b[2],b[3]
を求めると
a[0]=a[1]=a[3]=b[0]=b[2]=b[3]=0
b[1]=a[2]=1
よって
a=β^2…(5)
b=β…(6)
(1),(4)を使い以下が分かる。
β^0=1
β^1=γ^3+γ^4+γ^7
β^2=γ+γ^2+γ^3+γ^6
β^3=γ+γ^3
γβ^0=γ
γβ^1=1+γ^2+γ^3+γ^5
γβ^2=γ^2+γ^3+γ^4+γ^7
γβ^3=γ^2+γ^4
R^T=[γ^0　γ^1　γ^2　γ^3　γ^4　γ^5　γ^6　γ^7]
B^T=[β^0　β^1　β^2　β^3　γβ^0　γβ^1　γβ^2　γβ^3]
G=
[1 0 0 0 0 0 0 0]
[0 0 0 1 1 0 0 1]
[0 1 1 1 0 0 1 0]
[0 1 0 1 0 0 0 0]
[0 1 0 0 0 0 0 0]
[1 0 1 1 0 1 0 0]
[0 0 1 1 1 0 0 1]
[0 0 1 0 1 0 0 0]
とおくと
B=GR…(7)
とできる。
一方
GF(2)上の8次元列ベクトルx,yにより
R^Tx=B^Ty
ならば(7)により
R^Tx=(GR)^Ty
すなわち
x=G^Ty
A=(G^T)^-1=
[1 0 0 0 0 1 0 0]
[0 0 1 0 1 1 1 0]
[0 0 0 0 0 0 1 0]
[0 0 0 1 0 1 1 1]
[0 1 0 1 0 1 0 1]
[0 0 0 0 0 1 0 0]
[0 0 1 0 1 1 1 1]
[0 0 0 0 1 0 0 1]
とおくと
y=Ax

【GF(2^2)→GF(2^4)】
GF(2)→GF(2^4)の生成多項式として
x^4+x+1
を使い
GF(2)→GF(2^2)の生成多項式として
x^2+x+1
を使い
GF(2^2)→GF(2^4)の生成多項式として
x^2+ax+b　(a,b∈GF(2^2))
を使うとし
GF(2^2)の生成元をαとし
GF(2^4)の生成元をβとする。
すると以下が成立する。
β^4+β+1=0…(1)
α^2+α+1=0…(2)
β^2+aβ+b=0…(3)
α=α[0]+α[1]β+α[2]β^2+α[3]β^3　(α[0],α[1],α[2],α[3]∈GF(2))
とし
(2)に代入して(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてαをβの式として求める。
α[0]=0
α[1]=1
α[2]=1
α[3]=0
なおα[0]=0とおく。(α[0]は任意に設定できる。)
よって
α=β^2+β…(4)
同様に
a=a[0]+a[1]α　(a[0],a[1]∈GF(2))
b=b[0]+b[1]α　(b[0],b[1]∈GF(2))
とおき(1),(3),(4)に代入して
a[0],a[1],b[0],b[1]
を求めると
a[0]=1
a[1]=0
b[0]=0
b[1]=1
よって
a=1…(5)
b=α…(6)
(1),(4)を使い以下が分かる。
α^0=1
α^1=β^2+β
βα^0=β
βα^1=β^3+β^2
R^T=[β^0　β^1　β^2　β^3]
B^T=[α^0　α^1　βα^0　βα^1]
G=
［１　０　０　０］
［０　１　１　０］
［０　１　０　０］
［０　０　１　１］
とおくと
B=GR…(7)
とできる。
一方
GF(2)上の4次元列ベクトルx,yにより
R^Tx=B^Ty
ならば(7)により
R^Tx=(GR)^Ty
すなわち
x=G^Ty
A=(G^T)^-1=
［１　０　０　０］
［０　０　１　１］
［０　１　１　１］
［０　０　０　１］
とおくと
y=Ax

回答No.8

reiman

＞わかりが悪くてすみません。
＞γ^2+aγ+b=0
＞で、
＞(a,b∈GF(2^4))
＞(γ∈GF(2^8))
＞の混合演算はどうするのでしょう？

無効になった古いバージョンのところに書いてあったので見落としました。

GF(2^8)はGF(2^4)の拡大体なので
GF(2^4)の元は拡大されたGF(2^8)に含まれる。
GF(2^8)は体GF(2^4)上の2次元ベクトル空間なのである。

回答No.7

reiman

前回の編集ミスを修正

わかりやすくするために
GF(2^4)→GF((2^2)^2)
の場合にやってみます。

GF(2^4)の生成多項式として
x^4+x+1
を使い
GF(2^2)の生成多項式として
x^2+x+1
を使い
GF((2^2)^2)の生成多項式として
x^2+ax+b
(a,b∈GF(2^2))
を使うとし
GF(2^2)の生成元をαとし
GF(2^4)の生成元をβとする。
すると以下が成立する。
β^4+β+1=0…(1)
α^2+α+1=0…(2)
β^2+aβ+b=0…(3)
fを3次以下多項式として
α=f(β):=α[3]β^3＋α[2]β^2+α[1]β+α[0]
とし
(2)に代入して
f(β)^2+f(β)+1=0
これを(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてfすなわちαをβの式として求める。
(未知数も式も4個なので求まる。)
×＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
α[3]β^6＋α[2]β^4+α[1]β^2+α[0]+α[3]β^3＋α[2]β^2+α[1]β+α[0]+1=0
よって
(α[3]+α[1]+α[2])β^2+(α[2]+α[1])β+(α[2]+1)=0
よって
α[2]=1
α[2]=α[1]
α[3]+α[1]+α[2]=0
よって
α[0]=0
α[1]=1
α[2]=1
α[3]=0
とできる。
よって
α=β^2+β
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
同様に
g,hをそれぞれ2次以下の多項式として
a=g(f(β)):=a[1]α+a[0]=a[1](β^2+β)+a[0]
b=h(f(β)):=b[1]α+b[0]=b[1](β^2+β)+b[0]
として(3)に代入して
β^2+g(f(β))β+h(f(β))=0
これを(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてgとhすなわちa,bをβの式として求める。
(未知数も式も4個なので求まる。)
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
β^2+(a[1](β^2+β)+a[0])β+b[1](β^2+β)+b[0]=0
よって
(a[1])β^3+(1+a[1]+b[1])β^2+(a[0]+b[1])β+(b[0])=0
a[1]=0
1+a[1]+b[1]=0
a[0]+b[1]=0
b[0]=0
よって
a[0]=1
a[1]=0
b[0]=0
b[1]=1
よって
a=1
b=α
よって
β^2+β+α=0
これは先に求めた式と同じ
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
そして
α^0=1
α^1=β^2+β
βα^0=β
βα^1=β(β^2+β)=β^3+β^2
R=[β^0　β^1　β^2　β^3]^T
B=[α^0　α^1　βα^0　βα^1]^T
とおくと上記の関係式により求まるGF(2)上の4次正方行列Gによって
B=GR
とできる。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
G=
［１　０　０　０］
［０　１　１　０］
［０　１　０　０］
［０　０　１　１］
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
一方
GF(2)上の4次元行ベクトルx,yにより
xR=yB
ならば
xR=yGR
すなわち
x=yG
すなわち
y^T=(G^T)^-1x^T
結局
A=(G^T)^-1
とすればよい。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
A=
［１　０　０　０］
［０　０　１　１］
［０　１　１　１］
［０　０　０　１］
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

回答No.6

reiman

わかりやすくするために
GF(2^4)→GF((2^2)^2)
の場合にやってみます。

GF(2^4)の生成多項式として
x^4+x+1
を使い
GF(2^2)の生成多項式として
x^2+x+1
を使い
GF((2^2)^2)の生成多項式として
x^2+ax+b
(a,b∈GF(2^2))
を使うとし
GF(2^2)の生成元をαとし
GF(2^4)の生成元をβとする。
すると以下が成立する。
β^4+β+1=0…(1)
α^2+α+1=0…(2)
β^2+aβ+b=0…(3)
fを2次以下多項式として
α=f(γ):=α[3]β^3＋α[2]β^2+α[1]β+α[0]
とし
(2)に代入して
f(γ)^4+f(γ)+1=0
これを(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてfすなわちαをβの式として求める。
(未知数も式も4個なので求まる。)
×＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
α[3]β^6＋α[2]β^4+α[1]β^2+α[0]+α[3]β^3＋α[2]β^2+α[1]β+α[0]+1=0
よって
(α[3]+α[1]+α[2])β^2+(α[2]+α[1])β+(α[2]+1)=0
よって
α[2]=1
α[2]=α[1]
α[3]+α[1]+α[2]=0
よって
α[0]=0
α[1]=1
α[2]=1
α[3]=0
とできる。
よって
α=β^2+β
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
同様に
g,hをそれぞれ2次以下の多項式として
a=g(f(β)):=a[1]α+a[0]=a[1](β^2+β)+a[0]
b=h(f(β)):=b[1]α+b[0]=b[1](β^2+β)+b[0]
として(3)に代入して
β^2+g(f(β))β+h(f(β))=0
これを(1)を使って3次以下のβの多項式にして
βのべき乗の係数を0としてgとhすなわちa,bをβの式として求める。
(未知数も式も4個なので求まる。)
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
β^2+(a[1](β^2+β)+a[0])β+b[1](β^2+β)+b[0]=0
よって
(a[1])β^3+(1+a[1]+b[1])β^2+(a[0]+b[1])β+(b[0])=0
a[1]=0
1+a[1]+b[1]=0
a[0]+b[1]=0
b[0]=0
よって
a[0]=1
a[1]=0
b[0]=0
b[1]=1
よって
a=1
b=α
よって
β^2+β+α=0
これは先に求めた式と同じ
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
そして
α^0=1
α^1=β^2+β
βα^0=β
βα^1=β(β^2+β)=β^3+β^2
R=[β^0　β^1　β^2　β^3]^T
B=[α^0　α^1　βα^0　βα^1]^T
とおくと上記の関係式により求まるGF(2)上の4次正方行列Gによって
B=GR
とできる。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
G=
［１　０　０　０］
［０　１　１　０］
［０　１　０　０］
［０　０　１　１］
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
一方
GF(2)上の4次元行ベクトルx,yにより
xR=yB
ならば
xR=yGR
すなわち
x=yG
すなわち
y^T=(G^T)^-1x^T
結局
A=(G^T)^-1
とすればよい。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
A=
［１　０　０　０］
［０　０　１　１］
［０　１　１　１］
［０　０　０　１］
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

回答No.5

reiman

どうもNo.4を見ていると
敢えてa,bを求める必要は無さそうですね。

回答No.4

reiman

もっとスマートに変更。

GF(2^8)の生成多項式として
x^8+x^4+x^3+x^2+1
を使い
GF(2^4)の生成多項式として
x^4+x+1
を使い
GF((2^4)^2)の生成多項式として
x^2+ax+b
(a,b∈GF(2^4))
を使うとし
GF(2^4)の生成元をβとし
GF(2^8)の生成元をγとする。
すると以下が成立する。
γ^8+γ^4+γ^3+γ^2+1=0…(1)
β^4+β+1=0…(2)
γ^2+aγ+b=0…(3)
fを7次以下多項式として
β=f(γ)
とし
(2)に代入して
f(γ)^4+f(γ)+1=0
これを(1)を使って7次以下のγの多項式にして
γのべき乗の係数を0としてfすなわちβをγの式として求める。
(未知数も式も8個なので求まる。)
同様に
g,hをそれぞれ3次以下の多項式として
a=g(f(γ))
b=h(f(γ))
として(3)に代入して
γ^2+g(f(γ))γ+h(f(γ))=0
これを(1)を使って7次以下のγの多項式にして
γのべき乗の係数を0としてgとhすなわちa,bをγの式として求める。
(未知数も式も8個なので求まる。)
そして
β^0=1
β^1=f(γ)
β^2=f^2(γ)
β^3=f^3(γ)
γβ^0=γ
γβ^1=γf(γ)
γβ^2=γf^2(γ)
γβ^3=γf^3(γ)
の式において
右辺を(1)を使いすべてγの7次以下の多項式にする。
すると
R=[γ^0　γ^1　γ^2　γ^3　γ^4　γ^5　γ^6　γ^7]^T
B=[β^0　β^1　β^2　β^3　γβ^0　γβ^1　γβ^2　γβ^3]^T
とおくと上記の関係式により求まるGF(2)上の8次正方行列Gによって
B=GR
とできる。
一方
GF(2)上の8次元行ベクトルx,yにより
xR=yB
ならば
xR=yGR
すなわち
x=yG
すなわち
y^T=(G^T)^-1x^T
結局
A=(G^T)^-1
とすればよい。

回答No.3

reiman

GF(2^8)の生成多項式として
x^8+x^4+x^3+x^2+1
を使い
GF(2^4)の生成多項式として
x^4+x^+1
を使い
GF((2^4)^2)の生成多項式として
x^2+ax+b
(a,b∈GF(2^4))
を使うとすると
GF(2^4)の生成元βにより
a,bを表現し
βをGF(2^8)の生成元γにより表現する。
a,bを求めるときには
γ^8+γ^4+γ^3+γ^2+1=0
β^4+β+1=0
γ^2+aγ+b=0
であることを利用する。
a,bはそれぞれ15通りしかないので
かたっぱしから入れてみて上式を満たすものを求めれば良い。
存在が保証されているので一組は必ず有るので一組のみ求める。
C,PHPなどのプログラミングでやれば良いでしょう。
次にβをγの8次未満の多項式として表す。
すなわちfを7次多項式として
β=f(γ)
すると
β^0=1
β^1=f(γ)
β^2=f^2(γ)
β^3=f^3(γ)
γβ^0=γ
γβ^1=γf(γ)
γβ^2=γf^2(γ)
γβ^3=γf^3(γ)
なお、右辺はγ^8+γ^4+γ^3+γ^2+1=0を使いすべてγの7次以下の多項式にする。
すると
R=[γ^0　γ^1　γ^2　γ^3　γ^4　γ^5　γ^6　γ^7]^T
B=[β^0　β^1　β^2　β^3　γβ^0　γβ^1　γβ^2　γβ^3]^T
とおくと上記の関係式により求まるGF(2)上の8次正方行列Gによって
B=GR
とできる。
一方
GF(2)上の8次元行ベクトルx,yにより
xR=yB
ならば
xR=yGR
すなわち
x=yG
すなわち
y^T=(G^T)^-1x^T
結局
A=(G^T)^-1
とすればよい。

補足

わかりが悪くてすみません。
γ^2+aγ+b=0
で、
(a,b∈GF(2^4))
(γ∈GF(2^8))
の混合演算はどうするのでしょう？

回答No.2

reiman

No.1は撤回します。
まず元のGF(2^8)の生成多項式は
x^8+x^4+x^3+x^2+1
ですね？
参考サイトでは
x^8+x^4+x^3+x+1
になっていたのですがこれは原始多項式ではありませんね。
これを使ってもいいのですが原始多項式を使った方がいいでしょう。
次に
GF(2^4)の生成多項式は
x^4+x+1
ですね？
これは原始多項式です。
GF((2^4)^2)の生成多項式はGF(2^4)の生成元をαとしたとき
どのように選んだのでしょうか？
つまりp0,p1は？

お礼

現実には、
「Practical Implementation of Rijndael S-Box Using Combinational Logic」Edwin他
に添って、実装しています。
ハード的には、簡単な回路で、乗算や逆数演算ができます。
実際は、
GF(2^8)->GF(((2^2)^2)^2)に変換し、
演算をおこない、
GF(((2^2)^2)^2)->GF(2^8)
に戻します。
RS復号のように、加算、乗算、割り算が混在している場合はいちいちテーブルを引き直す必要がないので、ハードウエア化した場合は、動作速度が向上し、回路面積も小さくなります。

ポイントは、質問にも書いているように、
GF((2^4)^2)
での、β^1の考え方です。

β^1=10h
でいいのか？

補足

＞GF((2^4)^2)の生成多項式はGF(2^4)の生成元をαとしたとき
＞どのように選んだのでしょうか？
＞つまりp0,p1は？
そのあたりは文献に書いていますし、考え方は、質問の中にも書いています。

あと、文献はあくまで参考文献で、GF(2^8)の生成多項式は、
x^8＋x^4＋x^3＋x^2＋1
を使っています。
ただ、Rijndael Encryptionでは、
x^8+x^4+x^3+x+1
が正解のようです。他の文献でもそうなっています。

その辺の違いがあるので、線形変換マトリックス
Ａを求めなおしたいのですが。

回答No.1

reiman

何がしたいのか分からないのだけれども
GF((2^4)^2)とやらは
GF(2^4)の拡大体で
GF(2^8)のことですね。
それだと
もとのGF(2^8)と構造は全く同じで
生成元が違うだけですね。
すなわち
実質的に8次生成多項式の違いだけですから
xに対してx^-1をもとめるのに
GF(2^8)→GF(2^8)
の変換は余り意味はないように思います。

補足

何をしたいかは、例えば、
「A Systematic Evaluation of Compact Hardware Implementations
for the Rijndael S-Box」Nele Mentens他
を読んでいただけますか？検索で出てきます。多分。
テーブルを使わずにしかも極力簡単に逆元を求めたいのです。
ここでのp329のFig.3あたりの行列の求め方を知りたいのです。