Создание параметров Diffie-hellman (генератор)

Question

Я пытаюсь реализовать обмен ключами diffie-hellman. Скажем, я нашел большое простое число p - как я могу найти генератор g?

Ограниченный библиотекой multiprecision, которую я должен использовать, всего несколько основных операций (+, *, -, /, pow, modExp, modMult, mod, gcd, isPrime, genRandomPrime, genRandomBits и еще несколько) доступны.

это будет работать, чтобы искать безопасный прайм д, так что каждое число п, для которых gcd(n,q) == 1 должен быть генератором, верно?

Answer 1

Вы уже получили ритуальное предостережение, чтобы не рулить свой собственный крипто, если вы вообще не заботитесь о своей безопасности, так вот, как найти генератор по модулю безопасного простого q. Число g в замкнутом диапазоне [2, q - 2] является генератором тогда и только тогда, когда g^((q-1)/2)! = 1 mod q, который вы должны вычислить со стандартным алгоритмом модульного возведения в степень. Выбирайте случайные значения g, пока не пройдете тест.

Answer 2

Вы в основном ответили на свой вопрос. Просто тест gcd(n,q)==1 не нужен, так как q является простым. Это означает, что любое число n, так что n < q не имеют общих делителей с q и gcd(n,q) всегда будет выход 1.

Вы можете проверить, является ли д = 2р + 1 простое число. Если это так, то ord (Zq) = q-1 = (2p + 1) -1 = 2p. С ord (x) | Ord (Zq) для каждого х в ZqOrd (х) = 2 или Ord (х) = р или Ord (х) = 2p. Таким образом, вам просто нужно проверить, имеет ли ваш случайно выбранный элемент x из {2, ..., q-1} порядка 2. Если нет, то он имеет порядок p или 2p, и вы можете использовать его в качестве генератора.

Answer 3

Как правило, не спрашивайте у программистов вопросы о криптографии. Криптография является тонкой и, как результат, трудно невидимыми способами, которые легко приводят к самообману в отношении собственной компетенции. Вместо этого спросите криптографов (многие из которых также являются программистами). У Stack Exchange есть криптографическая плата, на которую уже был дан ответ.

https://crypto.stackexchange.com/questions/29926/what-diffie-hellman-parameters-should-i-use

я мог придраться с советами там, но это в основном звук. Если вы действительно не хотите изучать соответствующую математику, я бы отнесся к властям; они приводятся в ответе выше.

Что касается вопроса математики, который вы задаете, вот крошечное введение. Мультипликативная группа по модулю простого p имеет размер p-1. (См. Fermat's Little Theorem.) order of any element должен делить p-1. Наиболее благоприятным случаем является то, что p-1 = 2q, где q также является простым.