暗号理論

これはRSAを実際に使用可能にする定理である:送信者が公開指数で何を暗号化しても、秘密指数を持つ者はほぼすべてのメッセージだけでなく、あらゆる可能なメッセージに対して常に復号できることを保証する——証明では、メッセージが偶然モジュラスと因数を共有してしまう境界事例も扱わなければならない。

ここで $ed \equiv 1 \pmod{\phi(n)}$ により、モジュラー合同の定義から、ある非負整数 $k$ が存在して $ed = 1 + k\phi(n)$ が成り立つ。

場合1:$\gcd(m,n)=1$ のとき。オイラーの定理より $m^{\phi(n)} \equiv 1 \pmod n$ が成り立つので、両辺を $k$ 乗して $m$ を掛けると $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$ が得られる。

場合2:$\gcd(m,n) \ne 1$ のとき。$n = pq$ であるから、これは $p$ が $m$ を割り切るか、または $q$ が $m$ を割り切ることを意味する($m$ は $n$ より小さいので両方が同時に成り立つことはない)。法 $p$ のもとで考える:もし $p$ が $m$ を割り切るなら、$m$ と $m^{ed}$ はともに法 $p$ のもとで $0$ と合同である。そうでなければ $\gcd(m,p)=1$ であり、フェルマーの小定理より $m^{p-1} \equiv 1 \pmod p$ が成り立ち、$(p-1)$ が $\phi(n)$ を割り切ることから、場合1と同じ計算で $m^{ed} \equiv m \pmod p$ が示される。法 $q$ についても同様の議論により $m^{ed} \equiv m \pmod q$ が示される。

中国剰余定理により、法 $p$ と法 $q$ のそれぞれで成り立つ合同式は、その積 $n=pq$ を法としても成り立つ。したがって $(m^e)^d \equiv m \pmod n$ はすべてのメッセージ $m$ に対して成り立ち、$n$ と互いに素なものだけに限らない。

これにより、盗聴者が監視している公開チャネル上でも、二者が秘密鍵に合意できるようになる:盗聴者は底、法、そして両者の公開値を見ることができるが、そこから共有秘密を復元するには離散対数問題を解く必要があり、適切に選ばれたパラメータに対しては計算量的に困難であると信じられている。

定義より $A = g^a \bmod p$ と $B = g^b \bmod p$ はモジュラー冪乗の結果であるため、ボブは $A$ を受け取って $B^a = (g^b)^a \bmod p$ を計算し、アリスは $B$ を受け取って $A^b = (g^a)^b \bmod p$ を計算する。

モジュラー冪乗は通常の冪乗と同じ指数法則に従う。なぜなら法 $p$ のもとでの繰り返し乗算は、各段階で法 $p$ により簡約される点を除けば、整数の繰り返し乗算とまったく同じように合成されるからである:$g$ の指数として $(g^b)^a = g^{ba} = g^{ab} = (g^a)^b$ が成り立ち、この等式はどの段階で法 $p$ により簡約しても保たれる。

したがって $B^a \bmod p = g^{ab} \bmod p = A^b \bmod p$ である:アリスとボブは、自分の秘密指数と相手の公開値から、それぞれ独立に同じ値 $g^{ab} \bmod p$ を計算する。その際、秘密の $a$ や $b$ がチャネル上に現れることは一度もない。

安全性の議論はこの正当性の議論とは別である:正当性は両者が同じ数にたどり着くことしか示していない。$g$、$p$、$A$ から $a$ を計算する困難性(離散対数問題)こそが、その共有された数を観測者から秘密に保つ理由である。