primes - DSA：如何生成次贷？

Question

最近我对数字签名算法及其工作原理做了一些研究。我根据这个提出的问题对我来说不是实际问题，而是纯粹的兴趣。

但是，我很好奇如何在 DSA 中生成 subprime：在生成算法参数期间的某个地方选择 1024-bit prime p。下一步是找到一个 160 位素数q，它是 的除数p-1。这就是我卡住的地方。我不知道如何及时找到那个次贷q，而不必永远等待。我在互联网上也找不到任何关于 DSA 特定部分的文档，并且我发现的所有示例实现都使用库函数来创建参数。

有没有人知道更多关于次贷一代的信息，或者可以带我到一个我可以阅读它的地方？

提前致谢。

Answer 1

Answer 2

我个人对此了解不多，但我通过OpenSSL 源代码快速 grep，它提到了联邦信息处理标准出版物 186作为实现所依据的文档。

Answer 3

Saying that q divides p-1 is the same as saying that p ≡ 1 mod q.

The FIPS method essentially shifts and adds successive hash outputs to build a pseudorandom chunk of the correct size, and then subtracts a remainder such that p ≡ 1 mod 2q, and finally tests for primality. The only 'real' entropy in the process is the random seed.

Note also that the old FIPS-186 above is 'hardcoded' for 160 bit q

If you have plenty of entropy you can just as easily get a chunk of random from a good source, set the top and bottom bits to 1, subtract ((p mod q)-1) then test that for primality.

Answer 4

我不认为这是对的。如果您可以分解 p-1，那么您可以轻松分解公钥，这真的很糟糕。

通常的密钥生成需要两个相同位长的大素数 p 和 q；它们的乘积 n=pq 成为密码系统的模数。n 的总和计算为 phi(pq)=(p-1)(q-1)。然后选择两个密钥，加密密钥 e 和解密密钥 d，使得 de ≡ 1 (mod phi(pq)) 和 gcd(e, phi(pq)) = 1。E 必须是奇数，经常被选择为be prime 强制条件是它与 totient 互质，并且通常相当小；e=2^16+1=65537 很常见。

我在我的博客上为 RSA 编写了代码，包括密钥生成。