Рис. 63 Мартин Хеллман
Представьте себе, что Алиса и Боб живут в стране, в которой почтовая система совершенно аморальна и почтовые служащие читают всю незащищенную корреспонденцию. В один прекрасный день Алиса хочет отправить очень личное сообщение Бобу. Она кладет его в железную коробку, закрывает ее и запирает ключом замок. Затем она кладет запертую на замок коробку в почтовый ящик, а ключ оставляет себе. Но когда коробку доставляют Бобу, он не может открыть ее, так как у него нет ключа. Алиса может положить ключ в другую коробку, замкнуть ее на замок и отправить Бобу, но без ключа ко второму замку он не сможет открыть вторую коробку и достать оттуда ключ, которым откроет первую коробку. Для Алисы, по-видимому, единственный путь обойти эту проблему — это сделать дубликат своего ключа и заранее передать его Бобу, когда они встретятся за чашечкой кофе. До этого момента я просто переформулировал ту же старую задачу в новых условиях. Избежать распределения ключей кажется логически невозможным; если Алиса хочет запереть что-то в коробке так, чтобы только Боб мог открыть ее, она, безусловно, должна дать ему дубликат ключа. Или, на примере криптографии, если Алиса хочет зашифровать сообщение таким образом, чтобы только Боб мог расшифровать его, она должна передать ему копию ключа. Обмен ключами является неизбежной частью шифрования — или все-таки нет?
Теперь представим следующую картину. Как и прежде, Алиса хочет отправить очень личное сообщение Бобу. Она опять кладет свое секретное сообщение в железную коробку, запирает ее на замок и посылает Бобу. Когда коробка приходит, Боб навешивает свой собственный замок и высылает коробку обратно Алисе. Когда Алиса получит коробку, она уже заперта на два замка. Алиса снимает свой замок, оставляя на коробке только замок Боба, после чего посылает коробку назад Бобу. И вот здесь-то и заключается принципиальная разница: теперь Боб может открыть коробку, поскольку она заперта только на его собственный замок, к которому он один имеет ключ.
Значение этой небольшой истории огромно. В ней показано, что два человека могут безопасным образом обмениваться секретным сообщением, и при этом необходимости в обмене ключом нет. Впервые у нас появилось указание, что обмен ключами может не являться обязательной частью криптографии. Мы можем дать другое истолкование истории применительно к шифрованию. Алиса использует свой собственный ключ, чтобы зашифровать сообщение Бобу, который в свою очередь зашифровывает его уже своим ключом и возвращает его обратно. Когда Алиса получает дважды зашифрованное сообщение, она убирает свое шифрование и отсылает назад сообщение Бобу, который после этого может убрать уже свое шифрование и прочитать сообщение.
Кажется, что проблема распределения ключей может быть решена, поскольку в схеме с двойным зашифровыванием не требуется обмена ключами. Существует, однако, фундаментальное препятствие реализации системы, при которой Алиса зашифровывает, Боб зашифровывает, Алиса расшифровывает и Боб расшифровывает. Проблема состоит в том, в каком порядке выполняются зашифровывания и расшифровывания. Вообще говоря, порядок зашифровывания и расшифровывания является принципиальным и должен подчиняться принципу «последним пришел, первым ушел». Другими словами, последний этап при зашифровывании должен быть первым этапом при расшифровывании. В вышеприведенной же последовательности действий последним выполнял зашифровывание Боб, и поэтому при расшифровывании этот этап должен выполняться первым, но первой убирала свое шифрование Алиса — до того, как это сделал Боб. Важность порядка выполнения действий проще всего понять путем проверки чего-то такого, что мы выполняем каждый день. Утром мы надеваем носки, а затем ботинки, а вечером сначала снимаем ботинки, и только потом носки — не удастся снять носки раньше ботинок. Мы обязаны подчиняться принципу «последним пришел, первым ушел».
Некоторые самые элементарные шифры, такие как шифр Цезаря, являются настолько простыми, что порядок неважен. Однако в 70-х годах казалось, что любая форма стойкого шифрования должна подчиняться правилу «последним пришел, первым ушел». Если сообщение зашифровано ключом Алисы, а затем ключом Боба, то его необходимо вначале расшифровывать ключом Боба, а только потом — ключом Алисы. Порядок является критичным даже с одноалфавитным шифром замены. Представьте, что у Алисы и Боба имеются свои собственные ключи, как показано на следующей странице, и давайте взглянем, что случится, если порядок неправильный. Алиса использует свой ключ, чтобы зашифровать сообщение Бобу, затем Боб повторно зашифровывает то, что получилось, используя свой ключ; Алиса пользуется своим ключом, чтобы провести частичную расшифровку, и наконец, Боб своим ключом старается полностью расшифровать сообщение.