RSA暗号解読の素因数分解による方法について。

質問

下記の通りで正しいでしょうか。：

Microsoft Bing AI （＝ Bing Chat）生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。

自然数 N を、√N （＝ Nの平方根）未満の自然数であって末位の数字が１，３，７，９のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの４乗根）です。
実際には、RSA暗号による暗号文の暗号は、巨大素数を２つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が１，３，７，９のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。

上記の様に、問題サイズ N に対する、N の４乗根のオーダーの時間を上界（この場合は、自然数の計算ですので上限）とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、N の素因数分解が出来てしまいますので、RSA暗号も、いとも簡単に解けてしまう、ということです。

回答No.1

_kappe_ · ベストアンサー

結果が出るのが地球の滅亡後でもいいのなら「RSA暗号を解くのはいとも簡単」と言っていいでしょう。

RSA暗号で使う典型的なNの大きさは2048ビットです。2048ビットの数字を10進数表記にするとおおよそ616桁くらい。すなわち、√Nは10進数で308桁くらいとなります。

仮に、2048ビットの値の割り算を1ナノ秒に1回実行できるコンピューターがあったとします。1秒間に10億回、1年だと約3京回（10進数17桁）の割り算ができる速度です。1年かかっても10進数308桁分の候補のほんの17桁分の割り算試行しかできないわけで、1000年計算を続けてもやっと20桁分です。
「末尾の桁が1,3,7,9の場合だけ割り算を試行する」みたいな初歩的な工夫では、10進数308桁分という候補の数を1桁減らすことさえできません。

なお、量子コンピュータが本格的に実用化されたときには事情が変わると言われています。

お礼

謬見でしかない愚論を御批判いただきまして、誠に誠に有難う御座いました。深謝に堪えません。

補足

上記の方法では駄目な事は分かりました。が、それでも、結局、もはや、ＲＳＡ暗号はアウトです。∵、ツイッターの　@koitiluv1842 の拙「固定されたツイート」（Pinned Tweet) スレ、及び、このOKWave 、並びに、ヤフー知恵袋に掲げて居ります、小林吹代氏の、「RSA 暗号が破れ」ると仰る素数生成公式や、菅野正人（かんのまさと）氏（菅野氏も「ＲＳＡ暗号の終焉」という旨の事を言って居られます。）および故・川村甲子郎氏の素数生成アルゴリズム等々を用いれば、ごく初等的な計算で、ごく短時間に、任意の　ｎ に対して、ｎ　番目の素数が割り出せますので。

回答No.2

_kappe_

RSA暗号を解くのは容易だと主張したいのであれば、RSAチャレンジの未解決問題を一つでも解いてみせれば何よりの証拠になります。
https://en.wikipedia.org/wiki/RSA_numbersに載っているRSA-260以降の値をどれでもいいから実際に素因数分解してみるのはいかがでしょうか。
RSA-260は862ビットであり、世の中で使われているRSA暗号（現在は1024ビット以上）よりはるかに容易です。
RSA-260さえ解くことができないならRSA暗号はまだしばらくは実用上問題ない程度には安全だということです。

お礼

お言葉を返す様ですが、最近頻発する、犯人不明の、また、北朝鮮やロシアが国営で戦略としてやらしてもいる、ランサムウェア送り付けやクレジット・カード所有者本人なりすまし詐欺や生産ラインのダウンが、すべて、フィッシング・メールの「誤開封」による被害を生じているのでないのは明らかでしょう。クレジット成り済まし詐欺など、２０２２年は、全国で、被害総額３３０億円です。北朝鮮のデジタル通貨窃盗の金額も、ググれば、２０２２年は２０００億円超と出ます。