アルゴリズム論特論（塩田）第10回 (4) RSA 暗号に使ってはいけない危険な鍵
RSA 暗号に使ってはいけない危険な鍵
- フェルマ法は $p \mbox{ ≒ } q$ のときに有効な方法でしたが、
$p$ と $q$ の比が単純な分数に近いときに有効なようにフェルマ法を拡張することができます
（今日の付録参照）。
- $p-1$ 法は $p-1$ が小さな素因数しか持たないときに有効でした。
同様に、 $p+1$ が小さな素因数しか持たないときに有効な $p+1$ 法という素因数分解法もあります。
（その仕組みを理解するにはもっと代数学の知識が要ります。）
RSA 暗号を破ろうとする人は、
たくさんのコンピュータを用意して、
パラメータを変えた拡張フェルマ法や、$p-1$ 法、$p+1$ 法を仕込んで $n$ を素因数分解しようとします。
うち 1 つでも答えが出たら暗号は破れるのですから。
そこで、RSA 暗号の鍵を作るときは最低限、次の条件を満たすようにしなければなりません。
- $p$ と $q$ の比が単純な分数に近くにならないようにする。
- $p-1$, $q-1$ が大きな素因数を持つようにする。
- $p+1$, $q+1$ が大きな素因数を持つようにする。