Как сгенерировать открытый ключ RSA из закрытого ключа?

Question

Я читал вопрос о SO и узнал, что мы можем сгенерировать открытый ключ из закрытого ключа, используя openssl в python.Теперь мне интересно, как это работает (математическая часть) и как я могу реализовать метод на python или в C, без использования openssl или какой-либо другой библиотеки?

Answer 1

Если закрытый ключ хранится в формате CRT (китайская теорема об остатках), математика здесь не используется; формат включает в себя публичный показатель. Вот как инструменты OpenSSL «создают» открытый ключ из закрытого ключа.

Если частное не хранится в формате CRT, обычно вычислять открытый показатель степени не представляется возможным, учитывая частный показатель. Вы можете, однако, угадать общие публичные показатели и легко проверить свою догадку.

Математически, чтобы быстро вычислить один показатель степени, используя другой, вам нужно знать коэффициент, число, вычисленное из факторов модуля. И, конечно же, безопасность RSA основывается на невозможности факторизации модуля. Это отношение симметрично; не имеет значения, знаете ли вы открытый показатель и пытаетесь вычислить частный показатель или наоборот.