暗号ハッシュ関数の時間複雑度はどのくらいですか？

Question

たとえば、MD5またはSHA-1？これらの両方の時間の複雑さは何ですか？私はそれをインターネット上で見つけようとしましたが、それは非常に限られていて、私が得たものは両方ともO（n）です。誰も私をもっと啓発することはできますか？たぶん私に最悪のケースと最善のケースのシナリオを与えますか？

Answer 1

MD5アルゴリズムとSHA-1アルゴリズムの両方は、が暗号で保護されていないため、これ以上使用しないでください。 - Merkle-Damgard constructionに基づいています。これは

入力をパディング、それらはビットの入力固定幅ブロックとして取り、同じサイズのビットの固定幅のブロックを出力するブロック暗号で始まる

1. によって構築されていることを意味しますcryptographically secure padding schemeを使用してブロックサイズのいくつかの倍数に変換し、次に
2. を入力のいくつかのビット数の組み合わせに加えて、初期値または前のブロック暗号の出力のいずれかの組み合わせに繰り返し適用します。

ブロック暗号は固定サイズのビットブロックで動作するため、実行する時間の複雑さはO（1）です。そのブロック暗号には合計でΘ（n）個のアプリケーションがあります（入力は固定サイズのブロックに分割されているため、これらのブロックはΘ（n）あります）。パディングビットを計算するコストはおそらくO 1）でもO（n）になる可能性があります。全体として、これは、これらのハッシュ関数を計算する実行時間がΘ（n）であることを意味します。これは、各ビットが少なくとも1回は訪問され、ビットごとに行われる作業は一定であるため意味があります。

ブロック暗号は、通常、ビットの入力コンビネーション（または少なくとも同じ時間量に非常に近いもの）で実行するのに正確な同じ時間がかかるように実装されていますこれらはブロック暗号を計算するのに必要な時間量を使用してビットの一部を盗むために使用されているtiming attacksに耐性があります。結果として、これらのハッシュ関数が同じサイズの異なる入力で完了するのに異なる時間を要した場合は、非常に珍しいことです。したがって、ランタイムがΘ（n）であるという事実とは無関係に、ウォールクロックランタイムに大きな変化が見られるはずはありません。