-1

私はdPythonで見つけようとしています。

(2 ** d) mod n = s2

どこn = 

132177882185373774813945506243321607011510930684897434818595314234725602493934515403833460241072842788085178405842019124354553719616350676051289956113618487539608319422698056216887276531560386229271076862408823338669795520077783060068491144890490733649000321192437210365603856143989888494731654785043992278251

とs2 =

18269259493999292542402899855086766469838750310113238685472900147571691729574239379292239589580462883199555239659513821547589498977376834615709314449943085101697266417531578751311966354219681199183298006299399765358783274424349074040973733214578342738572625956971005052398172213596798751992841512724116639637

私は解決策を探しているわけではありませんが、これを行うためのかなり速い方法を探しています。powさまざまな値を使用してプラグインしようとしましたが、これは遅く、解決策が得られません。どうすれば見つけられますdか?

4

3 に答える 3

5

問題を解決できる既知のアルゴリズムはありません。これは離散対数問題と呼ばれ、その複雑さに依存する暗号システムもあります (n の因数分解を知らなければ、すぐに解を見つけることはできません)。

于 2012-09-17T19:25:45.933 に答える
2

公開鍵と「元のデータ=>暗号化されたデータ」エントリのセットを知っているRSA秘密鍵を取得することは可能ですか?への2番目の回答を見てください。. 既知の平文攻撃は、既知の暗号文よりも簡単ではありません。

于 2012-09-17T19:49:27.727 に答える
1

知られている唯一の離散対数ソルバーは、因数を知ることに基づいて構築されています。因子がない場合は、それらを生成する必要があります。

これに最適な妥当な時間アルゴリズムは、Shor のアルゴリズムです。問題は、十分な量子ビットを備えた量子コンピューターが必要であり、サンプル データに十分な大きさの量子コンピューターをまだ構築していないことです。そして、誰もがそうするまでにはかなりの数年かかるようです。現在でも人々は 15 や 21 のような素因数分解に興奮しています。

古典的なコンピューティングを使用したい場合、最もよく知られているアルゴリズムは「かなり高速」にはほど遠いものです。誰かが最近、2^1039-1 に関するボンの結果が最新の PC で 4 か月以内に再現可能であることを示したと思います。あと5年、もしかしたら1ヶ月くらいになるかもしれません。

合理的で高速なアルゴリズムが知られていないことは驚くべきことではありません。もしあったとしても、ほとんどの秘密鍵暗号化はクラック可能であり、したがって価値がないからです。あなたが探している答えを誰かが教えてくれたら、それは大きなニュースです。(「Is P=NP?」に対する SO の質問はありますか?)

于 2012-09-17T19:41:08.107 に答える