0

これは、暗号化の問題というよりは、実行時間や時間の複雑さに関する問題なので、読み続けてください:

大学では、ディフィー ヘルマン交換で秘密を見つけるために力ずくの離散対数アルゴリズムを実装する必要があり、データ型や大きな素数について心配する必要がないように、C++ と NTL ライブラリを使用して実装を開始しました。

私の例の数値は、25 ビットの素数を使用した次のとおりであり、離散対数を見つけたいと考えています。

p = 20084173;  /* the prime */
g = 2;         /* the generator */
a = 7709318;   /* the logarithm of a */
b = 6676335;   /* the logarithm of b */

NTL を使用して C++ で以下を実装しました。

int main() {

    ZZ p, g, a, b;

    // 25 Bit
    p = 20084173;
    g = 2;
    a = 7709318;
    b = 6676335;

    exhaustiveSearch(p, g, a);
    exhaustiveSearch(p, g, b);

    return 0;
}

ZZ exhaustiveSearch(ZZ p, ZZ g, ZZ t) {
    ZZ i, x;
    i = 0;
    x = 1;
    while ((x = (x % p)) != t) {
        i++;
        x = x * g;
    }
    cout << endl << endl << "p = " << p << endl << "g = " << g << endl << "t = " << t << endl << "secret: = " << i << endl;
    return i;
}

出力 (7.581 秒) :

p = 20084173
g = 2
t = 7709318
secret: = 557254

p = 20084173
g = 2
t = 6676335
secret: = 8949383

-> time: 7.581s

まあ、私はそれが本当に長いと思ったので、NTL なしでテストし、C++ で通常の long をテストしました -> すべての ZZ が long (0.124s) に置き換えられたと想像してください:

p = 20084173
g = 2
t = 7709318
Secret: = 557254

p = 20084173
g = 2
t = 6676335
Secret: = 8949383

-> time: 0.124s

なぜNTLがそれほど遅いのか、誰か説明してもらえますか? 私はこの分野の専門家ではなく、暗号化の基本とそれらを簡単な例で実装する方法を理解しようとしているだけであることを覚えておいてください.

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

4

1 に答える 1

1

一般に。NTL は、長い整数やその他の暗号関連の算術演算用の強力で適切に作成されたライブラリですが、明らかに小さい数の組み込み型の効率に勝るものはありません。long 型を使用する場合、すべての操作が単一の CPU 命令に変換されることに注意してください。可能な限り高速ですが、32/64 ビットに制限されています。

一方、ZZ は、メモリを管理する必要があり、任意の長さの整数を操作できる本格的なクラスです。これには代償が伴います。

可能な最適化。そうは言っても、ZZ がクラスであるという事実を考慮して、物事を少し試して最適化することができるので、たとえば不要な一時オブジェクトの作成を避けることは理にかなっているかもしれません。

たとえば、次の行を考えてみましょう

x = x * g;

2 つのオブジェクトを呼び出しoperator*、新しい値を x に再度割り当てます。その実装を見ると、次のことがわかります。

inline ZZ operator*(const ZZ& a, const ZZ& b)
      { ZZ x; mul(x, a, b); NTL_OPT_RETURN(ZZ, x); }

そのため、新しい一時オブジェクトが作成されて返されます。呼んだほうが効率いいと思う

x *= g

の実装によりoperator*=、一時的な作成が回避されるため

inline ZZ& operator*=(ZZ& x, const ZZ& a)
  { mul(x, x, a); return x; }

ZZ_p を使用します。考慮すべきもう 1 つのことは、基本的に Z_p で (つまり、Z modulo p で) 演算を行っていることです。そのため、必要に応じて自動的にリダクションを実行するクラス ZZ_p を使用することをお勧めします。

GMP での NTL の使用 (長い) 算術演算のパフォーマンスが気になる場合は、根底にある長い算術演算に GMP を使用するように NTL を構築することをお勧めします。これにより、通常の NTL よりもパフォーマンスが向上します。

于 2014-06-06T13:34:55.687 に答える