⚡️ Почему RSA в OpenSSL не делает «обычное деление»

В реализации RSA внутри OpenSSL почти не используется прямое модульное деление. Вместо этого там работает Montgomery reduction - алгоритм, который ещё в 1985 году предложил Питер Монтгомери.

Идея простая: в RSA постоянно нужны операции вида «умножили большие числа и взяли остаток по модулю». Обычное деление на больших числах дорогое, поэтому его стараются избегать.

Montgomery reduction переводит вычисления в специальную форму, где параметр R выбирают как степень двойки. После этого часть дорогих делений превращается в сдвиги битов и более дешёвую арифметику.

Для пользователя это незаметная деталь. Но без таких трюков современный RSA был бы намного медленнее.

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

@linux_education