【RSA暗号】適当にとった自然数eの割り算による素因数探索【未実装かつ自信なし】

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

RSA暗号解読に向けて試してみたこと

連分数によるRSA暗号の攻撃方法があることを知ったので、そこに着想を得て自分であれこれやってみた。この本に書いてありました。

現代暗号入門　いかにして秘密は守られるのか (ブルーバックス)

RSA暗号については、過去記事を参照してください。

sky-time-math.hatenablog.jp

のも教えないけど、公開鍵は教えているわけで、その意味でなんか数学的に関連はあって、は素因数分解しなくても、なんとかできるんじゃないかと思った次第。しかし、結局、公開鍵と秘密鍵の積はわからずじまいなので、普通の自然数を法としたアルゴリズムをとりあえず考えてみた。

過去に考えたアルゴリズム

 過去に考えたアルゴリズムも一応紹介しておく。

多因数分解法: 素因数分解を考えよう

収縮遡及法: とある物理学博士が素因数分解を考えてみた

 

を法とする素因数探索アルゴリズム

法を適当な自然数で割った商を、余りをとすると、

同様にして、分かってない素数の組について、をで割った余りをそれぞれ、ととすると、

となる。ここで、既知の数は、で、未知の数は、である。

ここで、次の関係式に注目する。

ここで、ほとんどの場合、と考えてもよさそうなので、そうしてみる。分子のeより大きい場合を考慮したければ、分子からをひき、整数部分にをたせばよい。

最初と最後の式を比較すると、

特に、上の等式をについて解くと(solve r+s/x=g+a+(d+b-1)/x - Wolfram|Alpha)、

となる。割りが発生しているので、この嘘を式変形前に戻って、整理し直すと、

を得る。すなわち、 はで割り切れて、ではない。

に着目すると、 をで割った商はかである。ところが不等式評価により、商は次のようにだとわかる。

結局、

と表せるので、

 

 

また、こうして求まった、各に対して、となり、約数が計算できるが、これは、に等しい。つまり、

となる。

不等式の評価

以上をまとめると、

 と計算したとき、

 であり、

であることが分かった。後は、を探索して、解と係数の関係を使って、2次方程式を解けば素因数が求まる。どのような自然数を適切に選べば、の探索範囲が狭まるかは謎である。

いまのところ、直観的には、の方が探索範囲が狭いように感じられる。気のせいかもしれないが……

どなたか実装してみたいよとかこのアルゴリズムダメじゃんとか言う人がいたら、twitterの@foxq0113までDMください。ここに、コメントしていただいても大丈夫ですが、あまり見ないこともあるので、反応が遅くなります。

最後に、繰り返しますが、今回のアルゴリズムはあまり自信がありません。