RSA暗号で実はpが素数でなかったら?

angel (as ㌵㌤の猫) @angel_p_57

先日tweetしたこのネタ。あんまり深く気にしてなかったとこだけど、良い機会なので? 軽く調べてみた。 twitter.com/angel_p_57/sta…

angel (as ㌵㌤の猫) @angel_p_57

そう言えばそんなネタもあったなあ。RSA的には n=pq の p が素数でなくても、a^p≡a mod p がほぼほぼ全ての a で成立すれば ( p がほぼほぼ全ての a に対するフェルマー擬素数であれば )、暗号化・復号として処理が破綻しないから。 twitter.com/urawazakun/sta…

2022-09-23 23:11:02

angel (as ㌵㌤の猫) @angel_p_57

どういう話になるかと言うと、RSAが巨大な数の素因数分解が難しいことを拠り所にしている技術であるという前提で、じゃあ「秘密鍵の所有者だけが知る、これまた巨大な素数、どうやって素数であることを保証しているのか」から始まる。

angel (as ㌵㌤の猫) @angel_p_57

例えば2,048bit RSAの場合、N=pq の大きさは10進数で600桁にもなり、これの素因数分解は現実的ではない。しかし同時に ( ある程度桁数を揃える ) p,q も実に300桁程度あるわけで、果たしてどうやってそんな素数を用意するのか、という話が出てくる。

angel (as ㌵㌤の猫) @angel_p_57

この素数、使い回しをすると秘密鍵が漏洩する糸口になるし、毎回偏りの出ないよう、ランダムに作らなければならない。なので、ランダムな候補を用意して素数判定して、素数でなければ次の候補を用意して…を繰り返し、で用意することになる。

angel (as ㌵㌤の猫) @angel_p_57

ここで問題になるのが素数判定。誰でもパッと思いつくのは「素因数分解を試してみて分解できなければ素数」という判定法だけど、それだと秘密鍵を用意する本人が「素因数分解の困難さ」に真っ先にやられることになり本末転倒だ。

angel (as ㌵㌤の猫) @angel_p_57

でも幸いなことに、素数判定には現実的な時間で行える方法がある。実際、SSH を使ったことがある人なら、認証鍵を作る操作ででも、直ぐにRSAの鍵を作れた経験があるはずだ。これは鍵を作るツールに、そういう判定法が組み込んであるからだ。

angel (as ㌵㌤の猫) @angel_p_57

とは言え、「確実に」素数であることを判定するのは現実的には割りに合わない。一応AKSというアルゴリズムがあるのだが、かなり計算量が大きい方法でもあるし。 そのため一般には「確率的」なアルゴリズムを使う。つまり、僅かとは言え「素数でないものを誤って素数と判定する」というリスクが残る。

angel (as ㌵㌤の猫) @angel_p_57

そうすると気になる点が出てくる。「誤判定しちゃったらどうするの?」と。そこが今まで深く気にしてなかったところになる。 ※ただ、ぶっちゃけて言うと、誤判定率は物凄く低くなるように実装されているため、気にしてもしようがないところではあるけど。

angel (as ㌵㌤の猫) @angel_p_57

で、誤判定した時にぱっと思いつく影響は2つある。1つは暗号が破られるリスクの向上、もう1つは暗号化・復号処理の破綻だ。 …ということで、この2点が調べた話の本題となる。

angel (as ㌵㌤の猫) @angel_p_57

長くなるので今回は「暗号が破られるリスクの向上」で。これは、「素因数分解が容易になること」と言い換えられる。

angel (as ㌵㌤の猫) @angel_p_57

RSAは「N=pqの素因数分解が困難」というのが、暗号としての「破られにくさ」の根拠だった。なので、素因数分解が容易になれば「暗号が破られるリスクの向上」につながるからだ。( 単純に秘密鍵漏洩のリスクが上がる )

angel (as ㌵㌤の猫) @angel_p_57

例えば2,048bit RSAで N が10進数で600桁程度、p,qがそれぞれ300桁程度だと素因数分解が現実的でないにしても、素数であるはずの p,q の一方が合成数だとすると、もっと小さい桁で素因数分解できることになる。直感的に分解できる素数に辿り着きやすいというのは分かり易いところだろう。

angel (as ㌵㌤の猫) @angel_p_57

ただそうは言っても、「大きな素数2個の積」ではなく「実は3個以上の素数の積になっている」というのが、本当に「素因数分解が容易になること」につながるか、は確認しなければならない。

angel (as ㌵㌤の猫) @angel_p_57

基本的な素因数分解法である「試し割り」なら、分解した時の素数の数が増える事は、最初に試し割りで見つかる素数が小さくなることにつながるので、結果として「容易になる」と言えるのだけど、RSAを破ろうとする時にそんな方法は使わないからだ。( 流石に試し割りでは効率が悪すぎる )

angel (as ㌵㌤の猫) @angel_p_57

では「素因数分解が容易になるか」この答えは、マルチプライムRSA ( MP-RSA ) という技術の安全性評価の話の中にある。

angel (as ㌵㌤の猫) @angel_p_57

MP-RSA というのは RSA の一種であって、使おうと思えば普通に使える。普通のRSAと何が違うかと言うと、普通は N=pq と2個の素数の積であるところ、N=pqr や N=pqrs のように、3個、4個といった複数の素数の積で N を構成するところだ。

angel (as ㌵㌤の猫) @angel_p_57

このことから気付くかもしれないが、結論を一部先に言うと「素数の数が増えたとしても特に問題がない『場合がある』」となる。

angel (as ㌵㌤の猫) @angel_p_57

しかし、幾ら複数の素数で使えるとは言え、5個、6個と増やすのは現実的ではないし、素数の桁数も揃えるというのがMP-RSAの前提になっている。なので、コントロールできない状態で素数の数が増えるのは大抵問題がある。

angel (as ㌵㌤の猫) @angel_p_57

話を戻して、なぜ複数の素数でもRSAが成立するのか。また、複数の素数を使う動機は何か。

angel (as ㌵㌤の猫) @angel_p_57

前者について。そもそもRSAは、a^x mod p が p-1 周期、a^x mod q が q-1 周期で変化するので a^x mod N が、その2つの周期の交わりである LCM(p-1,q-1) 周期で変化し、しかも素因数分解の結果を知らなければ周期が分からないところが重要なポイントになっていた。 参考: qiita.com/angel_p_57/ite…

angel (as ㌵㌤の猫) @angel_p_57

であれば素数をp,q,rの3つに増やして p-1周期、q-1周期、r-1周期の交わり LCM(p-1,q-1,r-1)周期というのを考えても、全く同じ理屈で話を進められる。4つ以上でも同様だ。なので、「素数の数が2つ」に拘る必要は実はなかったということになる。これが「複数の素数でもRSAが成立する」理由だ。