security - elgamal のジェネレータを見つける

Question

エルガマル署名スキームのジェネレーターはどのように見つけられますか? 優れたジェネレーターであるほとんどのプログラムで使用される値はありますか? または、素数のジェネレーターを見つける方法はありますか? もしそうなら、どのように？素数には少なくとも 1 つの生成元があると言うのは本当でしょうか?

Answer 1

ElGamal 署名スキームの代わりに DSA を使用します。

ElGamal の実装で犯す可能性のある間違いが多すぎます。それらの間違いの 1 つは、GregS が提案したもので、IKE パラメータを使用することです。これらのパラメーターは、ElGamal 暗号化用に生成されたものであり、署名スキーム用ではありません。2 つのスキームには異なる要件があります。特に、ジェネレーターとして g=2 を使用することは、暗号化には適していますが、署名スキームには非常に悪い選択です。(詳細については、たとえば、「応用暗号化ハンドブック」http://www.cacr.math.uwaterloo.ca/hac/ 11 章の注 11.67 を参照してください)。ジェネレーターをランダムに選択するのが正しいでしょう。しかし、繰り返しますが、DSA を使用するだけであれば、標準に従うことでこれらの落とし穴を簡単に回避できます。

もう少し追加します: OpenPGP https://www.rfc-editor.org/rfc/rfc4880は ElGamal 署名を許可するために使用されていましたが、しばらく前に非推奨になりました。DSA には利点しかないため、この非推奨は非常に合理的でした。より効率的で、より安全で、標準化されています。もちろん、古い PGP 実装を見ることもできますが、これらの実装が合理的な選択肢を提供するかどうかは、最初に文献を読まなければわかりません。

Answer 2

エルガマル署名スキームのジェネレーターはどのように見つけられますか? 優れたジェネレーターであるほとんどのプログラムで使用される値はありますか? または、素数のジェネレーターを見つける方法はありますか? もしそうなら、どのように？

Handbook of Applied Cryptographyの一般的な確率的アルゴリズム 4.86 を使用できます。ただし、そのようなアルゴリズムの出力から、Elgamal 署名にとって安全でないことがわかっている値を除外する必要があります。少なくとも、p-1を割る値(たとえば 2) と、その逆数がp-1を割る値。これらは私が今日認識している条件であることに注意してください。このトピックについて公開された論文に関する詳細な調査が必要になる場合があります。

個人的には、既存のプログラムで既に使用されているドメイン パラメータは信用できません。著者は上記のすべての条件を考慮していない可能性があります。さらに、研究により、それらが選択されてから新しい条件が明らかになった可能性があります。

素数には少なくとも 1 つの生成元があると言うのは本当でしょうか?

絶対に正しい: モジュロp ( pは素数)を法とする整数上の乗法群には、少なくとも 1 つの生成元が常に存在します。実際にはもっと多くのものがあります: phi(phi(p))で、phiはtotient functionです。ただし、それらすべてが Elgamal 署名スキームに対して安全であるとは限りません。

Answer 3

El Gamal は Diffie Hellman アルゴリズムの変形と見なすことができ、後者のパラメーターは前者に使用できます。たとえば、RFC 2409の IKE グループ 1 と 2 を使用したり、他の RFC に散りばめられたより大きな IKE グループを使用したりできます。DSA パラメータの生成については、 FIPS 186の説明に従うこともできます。また、原始根に関するこの議論も参照してください。

編集:
@abc で指摘されているように、これは el gamal 署名では正しくありません。DSA リンク (FIPS 186) に従ってください。