RSA暗号
RSA暗号の安全性が素因数が不明な法 n での冪根を求めるのが難しい事実に基づいていることから、その最大の攻撃が素因数分解であることは明白である。
しかし平文によっては、それ以外の攻撃方法でも暗号文から平文を入手することが可能である。
k = 1024 の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。 a = b d mod n {\displaystyle a=b^{d}{\bmod {n}}} を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 ( 1024 b i t × 1024 b i t {\displaystyle 1024\mathrm {bit} \times 1024\mathrm {bit} } ) を、1500回程繰り返すことで実現できる。これには相当の計算時間を要するため、中国の剰余定理を用いて、
a p = b d mod λ ( p ) mod p a q = b d mod λ ( q ) mod q a ′ = a p ( q − 1 mod p ) q + a q ( p − 1 mod q ) p {\displaystyle {\begin{aligned}ap&=b^{d{\bmod {\lambda }}(p)}{\bmod {p}}\\aq&=b^{d{\bmod {\lambda }}(q)}{\bmod {q}}\\a'&=ap(q^{-1}{\bmod {p}})q+aq(p^{-1}{\bmod {q}})p\end{aligned}}}
として求めることがある。