アルゴリズム論特論(塩田)第10回 (5) RSA 暗号に使ってはいけない危険な鍵

RSA 暗号に使ってはいけない危険な鍵

 $p-1$ 法は $p-1$ が小さな素因数しか持たないときに有効でした。 同様に、 $p+1$ が小さな素因数しか持たないときに有効な $p+1$ 法という素因数分解法もあります。 (その仕組みを理解するにはもっと代数学の知識が要ります。)

 RSA 暗号を破ろうとする人は、 たくさんのコンピュータを用意して、 パラメータを変えた拡張フェルマ法や、$p-1$ 法、$p+1$ 法を仕込んで $n$ を素因数分解しようとします。 うち 1 つでも答えが出たら暗号は破れるのですから。
 そこで、RSA 暗号の鍵を作るときは最低限、次の条件を満たすようにしなければなりません。
  1. $p$ と $q$ の比が単純な分数に近くにならないようにする。
  2. $p-1$, $q-1$ が大きな素因数を持つようにする。
  3. $p+1$, $q+1$ が大きな素因数を持つようにする。

参考