アルゴリズム論特論（塩田）第10回 (5) RSA 暗号に使ってはいけない危険な鍵
RSA 暗号に使ってはいけない危険な鍵
$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$ が大きな素因数を持つようにする。