暗号理論の問題

難易度 3期末試験の応用レベル証明問題大学数学暗号理論

$p$ を奇素数、 $g$ を $p$ を法とする原始根とする。 $p$ と互いに素な整数 $c$ について、 $y^{2} \equiv c (mod p)$ をみたす整数 $y$ が存在するとき $c$ を $p$ を法とする平方剰余、存在しないとき平方非剰余という。

アリスとボブが群 $(Z / p Z)^{\times}$ 上でディフィー・ヘルマン鍵共有を行う。アリスは秘密の正の整数 $a$ 、ボブは秘密の正の整数 $b$ を選び、 $A \equiv g^{a} (mod p)$ 、 $B \equiv g^{b} (mod p)$ を公開し、共有鍵を $K \equiv g^{ab} (mod p)$ とする。

このとき、「 $K$ が $p$ を法とする平方非剰余であるための必要十分条件は、 $A$ と $B$ がともに $p$ を法とする平方非剰余であることである」を証明せよ。ただし、原始根の定義（ $g$ の位数が $p - 1$ であり、 $p$ と互いに素な任意の整数は $p$ を法としてある $g^{t}$ （ $0 \leq t \leq p - 2$ ）と合同になること）と、「 $g^{m} \equiv 1 (mod p)$ となる整数 $m \geq 0$ は $p - 1$ の倍数に限る」ことは用いてよい。

この問題で使うもの

ディフィー・ヘルマン鍵共有（説明と入口の問題）
群の位数と元の位数（説明と入口の問題）
剰余類環の単元群とオイラー関数（説明と入口の問題）
合同式（説明と入口の問題）

この問題を解けるようになるまで（26 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$A, B, K$ はどれも $g$ のべき $g^{x}$ の形をしている。 $g^{x}$ が平方剰余かどうかが、指数 $x$ のどんな性質で決まるかを調べよう。

ヒント 2

補題「 $g^{x}$ が平方剰余 $⟺$ $x$ が偶数」を示す。 $y^{2} \equiv g^{x}$ なら $y \equiv g^{t}$ と書けるので $g^{x} \equiv g^{2 t}$ となり、 $g$ の位数が偶数 $p - 1$ であることが効く。

ヒント 3

偶数 $x$ なら $y = g^{x /2}$ がとれる。逆に $g^{x} \equiv g^{2 t}$ から $g^{∣ x - 2 t ∣} \equiv 1$ を導くと $p - 1 ∣ x - 2 t$ がいえる。あとは補題を $x = a, b, ab$ に当てはめ、 $ab$ の偶奇と $a, b$ の偶奇の関係を考える。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$A, B, K$ がいずれも $p$ と互いに素で、平方剰余・平方非剰余のどちらかであることを確認している（1 点）
$x$ が偶数のとき $y = g^{x /2}$ をとって $g^{x}$ が平方剰余であることを示している（2 点）
$g^{x}$ が平方剰余のとき、 $y$ が $p$ と互いに素であることから $y \equiv g^{t}$ と書き、 $g^{x} \equiv g^{2 t}$ から $p - 1 ∣ x - 2 t$ を導いている（3 点）
$p - 1$ が偶数であることを使って $x$ が偶数であると結論し、「 $g^{x}$ が平方非剰余 $⟺$ $x$ が奇数」を得ている（2 点）
補題を $a, b, ab$ に当てはめ、 $ab$ が奇数 $⟺$ $a, b$ がともに奇数であることを理由付きで述べて結論を出している（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

方針. まず補題「0 以上の整数 $x$ について、 $g^{x}$ が平方剰余であることと $x$ が偶数であることは同値」を示し、それを $x = a, b, ab$ に当てはめる。

準備. $g$ は原始根なので $p$ と互いに素であり、任意の 0 以上の整数 $x$ について $g^{x}$ も $p$ と互いに素である。よって $A, B, K$ はいずれも $p$ と互いに素で、平方剰余・平方非剰余のどちらかである。

補題. 0 以上の整数 $x$ に対し、 $g^{x}$ が $p$ を法とする平方剰余 $⟺$ $x$ は偶数。

（ $\Leftarrow$ ） $x$ が偶数なら $x = 2 s$ （ $s$ は 0 以上の整数）と書け、 $y = g^{s}$ とおくと $y^{2} = g^{2 s} = g^{x}$ なので、 $y^{2} \equiv g^{x} (mod p)$ をみたす整数 $y$ が存在する。よって $g^{x}$ は平方剰余である。

（ $\Rightarrow$ ） $g^{x}$ が平方剰余であるとし、 $y^{2} \equiv g^{x} (mod p)$ をみたす整数 $y$ をとる。 $g^{x}$ は $p$ と互いに素だから、 $y^{2}$ も $p$ で割り切れず、 $p$ は素数なので $y$ も $p$ で割り切れない。すなわち $y$ は $p$ と互いに素である。原始根の性質より、 $y \equiv g^{t} (mod p)$ となる整数 $t$ （ $0 \leq t \leq p - 2$ ）がある。すると
$g^{x} \equiv y^{2} \equiv g^{2 t} (mod p) .$
- $x \geq 2 t$ のとき、両辺に $g^{2 t}$ の逆元（ $g$ は $p$ と互いに素なので存在する）を掛けて $g^{x - 2 t} \equiv 1 (mod p)$ 。
- $x < 2 t$ のとき、同様に $g^{2 t - x} \equiv 1 (mod p)$ 。

どちらの場合も、指数 $∣ x - 2 t ∣$ は 0 以上の整数で $g^{∣ x - 2 t ∣} \equiv 1$ なので、用いてよい事実から $∣ x - 2 t ∣$ は $p - 1$ の倍数である。 $p$ は奇素数なので $p - 1$ は偶数であり、 $x - 2 t$ は偶数。 $2 t$ は偶数だから $x$ も偶数である。以上で補題が示された。

補題の対偶を合わせると、「 $g^{x}$ が平方非剰余 $⟺$ $x$ が奇数」である（準備より $g^{x}$ は平方剰余か平方非剰余のどちらかなので）。

本題. $a, b$ は正の整数なので $a, b, ab$ は 0 以上の整数であり、補題が使える。 $A \equiv g^{a}$ 、 $B \equiv g^{b}$ 、 $K \equiv g^{ab}$ で、平方剰余かどうかは $p$ を法とする剰余類だけで決まるから、
- $A$ が平方非剰余 $⟺$ $a$ が奇数
- $B$ が平方非剰余 $⟺$ $b$ が奇数
- $K$ が平方非剰余 $⟺$ $ab$ が奇数

である。整数の積 $ab$ が奇数であることは、 $a$ と $b$ がともに奇数であることと同値である（どちらかが偶数なら積は偶数、ともに奇数なら $a = 2 u + 1, b = 2 v + 1$ として $ab = 2 (2 uv + u + v) + 1$ は奇数）。したがって
$K が平方非剰余 ⟺ ab が奇数 ⟺ a, b がともに奇数 ⟺ A, B がともに平方非剰余 .$

以上より、共有鍵 $K$ が $p$ を法とする平方非剰余であるための必要十分条件は、公開値 $A$ と $B$ がともに平方非剰余であることである。（この結果は、 $(Z / p Z)^{\times}$ 全体で鍵共有を行うと、盗聴者が公開値だけから共有鍵の平方剰余性を知ることができることを意味する。） $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる