暗号理論の問題

出力が $N=200$ 通りの値のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に $200$ 通りの値から等確率で選ばれるものとする。

互いに異なる $k$ 個の入力 $m_1,m_2,\dots ,m_k$ のハッシュ値のうち、少なくとも $2$ つが一致する（衝突が起こる）確率 $p_k$ を、近似式
$$p_k\approx 1-e^{-\frac{k(k-1)}{2N}}$$
で見積もる。この近似値が $\frac{1}{2}$ 以上となる最小の正の整数 $k$ を求めよ。ただし、$\log 2=0.693$ として計算してよい（$\log$ は自然対数）。

出力が $N=1000$ 通りの値 $\{0,1,2,\dots ,999\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に $1000$ 通りの値から等確率で選ばれるものとする。

互いに異なる $k$ 個の入力（$k$ は正の整数）のハッシュ値を計算したとき、少なくとも $1$ 組の衝突（同じハッシュ値をもつ $2$ つの入力）が起こる確率を $p_k$ とする。$p_k$ を近似式
$$p_k\approx 1-e^{-\frac{k(k-1)}{2N}}$$
で見積もる。この近似値が $\frac{1}{2}$ 以上となる最小の正の整数 $k$ を求めよ。ただし、$\log 2=0.6931$ として計算してよい（$\log$ は自然対数）。

出力が $8$ 通りの値 $\{0,1,2,\dots ,7\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなす。すなわち、互いに異なる入力に対する出力は、それぞれ独立に $8$ 通りの値から等確率で選ばれるものとする。

攻撃者は互いに異なる $5$ 個の入力 $m_1,m_2,\dots ,m_5$ についてハッシュ値 $H(m_1),\dots ,H(m_5)$ を計算する。このとき、ある値 $v$ について $H(m_i)=v$ となる $i$ が $3$ 個以上存在する確率を求めよ。この事象を「$3$ 重衝突（3-マルチコリジョン）が起こる」という。

出力が $8$ 通りの値 $\{0,1,2,\dots ,7\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に $8$ 通りの値から等確率で選ばれるものとする。

攻撃者は、署名してもらいたい「正当な文書」の変種 $x_1,x_2,x_3$ と、すり替えたい「不正な文書」の変種 $y_1,y_2,y_3$ を用意する。これら $6$ 個の入力は互いに異なる。攻撃者は
$$H(x_i)=H(y_j)$$
を満たす $i,j(1\le i\le 3,1\le j\le 3)$ が少なくとも $1$ 組存在するとき、攻撃に成功するものとする。正当な文書どうし、または不正な文書どうしでハッシュ値が一致しても、それだけでは成功とはみなさない。

攻撃に成功する確率を、既約分数で求めよ。

出力が $4$ 通りの値 $\{0,1,2,3\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に $4$ 通りの値から等確率で選ばれるものとする。

攻撃者は互いに異なる入力 $m_1,m_2,m_3,\dots$ をこの順に $1$ つずつ $H$ に問い合わせ、それまでに得た出力のどれかと同じ出力が初めて得られた時点で問い合わせをやめる。すなわち、
$$H(m_t)=H(m_s)\text{となる}s<t\text{が存在する最小の正の整数}t$$
を $T$ とし、攻撃者は $T$ 回問い合わせる。$T$ の期待値 $E[T]$ を求めよ。