Криптографы хотят знать, в каком из пяти возможных миров мы живем, что покажет, возможна ли вообще по-настоящему безопасная криптография.

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

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

Чтобы создать действительно безопасный (и постоянный) метод шифрования, нам нужна вычислительная задача, которая достаточно сложна, чтобы создать доказуемо непреодолимый барьер для злоумышленников. Мы знаем о многих вычислительных задачах, которые кажутся сложными, но, возможно, мы просто недостаточно умны, чтобы решить их. Или, может быть, некоторые из них сложны, но их сложность не позволяет использовать их в безопасном шифровании. По сути, криптографы задаются вопросом: достаточно ли сложности во Вселенной, чтобы сделать криптографию возможной?

В 1995 году Рассел Импальяццо из Калифорнийского университета в Сан-Диего разбил вопрос о сложности на набор подвопросов, которые специалисты по информатике могли решать по одному за раз. Чтобы обобщить состояние знаний в этой области, он описал пять возможных миров – причудливо названных Алгоритмика, Эвристика, Пессиландия, Миникрипт и Криптомания – с возрастающими уровнями сложности и криптографической возможности. Любой из них может быть миром, в котором мы живем.

Алгоритмика

В этом мире самые естественные вычислительные вопросы решаются легко, что делает криптографию невозможной. Здесь набор проблем с эффективными решениями – набор под названием P – содержит не только проблемы, которые мы уже придумали, как решить. Он также включает в себя все задачи из иного набора, называемого NP, который состоит из задач, для которых легко проверить предложенное решение.

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

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

В Алгоритмике P и NP — это один и тот же набор задач. Доказательство этого было бы великолепной новостью, поскольку это означало бы, что существуют быстрые алгоритмы для таких вещей, как упаковка чемодана и всех иных, казалось бы, сложных задач в NP. Но это было бы катастрофой для криптографов, поскольку одна из проблем, которую мы могли бы эффективно решить, – это расшифровка.

Большинство учёных считают, что P отличается от NP по той простой причине, что в NP так много проблем, которые мы не можем эффективно решить. Но никому так и не удалось доказать (или опровергнуть) это, хотя вопрос «P против NP» считается самой известной проблемой в теоретической информатике на протяжении пяти десятилетий. С иной стороны, Юваль Ишай из Техниона в Хайфе, Израиль, сказал, – «помимо постоянных неудач самых умных людей, у нас нет доказательств того, что трудно показать, что P не равно NP».

Эвристика

В этом мире есть проблемы в NP, которые нелегко решить, но каждая проблема в NP является легкой «в среднем», что означает, что в большинстве случаев ее можно решить эффективно. Например, если мы находимся в Эвристике, то существует эффективный алгоритм упаковки чемоданов, который почти всегда срабатывает, но может дать сбой для нескольких редких комбинаций чемоданов и вещей, которые необходимо упаковать. (Эти быстрые и обычно успешные алгоритмы обычно называют «эвристиками».)

С точки зрения криптографии большой разницы между Эвристикой и Алгоритмикой нет. Если мы придумаем схему шифрования в Эвристике, можно изобрести какой-то быстрый метод расшифровки, который сможет обработать почти каждое сообщение, что сделает схему бесполезной для практических целей.

Пессиландия

Это худший из всех возможных миров. В Пессиландии некоторые задачи в NP сложны даже в среднем. Для этих задач любой эффективный алгоритм будет давать сбой не только время от времени, но и часто. Тем не менее, эти сложные проблемы не из тех, которые полезны в целях сокрытия секретной информации.

«Мы точно не хотим жить в Пессиландии», – сказал Эрик Аллендер из Университета Ратгерса. «Здесь мы получаем все плохие аспекты вычислительной сложности, но без каких-либо преимуществ, таких как криптография».

Миникрипт

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

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

Криптомания

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

Исключая миры

По словам Ишай, большинство криптографов считают, что по крайней мере какая-то криптография существует, поэтому мы, вероятно, живем в криптомании или миникрипте. Но они не ждут доказательств этого в ближайшее время. Такое доказательство потребовало бы исключения трех иных миров, а исключение лишь Алгоритмики уже требует решения проблемы «P против NP», над которой учёные бьются десятилетиями.

Однако недавно Пасс и его аспирант Яньи Лю нашли новый подход к изучению этих миров. Впервые они определили естественную проблему – названную колмогоровской сложностью с ограничением по времени, или сокращенно Kt, – уровень сложности которой создаёт яркую разделительную линию между мирами, включающими криптографию, и мирами, в которые она не входит. Если Kt в среднем проста, как показали Лю и Пасс, то безопасная криптография не может существовать, поэтому мы находимся в Алгоритмике, Эвристике или Пессиландии. Но если Kt в среднем сложна, то мы можем создавать односторонние функции, так что мы как минимум в Миникрипте, а возможно и в Криптомании.  

Этот новый результат означает, что учёные могут исключить Пессиландию – худший из миров – если они смогут доказать ещё одно утверждение: если Kt в среднем легка, то такова и любая задача в NP. В этом случае мы сузим список до миров, где Kt в среднем сложна (Миникрипт и Криптомания), и тех, где Kt – и любая другая проблема в NP — в среднем легка (Алгоритмика и Эвристика).

По словам Райана Уильямса из Массачусетского Технологического Института, учёные уже какое-то время пытаются разобраться в Пессиландии. «Я думаю, что все согласны с тем, что Пессиландию можно исключить, но через какое время мы это сделаем, я не знаю».

Криптографы также хотели бы исключить Эвристику, что потребовало бы доказательства того, что если Kt в среднем проста, то каждая проблема в NP проста во всех случаях (не только в среднем). Исключение этих двух миров означало бы, что мы либо живём в Алгоритмике, где всё всегда просто, либо у нас достаточно сложности для базовой криптографии.

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

Автор перевода @arielf


НЛО прилетело и оставило здесь промокод для читателей нашего блога:

— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.

Комментарии (10)


  1. pohjalainen
    12.07.2022 11:52
    +4

    Занятная концепция, спасибо.

    ИМХО во введении надо бы упомянуть, что все сказанное в статье относится к асимметричной криптографии - ведь в симметричном случае у нас есть абсолютно стойкий по Шеннону одноразовый шифрблокнот :)


    1. eimrine
      12.07.2022 12:51

      Криптография — не только симметричное/асимметричное шифрование. Насколько я знаю (не профессионал), современная криптография крутится вокруг криптографических хэш-функций.


      1. garwall
        12.07.2022 15:45
        +1

        хэш-функкции - это все-таки необратимое шифрование, исходный текст после применения не восстановить (достоверно - см. коллизии и за разумное время), и эрго, область их применения достаточно узка и специфична.


        1. alff31
          12.07.2022 18:14
          -2

          На хешах вся криптовалюта построена, не совсем уж узкая область


        1. eimrine
          12.07.2022 21:20

          область их применения достаточно узка и специфична.
          • Проверка целостности и/или идентичности данных
          • Диффи-Хеллман (https)
          • Хранение паролей без риска утечки
          • Цифровые подписи
          • Hashmap (то что в JS называется объект)
          • Продвинутые алгоритмы (bloom filter, cuckoo hashing, merkle tree).


          1. pohjalainen
            12.07.2022 21:32
            +2

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

            За Диффи-Хеллмана поясните?

            В hashmap и Bloom filter криптостойкие хэш-функции не нужны, как правило. Для контроля целостности - тоже (lможно взять хоть поломанную MD5, да хоть CRC32). Это общий computer science, не специфично для криптографии.


            1. eimrine
              12.07.2022 21:46

              Ошибаетесь. Хэш-функция — это не способ шифрования.
              Вы это писали не мне, но я тоже удивился с такой формулировки. Впрочим, судя по результатам гугления, может быть в русскоязычной среде термин «безвозвратное шифрование» более-менее устоявшийся, хотя лично я предпочитаю англоязычный термин «дайджест».

              За Диффи-Хеллмана поясните?
              Задача: обеспечить безопасный канал в небезопасной среде.

              Решение (упрощённо): Алиса и Боб генерят хэши к ограниченному набору данных (ограничение для того чтобы не затягивать процесс) и обмениваются этими хэшами по установленной процедуре. После первого совпадения хэшей у них обоих есть секрет который не был отправлен по незащищенному каналу. Этот секрет будет ключём от симметричного шифрования.

              upd:
              В hashmap и Bloom filter криптостойкие хэш-функции не нужны, как правило.
              Не криптостойкие, а криптографические и нужны, чтобы не было простых коллизий (требуется лавинообразный эффект).

              Для контроля целостности — тоже (lможно взять хоть поломанную MD5, да хоть CRC32).
              Если ваша задача не предусматривает защиту от подмены то можно MD5. Что касается CRC, у меня когда-то была очень редкая ситуация когда у двух разных файлов был одинаковый CRC (жаль молод был, не понимал что нужно сохранить скриншот на память), с тех пор лично я не пользуюсь этим алгоритмом из принципа.


              1. alexeibs
                13.07.2022 13:40

                Ни для хэшмап, ни для блумфильтра криптографические хэш-функции не являются необходимостью, и на практике обычно не используются из-за относительно высокой стоимости вычисления. Если завтра вдруг выяснится, что P = NP (т.е. мы живем в Алгоритмике), то хэшмапы и блумфильтры никуда не денутся. Так же как и чексуммы. То, что вы когда-то увидели 2 разных файла с одинаковым CRC32, большой проблемой не является. Вопрос - насколько эти файлы различались между собой, т.к. чексуммы используют для защиты от хардварных сбоев. Защита от подмены файла - это из области криптографии.


              1. pohjalainen
                14.07.2022 12:28

                термин «безвозвратное шифрование» более-менее устоявшийся

                Да такого термина вообще нет ввиду бессмысленности. Есть строгое определение шифрования как обратимого процесса.

                Задача: обеспечить безопасный канал в небезопасной среде.

                Решение (упрощённо): Алиса и Боб генерят хэши к ограниченному набору данных (ограничение для того чтобы не затягивать процесс) и обмениваются этими хэшами по установленной процедуре. После первого совпадения хэшей у них обоих есть секрет который не был отправлен по незащищенному каналу. Этот секрет будет ключём от симметричного шифрования.

                То есть и ДО совпадения ключей у Алисы и Боба был некий набор заранее распределенных общих данных? Зачем огород с хэшами городить, когда можно просто использовать эти данные как ключ? Диффи-Хеллман тем и хорош, что позволяет организовать защиту при полном отсутствии заранее разделенного секрета.

                Не криптостойкие, а криптографические и нужны, чтобы не было простых коллизий

                Ну например, функцию hash() из кишков Python никак нельзя назвать ни криптографической, ни стойкой, но она прекрасно решает задачу реализации словаря.


          1. garwall
            12.07.2022 22:22

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

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