DSA: Как создать субстандарт?

Question

В последнее время я провел небольшое исследование об алгоритме цифровой подписи и о том, как он работает.Мой вопрос в соответствии с этим не имеет для меня никакого практического значения, но представляет чистый интерес.

Однако мне любопытно, как создать субстандарт в DSA: где-то при генерации параметров для алгоритма выбирается1024-разрядное простое число p.Следующий шаг - найти 160-битное простое число q, которое является делителем p-1.Вот где я застреваю.Я понятия не имею, как найти этот субстандартный q вовремя, без необходимости ждать вечно.Я также не смог найти документацию об этой конкретной части DSA в Интернете, и все примеры реализации, которые я нашел, используют библиотечные функции для создания параметров.привести меня туда, где я могу прочитать об этом?

Заранее спасибо.

Answer 1

В соответствии с предложением Zoredache: алгоритм создания пары простых чисел p и q для DSA содержится в стандарте цифровой подписи .

Пусть 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.

Надеюсь, я не ошибся. Я еще не все полностью понял, но главный трюк в том, чтобы вычислить p из q вместо того, чтобы попробовать противоположную вещь.

Answer 2

Сказать, что q делит p-1 - то же самое, что сказать, что p ≡ 1 mod q.

Метод FIPS существенно сдвигает и добавляет последовательные выходные данные хеш-функции для построения псевдослучайного фрагмента правильного размера, а затем вычитает остаток так, что p ≡ 1 mod 2q, и, наконец, проверяет на простоту. Единственная «настоящая» энтропия в этом процессе - случайное семя.

Обратите внимание также, что старое FIPS-186 выше 'жестко закодировано' для 160 bit q

Если у вас много энтропии, вы можете так же легко получить кусок случайного числа из хорошего источника, установите верхний и нижний биты на 1, вычтите ((p mod q)-1), затем проверьте это на простоту.

Answer 3

Лично я не знаю много об этом, но я быстро перебрал код OpenSSL source и упомянул публикацию Федеральных стандартов обработки информации 186 в качестве документа, который реализация была основана на.

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 должно быть нечетным, часто выбирается так: быть основным, чтобы форсировать условие, что оно взаимно простое для общего числа и, как правило, довольно мало; е = 2 ^ 16 + 1 = 65537 часто встречается.

Я написал код для RSA, включая генерацию ключей, в моем блоге .