⚡️ Почему RSA в OpenSSL не делает «обычное деление»
В реализации RSA внутри OpenSSL почти не используется прямое модульное деление. Вместо этого там работает Montgomery reduction - алгоритм, который ещё в 1985 году предложил Питер Монтгомери.
Идея простая: в RSA постоянно нужны операции вида «умножили большие числа и взяли остаток по модулю». Обычное деление на больших числах дорогое, поэтому его стараются избегать.
Montgomery reduction переводит вычисления в специальную форму, где параметр R выбирают как степень двойки. После этого часть дорогих делений превращается в сдвиги битов и более дешёвую арифметику.
Для пользователя это незаметная деталь. Но без таких трюков современный RSA был бы намного медленнее.
Есть хороший шанс, что HTTPS-соединение, которым вы пользуетесь прямо сейчас, где-то внутри уже опиралось на эту технику.
