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暗号では公開鍵として(n,e)という整数のペアを利用します。nはすでに紹介した通り巨大素数p,qの積です。eは都合の良い固定値（65537など）がよく使われます。
教科書的な秘密鍵としては(n,d)が使われます。ここでのdは次のような性質を持つ値です。
- 任意のxに対して x^(e*d)=x (mod n) … (1)
このe,d,nを使うと、RSAの暗号化処理・復号処理は次のように表せます。
- 暗号化
- 平文をiとする、ただしi<n
- 暗号文 c = i^e (mod n)
- 復号
- 暗号文 c に対して c^d (mod n)で平文が得られる
このように、秘密鍵に含まれるdさえバレなければ、暗号化に必要なeは公開することができるという仕組みになっています。
このdはオイラー関数φを用いて次のように表すことができます。
- e*d = 1 (mod φ(n)) … (2)
つまり、eのモジュラ逆数を取ればdが計算できるというわけです。
たとえばn=3*5の場合について考えてみると、e=3,d=3のときに(2)式を満たします。(1)式で実際に試してみましょう。
Prelude> map (\x -> x^(3*3) `mod` 15) [0..14] [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
n未満の全ての平文が復元できていますので、RSAとして正しく機能することがわかります。
multi-prime RSAの実例
さて、実は上記の説明においてnの素因数が2つである必然性はありません。nとして3素数以上の積を使ったRSAをmulti-prime RSAと呼びます。
仮にn=3*5*7=105とすると、e=5,d=29のときに(2)式を満たします。先ほどと同様に(1)式を確認してみましょう。
Prelude> map (\x -> x^(5*29) `mod` 105) [0..104] [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104]
やはり期待通りに動いています。このように、multi-prime RSAが機能すること自体は間違いありません。
現実の秘密鍵
ところで、先ほど「教科書的な秘密鍵」という説明をしましたが、現実のRSA実装では上の計算をそのまま行うことはありません。我々が普段使っている秘密鍵には次のような値が含まれています。
- n
- e
- d
- p
- q
- d mod (p-1)
- d mod (q-1)
- q^-1 mod p
dはnと同じくらいの大きさになるので、暗号文cの復号c^dは重い処理となります。現実の実装ではc^dをマジメに計算する代わりに、中国の剰余定理を利用してc^(d mod (p-1))とc^(d mod (q-1))の計算に変形し、教科書的な実装より4倍高速に計算を行っています。
ちなみに、nが3素数や4素数の積だった場合は中国の剰余定理を利用することで9倍、16倍と高速になっていきます。このように復号処理を軽量化できる点がmulti-prime RSAのメリットになります。
しかし、実際にmulti-prime RSAでの計算量低減メリットを受けるには秘密鍵のフォーマットを変えてd mod (p1-1),d mod (p2-1),…を持っておかなくてはなりません。このようなフォーマットに対応している実装は存在しないように思います[要出典]。
また、素因数の数を増やせば増やしただけ素因数分解による攻撃可能性も増えていきますので、多くすれば良いというものではありません。適用するとしても3素数が現実的だと考えられているようです。
最初の疑問に対する答え
最初の疑問「入手した公開鍵に含まれるnの素因数が3個以上だった場合に、対応する秘密鍵は存在するのでしょうか？また、その秘密鍵を素因数分解の結果から計算できるのでしょうか？」に対する答えは以下のようにまとめられるでしょう。
そもそも筆者がこのような疑問を持ったきっかけは、2015年頃にgithub.com上のSSH公開鍵の素因数分解を試みていた際（参照：「江戸前セキュリティ勉強会でgithub.comの弱い鍵を探す話をしました」）に3つ以上の素因数を持つSSH公開鍵がいくつか見つかったためです。これらの公開鍵はおそらくコピペミスで作られてしまったもので、アカウントの持ち主も対応する秘密鍵を持っていないと考えられますが、このような鍵に対しても素因数分解さえできれば攻撃可能だというのは面白い結論だと感じます。
参考URL
*1:と思ったんですが、 http://xrekkusu.hatenablog.jp/entry/2015/08/17/001939 を見ると正しく動作する秘密鍵が作れているようにも見えますね。どういう理屈なんだろ…。
