encryption - 秘密鍵 x 大きい整数を見つける

Question

この方程式 y=g^x mod p の秘密鍵 x を見つけることは可能ですか? もちろん、p 、g、y、q がある場合は大きな整数です。調べる方法があるとすれば、どのような方法を使えばよいでしょうか？..........注: これらは大きな整数です

Answer 1

これは離散対数問題と呼ばれます。この問題の素体の特殊なケースに興味があるようです。

適切に選択されたフィールドが十分に大きい場合p、これは実行不可能です。これは、512 ビットではかなり安く (100 ドル程度) p、1024 ビットでは非常に高価であると予想しています。それを超えると、国家レベルの敵にとってもすぐに実行不可能になります。

分野によってはもっと安くなります。たとえば、バイナリ フィールド (あなたの例のように素体ではない) で DL を解くと、かなりの数の最近の論文が作成されました。たとえば、FFS を使用した GF(2^809) の離散対数および関数フィールド シーブについて、およびより高い分割確率の影響: F_2^1971 の離散対数への適用。