Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
2.1.3 Открытые ключи и квантовая криптография
Прежде чем продолжать дальше, позвольте представить трех наших основных персонажей. Это Алиса и Боб - два лица, которые хотят секретно общаться, - и Ева, которая их подслушивает. Сценарий таков: Алиса и Боб хотят установить секретный ключ, а Ева хочет получить хотя бы частичную информацию о ключе.
Криптологи очень старались, чтобы дать Алисе и Бобу преимущество и решить проблему распределения ключа. Например, в 1970-х появилось хитрое математическое открытие - системы с «открытым ключом». Сегодня используются две основных криптографические системы с открытым ключом - протокол обмена ключом Диффи-Хел-
38 Квантовая криптография
лмэна [34] и система шифрования RSA. Они были открыты в академическом сообществе, соответственно, в 1976 и 1978 годах. Однако эти методики были известны британским правительственным агентствам и до того, хотя этот факт вплоть до недавнего времени не был официально подтвержден. На самом деле, эти методы были впервые открыты в CESG в начале 1970-х Джоном Эллисом, который назвал их «несекретным шифрованием». В 1973 на основе идеи Эллиса К. Кокс разработал то, что мы сейчас называем RSA, а в 1974 М. Вильямсон предложил то, что по существу сейчас известно как протокол обмена ключом Диффи-Хеллмэна.
Рис. 2.2. Криптосистему с открытым ключом можно объяснить с помощью следующей механической аналогии. Представим, что Боб может изготовить много висячих замков, и любой желающий послать Бобу секретное сообщение может получить открытый замок, который сделал Боб. Открытый висячий замок можно рассматривать как открытый ключ. В частности, один берет себе Алиса. Как только Алиса закрыла замок, только Боб может его открыть, потому что только у Боба есть ключ — секретный ключ. Таким образом, Ализа может запереть любые данные по своему усмотрению и послать их Бобу с этим замком. Когда данные заперты, только Боб имеет к ним доступ благодаря своему секретному ключу.
В системах с открытым ключом пользователям не нужно договариваться о секретном ключе перед тем, как послать сообщение. Они работают по принципу сейфа с двумя ключами, так что есть один общий открытый ключ, чтобы его запереть, и еще один секретный ключ, чтобы его отпереть. У всех есть ключ, запирающий сейф, но только у кого-то одного есть ключ, который снова его откроет, так что кто угод-
Что не так в классической криптографии? 39
но может положить в сейф сообщение, но только один человек может его оттуда забрать. Еще одной аналогией является пример с висячими замками, показанный на Рис. 2.2. Эти системы основаны на том факте, что некоторые математические операции гораздо легче провести в одном направлении, чем в другом. Поэтому в таких системах нет проблемы распределения ключей, но, к сожалению, их надежность основана на недоказанных математических фактах, таких, как сложность разложения больших целых чисел на простые множители (факторизации). То есть, всегда возможно найти секретный ключ по открытому ключу, но просто это трудно сделать. Например, безопасность RSA - очень популярной системы с открытым ключом, названной в честь трех ее изобретателей, Рона Ривеста, Ади Шамира и Леонарда Адлемана (Ron Rivest, Adi Shamir, Leonard Adleman) [35], -основана на трудности факторизации больших чисел. Математики уверены (твердо, хоть они этого и не доказали), что для того, чтобы факторизовать число из N десятичных цифр, классическому компьютеру требуется число шагов, которое растет экспоненциально в зависимости от N: то есть, прибавление еще одной цифры к числу, которое надо факторизовать, умножает требуемое время на фиксированный множитель. Таким образом, при увеличении числа цифр, задача быстро становится нерешаемой.
Это означает, что если и как только математики и компьютерщики придумают быстрые и хитрые процедуры для факторизации больших целых чисел, вся секретность и надежность криптосистем с открытым ключом исчезнут в одну ночь. Между тем, недавние исследования по квантовым вычислениям показывают, что квантовые компьютеры способны, по крайней мере, в принципе, факторизовать гораздо быстрее, чем классические компьютеры [36]! Это значит, что в некотором смысле криптосистемы с открытым ключом уже неза-щищены: любое сообщение, зашифрованное с помощью RSA, можно будет прочесть через несколько мгновений после того, как будет включен первый квантовый компьютер, и, следовательно, нельзя использовать RSA для шифрования информации, которая в тот счастливый день должна будет все еще оставаться секретной. Возможно, тот день наступит через десятилетия, но разве может кто-нибудь доказать или дать надежные гарантии, что так оно и будет? Все, на чем сейчас основывается надежность системы RSA - это уверенность в медленности технического прогресса.
Квантовая криптография предлагает совершенно новый способ решения проблемы распределения ключа. То, что квантовое вычисление отнимает одной рукой, оно возвращает, по крайней мере, частично, другой. Одним из простейших видов квантового вычисления -
40 Квантовая криптография
