たとえば、MD5またはSHA-1?これらの両方の時間の複雑さは何ですか?私はそれをインターネット上で見つけようとしましたが、それは非常に限られていて、私が得たものは両方ともO(n)です。誰も私をもっと啓発することはできますか?たぶん私に最悪のケースと最善のケースのシナリオを与えますか?暗号ハッシュ関数の時間複雑度はどのくらいですか?
0
A
答えて
1
MD5アルゴリズムとSHA-1アルゴリズムの両方は、が暗号で保護されていないため、これ以上使用しないでください。 - Merkle-Damgard constructionに基づいています。これは
入力をパディング、それらはビットの入力固定幅ブロックとして取り、同じサイズのビットの固定幅のブロックを出力するブロック暗号で始まる- によって構築されていることを意味しますcryptographically secure padding schemeを使用してブロックサイズのいくつかの倍数に変換し、次に
- を入力のいくつかのビット数の組み合わせに加えて、初期値または前のブロック暗号の出力のいずれかの組み合わせに繰り返し適用します。
ブロック暗号は固定サイズのビットブロックで動作するため、実行する時間の複雑さはO(1)です。そのブロック暗号には合計でΘ(n)個のアプリケーションがあります(入力は固定サイズのブロックに分割されているため、これらのブロックはΘ(n)あります)。パディングビットを計算するコストはおそらくO 1)でもO(n)になる可能性があります。全体として、これは、これらのハッシュ関数を計算する実行時間がΘ(n)であることを意味します。これは、各ビットが少なくとも1回は訪問され、ビットごとに行われる作業は一定であるため意味があります。
ブロック暗号は、通常、ビットの入力コンビネーション(または少なくとも同じ時間量に非常に近いもの)で実行するのに正確な同じ時間がかかるように実装されていますこれらはブロック暗号を計算するのに必要な時間量を使用してビットの一部を盗むために使用されているtiming attacksに耐性があります。結果として、これらのハッシュ関数が同じサイズの異なる入力で完了するのに異なる時間を要した場合は、非常に珍しいことです。したがって、ランタイムがΘ(n)であるという事実とは無関係に、ウォールクロックランタイムに大きな変化が見られるはずはありません。
関連する問題
- 1. この関数の時間複雑度はどのくらいですか?
- 2. この関数の時間複雑度はどのくらいですか?
- 3. yieldからのツリートラバーサルの時間複雑度はどのくらいですか?
- 4. この関数の時間複雑度はO(1)ですか?
- 5. javaのlastIndexOfの時間複雑度はどのくらいですか?
- 6. このアルゴリズム(コード)の時間複雑度はどのくらいですか?
- 7. この擬似コードの時間複雑度はどのくらいですか?
- 8. 次のコードの時間的複雑度はどのくらいですか?
- 9. アルゴリズム全体の時間複雑度はどのくらいですか?
- 10. クイックソートの平均的な時間複雑度はどのくらいですか?
- 11. 暗号ハッシュ関数
- 12. スキームのacc関数の時間複雑度は?
- 13. 多次元ハッシュの空間複雑度
- 14. random.sampleの時間複雑度
- 15. プログラムの時間複雑度
- 16. フィボナッチアルゴリズムの時間複雑度
- 17. プログラムの時間複雑度
- 18. この順列アルゴリズムの空間複雑度はどのくらいですか?
- 19. Pythonでzip()の時間の複雑さはどのくらいですか?
- 20. JavaScriptのparseInt()の時間の複雑さはどのくらいですか?
- 21. 次の式の時間の複雑さはどのくらいですか?
- 22. ツリートラバーサルの時間の複雑さはどのくらいですか?
- 23. C:qsort関数の時間の複雑さは何ですか?
- 24. forループを含む再帰関数の時間複雑度
- 25. 以下の関数の時間複雑度を計算するにはどうすればよいですか?
- 26. BST時間複雑度
- 27. 2番目のfor-loopの時間複雑度はどのくらいですか?
- 28. Haskell GHC:N個のコンストラクタによるパターン一致の時間複雑度はどのくらいですか?
- 29. このインプレース配列反転の時間複雑度はどのくらいですか?
- 30. clojureのカウント関数の複雑さはどのくらいですか?