Zenn
Open12

「暗号技術のすべて」メモ

inabajunmrinabajunmr

p124 の統計的距離の式

\sum_{ \begin{subarray}{l} x\in \{0,1\}^{n} \end{subarray}} | Pr [Xn = x] - Pr[Zn = x] |

は、n ビットのすべての集合 x に対する、Xn が x である確率 - Zn が x である確率の合計を表す。

Xn について

各要素の確率は \frac{1}{2^n} で、要素数は 2^nとなる。

Zn について

全部 1 はやり直しなので、確率は 0、それ以外の各要素の確率は \frac{1}{2^n-1} で、要素数は 2^n-1となる。

まとめると

Xn も Zn も、発生しうる値のパターンは (2^n - 1) あるので、各要素の確率の差に (2^n - 1) をかける。

(2^n - 1)| \frac{1}{2^n} - \frac{1}{2^n-1} |

さらに、全部 1 のパターンは 1 パターンのみで、その確率はそれぞれ \frac{1}{2^n} と 0 なので、差をとってパターン数をかけると以下になる。

1 \cdot |\frac{1}{2^n} - 0|

全部足すと p124 に出てくる数式になる。

\sum_{ \begin{subarray}{l} x\in \{0,1\}^{n} \end{subarray}} | Pr [Xn = x] - Pr[Zn = x] | = (2^n - 1)| \frac{1}{2^n} - \frac{1}{2^n-1} | + 1 \cdot |\frac{1}{2^n} - 0|
inabajunmrinabajunmr

p124 の 図 3.19

そもそも b って何？

識別子 D は b の推測値 b' を出力します

p130

「オラクルがランダム置換である状況」を b = 0、「オラクルがブロック暗号の暗号化アルゴリズムである状況」を b = 1 とします。

これか？

とすると、Pr[b' = b] は、オラクルがランダムである、もしくはブロック暗号の暗号化アルゴリズムである確率なので、これが全く区別できない(=1/2) であれば、Adv(D) は 0 になる。（=識別できない）と解釈できそう。

max{Adv(D)} は、任意の b に対して取得した Adv(D) が最も大きいもので、つまりランダムである場合の Pr[b' = b] が 1 だと暗号化アルゴリズムである可能性は 0 となる。

Adv(D) = |Pr[b'=b] - \frac{1}{2}|
Adv(D) = |1 - \frac{1}{2}|
Adv(D) = \frac{1}{2}

なので、max{Adv(D)} は 1/2 となる。
となると、演習問題の回答は 1 なのでなんか違う。なんとなく p132 の式変形で吸収されている、という理解でよさそう。つまり、max{Adv(D)} が 1=2*1/2 で、もし 1/2 が無視できるほど小さければ、1 だって無視できるほど小さい、という考え方。で、この場合は無視できるほど小さいとは言えない。

b は多分、分布 Xn を使っているという事実=1、Yn を使っているという事実=0 のマッピングで、その推測が b' で、b'=b とは推測があたっている、という状態を表す。で、それをブロック暗号の暗号アルゴリズム、という具体的な例に当てはめると、

「オラクルがランダム置換である状況」を b = 0、「オラクルがブロック暗号の暗号化アルゴリズムである状況」を b = 1 とします。

となる。

inabajunmrinabajunmr

p127 確率分布の族とは

そもそも確率分布とは

確率変数がとる値とその値をとる確率の対応の様子を「確率分布」と言います。
https://bellcurve.jp/statistics/course/6596.html より

確率分布 Xn は

Xn, Yn を {0, 1} ^n 上の確率分布とします。
p124

とあるので、n ビットの各ビット列が起きうる確率のこと。識別子にこの発生確率を入力した時に、それがランダムかどうかを判定してくれる。

これに対して、確率分布 Xn ではなく 確率分布の族{Xn} でも識別不可能性を定義できる、と書いてある。

で、確率分布の族とは？ // TODO

inabajunmrinabajunmr

p132 の (1) 式の変形

Pr[b'=b] - \frac{1}{2}

Pr[b'=b] は、識別した結果の b' と実際の b が等しい（=予想通り）なので、つまり「b が 0 でかつ b' が 0」もしくは「b が 1 で b' が 1」なので、

Pr[b'=b=0] + Pr[b'=b=1] - \frac{1}{2}

言い換えると

Pr[b'=0 かつ b=0] + Pr[b'=1 かつ b=1] - \frac{1}{2}

条件付き確率の定義（p102）

Pr(A|B) = \frac{Pr(A かつ B)}{Pr(B)}
Pr(A|B){Pr(B)} = {Pr(A かつ B)}

なので、

Pr[b'=0|b=0]Pr[b=0] + Pr[b'=1|b=1]Pr[b=1] - \frac{1}{2}

と変形できる。b がいずれかの値である可能性は \frac{1}{2} なので（ほんとか？）

\frac{1}{2}Pr[b'=0|b=0] + \frac{1}{2}Pr[b'=1|b=1] - \frac{1}{2}

となり、Pr[b'=0|b=0] は 1-Pr[b'=1|b=0] と変形できる。（b=0 の時、b'=1 である確率は、b=0 の時、b'=0 でない確率だから）

結果、

(1-Pr[b'=1|b=0])\frac{1}{2} + Pr[b'=1|b=1]\frac{1}{2} - \frac{1}{2}

となる。あとは単純に展開していくと最終的な式が得られる。

inabajunmrinabajunmr

p153 暗号文が元の平文に戻ることを確認する式

全然わからない

inabajunmrinabajunmr

p154 相補性の証明

E(\overline{x})=\overline{(E(x)} の E(\overline{x}) = PG1(\overline{x1},...,\overline{x32}) で何が起きているのかわからない

縮小転置 PG1 の結果の反転と、PG1 の入力 64 ビットの前半 32 ビットをそれぞれ反転させて拡大転置 E に入力した結果はおなじになる？

拡大転置は入力された位置にしたがってビットを拡大しているだけなので、ビットの値は拡大の方法に影響しないので、反転したビットを拡大転置しても拡大転置してから反転しても結果は変わらない、というのはわかるんだけど、PG1 がなんで絡んでくるのかよくわからない。

p147 を見るに、この PG1 は E だったりしない？
-> といあわせたら E であってた（https://www.shoeisha.co.jp/book/detail/9784798148816 ）

反転した値を転置すると、結果も反転している、はわかる。
反転した値を XOR した結果と、反転していない値を XOR した結果がおなじになる、もわかる。
\overline{L} ⊕ Q = \overline{L ⊕ Q} は、XOR で片方反転すると結果も反転するやつ。

inabajunmrinabajunmr

p168 Rcon の算出方法

Rcon_i=(x^{i-1} mod\ m(x), 0, 0, 0)
m(x) = x^8 + x^4 + x^3 + x + 1

x、どこから出てきた？（任意の x でも Rcon の値は i によって一意に決まる？）

FIPS 197 より

The round constant word array, Rcon[i], contains the values given by [x^{i-1},{00},{00},{00}], with x^{i-1} being powers of x (x is denoted as {02}) in the field GF(2^8), as discussed in Sec. 4.2 (note that i starts at 1, not 0).

FIPS 197 の 4.2 にもなんか書いてあるけどよくわからない

inabajunmrinabajunmr

MixColumns について

https://tex2e.github.io/blog/crypto/aes-mix-columns

多項式の掛け算

x をかけて既約多項式を引くと法を既約多項式とした時に x でかけた結果がわかる、はわかる気がするんだけど、b_7 = 1 だからそうする、でいいのかがわからない

x^7 × x は法 x^8 + x^4 + x^3 + x + 1 の世界でも x^8 にならない？
→ならない
→この場合、9 ビット目のビットが立ってる状態になるので、割ってあまりを出さないと駄目

掛け算のアルゴリズム

\{\text{57}\}{57} と 1,2,4,8,16,…,1281,2,4,8,16,…,128 を掛け算したときの結果を用意します。

の表がわからない
なんで 8 の次 10 なんだろ

適当に計算すると計算結果自体はあってる気がするんだけど、なんで 08 の次が 10 になる？

func Test(t *testing.T) {
	x2 := xtime(0x57)
	fmt.Printf("%02x\n", x2)
	x3 := xtime(x2)
	fmt.Printf("%02x\n", x3)
	x4 := xtime(x3)
	fmt.Printf("%02x\n", x4)
	x5 := xtime(x4)
	fmt.Printf("%02x\n", x5)
	x6 := xtime(x5)
	fmt.Printf("%02x\n", x6)
	x7 := xtime(x6)
	fmt.Printf("%02x\n", x7)
	x8 := xtime(x7)
	fmt.Printf("%02x\n", x8)
	t.Error()
}

func xtime(b byte) byte {
	data := binary.LittleEndian.Uint16([]byte{b, 0})
	x := data << 1
	r := make([]byte, 8)
	if x&0x100 != 0 {
		binary.LittleEndian.PutUint16(r, x^0x1b)
	} else {
		binary.LittleEndian.PutUint16(r, x)
	}
	return r[0]
}

→ふつうに 2 進数で桁があがっていくのを 16 進数で書いてるだけだった・・・

dot は

x=01010111(57)
y=10000011(83)
で考えると、

mask=00000001

y の 00000001 が立ってるので
product = product xor x = 01010111
x = xtime(x) = 10101110(ae)

mask=00000010

y の 00000010 が立ってるので
product = product xor x = 11111001
x = xtime(x) = 10101110(ae)

mask=00000100

y の 00000100 が立ってないので
x = xtime(x) = 10101110(47)

...

mask=10000000

y の 10000000 が立ってるので
product = product xor x = (57 * 1 + 57 * 2) xor 57 * 80

つまり、x に 57 * n を入れておいて都度
0 xor x を product に代入
57 * 1 xor 57 * 2 を product に代入
...
57 * 1 xor 57 * 2 xor 57 * 80 を product に代入