ガロア体
計算結果が有限の値に納まるらしいもの
素数 $ p
自然数 $ n
体? $ GF(p)
ガロア体 有限体 $ GF(p^n)
原始元
体は閉じた計算ができる形?
a mod p だかなんだかで pが2で 0 と 1
table:a
a b 加算・減算 乗算
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
暗号で使うのはp = 2の拡大体 $ GF(2^m)的なものと素数のガロア体
RSAでは ガロア体ではない形 ? GF(n) は素数2つで拡大体に似たなにか?
AESでは8bitの$ GF(2^8) のようなものが使われる。
GCM, などでは$ GF(2^{128})
乗算で使う多項式 (複数パターンあり ビット逆順でも可?)
$ x^8+x^4+x^3+x^1 + 1 = 0b100011011 = 0x11b
$ x^{128} + x^7 + x^2 + x^1 + 1 = 0x10000000000000087 = 0b1000...010000111
$ a を省略した書き方?
2以外の素数の乗算をしていって一周できるものが原始多項式かな?
ガロア体とは説明されていたりいなかったり、CBC、GCM、CMAC、OMAC1、OMAC2でも使われていたり。 8bitのものと128bitのものを抑えておけばだいたい使える。CBCは32bit
掛け算、足し算しかできないように思われているが、じつはビットシフトもできるのでOMAC2で使われている/2とか簡単。
利用目的
特定の範囲でくり返す輪(x進数)をわかりにくく並べ替えてみたい時にちょうどよかった?
逆数で簡単に戻すことができるので暗号として利用可能
べき乗表現と ベクトル表現(ビットっぽいもの)あり
$ GF(2^n)の場合
加算・減算
$ a \oplus b 減算も同じ
桁上がりしない
a XOR b
記号 \u2A01 ⨁ N-ARY CIRCLED PLUS OPERATOR
add
シフト演算 (独自)
シフト、桁があふれたところで多項式を使って丸める mod P
乗算に利用する 左シフトを桁上りの最小単位として分けておくといいかも
キャッシュしておくことで乗算での高速化が可能
シフトでいいのか?
OMAC2などでは逆に右シフトも可能なことがわかる
乗算
$ a \cdot b
ビット単位の掛け算 (加算・減算で桁上りしない)
$ a \cdot 2がビットシフトと桁あふれの処理で計算できる
$ a \cdot 2 = a << 1
$ a^x \cdot a^y = a^{x+y}
mul
べき乗 $ a^x と$ a^yのxとyがわかる場合(8bit程度)は$ a^{x+y}の足し算で可能
記号 ⨀ を使うことも ある?
$ aは素数が使えるが、3を使ったりすることもよくあり
除算
べき乗では引き算
$ a^x / a^y = a^{x-y} x-y<0ならx-y+max
ベクトルでは逆数inv()してから乗算に若干調整
$ a / b = a・b^{-1} = a・inv(b)
div
8bit の場合は $ a(素数?) は255回の乗算で元に戻る ので、254回で-1回と同じ
逆数
乗算で1になる対
inv
8bitでは254乗で1周するので$ a^{-1} = a^{255 - 1}
暗号
$ a \cdot 3 が $ a \cdot 2 \oplus a で計算できるが逆は $ a / 3 では計算できない
2が3と関係ないから?
$ a^x・a^yのxとyでaと3を知っていれば計算可能、3からすぐにyが計算できない 加算で壊れる
似たもの