Золотой билет

У каждого из нас есть секреты. Как минимум мы храним в тайне пароли и не желаем, чтобы кто-то читал нашу почту. Если P ≠ NP, то секреты есть и у NP-полных задач: это их решения, найти которые не так-то просто. В 1976 году Уитфилд Диффи и Мартин Хеллман предложили шифровать информацию при помощи класса NP. В истории криптографии, т. е. науки о шифровании, наступил поворотный момент.

Очень краткая история классической криптографии

Шифрование существует столько же, сколько и переписка. Юлий Цезарь пользовался простым подстановочным шифром, в котором каждая буква заменялась на другую букву, отстоящую от нее в алфавите на три позиции.

Фраза The early bird gets the worm («Кто рано встает, тому бог дает») после такой кодировки превращается в Wkh hduob elug jhwv wkh zrup. Способ шифрования, при котором все буквы циклически сдвигаются на определенное число позиций, стали называть шифром Цезаря.

В Древнем Риме этот метод работал хорошо. Зашифрованные сообщения выглядели как случайный набор букв, а люди пока еще не обладали необходимыми навыками для взлома шифров. К IX веку математики разработали методы восстановления исходного сообщения; эти методы учитывали частоту появления букв и анализировали короткие слова. Глядя на фразу Wkh hduob elug jhwv wkh zrup, можно заметить, что буква h встречается четыре раза, т. е. чаще остальных. Самая распространенная буква английского алфавита – это e, ее частота составляет примерно 12 процентов. Вы можете предположить, что буква h кодирует букву e, – и будете совершенно правы. Сочетание wkh встречается дважды; вы уже знаете, что h – это e, поэтому делаете вывод, что wkh – это, наверно, the. Еще чуть-чуть – и исходное сообщение будет восстановлено!

Рис. 8.1. Шифр Цезаря

В XV веке, в эпоху Возрождения, итальянский ученый Леон Баттиста Альберти разработал более сложный метод. Это был шифр многоалфавитной замены, в котором сообщение разбивалось на несколько частей, и для каждой части использовался свой алфавит подстановки. Система Альберти практически не поддавалась взлому вплоть до XIX века, когда на шифры началось систематическое наступление.

Американский писатель и поэт Эдгар Аллан По мастерски владел техникой криптоанализа. В 1839 году он обратился к широкой публике с предложением присылать ему тексты, зашифрованные сложным, не поддающимся взлому шифром, и обещал разгадать их все. Годом позже По опубликовал эссе «Несколько слов о тайнописи», в котором утверждал, что человеческий разум не способен изобрести такой шифр, который разум другого человека был бы не в силах разгадать. В нашумевшем рассказе По «Золотой жук», появившемся в 1843 году, события вертятся вокруг расшифровки тайного сообщения. Это было одно из первых художественных произведений, в котором речь шла о секретных кодах.

В 1903 году выходят «Пляшущие человечки» Конан Дойля, где Шерлок Холмс взламывает подстановочный шифр, состоящий из странных пляшущих фигурок.

Наступила эра механики; люди начали изобретать машины, способные создавать ключи для шифровки и дешифровки. Самая известная шифровальная машина – это, пожалуй, «Энигма», первую версию которой в 1918 году в Германии разработал Артур Шербиус.

В «Энигме» было несколько роторов, искажавших набранные на клавиатуре символы. Роторы вращались в разных режимах, и каждый символ получал свой индивидуальный шифр замены. В результате машина выдавала усложненную версию многоалфавитного шифра Альберти, взломать которую было чрезвычайно трудно.

Рис. 8.2. Пляшущие человечки

Рис. 8.3. Шифровальная машина «Энигма»

У немцев во время Второй мировой большинство сообщений шифровалось при помощи «Энигмы». Незадолго до начала войны Великобритания получила от польской разведки описание машины и некоторых методов дешифровки. Британское правительство запустило засекреченный проект с кодовым названием «Ультра», целью которого был взлом шифров «Энигмы». В штат набирали известных шахматистов, чемпионов по решению кроссвордов и, конечно, талантливых математиков, среди которых был и основоположник теории вычислений Алан Тьюринг. В рамках проекта был спроектирован и построен «Колоссус» – первый в мире программируемый цифровой компьютер. «Именно благодаря проекту „Ультра“ мы выиграли войну», – скажет позже Уинстон Черчилль.

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

Современная криптография

«Мы стоим на пороге криптографической революции» – таковы первые слова нашумевшей статьи Уитфилда Диффи и Мартина Хеллмана, вышедшей в свет еще в 1976 году. «Благодаря развитию массового производства дешевых цифровых устройств криптография освободилась от аппаратных ограничений и перестала испытывать недостаток в вычислительных ресурсах, – продолжают авторы. – Стоимость надежных криптографических систем значительно снизилась; теперь эти системы можно использовать в различных коммерческих приложениях – например, для удаленного управления кэш-диспенсерами и компьютерными терминалами».

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

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

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

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

Основываясь на результатах, полученных ранее Ральфом Мерклом, Диффи и Хеллман предложили обойти эту проблему при помощи так называемых криптосистем с открытым ключом. Компьютер создает два ключа – открытый и закрытый; открытый можно послать кому угодно, а закрытый хранится в тайне и по сети не передается.

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

Допустим, Диффи хочет отправить Хеллману такое сообщение: «Наступление в полночь». Хеллман создает пару ключей; открытый ключ он посылает Диффи и другим заинтересованным участникам, а закрытый держит в тайне. С помощью открытого ключа Диффи зашифровывает сообщение «Наступление в полночь» и отправляет результат Хеллману. Секретный ключ ему знать не нужно, поскольку для шифрования он не используется. Хакер, перехвативший шифровку, не сможет восстановить исходный текст даже в том случае, если знает открытый ключ. А вот Хеллман с помощью закрытого ключа расшифрует сообщение и узнает о том, что наступление начинается в полночь.

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

В 1976 году большинство ученых уже склонялись к тому, что P ≠ NP, а потому системы с открытым ключом имеют право на жизнь. Диффи и Хеллман такую систему предложили, однако более широкое распространение получила криптосистема RSA, которую в 1978 году разработали Рональд Ривест, Ади Шамир и Леонард Адлеман. Система была названа по первым буквам фамилий ее создателей – Rivest, Shamir, Adleman.

В основе алгоритма RSA лежит тот факт, что умножать легко, а раскладывать на множители – очень трудно. Возьмем, к примеру, два достаточно больших простых числа, 5754853343 и 2860486313. Найти их произведение легко: это 16461679220973794359. А вот с обратным процессом все обстоит гораздо сложнее – попробуйте-ка по числу 16461679220973794359 восстановить сомножители 5754853343 и 2860486313! В системе RSA используются громадные простые числа, состоящие, как правило, из нескольких сот цифр. Нельзя утверждать, что разложение на простые множители практически неразрешимо, пока неравенство классов P и NP остается недоказанным; однако по мнению ученых задача эта представляет огромную вычислительную трудность.

За свое изобретение Ривест, Шамир и Адлеман в 2002 году получили премию Тьюринга.

Удивительный факт: позднее выяснилось, что впервые подобную криптосистему описал в 1973 году Клиффорд Кокс, работавший в то время в Центре правительственной связи Великобритании. Эта информация была обнародована лишь в 1997 году.

С системой RSA вы наверняка неоднократно сталкиваетесь каждый день. Возьмем для примера какой-нибудь часто посещаемый веб-сайт (в вашем браузере он может отображаться немного по-другому).

Рис. 8.4. Верхняя часть страницы Facebook

Обратите внимание на букву s в адресной строке и на замочек.

Рис. 8.5. Верхняя часть страницы Facebook с отметками

Буква s указывает на безопасное соединение (от англ. secure). Facebook опубликовал свой открытый ключ; этим ключом браузер шифрует ваш пароль. Злоумышленник с ноутбуком, расположившийся в другом углу кофейни, не сможет взломать пароль, даже если будет перехватывать все передаваемые по Wi-Fi данные, а вот Facebook легко восстановит его с помощью закрытого ключа. Аналогичным образом ваш браузер при необходимости создаст пару ключей и сообщит открытый ключ Facebook, а тот в ответ пришлет вам зашифрованную информацию об обновленных статусах ваших друзей, которую больше никто, кроме вас, не увидит.

Криптография в совершенном мире

Что станет с криптографией в совершенном мире? В мире из второй главы, где P = NP? Определить, что число 16461679220973794359 представляется в виде 5754853343 × 2860486313, а числа 5754853343 и 2860486313 – простые, не составит особого труда; подобные вычисления можно будет проделывать с числами из тысяч и даже миллионов цифр! Задача разложения на множители лежит в классе NP, поскольку потенциальное решение можно проверить очень быстро; если классы P и NP совпадают, то для этой задачи существует эффективный алгоритм, а значит, мы легко отыщем все делители любого, сколь угодно большого числа. Протокол RSA, как и любая другая система шифрования с открытым ключом, станет абсолютно бесполезен, поскольку закрытый ключ будет быстро восстанавливаться по открытому ключу. Равенство P и NP приведет к тому, что мы больше не сможем обмениваться секретной информацией, не условившись предварительно о способе ее передачи.

Так, значит, в совершенном мире о криптографии придется забыть? Вообще-то есть один шифр, надежность которого не зависит от отношений между P и NP: это так называемый одноразовый шифровальный блокнот. Предположим, Элис придумала пароль из 12 символов: FIDDLESTICKS. Шифровальный ключ – он же блокнот – представляет собой случайную последовательность символов той же длины: JXORMQNAMRHC. Возьмем первые символы пароля и ключа, F и J. Это шестая и десятая буквы алфавита, соответственно. В сумме их номера дают число 16, поэтому первым символом шифрованного текста будет шестнадцатая буква алфавита – P. Теперь возьмем вторые символы пароля и ключа, I и X. Это девятая и двадцать шестая буквы алфавита. В сумме их номера дают 33, однако тридцать третьей буквы алфавита в английском языке не существует, поэтому мы вычитаем из числа 33 количество букв в алфавите, т. е. 26. Получается 7, а значит, вторым символом шифровки будет седьмая буква алфавита – G. Действуя аналогичным образом, мы в итоге получим PGSVYVGUVUSV. Эту криптограмму Элис отошлет на Facebook, а он расшифрует ее с помощью точно такого же блокнота, выполняя вычитание вместо сложения.

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

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

Рис. 8.6. Судоку с нулевым разглашением

Равенство P = NP многое упрощает, однако криптографам оно может принести лишь головную боль.

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

Судоку с нулевым разглашением

Боб пожертвовал обедом, чтобы добить судоку из последнего номера газеты.

«У них тут ошибка. Это решить невозможно!» – восклицает он, совершенно выбившись из сил. На крики приходит его коллега Элис; взглянув на судоку, она видит ту самую головоломку, которую утром решила в метро. Боб зря ругается. На рисунке ниже вы видите решение Элис.

Боб вот-вот сдастся, и Элис хочется его поддержать. Она говорит, что решила задачу, но он ей, конечно, не верит. Он ужасно расстроится, когда увидит в завтрашней газете ответ, так что нужно обязательно убедить его подумать еще. Показать свое решение значит испортить Бобу все удовольствие от процесса; но как доказать, что задача решается, не давая при этом никаких подсказок?

Рис. 8.7. Решение судоку с нулевым разглашением

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

Вернувшись к своему столу и зная, что Боб не может видеть ее за перегородкой, Элис берет цифры от 1 до 9 и случайным образом их упорядочивает.

Рис. 8.8. Новый порядок цифр

С помощью полученной таблицы Элис шифрует свое решение, заменяя 1 на 2, 9 на 3, и т. д., и рисует его на большом листе бумаги. Вот что у нее выходит:

Рис. 8.9. Зашифрованное решение

Дальше Элис аккуратно режет сетку с решением на маленькие квадратики по одной цифре в каждом. Всего квадратиков получается 81. Каждый квадратик она прячет в маленький пакетик и кладет в соответствующую ячейку нарисованной на другом листе пустой сетки.

Рис. 8.10. Решение спрятано

Рис. 8.11. Открытая строка

В левом верхнем пакетике лежит цифра 2, справа от него – цифра 3, и так далее.

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

• открыть все пакетики в одной из строк;

• открыть все пакетики в одном из столбцов;

• открыть все пакетики в одном из девяти блоков 3 × 3;

• открыть все пакетики, расположенные на тех же позициях, что и заданные цифры исходной головоломки.

Допустим, Боб решил открыть третью строку. Что он там увидит?

Если бы в строке оказалось две одинаковых цифры, это означало бы, что Элис наврала. Но поскольку решение у нее действительно есть, и она четко объяснила Бобу, что сделала с пакетиками, Боб видит все различные цифры от 1 до 9 в случайном порядке. Тест пройден!

Если Боб решит открыть столбец или блок 3 × 3, результат будет точно таким же.

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

Рис. 8.12. Открытые позиции соответствуют заданным цифрам

Рис. 8.13. Новый порядок цифр

Это единственный случай, когда Боб получает от Элис еще и таблицу кодировки, при помощи которой он проверит, соответствуют ли открытые цифры тем, что были указаны в задаче изначально. Например, согласно схеме, цифра 9 должна была превратиться в цифру 3… так и есть!

Если Элис и правда решила задачу и четко следовала правилам, она пройдет любую проверку. А что же Боб? Получит ли он хоть какую-нибудь подсказку, когда откроет строку, столбец или блок 3 × 3? Исключено: перед ним будут лишь цифры от 1 до 9, расположенные в случайном порядке.

Последний вариант даст ему перестановку цифр, при помощи которой было зашифровано решение. Но что он при этом узнает? Ничего.

Другое дело, если Элис наврала: один из тестов обязательно провалится, и она ничего не сможет с этим поделать. Когда Боб выбирает тест наугад, вероятность попасться на вранье составляет одну двадцать восьмую, или примерно 3,57 %. Не так уж и рискованно, правда? Однако если Элис и Боб проведут 83 эксперимента подряд и при этом будут каждый раз менять схему кодировки, вероятность провалить один из тестов возрастет до 95 %.

Боб убедился, что Элис действительно решила судоку, а ей при этом удалось соблюсти принцип «нулевого разглашения»: о решении Боб знает только то, что оно существует. Эта мысль будет греть его, когда он вернется к головоломке, но справляться ему придется исключительно своими силами.

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

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

В четвертой главе мы уже упоминали, что решение судоку – задача NP-полная. А раз к судоку сводится любая задача из NP, то и описанный выше метод доказательства с нулевым разглашением также годится для любой NP-задачи. Элис сможет убедить Боба в том, что она нашла максимальную клику, раскрасила карту в три цвета или составила маршрут для коммивояжера, не раскрывая при этом никакой дополнительной информации; о решении Боб будет знать только то, что оно существует.

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

Криптография в играх

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

Все бы хорошо, но что, если Боб и Элис говорят по телефону или переписываются по почте? Боб может соврать и сказать, что выпала решка, когда на самом деле выпал орел. А может и вообще монетку не бросать. Как убедиться, что он говорит правду?

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

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

Элис выбирает «чет» или «нечет» и сообщает об этом Бобу. В ответ он отправляет ей секретный ключ. Расшифровав криптограмму, Элис узнает, что Боб загадал 69441251920931124. Если она выбрала «чет», то выиграла, а если «нечет» – выиграл Боб.

Давайте разберемся, почему эта схема работает. Боб выбирает число еще до того, как Элис делает ставку. Но когда она загадывает «чет» или «нечет», то не знает, что он выбрал 69441251920931124. У нее есть лишь криптограмма, и если она не умеет взламывать шифры, то не получит никакой информации об этом числе. Все, что она может сделать, – это положиться на интуицию. Боб не станет менять свое число, поскольку уже отправил Элис криптограмму. Теперь ему остается лишь сообщить ей секретный ключ, чтобы она увидела, какое число он выбрал. Когда ставки делаются без всякой системы, каждый игрок выигрывает в половине случаев. Надежность шифров с открытым ключом исключает возможность обмана.

Бросать монетку – это как-то слишком просто. Что, если взять какую-нибудь более сложную игру?

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

Как насчет игры в кости, нарды или «Монополию»? Поверит ли Элис, что Боб не врет насчет выпавших очков? Безусловно – для этого лишь нужно будет утвердить протокол бросания костей, во многом совпадающий с протоколом бросания монетки.

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

В интернете сейчас очень много покерных сайтов, однако все они играют роль ведущего, так как сами тасуют карты и раздают их игрокам.

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

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

Облако секретных вычислений

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

В этом случае помогут системы, называемые полностью гомоморфными. Протокол RSA устроен таким образом, что, умножив шифр одного числа (к примеру, числа 28) на шифр другого (к примеру, 45), мы в итоге получим шифр их произведения (т. е. числа 1260). Умножение чисел можно проводить без расшифровки, и исходные данные при этом знать не обязательно. Для сложения, однако, это правило не действует, и по кодам чисел 28 и 45 код числа 73 в системе RSA не получишь.

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

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

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

В поисках случайности

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

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

Какова оптимальная стратегия в этой игре? Хорошо, если вы можете предсказать выбор противника; но что, если все наоборот, и противник знает ход ваших рассуждений? Неужели вы обречены на вечный проигрыш?

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

Рис. 8.14. «Камень, ножницы, бумага»

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

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

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

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

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

Генераторы псевдослучайных чисел спасают нас лишь до тех пор, пока существуют относительно трудные задачи. Если P = NP, то любой вычислительный процесс можно в той или иной степени инвертировать. В совершенном мире будет чрезвычайно трудно – а то и вовсе нереально – программно реализовать полностью случайное подбрасывание монетки. А компьютерный вариант «Камня, ножниц и бумаги» вряд ли сможет называться азартным.

Проблемы разрастаются

Шифрование с открытым ключом базируется на «неприступности» таких NP-задач, как разложение на множители. Достаточно случайным образом выбрать два больших простых числа и перемножить их – и вы получите число, которое никто, кроме вас, на множители, скорее всего, не разложит.

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

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

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

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

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

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