RSA暗号の「破られにくさ」の根拠

angel (as ㌵㌤の猫) @angel_p_57

一応、一般的な「離散対数問題」は、何らかの「群」という数学上の構造を舞台とするもので、mod p だとその群は「剰余類の乗法群」というものになる。他に暗号技術で実用される有名な群は「楕円曲線上の有理点のなす加法群」だ。

angel (as ㌵㌤の猫) @angel_p_57

で、一般的な「離散対数」が簡単に計算できるかはその「群」次第ということになるが、mod p での離散対数、楕円曲線での離散対数、これらは簡単に計算する方法が見つかっていないものとして知られている。

angel (as ㌵㌤の猫) @angel_p_57

実際、計算が簡単でないことから、「楕円曲線」と言えば、SSL/TLS でもよく使われる ECDH や、暗号通貨で話にのぼる署名技術 ECDSA 等「楕円曲線暗号」に活用されているし、mod p の話だと、RSAよりも前に発表された DH(の鍵交換) に活用されている。

angel (as ㌵㌤の猫) @angel_p_57

このまとめ togetter.com/li/1944444#h22… で、「最初の公開鍵暗号の論文には公開鍵暗号以外の技術の話も載っている」という話をしているけど、それが実はこの DH(の鍵交換) のことだ。

angel (as ㌵㌤の猫) @angel_p_57

ということで、離散対数問題の一種 a^x≡b mod p ( pの素数 ) の逆計算 x=log[a,mod p]b は難しい、と。RSAの場合の d=log[C,mod N]M は mod p, mod N がやや違うけれど、ほとんど同じ形をしている。

angel (as ㌵㌤の猫) @angel_p_57

この違いがどう効いてくるか分からないので確かなことは言えないけど、でもじゃあ RSA の場合の逆計算も難しいんじゃないかなというのは想像がつく。なのでここは問題にされていないんだろうと思う。

angel (as ㌵㌤の猫) @angel_p_57

では今度は M≡[e]√C mod N 的な計算なんだけど…。正直、こちらは情報があんまり見当たらなくてよく分からない。

angel (as ㌵㌤の猫) @angel_p_57

ただ、次の論文 "A Generalized qth Root Algorithm" で、mod p に関するべき乗根の計算法が説明されている。先程の「離散対数問題」と合わせると「離散べき乗根」とでも言うべきか。 dl.acm.org/doi/pdf/10.555…

angel (as ㌵㌤の猫) @angel_p_57

と言うか、こちらの "Entropoid Based Cryptography" という論文の Definition 26 で CDRP ( 離散べき乗根問題 ) という名前で紹介されてたりする。( 先程の論文はその引用元として見つけたもの ) eprint.iacr.org/2021/469.pdf

angel (as ㌵㌤の猫) @angel_p_57

で、この離散べき乗の計算法としては、離散対数を使うやり方になっている。なので離散対数問題と同等の難しさか、それよりは簡単なんだろうけど、「より簡単なやり方」は探しても見つからない。

angel (as ㌵㌤の猫) @angel_p_57

であれば、「離散べき乗根」も難しいということで、mod p と mod N という違いはあれど、RSA の M≡[e]√C mod N もやっぱり難しいということなんだろうなあ、と思う。

angel (as ㌵㌤の猫) @angel_p_57

ということで、色々調べてみたけれど、やっぱりRSAの難しさの源泉は「素因数分解の難しさ」ということでいいんじゃなかろうか。