В США подвели советскую теорию под всю мировую криптографию
Вопрос о том, существует ли в природе принципиально невзламываемый код, всегда был центральным в криптографии. И до сих пор именно он лежит в основе всех усилий по обеспечению конфиденциальности частной информации в Интернете.
Специалисты из Корнельского университета (Cornell Tech University) определили проблему, которая, по их мнению, является ключом к пониманию того, может ли быть принципиально нарушено все существующее сегодня шифрование. При этом в основу этих важных для всей мировой криптографии исследований легли выводы гениального русского и советского математика Андрея Колмогорова.
Вот как описал суть своих исследований Рафаель Пасс (Rafael Pass), профессор компьютерных наук в Cornell Tech: «Если вам удастся придумать алгоритм, чтобы решить ограниченную во времени проблему сложности Колмогорова, то вы можете взломать все криптокоды, все схемы шифрования, все цифровые подписи. Однако, если не существует эффективного алгоритма для решения этой проблемы, вы можете получить одностороннюю функцию, и, следовательно, получить абсолютно безопасный алгоритм шифрования».
Все исследование закручено вокруг того, что на протяжении тысячелетий криптография считалась циклом: кто-то изобрел код, тот был эффективен до тех пор, пока кто-то не взломал его. В 1970-х годах исследователи, ищущие все более совершенную теорию криптографии, ввели концепцию односторонней функции – простой, но необратимой вспять задачи или проблемы. В качестве примера можно привести зажженную спичку, которую легко поджечь, но практически (не переставив в исходное состояние все ее атомы) невозможно вернуть в исходное состояние.
«Идея заключалась в том, что односторонняя функция – идеальная отправная точка для понимания криптографии», - сказал Пасс. - «Зашифровать сообщение очень просто. Осталось сделать так, чтобы тот, кто не знает ключ шифрования, должен сделать невозможное с практической точки зрения – грубо говоря, восстановить уже зажженную спичку».
Отправная точка – это хорошо, но проблема в том, что исследователи до сих пор не смогли доказать существование односторонней функции. Именно поэтому, к слову, в основе современного шифрования лежит не математическая «зажженная спичка», а иные, принципиально взламываемые механизмы.
Пасс взял за возможную природную основу криптографии принцип сложности Колмогорова, описанный математиками в 1960-х годах. Колмогоровская сложность строки чисел определяется как длина (в двоичном алфавите) самой короткой компьютерной программы, которая может генерировать строку. По словам Пасса, его исследования не только показывают, что криптография в основе своей имеет некий базовый принцип, но также демонстрируют глубокую связь между двумя совершенно отдельными областями математики и информатики - криптографией и алгоритмической теорией информации.
Исследование было частично профинансировано Национальным научным фондом и Управлением научных исследований Военно-воздушных сил США и основывалось на программах, осуществляемых в рамках исследовательских проектов Национальной разведки.
