16.12.13

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 до реального взлома алгоритма пройдет время. Но задуматься стоит в любом случае...

5 коммент.:

StepFor комментирует...

"А что если на секунду представить, что Анатолий Плотников прав?.."

Может быть Анатолий Панюков?

Сергей Борисов комментирует...

А заголовок то какой желтопресный.

Даже если теорию докажут, работы ФСБ только прибавится - разрабатывать новые ГОСТ, новые методики испытаний. С чего бы разгонять?

Алексей Лукацкий комментирует...

Не желтопрессный, а призывный :-) Чтобы задумались, если не думали. Или готовились, если уже готовы :-)

СВП комментирует...

Леша, однако Сергей прав - заголовок крутоват для постинга с новостью про наших и не только
"петриков":-)
Вот тут http://habrahabr.ru/post/206202/
наши физтехи неплохо резвятся...
Вообще-то мне ближе рассуждения о нереальности N=NP с точки зрения физики http://www.scottaaronson.com/papers/npcomplete.pdf , где все довольно внятно и давно показано

Алексей Лукацкий комментирует...

Задача заголовка - лишний раз задуматься "А что если"...