Теория случайности может быть ключом к безопасности в Интернете

Этот вопрос был центральным в криптографии на протяжении тысячелетий и лежит в основе усилий по обеспечению конфиденциальности частной информации в Интернете. В новой статье исследователи Cornell Tech определили проблему, являющейся ключом к тому, может ли быть нарушено все шифрование, а также удивительную связь с математической концепцией, целью которой является определение и измерение случайности.

«Наш результат не только показывает, что криптография имеет «материнскую» проблему, но также показывает глубокую связь между двумя совершенно разными областями математики и информатики – криптографией и алгоритмической теорией информации», – рассказывает Рафаэль Пасс, профессор компьютерных наук в Cornell Tech.

Пасс является соавтором книги «Об односторонних функциях и колмогоровской сложности», которая будет представлена на симпозиуме IEEE по основам информатики 16-19 ноября в Дареме, штат Северная Каролина.

«Результатом, – сказал он, – является то, что вычислительная проблема, возникшая в 1960-х годах в Советском Союзе, характеризует осуществимость базовой криптографии – например, шифрование личным ключом, цифровой подписью и аутентификацией».

На протяжении тысячелетий криптография двигалась в своем развитии циклом: кто-то изобрел код, код был эффективен, пока кто-то не сломал его, и код стал неэффективным. В 1970-х годах исследователи, пытающиеся найти более совершенную теорию криптографии, ввели концепцию односторонней функции – простой односторонней задачи, невыполнимой в другом направлении.

Например, легко зажечь спичку, но невозможно вернуть горящую спичку в ее прежнее состояние, не переставив атомы.

«Идея заключалась в том, что если у нас есть такая односторонняя функция, возможно, это очень хорошая возможность для понимания криптографии», – сказал Пасс. «Зашифровать сообщение очень просто. И если у вас есть ключ, вы также можете расшифровать его. Но тот, кто не знает ключ, должен сделать то же самое, чтобы восстановить зажженную спичку».

Но исследователи не смогли доказать существование односторонней функции. Наиболее известный кандидат, который также является основой наиболее часто используемых схем шифрования в Интернете, полагается на целочисленную факторизацию. Легко умножить два случайных простых числа – например, 23 и 47 – но значительно сложнее найти эти два фактора, кроме как с учетом их произведения.

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

«Центральный вопрос, стоявший перед такой задачей: существует ли такой алгоритм? Есть ли какая-то естественная проблема, которая характеризует существование односторонних функций? Если это обнаружат, мы получим способ решить проблему и получить возможность сломать все предполагаемые односторонние функции. В противном случае мы можем получить безопасную криптографию» – говорит Пасс.

Между тем математики в 1960-х годах определили так называемую сложность Колмогорова, которая относится к количественному определению количества случайности или последовательности чисел. Колмогоровская сложность строки чисел определяется как длина самой короткой компьютерной программы, которая может генерировать строку; для некоторых строк, таких как 121212121212121212121212121212, существует короткая программа, которая генерирует ее – альтернативные 1 и 2. Но для более сложных и явно случайных строк чисел, таких как 37539017332840393452954329, может не существовать программы, которая короче длины самой строки.

Проблема давно интересовала математиков и компьютерщиков, в том числе Юриса Хартманиса, почетного профессора информатики и инженерии. Поскольку компьютерная программа, пытающаяся сгенерировать это число, может занять миллионы или даже миллиарды лет, исследователи в Советском Союзе в 1960-х годах, а также Хартманис и другие в 1980-х годах разработали ограниченную во времени сложность Колмогорова – самую короткую программу, которая может выводить строку чисел за определенное время.

В статье Пасс и аспирант Яньи Лю показали, что если вычисление ограниченной по Колмогорову сложности сложно, то односторонние функции существуют.

Хотя их вывод является теоретическим, он имеет потенциальные последствия для криптографии, включая интернет-безопасность.

«Если вам удастся придумать алгоритм, чтобы решить ограниченную во времени проблему сложности Колмогорова, то вы можете взломать все крипто, все схемы шифрования, все цифровые подписи», – сказал Пасс. «Однако, если не существует эффективного алгоритма для решения этой проблемы, вы можете получить одностороннюю функцию, и, следовательно, вы можете получить безопасное шифрование, цифровые подписи и так далее».

Источник: evo-rus.com

Комментарии: