8-й Центр могут разогнать из-за челябинского математика?!

Пришла тут новость из Челябинска — уральский ученый Анатолий Панюков доказал равенство классов P и NP (одна из семи математических проблем тысячелетия по версии Институт Клея). И новость эта имеет прямое отношение к современной криптографии, которая исходит из применения асимметричной криптографии для передачи криптографического ключа. Большинство ученых считает, что эти классы неравны и именно на этом «неравенстве» и построены многие современные асимметричные криптографические алгоритмы, относимые к классу NP.

В 2012-м году луганский кандидат технических наук Анатолий Плотников опубликовал свой вариант доказательства, правда, с точностью до наоборот. Он доказал, что эти классы неравны. Свое доказательство он вроде как отправил в Институт Клея на проверку, но на сайте Института до сих пор висит надпись, что проблема равенства/неравенства классов P и NP не решена (в 2010-м году такую попытку предпринял сотрудник HP Виней Деолаликар, но потом оказалось, что в его доказательстве есть ошибки). Доказательству челябинского математика еще только предстоит проверка и вполне может оказаться так, что 30 лет его исследований тоже ошибочны. Я сейчас не готов обсуждать правоту нашего соотечественника; можно сказать точно, что он пополнит список из 100 с лишним «доказательств» равенства/неравенства классов P и NP. Меня в этой истории заинтересовало совсем другое.

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

Но даже в случае с шифром Вернама встанет вопрос — как мы будем обмениваться криптографическими ключами? Асимметрия нам не сильно поможет, так как ее надежность будет поставлена под сомнение доказательством классов P и NP. И сейчас-то регулярно всплывает вопрос о необходимости пересмотра безопасной длины ключей (за последние 30 лет «безопасная» длина ключа для симметричной криптографии увеличилась все вдвое, а для асимметричной уже в 10 раз). Схемы с разделением секрета могли бы помочь, но тоже не все, а только те, которые не рассчитаны на неравенство классов P и NP.

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

Собственно к чему эта заметка, если даже еще не понятно, а действительно ли челябинский математик нашел доказательство проблемы тысячелетия? А к тому она, чтобы задаться вопросом: «А что если?» Есть ли у нас (у криптографов, у регулятора, у производителей, у потребителей) резервный план на случай доказательства P=NP? Что мы будет делать, если это действительно так и такое доказательство найдет практическое применение в криптографии? У меня ответа пока нет…

PS. Симметричная криптография не умрет. И некоторая эллиптика тоже. Вот только с «традиционной» асимметричной криптографией (RSA и иже с ним) будут сложности. Разумеется, от доказательства P = NP до реального взлома алгоритма пройдет время. Но задуматься стоит в любом случае…