Безопасность выбора чисел для генерации RSA?

Question

[rav_pr]

Здравствуйте.
Заинтересовала тема криптографии
Интересует пару вопросов
Первый Вопрос про число k которое участвует в генерации секретной экспоненты d. Я так понял оно нужно для округления числа d до целого

1) Как быстро искать K?
2) можно ли всегда использовать некое большое число десятков там условно 20000 300 000? То есть чтобы быстрее найти нужное число k скакать по целым десяткам сотням?

Второй
Есть ли дополнительные требования к числам учавствующим в генерации RSA чтобы обезопасить систему?
Кроме основных, что p и q простые, что е это число 65536
Какая-то проверка взаимной связи между p и q должна быть? Или я эти числа могу абсолютно случайно генерировать, проверять на простоту и использовать?
Перепроверка секретной экспоненты может еще какая есть?

Comments

[alexalexes]

Ту, формулу, которую привели, она решает это условие:
de = 1 (mod φ(n))
То k, которое приведет к делению без остатка в вашей формуле и будет решение.

Какая-то проверка взаимной связи между p и q должна быть?

В бинарном представлении p и q не должны быть слишком длинные последовательности только единиц или только нулей. Это снижает энтропию некоторых разрядов числа n.

[rav_pr]

alexalexes, а есть название такого рода тестам?
Не очень получается найти имплементации теста на подсчёте длины последовательностей нулей и единиц

Answer 1

[Rsa97]

e выбирается из условий 1 < e < φ(n) и НОД(e, φ(n)) = 1. Самый тривиальный вариант для удовлетворения этих условий - взять для e простое число, меньшее φ(n). При этом берут значение e, содержащее минимум единиц в двоичном представлении, чтобы ускорить вычисления.

k искать не надо, надо искать d, такое, что d ⋅ e ≡ 1 (mod φ(n)). Обычно используется расширенный алгоритм Евклида.
d ⋅ e + k ⋅ φ(n) = НОД(e, φ(n)) = 1
При известных e и φ(n) алгоритм позволяет вычислить d и k как коэффициенты Безу.

К p и q требования только по длине. Чем длиннее число, тем более криптостойкое будет шифрование. Используют числа длиной 1024, 2048 или 4096 бит.

Comments

[rav_pr]

Но ведь d и ищется в частности по формуле как на картинке.
И это пока самая понятная мне формула, подсмотренная в видео от Академии Хана на ютубе

И в этой формуле есть k. Как число которое методом перебора так понимаю ищется?

[Rsa97]

rav_pr, Зачем искать k подбором, если есть алгоритм, который гарантированно и с меньшими затратами выдаёт значение d?

[rav_pr]

Rsa97, гораздо сложнее в осознавании.
Вот и хочется по формуле которая на картинке

Буду пытаться понять алгоритм поиска который вы описали

[alexalexes]

rav_pr, простые формулы в математике с остатками только описывают свойства, которым должен соответствовать результат.
Быстрое решение никогда не выражается простым переносом переменных из левой части в правую.
Под такое решение применяют отдельную гипотезу, а к ней толстый вычислительный метод.
Бытовой логикой можно только проверить результат метода.

[rav_pr]

Rsa97, alexalexes,

Я не очень понял как может ровняться сумма двух произведений НОДу а затем единице?
Или это имелось ввиду не щнак равно там?

[Rsa97]

rav_pr, Элементарно.
НОД(14, 39) = 1
14 * 14 + (-5) * 39 = 1 = НОД(14, 39)