完全性の証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/15 05:03 UTC 版)
定義により以下が成立する。 a ′ ≡ a ( d ⋅ e ) ( mod n ) = a ( x ⋅ ϕ ( n ) + 1 ) = ( a ϕ ( n ) ) x ⋅ a {\displaystyle a^{\prime }\equiv a^{(d\cdot e)}{\pmod {n}}=a^{(x\cdot \phi (n)+1)}=(a^{\phi (n)})^{x}\cdot a} これにより以下も成立する。 a ′ ≡ ( a ϕ ( n ) ) x ⋅ a ( mod p ) a ′ ≡ ( a ϕ ( n ) ) x ⋅ a ( mod q ) {\displaystyle {\begin{aligned}a^{\prime }\equiv (a^{\phi (n)})^{x}\cdot a{\pmod {p}}\\a^{\prime }\equiv (a^{\phi (n)})^{x}\cdot a{\pmod {q}}\\\end{aligned}}} a {\displaystyle a} が n {\displaystyle n} と互いに素な整数のときは a {\displaystyle a} が2つの素数 p , q {\displaystyle p,q} のそれぞれと互いに素であるから フェルマーの小定理 を使い a ϕ ( n ) = ( a ( p − 1 ) ) ( q − 1 ) ≡ 1 ( q − 1 ) ( mod p ) = 1 a ϕ ( n ) = ( a ( q − 1 ) ) ( p − 1 ) ≡ 1 ( p − 1 ) ( mod q ) = 1 {\displaystyle {\begin{aligned}a^{\phi (n)}=(a^{(p-1)})^{(q-1)}\equiv 1^{(q-1)}{\pmod {p}}=1\\a^{\phi (n)}=(a^{(q-1)})^{(p-1)}\equiv 1^{(p-1)}{\pmod {q}}=1\\\end{aligned}}} よって ( a ϕ ( n ) − 1 ) {\displaystyle (a^{\phi (n)}-1)} は p , q {\displaystyle p,q} で割り切れるから a ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}} となり a ′ ≡ ( a ϕ ( n ) ) x ⋅ a ( mod n ) ≡ 1 x ⋅ a ( mod n ) = a {\displaystyle a^{\prime }\equiv (a^{\phi (n)})^{x}\cdot a{\pmod {n}}\equiv 1^{x}\cdot a{\pmod {n}}=a} となる。 a = 0 {\displaystyle a=0} のときは明らかに a ′ = b = a = 0 {\displaystyle a^{\prime }=b=a=0} となる。 g c d ( n , a ) = p {\displaystyle \mathrm {gcd} (n,a)=p} であり a ∈ Z n − { 0 } {\displaystyle a\in {\mathbb {Z}}_{n}-\{0\}} のときは a {\displaystyle a} は q − 1 {\displaystyle q-1} 個の整数からなる 集合 { 1 ⋅ p , 2 ⋅ p , 3 ⋅ p , . . . , ( q − 1 ) ⋅ p } {\displaystyle \{1\cdot p,2\cdot p,3\cdot p,...,(q-1)\cdot p\}} の元であり a ≡ 0 ( mod p ) {\displaystyle a\equiv 0{\pmod {p}}} である。 また a {\displaystyle a} と q {\displaystyle q} が素なので フェルマーの小定理 により a ϕ ( n ) = ( a ( q − 1 ) ) ( p − 1 ) ≡ 1 ( p − 1 ) ( mod q ) = 1 {\displaystyle {\begin{aligned}a^{\phi (n)}=(a^{(q-1)})^{(p-1)}\equiv 1^{(p-1)}{\pmod {q}}=1\end{aligned}}} よって a ′ ≡ ( a ϕ ( n ) ) x ⋅ a ( mod p ) ≡ ( a ϕ ( n ) ) x ⋅ 0 ( mod p ) = 0 a ′ ≡ ( a ϕ ( n ) ) x ⋅ a ( mod q ) ≡ 1 x ⋅ a ( mod q ) = a {\displaystyle {\begin{aligned}a^{\prime }\equiv (a^{\phi (n)})^{x}\cdot a{\pmod {p}}\equiv (a^{\phi (n)})^{x}\cdot 0{\pmod {p}}=0\\a^{\prime }\equiv (a^{\phi (n)})^{x}\cdot a{\pmod {q}}\equiv 1^{x}\cdot a{\pmod {q}}=a\\\end{aligned}}} よって a ′ ≡ 0 ( mod p ) ≡ a ( mod p ) a ′ ≡ a ( mod q ) {\displaystyle {\begin{aligned}a^{\prime }\equiv 0{\pmod {p}}\equiv a{\pmod {p}}\\a^{\prime }\equiv a{\pmod {q}}\\\end{aligned}}} よって ( a ′ − a ) {\displaystyle (a^{\prime }-a)} は p , q {\displaystyle p,q} で割り切れるから a ′ ≡ a ( mod n ) {\displaystyle {\begin{aligned}a^{\prime }\equiv a{\pmod {n}}\\\end{aligned}}} となる。 g c d ( n , a ) = q {\displaystyle \mathrm {gcd} (n,a)=q} であり a ∈ Z n − { 0 } {\displaystyle a\in {\mathbb {Z}}_{n}-\{0\}} のときについても同様に a ′ ≡ a ( mod n ) {\displaystyle a^{\prime }\equiv a{\pmod {n}}} となる。 しかるに a , a ′ ∈ Z n {\displaystyle a,a^{\prime }\in {\mathbb {Z}}_{n}} なので何れにしても a ′ = a {\displaystyle a^{\prime }=a} が成り立ち 平文 a {\displaystyle a} の 暗号文 b {\displaystyle b} は 秘密鍵 d {\displaystyle d} と 公開鍵の1つ n {\displaystyle n} を用いて 平文 a {\displaystyle a} に復号できることが分かる。
※この「完全性の証明」の解説は、「RSA暗号」の解説の一部です。
「完全性の証明」を含む「RSA暗号」の記事については、「RSA暗号」の概要を参照ください。
- 完全性の証明のページへのリンク
