最近、デジタル署名アルゴリズムとその仕組みについて少し調べました。これによる私の質問は、私にとって実際的な問題ではなく、純粋な関心事です。
ただし、DSA でサブプライムを生成する方法に興味があります。アルゴリズムのパラメーターの生成中のどこかで、1024 ビットの素数が選択されますp。q次のステップは、 の約数である160 ビットの素数を見つけることですp-1。それが私が立ち往生するところです。q永遠に待たずに、そのサブプライムを時間内に見つける方法がわかりません。また、インターネット上で DSA の特定の部分に関するドキュメントを見つけることができませんでした。私が見つけたすべての実装例では、ライブラリ関数を使用してパラメーターを作成しています。
そのサブプライム世代についてもっと知っている人、またはそれについて読むことができる場所に私を導くことができる人はいますか?
前もって感謝します。
個人的にはあまり知りませんが、OpenSSL のソースコードを簡単に grep したところ、実装の基となった文書として連邦情報処理標準公告 186が言及されていました。
q割ると言うのは、そうp-1言うのと同じp ≡ 1 mod q.
このFIPS方法は、基本的にシフトして連続したハッシュ出力を追加して、正しいサイズの擬似ランダムチャンクを構築し、その後p ≡ 1 mod 2q、最終的に原発性をテストするように残りを差し引きます。プロセスにおける唯一の「実際の」エントロピーはランダムシードです。
上記の古いものFIPS-186は「ハードコード」されていることにも注意してください160 bit q
エントロピーが十分にある場合は、適切なソースからランダムなチャンクを簡単に取得し、上位ビットと下位ビットを 1 に設定し、減算((p mod q)-1)してから素数をテストできます。
そうではないと思います。p-1を因数分解できれば、公開鍵を簡単に因数分解できますが、これは非常に悪いことです。
通常の鍵生成では、ビット長が等しい2つの大きな素数pとqが必要です。それらの積n=pqは、暗号システムのモジュラスになります。nのトーティエントは、phi（pq）=（p-1）（q-1）として計算されます。次に、de≡1（mod phi（pq））およびgcd（e、phi（pq））= 1となるように、暗号化キーeと復号化キーdの2つのキーが選択されます。それが互いに素であり、一般的にかなり小さいという条件を強制するために素数である; e = 2 ^ 16 + 1=65537が一般的です。
ブログで、キー生成を含むRSAのコードを作成しました。