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