アルゴリズム論特論（塩田）第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 が大きな素因数を持つようにする。