15 Декабря, 2013

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

CAPTCHA
16 Декабря, 2013
"Большинство ученых считает, что эти классы неравны и именно на этом "неравенстве" и построены многие современные асимметричные криптографические алгоритмы, относимые к классу NP." "Анатолий Плотников опубликовал свой вариант доказательства, правда, с точностью до наоборот. Он доказал, что эти классы неравны." Так что же доказал Анатолий Плотников???
0 |
  • Поделиться
  • Ссылка
16 Декабря, 2013
"уральский ученый Анатолий Панюков доказал равенство классов P и NP" "луганский кандидат технических наук Анатолий Плотников опубликовал свой вариант доказательства, правда, с точностью до наоборот. Он доказал, что эти классы неравны."
0 |