DSA:如何产生次贷? [英] DSA: How to generate the subprime?

问题描述

最近，我对数字签名算法及其工作方式进行了一些研究.根据这个问题，我的问题对我来说没有任何实际意义，而纯粹是出于兴趣.

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.

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

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?

谢谢.

推荐答案

如Zoredache所建议:用于为DSA创建素数对p和q的算法，可在

As suggested by Zoredache: The algorithm to create the pair of primes p and q for DSA, found in the Digital Signature Standard.

让L-1 = 160*n + b，其中b,n ∈ ℕ和0 ≤ b < 160

1. 选择一个随机数seed > 2¹⁶⁰.假设g是seed的长度(以位为单位).
2. U = sha(seed) XOR sha(seed+1 mod 2^g)(其中sha是安全哈希算法)
3. q = U OR 2¹⁵⁹ OR 1
4. 测试q是否为质数，如果不是，则转到步骤1.
5. counter = 0, offset = 2
6. For k = 0,...,n: V_k = sha((seed + offset + k) mod 2^g)
7. W = V_0 + V_1 * 2^160 + ... + V_(n-1) * 2^((n-1)*160) + (V_n mod 2^b) * 2^(n*160)
8. X = W + 2^(L-1)
9. c = X mod 2*q
10. p = X - (c-1)
11. If p < 2^(L-1)转到步骤13.
12. 测试p是否为素数，如果是，则转到步骤15.
13. counter = counter + 1, offset = offset + n + 1
14. 如果counter >= 4096转到步骤1，否则转到步骤7.
15. 我们现在有p和q，因此q是p-1的除数.

1. Choose a random number seed > 2¹⁶⁰. Let g be the length of seed in bits.
2. U = sha(seed) XOR sha(seed+1 mod 2^g) (where sha is the Secure Hash Algorithm)
3. q = U OR 2¹⁵⁹ OR 1
4. Test if q is prime, if not go to step 1.
5. counter = 0, offset = 2
6. For k = 0,...,n: V_k = sha((seed + offset + k) mod 2^g)
7. W = V_0 + V_1 * 2^160 + ... + V_(n-1) * 2^((n-1)*160) + (V_n mod 2^b) * 2^(n*160)
8. X = W + 2^(L-1)
9. c = X mod 2*q
10. p = X - (c-1)
11. If p < 2^(L-1) go to step 13.
12. Test if p is prime, if so go to step 15.
13. counter = counter + 1, offset = offset + n + 1
14. If counter >= 4096 go to step 1, if not go to step 7.
15. We have now p and q so that q is a divisor of p-1.

我希望我没有做错任何事情.我还没有完全理解所有内容，但是主要的窍门是从q中计算出p而不是尝试相反的事情.

I hope I did not get anything wrong. I didn't understand everything completely yet but the major trick is to calculate p out of q instead of trying the opposite thing.

这篇关于DSA:如何产生次贷?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！