Max Home IndustryЕсть ли небьющийся код?
Этот вопрос был центральным для криптографии на протяжении тысячелетий и лежит в основе усилий по защите частной информации в Интернете. В новой статье исследователи Cornell Tech определили проблему, которая является ключом к тому, можно ли взломать все шифрование, а также удивительную связь с математической концепцией, направленной на определение и измерение случайности.
«Наш результат не только показывает, что криптография имеет естественную« материнскую »проблему, но также показывает глубокую связь между двумя совершенно разными областями математики и информатики — криптографией и алгоритмической теорией информации», — сказал Рафаэль Пасс, профессор информатика в Cornell Tech.
Пасс является соавтором книги «Об односторонних функциях и сложности Колмогорова», которая будет представлена на симпозиуме IEEE по основам информатики, который состоится 16-19 ноября в Дареме, Северная Каролина.
«В результате, — сказал он, — естественная вычислительная проблема, возникшая в 1960-х годах в Советском Союзе, характеризует осуществимость базовой криптографии — например, шифрования с закрытым ключом, цифровых подписей и аутентификации».
На протяжении тысячелетий криптография считалась циклом: кто-то изобрел код, код был эффективен, пока кто-то в конце концов его не сломал, и код стал неэффективным. В 1970-х годах исследователи, ищущие более совершенную теорию криптографии, представили концепцию односторонней функции — легкой задачи или проблемы в одном направлении, которые невозможны в другом.
Например, легко зажечь спичку, но невозможно вернуть горящую спичку в ее незажженное состояние, не переставляя ее атомы — чрезвычайно сложная задача.
«Идея заключалась в том, что если у нас будет такая односторонняя функция, возможно, это будет очень хорошей отправной точкой для понимания криптографии», — сказал Пасс. «Зашифровать сообщение очень просто. И если у вас есть ключ, вы также можете его расшифровать. Но тот, кто не знает ключа, должен будет сделать то же самое, что и восстановить зажженную спичку».
Но исследователям не удалось доказать существование односторонней функции. Самый известный кандидат, который также является основой наиболее часто используемых схем шифрования в Интернете, полагается на целочисленную факторизацию. Легко перемножить два случайных простых числа — например, 23 и 47, — но значительно сложнее найти эти два множителя, если учесть их произведение — 1081.
Считается, что не существует эффективного алгоритма факторинга для больших чисел, сказал Пасс, хотя исследователи, возможно, еще не нашли подходящие алгоритмы.
«Главный вопрос, который мы решаем: существует ли он? Существует ли какая-то естественная проблема, которая характеризует существование односторонних функций?» он сказал. «Если это так, это мать всех проблем, и если у вас есть способ решить эту проблему, вы можете сломать все предполагаемые односторонние функции. И если вы не знаете, как решить эту проблему, вы действительно можете получить безопасная криптография. «
Между тем математики в 1960-х годах определили так называемую сложность Колмогорова, которая относится к количественной оценке количества случайности или шаблона строки чисел. Колмогоровская сложность строки чисел определяется как длина самой короткой компьютерной программы, которая может генерировать строку; для некоторых строк, таких как 121212121212121212121212121212, есть короткая программа, которая их генерирует — чередующиеся 1 и 2. Но для более сложных и явно случайных строк чисел, таких как 37539017332840393452954329, может не существовать программа, длина которой короче самой строки.
Эта проблема давно интересовала математиков и компьютерных ученых, в том числе Юриса Хартманиса, заслуженного профессора информатики и инженерии. Поскольку компьютерная программа, пытающаяся вычислить число, могла занять миллионы или даже миллиарды лет, исследователи в Советском Союзе в 1960-х, а также Хартманис и другие в 1980-х разработали ограниченную по времени сложность Колмогорова — длину самая короткая программа, которая может выводить строку чисел за определенное время.
В своей статье Пасс и докторант Яни Лю показали, что если вычислить ограниченную по времени сложность Колмогорова сложно, то существуют односторонние функции.
Хотя их вывод является теоретическим, он имеет потенциальное значение для криптографии, включая безопасность в Интернете.
«Если вы можете придумать алгоритм для решения ограниченной по времени проблемы сложности Колмогорова, то вы сможете взломать всю криптографию, все схемы шифрования, все цифровые подписи», — сказал Пасс. «Однако, если не существует эффективного алгоритма для решения этой проблемы, вы можете получить одностороннюю функцию, и, следовательно, вы можете получить безопасное шифрование, цифровые подписи и т. Д.»
Исследование частично финансировалось Национальным научным фондом и Управлением научных исследований ВВС США и основывалось на исследованиях, финансируемых Отделом перспективных исследовательских проектов в Управлении национальной разведки.