Отправитель и получатель. Сообщения и шифрование 14 глава

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

Применение этого протокола выходит далеко за пределы обеденного стола. Вот пример безусловного отправителя и неотслеживаемого отправителя. Группа пользователей сети может использовать этот протокол для отправления анонимных сообщений.

(1) Пользователи упорядочиваются по кругу.

(2) Через регулярные интервалы времени соседние пары пользователей бросают между собой монету, используя какой-нибудь безопасный от злоумышленников протокол бросания "честной" монеты.

(3) После каждого броска каждый пользователь объявляет либо "одинаковые", либо "разные".

Если Алиса хочет передать широковещательное сообщение, она просто начинает инвертировать свое утверждение в тех раундах, которые соответствуют 1 в двоичном представлении ее сообщения. Например, если ее сообщение было "1001", она инвертирует ее утверждение, сообщит правду, сообщит правду, и затем инвертирует снова утверждение. При условии, что результатом ее бросков было были "разные", "одинаковые", "одинаковые", "одинаковые", она будет говорить "одинаковые", "одинаковые ", "одинаковые", "разные".

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

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

Альтернативой бросанию монет между соседними сторонами могло бы быть использование файла случайных битов. Возможно, стороны могли бы хранить файл на CD-ROM, или один член пары мог бы генерировать пачку битов и посылать их другой стороне (конечно, в зашифрованном виде). Или, они могли бы договориться использовать совместно криптографически безопасный генератор псевдослучайных чисел, и каждый из них смог бы генерировать для протокола ту же самую последовательность псевдослучайных битов.

Проблемой этого протокола является то, что хотя мошенничающий участник и не сможет читать никаких сообщений, он может незаметно испортить всю систему, постоянно обманывая на этапе (3). Существует модификация предыдущего протокола, позволяющая обнаружить вредительство [1578, 1242]. Эта проблема называется "Обедающие криптографы в дискотеке".

6.4 Электронные наличные

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

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

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

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

Протоколы электронных денег очень сложны. Дальше мы шаг за шагом построим один из них. Более подробно об этом протоколе можно прочитать в [318, 339, 325, 335, 340]. Но помните, это только один из протоколов электронных денег, существуют и другие.

Протокол №1

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

(1) Алиса готовит 100 анонимных денежных чеков по $1000 каждый.

(2) Алиса вкладывает каждый из них и листок копировальной бумаги в 100 различных конвертов и относит все конверты в банк.

(3) Банк открывает 99 конвертов и убеждается, что каждый чек выписан на $1000.

(4) Банк подписывает единственный оставшийся нераспечатанным конверт. С помощью копировальной бумаги подпись переводится на чек. Банк возвращает нераспечатанный конверт Алисе и списывает $1000 с ее счета.

(5) Алиса вскрывает конверт и отдает денежный чек продавцу.

(6) Продавец проверяет банковскую подпись, убеждаясь в законности денежного чека.

(7) Продавец относит денежный чек в банк.

(8) Банк проверяет свою подпись и начисляет $1000 на счет продавца.

Этот протокол работает. Банк не видит денежный чек, который он подписывает, поэтому, когда продавец принесет чек в банк, банк никогда не узнает, что это чек Алисы. Благодаря подписи банк убежден в законности чека. А из-за протокола "разрезать и выбрать" (см. раздел 5.1) банк уверен, что нераспечатанный денежный чек - на сумму $1000 (а не $100000 или $100000000). Он проверяет остальные 99 конвертов, поэтому вероятность обмана банка Алисой составляет только 1 процент. Конечно, банк назначит за обман достаточно большой штраф, такой, чтобы не стоило мошенничать. Ведь если банк просто откажется подписать последний чек (если Алиса поймана на обмане), не штрафуя Алису, она продолжит свои попытки, пока ей не повезет. Лучшее средство устрашения - это тюремное заключение.

Протокол №2

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

(1) Алиса готовит 100 анонимных денежных чеков по $1000 каждый. К каждому денежному чеку она добавляет уникальную строку, выбранную случайным образом и достаточно длинную, чтобы вероятность использования этой строки другим человеком была пренебрежимо мала.

(2) Алиса вкладывает каждый из них и листок копировальной бумаги в 100 различных конвертов и относит все конверты в банк.

(3) Банк открывает 99 конвертов и убеждается, что каждый чек выписан на $1000.

(4) Банк подписывает единственный оставшийся нераспечатанным конверт. С помощью копировальной бумаги подпись переводится на чек. Банк возвращает нераспечатанный конверт Алисе и списывает $1000 с ее счета.

(5) Алиса вскрывает конверт и отдает денежный чек продавцу.

(6) Продавец проверяет банковскую подпись, убеждаясь в законности денежного чека.

(7) Продавец относит денежный чек в банк.

(8) Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет $1000 на счет продавца и записывает уникальную строку в базу данных.

(9) Если денежный чек уже был депонирован ранее, банк отказывается принять его.

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

Протокол №3

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

(1) Алиса готовит 100 анонимных денежных чеков по $1000 каждый. К каждому денежному чеку она добавляет уникальную строку, выбранную случайным образом и достаточно длинную, чтобы вероятность использования этой строки другим человеком была пренебрежимо мала.

(2) Алиса вкладывает каждый из них и листок копировальной бумаги в 100 различных конвертов и относит все конверты в банк.

(3) Банк открывает 99 конвертов и убеждается, что каждый чек выписан на $1000, и что все случайные строки различны.

(4) Банк подписывает единственный оставшийся нераспечатанным конверт. С помощью копировальной бумаги подпись переводится на чек. Банк возвращает нераспечатанный конверт Алисе и списывает $1000 с ее счета.

(5) Алиса вскрывает конверт и отдает денежный чек продавцу.

(6) Продавец проверяет банковскую подпись, убеждаясь в законности денежного чека.

(7) Продавец просит Алису написать случайную идентификационную строку на денежном чеке.

(8) Алиса выполняет это.

(9) Продавец относит денежный чек в банк.

(10) Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет $1000 на счет продавца и записывает уникальную строку в базу данных.

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

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

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

Алиса также может приспособиться и к этому. Она может потратить копию денежного чека второй раз, написав ту же самую идентификационную строку на этапе (7). Если продавец не ведет базу данных уже полученных денежных чеков, он будет введен в заблуждение. Эту проблему устраняет следующий протокол.

Протокол №4

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

Чтобы спрятать имя Алисы в электронном чеке, можно воспользоваться методикой разделения секрета.

(1) Алиса готовит nанонимных денежных чеков на заданную сумму.

Каждый из чеков содержит уникальную строку, X, полученную случайным образом и достаточно длинную, чтобы вероятность появления двух одинаковых строк была пренебрежимо мала.

На каждом чеке есть также n пар битовых строк идентификации, I₁, I₂, ..., I_n. (Именно так, n различных пар на каждом чеке.) Каждая из этих пар генерируется следующим образом: Алиса создает строку, содержащую ее имя, адрес и прочие сведения, требуемые банком. Затем она делит эту строку на две части, используя протокол деления секрета (см. раздел 3.6) и вручает каждую часть, используя протокол вручения битов.

Например, I₃₇ состоит из двух частей: и . Каждая часть представляет собой пакет врученных битов, который Алису могут попросить открыть, и чье открытое содержание может быть мгновенно проверено. Любая пара (например, и , но не и ), раскрывает личность Алисы. Каждый из чеков выглядит следующим образом:

Сумма

Уникальная строка: X

Строки идентификации:

. . . .

(2) Алиса маскирует все n чеков с помощью протокола слепой подписи и относит чеки в банк.

(3) Банк просит Алису снять маскировку с n-1 денежных чеков и убеждается, что все они правильно оформлены. Банк проверяет сумму, уникальную строку и просит Алису раскрыть все строки идентификации.

(4) Если банк удовлетворен, не обнаружив попыток мошенничества, он подписывает оставшийся замаскированный денежный чек. Банк возвращает замаскированный чек Алисе и списывает сумму с ее счета.

(5) Алиса снимает маскировку с чека и тратит его у продавца.

(6) Продавец проверяет банковскую подпись, убеждаясь в законности денежного чека.

(7) Продавец случайным образом просит Алису раскрыть либо левые, либо правые половины всех строк идентификации на чеке. По сути, продавец выдает Алисе случайную n-битовую строку-селектор, b₁, b₂, ..., b_n. Левую или правую половину I_i откроет Алиса, зависит от значения b_i, 0 или 1.

(8) Алиса выполняет это.

(9) Продавец относит денежный чек в банк.

(10) Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет указанную сумму на счет продавца и записывает уникальную строку в базу данных.

(11) Если уникальная строка уже есть в базе данных, банк отказывается принять денежный чек и сравнивает идентификационную строку на денежном чеке с хранимой в базе данных. Если они совпадают, то банк убеждается, что чек был скопирован продавцом. Если идентификационные строки различны, то банк знает, что чек был скопирован человеком, который готовил этот денежный чек. Так как второй продавец, получивший чек, выдал Алисе другую, чем первый, строку-селектор, банк обнаружит, что для какой-то из позиций Алиса открыла левую половину одному продавцу, а правую - другому. Выполнив над этими половинами строки идентификации операцию XOR, банк определит личность Алисы.

Это весьма интересный протокол, поэтому посмотрим на него с разных сторон.

Может ли Алиса смошенничать? Ее электронные деньги представляют собой просто строку битов, которую она легко может скопировать. Потратить их в первый раз - не проблема, она просто выполнит протокол, и все пройдет без проблем. Продавец выдаст ей на этапе (7) случайную n-битовую строку-селектор, и Алиса откроет либо левую, либо правую половину каждой I_i на этапе (8). На этапе (10) банк запишет все эти данные вместе с уникальной строкой денежного чека.

Когда она попытается использовать те же электронные деньги второй раз, продавец (тот же или иной) выдаст ей на этапе (7) другую случайную n-битовую строку-селектор. Алиса должна выполнить этап (8), ее отказ немедленно встревожит продавца. Теперь, когда продавец приносит деньги в банк на этапе (10), банк немедленно заметит, что денежный чек с этой уникальной строкой уже был депонирован. Банк сравнивает открытые половины строк идентификации. Вероятность совпадения двух случайных строк-селекторов составляет один шанс из 2ⁿ, этого не случится до следующего оледенения. Теперь банк находит пару, первая половина которой была открыта в первый раз, а вторая - во второй, выполняет над этими половинами операцию XOR и извлекает имя Алисы. Так банк узнает, кто попытался воспользоваться чеком дважды.

Что этот протокол не мешает Алисе мошенничать, но ее мошенничество почти наверняка будет обнаружено. Смошенничав, Алиса не сможет сохранить в тайне свою личность. Она не может изменить ни уникальную строку, ни какую-нибудь из строк идентификации, иначе испортится банковская подпись, и продавец немедленно заметит это на этапе (6).

Алиса могла бы попытаться подсунуть банку плохой денежный чек, такой, на котором строки идентификации не раскрывают ее имени, или, еще лучше, раскрывают имя кого-то еще. Вероятность, что такая уловка проскочит мимо банка на этапе (3), составляет 1 из n. Это не невозможно, но если штраф за мошенничество достаточно суров, Алиса не будет испытывать судьбу. Или вы можете увеличить число избыточных чеков, предъявляемых Алисой на этапе (1).

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

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

А как насчет банка? Может ли он вычислить, что денежный чек, полученный от продавца, это и есть тот самый чек, который был подписан для Алисы? На этапах (2)-(5) Алиса защищена протоколом слепой подписи. Банк не сможет связать Алису и чек, даже если он полностью сохраняет запись каждой транзакции. Более того, даже объединившись, банк и продавец не смогут установить личность Алисы. Алиса может пройтись по магазину и, оставаясь полностью анонимной, купить то, что ей надо.

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

Место этого протокола где-то между протоколом с посредником и самодостаточным протоколом. И Алиса, и продавец доверяют банку в том, что касается денег, но Алиса не должна доверять банку сведения о своих покупках.

Электронные наличные и идеальное приведение

У электронных наличных есть и своя темная сторона. Иногда людям не нужно так много секретности. Смотрите, как Алиса совершает идеальное преступление [1575]:

(1) Алиса крадет ребенка.

(2) Алиса готовит 10000 анонимных денежных чеков по $1000 (или другое количество чеков нужного ей достоинства).

(3) Алиса маскирует все 10000 денежных чеков, используя протокол слепой подписи. Она посылает их властям с угрозой убить ребенка, если не будут выполнены следующие инструкции:

(a) Все 10000 денежных чеков должны быть подписаны банком.

(b) Результаты должны быть опубликованы в газете.

(4) Власти соглашаются.

(5) Алиса покупает газету, снимает маскировку с денежных чеков и начинает тратить их. Не смогут найти ее, проследив за денежными чеками.

(6) Алиса освобождает ребенка.

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

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

Реальные электронные наличные

Голландская компания, DigiCash, владеет большей частью патентов в области электронных наличных и реализовала протоколы электронных наличных в работающих продуктах owns. Если вы заинтересовались этим, обратитесь в DigiCash BV, Kruislaan 419, 1098 VA Amsterdam, Netherlands.

Другие протоколы электронных наличных

Существуют и другие протоколы электронных наличных, см. [707, 1554, 734, 1633, 973]. Ряд из них использует весьма изощренную математику. Различные протоколы электронных наличных можно разделить на различные категории. Диалоговыесистемы требуют, чтобы продавец связывался с банком при каждой продаже, что очень похоже на сегодняшний протокол для кредитных карточек. Если возникает какая-нибудь проблема, банк не принимает наличные, и Алиса не может смошенничать.

Автономныесистемы, подобные протоколу №4, не требуют соединения между продавцом и банком до окончания транзакции между продавцом и покупателем. Эти системы не помешают Алисе мошенничать, но вместо этого обнаружат ее мошенничество. Протокол №4 обнаруживает мошенничество Алисы, раскрывая ее личность при попытке мошенничать. Алиса знает о последствиях и, поэтому, не мошенничает.

Другой путь состоит в создании специальной интеллектуальной карты (см. Раздел 24.13), содержащей защищенную микросхему, называемую наблюдателем [332, 341, 387]. Микросхема-наблюдатель хранит мини-базу данных всех частей электронных наличных, потраченных этой интеллектуальной платой. Если Алиса попытается скопировать какие-то электронные наличные и потратить их дважды, внедренная микросхема-наблюдатель обнаружила бы такую попытку и не разрешила транзакцию. Так как микросхема-наблюдатель защищена от вмешательства извне, Алиса не сможет стереть мини-базу данных без разрушения интеллектуальной карты. Наличные деньги могут оборачиваться в экономике, когда они, наконец будут депонированы, банк может проверить наличные и определить мошенника, если произошел обман.

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

Двумя отличными совершенно отличающимися друг от друга автономными протоколами электронных монет являются [225, 226, 227] и [563, 564, 565]. Также можно предложить система NetCash (Сетевые наличные) с более слабыми свойствами [1048, 1049]. Другой новой системой является [289].

В [1211] Тацуаки Окамото (Tatsuaki Okamoto) и Казуо Охта (Kazuo Ohta) перечислили шесть свойств идеальной системы электронных наличных:

1. Независимость. Безопасность электронных наличных не зависит от местонахождения. Наличные могут быть переданы по компьютерным сетям.

2. Безопасность. Электронные наличные нельзя скопировать и повторно использовать.

3. Тайна личности (Неотслеживаемость). Тайна личности пользователя защищена, связь между пользователем и его покупками обнаружить невозможно.

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

5. Перемещаемость. Наличные могут передаваться другим пользователям.

6. Делимость. Заданная сумма электронных наличных может быть поделена на части меньшей суммы. (Конечно, общая сумма в конце должна сойтись.)

Ранее приведенные протоколы удовлетворяют требованиям 1, 2, 3 и 4, но не удовлетворяют требованиям 5 и 6. Ряд диалоговых систем электронных наличных удовлетворяет всем требованиям кроме 4 [318, 413, 1243]. Первая автономная система, удовлетворяющая требованиям 1, 2, 3 и 4, похожая на одну из описанных, была предложена [339]. Окамото и Охта предложили систему, удовлетворяющая требованиям с 1 по 5 [1209], они также предложили систему, удовлетворяющую требованиям с 1 по 6, объем данных для одного платежа составил приблизительно 200 мегабайт. Другая автономная система электронных монет с возможностью деления описана в [522].

Схема электронных наличных, предложенная теми же авторами [1211], удовлетворяет требованиям с1 по 6 без необходимости такого огромного объема данных. Общий объем данных для одного электронного платежа составляет около 20 килобайт, и протокол может быть выполнен за несколько секунд. Авторы рассматривают эту схему как первую идеальную систему неотслеживаемых электронных наличных.

Анонимные кредитные карточки

Этот протокол [988] для защиты личности клиента использует несколько различных банков. Каждый клиент имеет счет в двух различных банках. Первый банк, которому известна личность человека, может зачислять деньги на его счет. Второй банк знает клиента только под псевдонимом (подобно номерному счету в швейцарском банке).

Клиент может брать деньги из второго банка, доказывая, что он является владельцем счета. Но, этот банк не знает личности человека и не может зачислять деньги на его счет. Первый банк знает клиента и перечисляет деньги во второй банк, не зная псевдонима. Затем клиент анонимно тратит эти деньги. В конце месяца второй банк выставляет счет первому банку, веря, что он его оплатит. Первый банк передает счет клиенту, веря, что тот его оплатит. Когда клиент оплачивает счет, первый банк перечисляет дополнительные деньги во второй банк. Все транзакции проводятся через посредника, который действует подобно электронному Федеральному Резерву: оплачивает банковские счета, регистрирует сообщения и создает контрольный след.

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

Часть II
Криптографические методы

7 Длина ключа

7.1 Длина симметричного ключа

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

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

Для выполнения такого вскрытия криптоаналитику требуется кусочек шифротекста и соответствующего открытого текста, вскрытие грубой силой представляет собой вскрытие с известным открытым текстом. Для блочного шифра криптоаналитику понадобится блок шифротекста и соответствующий открытый текст: обычно 64 бита. Заполучить такие кусочки открытого текста и шифротекста легче, чем можно себе представить. Криптоаналитик может получить каким-то образом копию открытого текста сообщения и перехватить соответствующий шифротекст. Он может знать что-то о формате шифротекста: например, что это файл в формате WordPerfect, или у него есть стандартный заголовок сообщения электронной почты, или файл каталога UNIX, или изображение в формате TIFF, или стандартная запись в базе данных клиентов. Все эти форматы содержат некоторые предопределенные байты. Криптоаналитику для такого вскрытия не нужно много открытого текста.

Рассчитать сложность вскрытия грубой силой нетрудно. Если используется 8-битовый ключ, то существует 2⁸, или 256, возможных ключей. Следовательно, для обнаружения правильного ключа потребуется, самое большее, 256 попыток, с 50-процентной вероятностью найти нужный ключ после половины попыток. Если длина ключа равна 56 битам, то существует 2⁵⁶ возможных ключей. Если компьютер может проверить миллион ключей в секунду, поиск нужного ключа займет в среднем 2285 лет. Если используется 64-битовый ключ, то тому же суперкомпьютеру понадобится около 585000 лет, чтобы найти правильный ключ среди 2⁶⁴ возможных ключей. Если длина ключа равна 128 битам поиск ключа займет 10²⁵ лет. Возраст вселенной составляет всего 10¹⁰ лет, поэтому 10²⁵ лет - это большое время. При 2048-битовом ключе миллион компьютеров, работая параллельно и проверяя миллион ключей в секунду, потратят 10⁵⁸⁷ лет в поисках ключа. К этому времени вселенная давно расширится, превратившись в ничто или сожмется.