0

ここの教祖が私を助けてくれることを願っています

ハッシュ アルゴリズムとして SHA1 を使用してコンシステント ハッシュを実装する C/C++ コードを作成しています。

次のようにモジュール操作を実装する必要があります。

0100 0011....0110 100 mod 0010 1001 = ?

除数 ( 0000 1111) が 2 のべき乗である場合、被除数pow(2,n)の最後の n ビットが結果であるため、簡単です。

SHA1 の長さは 160 ビット (または 40 hex ) です。私の質問は、長いビット文字列のモジュロ演算を別の任意のビット文字列に実装するにはどうすればよいですか?

ありがとうございました。

4

1 に答える 1

1

ユーザースタークがコメントで指摘しているように（必要以上に無礼だと思います）、これは基数2 ^ 32の長除算です。または、基数 2 で、桁数を増やします。また、学校で学んだ 10 を底とする長除算のアルゴリズムを使用できます。

はるかに大きな数で除算を行うためのより洗練されたアルゴリズムがありますが、アプリケーションでは、次の行に沿って非常に単純かつ非効率的に行う余裕があると思います (これは底 2 バージョンで、左から減算するだけです-できなくなるまで、分母のシフトされたバージョン):

// Treat x,y as 160-bit numbers, where [0] is least significant and
// [4] is most significant. Compute x mod y, and put the result in out.
void mod160(unsigned int out[5], const unsigned int x[5], const unsigned y[5]) {
  unsigned int temp[5];
  copy160(out, x);
  copy160(temp, y);
  int n=0;
  // Find first 1-bit in quotient.
  while (lessthanhalf160(temp, x)) { lshift160(temp); ++n; }
  while (n>=0) {
    if (!less160(out, temp)) sub160(out, temp); // quotient bit is 1
    rshift160(temp); --n; // proceed to next bit of quotient
  }
}

誤解を避けるために、上記は大まかなスケッチにすぎません。

  • バグだらけかもしれません。
  • のようなビルディングブロック関数の実装は書いていませんless160。
  • 実際には、個別の関数を使用するのではなく、それらのコードをインラインに配置することになるでしょう。たとえば、copy1605 つの割り当て、または短いループ、またはmemcpy.

確かにもっと効率的にすることができます。たとえば、最初のステップでは、一度に 1 か所ずつシフトするのではなく、先頭の 0 ビットをカウントしてから 1 つのシフトを行う方がよい場合があります。(しかし、右シフトはおそらくそれをしたくありません。なぜなら、半分の時間は 1 つのシフトだけを行うからです。)

「base-2^32」バージョンの方が高速かもしれませんが、実装はもう少し複雑になります。

于 2016-04-13T11:59:07.940 に答える