26.10 // Крипто // Взлом RSA без факторизации реален, но неэффективен

Никем не доказано, что целочисленная факторизация (разложение чисел на простые множители) является абсолютно трудной задачей. Никем не доказано, что найти закрытый ключ RSA по открытому нельзя в обход факторизации. Наоборот, такие методы стали известны еще в конце 90-х годов прошлого века.

Исследователь Daniel R. L. Brown в работе "Breaking RSA May Be As Difficult As Factoring" представил обобщенный метод нахождения секретного ключа RSA и попытался показать, что множество таких методов делают задачу взлома RSA столь же трудной, что и факторизация чисел.

Именно этим можно объяснить, что часто появляющиеся фантастические доказательства нестойкости RSA в обход факторизации не работают с достаточной скоростью на больших числах. Тем не менее, существование таких методов может компрометировать RSA в определенных практических реализациях.

Источник: "openPGP в России"