ガロア体
計算結果が有限の値に納まるらしいもの
暗号で使うのは拡大体 $ GF(2^m)的なものと素数のガロア体
RSAでは ガロア体 ?
AESでは8bitのが使われる。3*5*17 = 255 0x11b
ガロア体とは説明されていないものの、CMAC、OMAC1、OMAC2でも使われていたり。
8bitのものと128bitのものを抑えておけばだいたい使える。
掛け算、足し算しかできないように思われているが、じつはビットシフトもできるのでOMAC2で使われている/2とか簡単。
利用目的
特定の範囲でくり返す輪(x進数)をわかりにくく並べ替えてみたい時にちょうどよかった?
逆数で簡単に戻すことができるので暗号として利用可能
べき乗表現と ベクトル表現(ビットっぽいもの)あり
$ GF(2^m)の場合
加算・減算
$ a \oplus b 減算も同じ
桁上がりしない
a XOR b
記号 \u2A01 ⨁ N-ARY CIRCLED PLUS OPERATOR
add
乗算
$ 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^x / a^y = a^{x-y} x-y<0ならx-y+max
ベクトルでは逆数inv()してから乗算に若干調整
a / b = a・inv(b)
div
8bit の場合は 255回の乗算で元に戻る (0除く)ので、254回で-1回と同じ
逆数
inv
暗号
$ a \cdot 3 が $ a \cdot 2 \oplus a で計算できるが逆は $ a / 3 では計算できない
2が3と関係ないから?
$ a^x・a^yのxとyでaと3を知っていれば計算可能、3からすぐにyが計算できない 加算で壊れる
似たもの