同一平文
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/15 05:03 UTC 版)
法 n {\displaystyle n} における e {\displaystyle e} 乗根が計算できれば、暗号文を復号できる。当然これは（法 n {\displaystyle n} の素因数がわからない限り）非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。 しかし、まったく同一の平文を、異なる法において同一の e {\displaystyle e} を用いて暗号化した暗号文を e {\displaystyle e} 個以上集めることで、各々の法に関して中国の剰余定理を用いれば通常の冪根演算によって平文を復元できる。これが同報通信の誤用である。 c 1 ≡ m e ( mod n 1 ) c 2 ≡ m e ( mod n 2 ) c 3 ≡ m e ( mod n 3 ) c e ≡ m e ( mod n e ) {\displaystyle {\begin{aligned}c_{1}&\equiv m^{e}{\pmod {n_{1}}}\\c_{2}&\equiv m^{e}{\pmod {n_{2}}}\\c_{3}&\equiv m^{e}{\pmod {n_{3}}}\\\\c_{e}&\equiv m^{e}{\pmod {n_{e}}}\end{aligned}}} ここから中国の剰余定理によって上記式を満たす、 c ≡ m e ( mod n 1 n 2 n 3 … n e ) {\displaystyle c\equiv m^{e}{\pmod {n_{1}n_{2}n_{3}\dots n_{e}}}} を求めることができる。このとき c < n 1 n 2 n 3 … n e {\displaystyle c<n_{1}n_{2}n_{3}\dots n_{e}} であり、また m {\displaystyle m} はどの法 n {\displaystyle n} よりも小さいため m e < n 1 n 2 n 3 … n e {\displaystyle m^{e}<n_{1}n_{2}n_{3}\dots n_{e}} であることから、 c = m e {\displaystyle c=m^{e}} この c {\displaystyle c} の e {\displaystyle e} 乗根を求めることで平文 m {\displaystyle m} が求められる。 これは e {\displaystyle e} として特に 3 {\displaystyle 3} や 65537 {\displaystyle 65537} は、 2 {\displaystyle 2} 進数表示したときに 1 {\displaystyle 1} の個数が少ないために暗号化処理を高速化できるという理由から好んで用いられるために発生しうる問題である。実際の暗号への応用においてはフォーマットとして、 m {\displaystyle m} の一部に毎回生成する乱数を挿入することでこの攻撃を回避している。
※この「同一平文」の解説は、「RSA暗号」の解説の一部です。
「同一平文」を含む「RSA暗号」の記事については、「RSA暗号」の概要を参照ください。
- 同一平文のページへのリンク
