RSA暗号
全く同一の平文を複数の送信先へ各々の公開鍵で暗号化して同報通信するには適していない。同じ e を持つ公開鍵(ハミング重み HW = 2 である 3 や 65537 が好んで用いられる)で暗号化された e 個以上の暗号文を手に入れたなら各々の公開鍵の法に関して中国の剰余定理を用いることで、通常の冪根によって平文を復元できるからである。詳しくは下記の同一平文を参照のこと。
このため、現在規格化されている暗号への応用においては、パディングとして毎回乱数を生成して挿入するなどの対策がされている。
もしも平文 m が、n の e 乗根よりも小さかったら、暗号文 c = m e mod n = m e {\displaystyle c=m^{e}\;\operatorname {mod} \;n=m^{e}} となるから、通常の冪根演算によって c の e 乗根を計算するだけで平文 m が復元できてしまう。
実際の暗号への応用においてはフォーマットの一部として、m の比較的高位のビットに1を挿入することでこの攻撃を回避している。
p, q を異なる2つの素数とし n = pq とし λ(n) = (p − 1)(q − 1) とする。e を λ(n) と素な正整数とすると α ⋅ e + β ⋅ λ(n) = 1 となる2整数 α, β が存在する。α として1つの正整数 d を選択してそのときの β を −x とすると d ⋅ e = x ⋅ λ(n) + 1 となる。ここで d を秘密鍵とし、n と e を公開鍵とする。
ここで、α ⋅ e + β ⋅ λ(n) = 1 のとき i を整数とすると (α + i ⋅ λ(n)) ⋅ e + (β − i ⋅ e) ⋅ λ(n) = 1 であるから α に λ(n) の整数倍を加えたものも改めて α とできるため、α として正整数 d を選択できるとした。
以下 Zn を 0 以上 n 未満の整数の集合とする。
2004年の時点では、インターネットで公募した数多くのPCを用いると512ビット程度の数なら素因数分解できるので、RSA暗号に使用する法 n は1024-4096ビット(10進数で300-1000桁程度)にすることが推奨されている。
しかしシャミアは、RSA問題を解くための専用装置 (TWIRL) を作成すれば、1024ビットの n に関するRSA問題ですら解くことができると主張している。また、実用的な量子コンピュータが登場した場合には、素因数分解の桁数増に対する計算時間の増加が緩やかなショアのアルゴリズム(英語版)と呼ばれる高速な量子コンピュータアルゴリズムが実行可能となるため、たとえ鍵のビット数を増やしてもRSA暗号の安全性が保証されなくなる可能性が指摘されている。
定義により以下が成立する。
a ′ ≡ a ( d ⋅ e ) ( mod n ) = a ( x ⋅ λ ( n ) + 1 ) = ( a λ ( n ) ) x ⋅ a {\displaystyle a'\equiv a^{(d\cdot e)}{\pmod {n}}=a^{(x\cdot \lambda (n)+1)}=(a^{\lambda (n)})^{x}\cdot a}
これにより以下も成立する。
a ′ ≡ ( a λ ( n ) ) x ⋅ a ( mod p ) a ′ ≡ ( a λ ( n ) ) x ⋅ a ( mod q ) {\displaystyle {\begin{aligned}a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {p}}\\a'\equiv (a^{\lambda (n)})^{x}\cdot a{\pmod {q}}\end{aligned}}}
a が n と互いに素な整数のときは a が2つの素数 p, q のそれぞれと互いに素であるから
フェルマーの小定理 により a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} かつ a q − 1 ≡ 1 ( mod q ) {\displaystyle a^{q-1}\equiv 1{\pmod {q}}} であり
法 n における e乗根が計算できれば、暗号文を復号できる。当然これは(法 n の素因数が分からない限り)非常に難しいと考えられていて、RSA暗号の安全性の重要な根拠の一つになっている。
しかし、全く同一の平文を、異なる法において同一の e を用いて暗号化した暗号文を 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}}}
ここから中国の剰余定理によって上記式を満たす、