[Перевод] Математики доказали, что многочлены не помогут взломать RSA

Недавно в журнале Quanta вышел материал, в котором автор рассказывал про удивительный с точки зрения неискушенных читателей феномен, доказанный математиками. Его суть в том, что почти все многочлены определенного типа — неприводимые, то есть не поддаются разложению. Это доказательство применяется во многих областях чистой математики. Но также это хорошая новость для одного из столпов современной жизни — цифрового шифрования.

Для надежного хранения цифровой информации широко используется шифрование с помощью алгоритма RSA. Это прокачанная версия схемы, которую может придумать даже семиклассник, чтобы обмениваться сообщениями с друзьями: каждой букве присваивается свой номер, который умножается на некий секретный, заранее оговоренный ключ. Чтобы расшифровать сообщение, достаточно просто поделить его на секретный ключ.

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

*

Простые множители какого-либо числа — это простые числа, которые необходимо перемножить, чтобы получилось это число. Так, для числа 12 это 2*2*3, а для числа 495 это 3, 3, 5 и 11.

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

Но есть и обходной путь. Читать дальше →

Источник: Хабрахабр