Я пытаюсь реализовать обмен ключами Диффи-Хеллмана. Допустим, я нашел большое простое число p — как мне найти образующую g?
Ограничено многоточной библиотекой, которую мне приходится использовать, доступны только несколько основных операций (+, *, -, /, pow, modExp, modMult, mod, gcd, isPrime, genRandomPrime, genRandomBits и некоторые другие).
Будет ли работать поиск безопасного простого числа q, чтобы каждое число n, для которого gcd(n,q) == 1, было генератором, верно?
Вы уже получили ритуальное наставление не сворачивать свою собственную криптовалюту, если вы вообще заботитесь о своей безопасности, так что вот как найти мод генератора безопасным простым q. Число g в закрытом диапазоне [2, q - 2] является генератором тогда и только тогда, когда g^((q-1)/2) != 1 mod q, что вы должны вычислить с помощью стандартного алгоритма модульного возведения в степень. Выбирайте случайные значения g, пока одно из них не пройдет тест.
Вы в принципе ответили на свой вопрос. Просто тест gcd(n,q)==1 не нужен, так как q простое. Это означает, что любое число n, такое что n < q не имеет общего делителя с q и gcd(n,q), всегда будет давать 1.
Вы можете проверить, является ли q=2p + 1 простым числом. Если это так, то ord(Zq) = q-1 = (2p+1)-1 = 2p. Поскольку ord(x) | ord(Zq) для каждого x в Zq ord(x)=2 или ord(x)=p или ord(x)=2p. Таким образом, вам просто нужно проверить, имеет ли ваш случайно выбранный элемент x из {2,...,q-1} порядка 2. Если нет, то он имеет порядок p или 2p, и вы можете использовать это как генератор.
Как правило, не задавайте программистам вопросов о криптографии. Криптография тонка и, как следствие, сложна невидимыми способами, которые легко ведут к самообману относительно собственной компетентности. Вместо этого спросите у криптографов (многие из которых также являются программистами). У Stack Exchange есть доска криптографии, где уже был дан ответ на этот вопрос.
https://crypto.stackexchange.com/questions/29926/what-diffie-hellman-parameters-should-i-use
Я мог бы поспорить с советом там, но в основном это звучит. Если вы действительно не хотите изучать соответствующую математику, я бы уступил авторитетам; они указаны в ответе выше.
Что касается вопроса по математике, который вы задаете, вот небольшое введение. Мультипликативная группа по простому модулю p имеет размер p-1. (См. Маленькую теорему Ферма.) порядок любого элемента должен делиться на p-1. Наиболее благоприятный случай, когда p-1=2q, где q также простое число.
