DSA：次贷是如何产生的？
最近我对数字签名算法及其工作原理做了一些研究。我的问题对我来说没有实际意义，而是纯粹的兴趣。
然而，我很好奇如何在 DSA 中生成次质数：在生成算法参数的过程中，我们选择了 1024 位质数 p。下一步是找到 160 位素数 q，它是 p-1 的除数。这就是我被困住的地方。我不知道如何及时找到次级q，而不必永远等待。我还在互联网上找不到有关 DSA 特定部分的任何文档，并且我发现的所有示例实现都使用库函数来创建参数。
有谁对次贷一代有更多了解，或者可以带我到一个可以阅读相关内容的地方吗？
提前致谢。
Lately I did a bit of research about the Digital Signature Algorithm and how it works. My question according to this is of no practical matter for me but of pure interest.
However, I'm curious how to generate the subprime in DSA: Somewhere during the generation of the parameters for the algorithm one chooses a 1024-bit prime p. The next step is to find a 160-bit prime q which is a divisor of p-1. That's where I get stuck. I have no idea how to find that subprime q in time, without having to wait forever. I also couldn't find any documentation about that particular part of DSA on the internet and all the example implementations I've found use library functions to create the parameters.
Does anyone know more about that subprime generation or can lead me to a place where I can read about it?
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
正如 Zoredache 所建议的：为 DSA 创建素数对
p和q的算法，可在 数字签名标准。令
L-1 = 160*n + b，其中b,n ∈ ℕ且0 ≤ b160种子> 2^⁶⁰。令g为seed的长度（以位为单位）。U = sha(seed) XOR sha(seed+1 mod 2^g)（其中 sha 是安全哈希算法）q = U OR 2¹⁵⁹ OR 1counter = 0, offset = 2For k = 0,...,n: V_k = sha((种子 + 偏移量 + k) mod 2^g)W = V_0 + V_1 * 2^160 + ... + V_(n-1) * 2^((n-1) *160) + (V_n mod 2^b) * 2^(n*160)X = W + 2^(L-1)c = X mod 2*qp = X - (c-1)如果 p2^(L-1)转到步骤 13。p是否为素数，如果是，则转到步骤 15。counter = counter + 1, offset = offset + n + 1counter >= 4096则转到步骤 1，如果不是，则转到步骤 7。p和q> 这样q是p-1的除数。我希望我没有弄错什么。我还没有完全理解所有内容，但主要技巧是从
q中计算p而不是尝试相反的事情。As suggested by Zoredache: The algorithm to create the pair of primes
pandqfor DSA, found in the Digital Signature Standard.Let
L-1 = 160*n + b, whereb,n ∈ ℕand0 ≤ b < 160seed > 2¹⁶⁰. Letgbe the length ofseedin bits.U = sha(seed) XOR sha(seed+1 mod 2^g)(where sha is the Secure Hash Algorithm)q = U OR 2¹⁵⁹ OR 1qis prime, if not go to step 1.counter = 0, offset = 2For k = 0,...,n: V_k = sha((seed + offset + k) mod 2^g)W = V_0 + V_1 * 2^160 + ... + V_(n-1) * 2^((n-1)*160) + (V_n mod 2^b) * 2^(n*160)X = W + 2^(L-1)c = X mod 2*qp = X - (c-1)If p < 2^(L-1)go to step 13.pis prime, if so go to step 15.counter = counter + 1, offset = offset + n + 1counter >= 4096go to step 1, if not go to step 7.pandqso thatqis a divisor ofp-1.I hope I did not get anything wrong. I didn't understand everything completely yet but the major trick is to calculate
pout ofqinstead of trying the opposite thing.我个人对此了解不多，但我通过 OpenSSL 源 代码进行了快速 grep 并它提到联邦信息处理标准出版物 186 作为实施的文件基于。
I don't know much about it personally, but I did a quick grep through the OpenSSL source code and it mentioned the Federal Information Processing Standards Publication 186 as the document that the implementation was based on.
说
q除p-1与说p ≡ 1 mod q 相同。FIPS方法本质上是移位并添加连续的散列输出以构建正确大小的伪随机块，然后减去余数，使得 p == 1 mod 2q ，最后测试素数。该过程中唯一“真实”的熵是随机种子。另请注意，上面的旧
FIPS-186是160位q的“硬编码”如果你有足够的熵，你可以很容易地从一个好的源，将顶部和底部位设置为 1，减去
((p mod q)-1)然后测试其素数。Saying that
qdividesp-1is the same as saying thatp ≡ 1 mod q.The
FIPSmethod essentially shifts and adds successive hash outputs to build a pseudorandom chunk of the correct size, and then subtracts a remainder such thatp ≡ 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-186above is 'hardcoded' for160 bit qIf 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.我认为这是不对的。如果你可以分解 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 必须是奇数，经常被选择为是质数以强制其与 totient 互质的条件，并且通常相当小； e=2^16+1=65537 是常见的。
我在我的博客中编写了 RSA 代码，包括密钥生成。
I don't think that's right. If you can factor p-1, then you can easily factor the public key, which is really bad.
The usual key generation takes two large primes p and q, of equal bit length; their product n=pq becomes the modulus of the cryptosystem. The totient of n is computed as phi(pq)=(p-1)(q-1). Then two keys are chosen, the encryption key e and the decryption key d, such that de ≡ 1 (mod phi(pq)) and gcd(e, phi(pq)) = 1. E must be odd, is frequently chosen to be prime to force the condition that it is co-prime to the totient, and is generally fairly small; e=2^16+1=65537 is common.
I wrote code for RSA, including key generation, at my blog.