Поразительно, если подумать, что такая фундаментальная идея была высказана только в 1970-е гг. Физики уже причесывали Стандартную модель элементарных частиц, а криптографы все еще топтались на месте где-то на уровне Коперника!
Итак, как же возникла криптография с открытым ключом? Первыми изобретателями — или, скорее, первооткрывателями — были Эллис, Кокс и Уильямсон, работавшие в GCHQ (британский аналог американского Агентства национальной безопасности АНБ/NSA) в начале 1970-х гг. Разумеется, они не могли опубликовать результаты своей работы, и сегодня мало кто их знает! Пусть это будет для вас уроком.
Первой открытой криптосистемой с открытым ключом стала в 1976 г. система Диффи и Хеллмана. Парой лет позже Ривест, Шамир и Адлеман открыли знаменитую систему RSA, названную по их инициалам. А кто-нибудь из вас знает, как RSA была впервые представлена миру? Верно: как головоломка в колонке Мартина Гарднера[49] в Scientific American, посвященной математическим играм!
По сравнению с системой Диффи — Хеллмана RSA имеет несколько преимуществ: к примеру, в ней только одна сторона, а не обе, должна генерировать открытый ключ, и она позволяет пользователям, помимо приватного общения, удостоверять себя. Но если вы прочтете статью Диффи и Хеллмана[50], то заметите, что там присутствуют практически все основные идеи.
Во всяком случае, сердцем любой криптосистемы с открытым ключом является так называемая односторонняя функция с потайным входом, или «лазейкой». Это такая функция, которая
1. Легко вычисляется,
2. С трудом инвертируется и
3. Легко инвертируется при наличии некоторой секретной информации, то есть «лазейки».
Первые два требования, по существу, совпадают с требованиями к обычным односторонним функциям. Третье требование — что OWF должна иметь «лазейку», которая сильно упрощает задачу обращения функции, — является новым. Для сравнения обратите внимание, что существование обычных односторонних функций подразумевает существование надежных криптосистем с закрытым ключом, тогда как существование односторонних функций с лазейкой подразумевает существование надежных криптосистем с открытым ключом.
Итак, что может послужить реальным примером криптосистемы с открытым ключом? Ну, большинство из вас в какой-то момент вашей математической жизни встречали RSA, поэтому я опишу его лишь кратко.
Предположим, что вы хотите передать номер своей кредитной карты на Amazon.com. Как это происходит? Сначала, Amazon случайным образом выбирает два больших простых числа p и q (это можно сделать за полиномиальное время) с формальным ограничением, что p — 1 и q — 1 не должны делиться на 3. (Причину такого ограничения мы увидим позже.) Затем Amazon вычисляет произведение N = pq и публикует его в открытом доступе для всех желающих, сохраняя при этом сами p и q в строгом секрете.
Предположим без потери общности, что номер вашей кредитки зашифрован в виде положительного целого числа x, которое меньше N, но не слишком намного меньше. После этого что вы делаете? Очень просто: вы вычисляете x³ mod N и высылаете результат на Amazon! Если какой-нибудь мошенник умудрится перехватить в пути ваше сообщение, ему придется восстанавливать x, зная только x³ mod N. Но вычисление кубических корней по модулю составного числа считается чрезвычайно трудной задачей, по крайней мере для классических компьютеров! Если p и q достаточно велики (скажем, по 10 000 знаков каждое), то мы можем надеяться, что любому классическому злоумышленнику, перехватившему сообщение, на поиск x потребуются миллионы лет.
Это оставляет очевидный вопрос: как сам Amazon восстанавливает x? Раз плюнуть — с использованием p и q! Наш друг мистер Эйлер еще в 1761 г. сообщил, что последовательность
x mod N, x ² mod N, x ³ mod N , …
повторяется с периодом (p — 1) (q — 1). Так что, если Amazon в состоянии найти целое число k, такое, что
3k= 1 mod (p — 1) (q — 1),
то в результате он получит
(x³)kmodN=x3kmodN=xmodN.
Далее, мы знаем, что такое k существует, по нашему предварительному условию, что p — 1 и q — 1 не делится на 3. Более того, Amazon может найти такое k за полиномиальное время при помощи алгоритма Евклида (известного очень-очень давно, примерно с 300 г. до н. э.) Наконец, имея x³ mod N, Amazon может вычислить (x³)k за полиномиальное время при помощи простого фокуса с последовательным возведением в квадрат. Вот вам RSA.
Чтобы сделать все как можно конкретнее и примитивнее, я предположил, что x всегда возводится в третью степень. Получающаяся в результате криптосистема — ни в коей мере не игрушка: насколько можно судить, она надежна! Однако на практике пользователи могут возводить (и возводят) x в произвольную степень. И еще одно замечание: возведение x не в куб, а в квадрат извлекло бы на свет божий новый клубок проблем, поскольку любое ненулевое число, имеющее квадратный корень по модулю N, имеет не один такой корень.
Конечно, если бы мошенник мог разложить N на произведение pq, он мог бы применить тот же алгоритм расшифровки, какой применяет и Amazon, и восстановить таким образом послание x. Так что вся схема шифрования опирается на предположение о том, что разложение на простые множители — трудная задача! Из этого немедленно следует, что мошенник с квантовым компьютером смог бы без особого труда взломать шифр RSA. Однако среди классических механизмов самый известный алгоритм разложения на простые множители — это метод решета числового поля, требующий примерно шагов.
В скобочках отметим, что никто еще не доказал, что взлом шифра RSA требует разложения на простые множители, возможно, существует более прямой путь к восстановлению послания x — путь, не требующий знания p и q. С другой стороны, в 1979 г. Рабин открыл вариант RSA, для которого доказано, что расшифровка исходного текста столь же трудна, как и разложение на простые множители.
Заметим, однако, что все эти разговоры о криптосистемах, основанных на разложении больших чисел на простые множители и модульной арифметике, отдают прошлым веком! Сегодня мы понимаем, что стоит нам построить квантовый компьютер, и алгоритм Шора (речь о нем пойдет в главе 10) без труда взломает все эти вещи. Разумеется, специалисты по теоретической информатике не обошли вниманием этот факт; многие из них уже занимаются поиском односторонних функций с лазейками, которые могут оказаться надежными даже при наличии квантовых компьютеров. В настоящее время наши лучшие кандидаты на эту роль основаны на задачах с решетками, таких как уже описанная задача нахождения кратчайшего вектора. Если разложение на простые множители сводится к задаче о абелевой скрытой подгруппе, решаемой за квантовое полиномиальное время, то задача нахождения кратчайшего вектора, насколько известно, сводится только к задаче о диэдральной скрытой подгруппе, для которой не удалось установить, что она решаема за полиномиальное время, несмотря на более чем десятилетние усилия.
Вдохновленный этим наблюдением и опираясь на более ранние работы Айтаи и Дворка, Одед Регев предложил[51] криптосистемы с открытым ключом, доказуемо надежные в ситуации с наличием квантового противника, если считать, что задача нахождения кратчайшего вектора трудна для квантовых компьютеров. Стоит отметить, что сами по себе его криптосистемы являются чисто классическими. С другой стороны, даже если бы вам нужна была надежность в отношении классического противника, вам все равно пришлось бы считать, что задача нахождения кратчайшего вектора трудна для квантовых компьютеров, поскольку переход от этой задачи к взлому криптосистемы — это квантовое сведение! Позже, в 2009 г., Крис Пикерт[52] открыл способ «деквантизации» сведения Регева, так что теперь достаточно уверенности в классической трудности задачи нахождения кратчайшего вектора.
Что еще интереснее, Крейг Джентри показал[53] в 2009 г., что, воспользовавшись предполагаемой трудностью определенных задач с решетками, связанных с нахождением кратчайшего вектора, можно строить полностью гомоморфные криптосистемы: то есть криптосистемы с открытым ключом, которые позволяют вам проводить произвольные вычисления с зашифрованными данными вообще без их расшифровки. Почему это важно? Ну, для таких приложений, как «облачные вычисления»: вам может потребоваться, скажем, переложить какие-то длинные вычисления с вашего мобильного устройства на какой-то внешний сервер, но так, чтобы не позволить этому серверу заглянуть в ваши секретные данные. То есть вы должны иметь возможность переслать на сервер зашифрованные входные данные, а сервер должен иметь возможность провести сложные вычисления, за которые вы заплатили, и переслать вам обратно зашифрованные выходные данные, которые вы затем сможете самостоятельно расшифровать (а может быть, даже и проверить); при этом сервер ничего о ваших данных не узнает. И дополнительный бонус: поскольку наши нынешние полностью гомоморфные системы шифрования основаны на задачах, связанных с решетками, то у них с системами Регева есть одна общая черта: никто не знает, как их взломать даже при помощи квантового компьютера. О возможности полностью гомоморфной криптографии впервые заговорили в 1970-е гг., но до самого последнего времени никто не знал, как это организовать. Так что это одно из крупнейших достижений теоретической криптографии за несколько десятков лет.
Но имеет ли все это практическое значение? Традиционно считалось, что нет. Лет десять назад длины ключей и сообщений в системах на основе решетки были хотя формально и полиномиальными, но такими длинными, что сам вопрос казался почти шуткой: объем данных на пути от обычного текста к шифрованному увеличивался иногда в миллионы раз (в зависимости от того, какую степень надежности вы хотели получить). Но с тех пор криптография на решетках постепенно движется в направлении практичности, отчасти, откровенно говоря, потому, что все поняли: можно значительно повысить эффективность, поступившись в небольшой степени требованиями к надежности. Если когда-нибудь масштабируемые квантовые компьютеры, способные взломать RSA, покажутся серьезной и реальной опасностью, я предсказываю, что ответом на это станет переход на новые криптосистемы с открытым ключом, похожие на криптосистемы на решетках. И опять же перспектива создания полностью гомоморфного шифрования может дать дополнительный и совершенно отдельный повод для такого перехода.
А что же криптосистемы на основе эллиптических кривых — еще один важный класс криптосистем с открытым ключом (в отличие от криптосистем на решетках, этот класс сегодня уже используется коммерчески)? К несчастью, криптосистемы на эллиптических кривых легко взламываются квантовыми компьютерами, поскольку задача их взлома может быть выражена как задача поиска абелевой скрытой подгруппы. (Потому что группы эллиптических кривых — это абелевы группы.) С другой стороны, самые известные классические алгоритмы взлома криптосистем на эллиптических кривых, судя по всему, работают медленнее, чем решето числового поля при взломе RSA, — речь идет о степени ~2n против ~ . Не исключено, что этот факт относится к категории фундаментальных, но не исключено также, что причина просто в том, что группы эллиптических кривых не слишком хорошо изучены.
На этом мы завершаем наш краткий обзор классической теории сложности и криптографии; мы готовы говорить о квантовой механике.