Золотой билет. P, NP и границы возможного - Лэнс Фортноу Страница 29

Том отправился в ресторан, чтобы сообщить плохие новости. Это был его первый провал: до сих пор ему всегда удавалось помочь Джейн с рецептом. «Мы можем хоть немного изменить условия задачи? Требования ко вкусу, например? – поинтересовался он. – Иначе никакого соуса не будет». В ответ Джейн заявила, что ничего менять нельзя и что вкус и консистенция должны быть в точности такими, как она просила, – в противном случае блюдо будет безнадежно испорчено. «А как насчет самой запеканки?» – осенило Тома.

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

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

Смарт-карта – это примерно то же, что кредитка с чипом. Там есть микропроцессор и память, которая хранит секретный код. Смарт-карты можно применять для идентификации личности; на них также можно класть деньги, чтобы совершать покупки в магазине или, к примеру, платить за парковку, не устанавливая при этом соединение с сервером. Даже если данные, отправленные или полученные картой, будут перехвачены, расшифровать их без знания секретного кода вряд ли удастся.

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

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

А нестандартное поведение – это как раз то, что требуется Томасу: он не сможет подобрать секретный код, если карта работает как надо. Поврежденная (в меру) карта продолжает реагировать на запросы, вот только реакции ее уже могут быть не те, что прежде.

Поведение испорченной карты по-прежнему зависит от секретного ключа – но уже не так, как задумали разработчики, стремившиеся усложнить подбор ключа по максимуму. Теперь у Томаса есть шанс, и в надежде подобрать секретный ключ он будет применять все известные ему алгоритмы.

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

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