@rav_pr

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

Здравствуйте.
Заинтересовала тема криптографии
Интересует пару вопросов
Первый Вопрос про число k которое участвует в генерации секретной экспоненты d. Я так понял оно нужно для округления числа d до целого
6688f117b7c70131052950.png
1) Как быстро искать K?
2) можно ли всегда использовать некое большое число десятков там условно 20000 300 000? То есть чтобы быстрее найти нужное число k скакать по целым десяткам сотням?

Второй
Есть ли дополнительные требования к числам учавствующим в генерации RSA чтобы обезопасить систему?
Кроме основных, что p и q простые, что е это число 65536
Какая-то проверка взаимной связи между p и q должна быть? Или я эти числа могу абсолютно случайно генерировать, проверять на простоту и использовать?
Перепроверка секретной экспоненты может еще какая есть?
  • Вопрос задан
  • 89 просмотров
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
e выбирается из условий 1 < e < φ(n) и НОД(e, φ(n)) = 1. Самый тривиальный вариант для удовлетворения этих условий - взять для e простое число, меньшее φ(n). При этом берут значение e, содержащее минимум единиц в двоичном представлении, чтобы ускорить вычисления.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы