RSAは現在主流と言える公開鍵暗号の方式で、SSHやHTTPSなど重要プロトコルで利用されています。我々が普段利用しているRSA暗号では2つの巨大素数p,qを生成し、2素数の積nを公開鍵として利用します。万一nが素因数分解されてしまうと秘密鍵を計算で求めることが可能になりますが、nが2048bitであれば2030年くらいまで素因数分解は非現実的だろうと言われています。 ところで、入手したRSA公開鍵に含まれるnの素因数が3個以上だった場合に、対応する秘密鍵は存在するのでしょうか?また、その秘密鍵を素因数分解の結果から計算できるのでしょうか?筆者はこの疑問に長らく答えが出せずにいたのですが、RFC3447(PKCS #1)に「multi-prime RSA」として定義されていることを知りました。本稿ではこの multi-prime RSA について紹介します。 RSA暗号の原理 RSA暗号で