Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Как может группа людей вычислить свою среднюю зарплату без того, чтобы зарплата одного стала известна другому? (1) Алиса добавляет секретное случайное число к сумме своей зарплаты, шифрует результат открытым кл ю- чом Боба и посылает его Бобу. (2) Боб расшифровывает результат своим закрытым ключом. Он добавляет сумму своей зарплаты к получе н- ному от Алисы значению, шифрует результат открытым ключом Кэрол и посылает его Кэрол. (3) Кэрол расшифровывает результат своим закрытым ключом. Она добавляет сумму своей зарплаты к пол у- ченному от Боба значению, шифрует результат открытым ключом Дэйва и посылает его Дэйву. (4) Дэйв расшифровывает результат своим закрытым ключом. Он добавляет сумму своей зарплаты к пол у- ченному от Кэрол значению, шифрует результат открытым ключом Алисы и посылает его Алисе. (5) Алиса расшифровывает результат своим закрытым ключом. Она вычитает случайное число, прибавленное на этапе (1), получая сумму всех зарплат. (6) Алиса делит результат на число людей (в данном случае на четыре) и объявляет результат. Этот протокол подразумевает, что каждый участник честен - они хотя и могут любопытствовать, но следуют протоколу. Если любой из участников солжет о своей зарплате, средняя зарплата будет рассчитана неправильно. Более серьезная проблема состоит в том, что Алиса может искажать итоговый результат. Она может вычесть на этапе (5) любое число, которое ее устраивает, и никто об этом не узнает. Помешать Алисе сделать это можно, потребовав от нее вручить ее случайное число с помощью одной из схем вручения бита из раздела 4.9, но когда она откроет свое случайное число в конце протокола Боб сможет узнать ее зарплату. Протокол №2 Алиса и Боб вместе в ресторане и спорят о том, кто старше. Никто, однако, не хочет сообщить другому свой возраст. Каждый из них мог бы прошептать свой возраст на ушко доверенной нейтральной стороне (например, официанту), кто мог бы сравнить числа в уме и объявить результат и Алисе, и Бобу. У приведенного протокола есть две проблемы. Во первых, вычислительные способности среднего официант не позволяю ему обработать ситуации более сложный чем определение большего из двух чисел. И во вторых, если бы Алиса и Боб действительно заботились о сохранении своей информации в тайне, им пришлось бы ут о- пить официанта в ванне с минеральной водой, чтобы он ничего не разболтал буфетчику. Криптография с открытыми ключами предлагает существенно менее жесткое решение. Существует прот о- кол, в соответствии с которым Алиса, зная значение a, и Боб, зная b, могут совместно определить верно ли, что a какая разница) солгать о своем возрасте. Если бы Боб был компьютерной программой, которая слепо следовала бы протоколу, Алиса могла бы узнать его возраст (является ли возрастом компьютерной программы отрезок времени с момента ее написания или с момента ее запуска?), повторно выполняя протокол. Алиса могла бы ук а- зать, что ее возраст - 60 лет. Узнав, что она старше, она могла бы выполнить протокол снова, указав, что ее во з- раст - 30 лет. Узнав, что Боб старше, она могла бы снова выполнить протокол, указав, что ее возраст - 45 лет, и так далее, пока Алиса не узнает возраст Боба с любой нужной ей степенью точности. При условии, что участники не обманывают специально, этот протокол легко расширить для нескольких участников. Любое количество людей может определить порядок их возрастов с помощью последовательных честных применений протокола, и никакой участник не сможет узнать возраст другого. Протокол №3 Алиса нравится забавляться с плюшевыми медведями. В эротических фантазиях Боба важное место зан и- мают мраморные столы. Оба весьма стесняются своих привычек, но с удовольствием нашли бы кого-нибудь, кто разделил бы с ними их... гм... образ жи зни. В Службе безопасных вычислений с несколькими участниками мы спроектировали протокол для подобных людей. Мы занумеровали впечатляющий список их пристрастий от "африканских муравьедов" до "яблочных пирогов". Разделенные модемной линией связи, Алиса и Боб могут участвовать в безопасном протоколе с н е- сколькими участниками. Они вместе могут определить, есть ли у них общие привычки . Если есть, они могли бы устремиться к обоюдному счастью. Если нет, то они могли бы безопасно расстаться, сохраняя уверенность, что их привычки остались в тайне. Никто, даже Служба безопасных вычислений с несколькими участниками, ник о- гда не узнает об их пристрастиях. Вот как это работает: (1) С помощью однонаправленной функции Алиса хэширует свою привычку как семизначную строку . (2) Используя эту семизначную строку как телефонный номер, Алиса звонит по этому номеру и оставляет с о- общение Бобу. Если никто не отвечает, или номер не обслуживается. Алиса применяет однонаправленную функцию к телефонному номеру до тех пор, пока не найдется кто-нибудь, кто подхватит протокол . (3) Алиса сообщает Бобу, сколько раз ей пришлось применять однонаправленную функцию к своей привы чке. (4) Боб хэширует свою привычку столько же раз. Он также использует семизначную строку как телефонный номер и спрашивает человека на другом конце провода, нет ли для него сообщений. Обратите внимание, что у Боба есть возможность вскрытия с использованием выбранного открытого текста . Он может хэшировать распространенные привычки и позвонить по получившемуся телефону, разыскивая соо б- щения для него. Это протокол реально работает только такое вскрытие непрактично из-за достаточного числа возможных открытых текстов сообщений . Также существует математический протокол, похожий на Протокол № 2 . Алиса знает a, Боб знает b, и они вместе пытаются определить, верно ли, что a = b, причем так, чтобы Боб ничего не узнал об a, а Алиса - о b. Подробности можно найти в разделе 23.14. Протокол №4 Вот другая проблема для безопасных вычислений со многими участниками [1373]: совет семи регулярно встречается, чтобы тайно проголосовать по некоторым вопросам. (Все в порядке, они управляют миром - не говорите никому, что я вам проговорился.) Все члены совета могут голосовать "да" или "нет". Кроме того, две стороны обладают "супер-бюллетенями": 5-да и 5-нет. Они не обязаны использовать эти "супер-бюллетени" и, если хотят, могут воспользоваться обычными бюллетенями. Если никто не использует "супер-бюллетени", то вопрос решается простым большинством голосов. В случае применения одного или двух эквивалентных "супер- бюллетеней" все обычные голоса игнорируются. В случае двух противоречащих вопрос решается большинством обычных голосов. Нам нужен протокол, который надежно осуществляет такую форму голосования. Следующие два примера иллюстрируют процесс голосования . Пусть участвуют пять обычных избирателей , от N 1 до N 5 , и два суперизбирателя: S 1 и S 2 . Вот голосование по вопросу №1: S 1 S 2 N 1 N 2 N 3 N 4 N 5 Супер-да нет нет нет нет да да В этом примере действует только один "супер-бюллетень" S 1 , и результат голосования - "да". А вот голос о- вание по вопросу №2: S 1 S 2 N 1 N 2 N 3 N 4 N 5 Супер-да Супер-нет нет нет нет да да В этом примере два "супер-бюллетеня" нейтрализуют друг друга, и вопрос решается большинством обы ч- ных "нет". Если не требуется скрыть информацию о том, обычный или супербюллетель был решающим, то это простое применение безопасного протокола голосования. Сокрытие этой информации потребует более сложного без о- пасного протокола вычислений с несколькими участниками. Этот вид голосования может произойти в реальной жизни. Это может быть часть организационной структ у- ры корпорации, где некоторые люди обладают большей властью чем другие, или часть процедуры ООН, где одни государства имеют большее значение, чем другие. Безусловные безопасные протоколы с несколькими участниками Это только частный случай общей теоремы: любая функция с n входами может быть вычислена n игроками способом, который позволит всем узнать значение функции, но любое количество игроков, меньшее, чем n/2, не сможет получить никакой дополнительной информации, не следующей из их собственных входов и результата вычислений. Подробности можно найти в [136, 334, 1288, 621]. Безопасная оценка схемы Вход Алисы - a, а Боба - b. Они вместе хотят вычислить некоторую функцию f(a,b) так, чтобы Алиса не смогла ничего узнать о входе Боба, а Боб - о входе Алисы. Главная проблема безопасных вычислений с н е- сколькими участниками также называется безопасной оценкой схемы. Алиса и Боб могут создать произволь- ную логическую схему. Эта схема получает на вход значения Алисы и Боба и выдает результат . Безопасная оценка схемы является протоколом, который реализует следующие три требования : 1. Алиса может ввести свое значение так, что Боб не сможет его узнать . 2. Боб может ввести свое значение так, что Алиса не сможет его узнать . 3. И Алиса, и Боб могут вычислить результат, причем обе стороны будут убеждены в том, что результат правилен и не подтасован ни одной стороной . Детали протокола безопасной оценки схемы можно найти в [831]. 6.3 Анонимная широковещательная передача сообщений Вам не удастся пообедать с компанией криптографов и не оказаться среди ожесточенной перепалки . В [321] Дэвид Чаум вводит Проблему обедающих криптографов : Три криптографа сидят за обедом в своем любимом трехзвездочном ресторане . Их официант сообщает им, что метрдо- тель принял необходимые меры, чтобы счет можно было бы оплатить анонимно . За обед мог бы заплатить один из крипт о- графов или NSA. Три криптографа очень уважают право каждого из них заплатить анонимно, но им хотелось бы знать, з а- платит ли NSA. Как криптографам Алисе, Бобу и Кэрол узнать, не заплатил ли за обед кто-нибудь из них, и в то же время не нарушить анонимность плательщика? Чаум решает проблему: Каждый криптограф бросает несмещенную монету, прикрывшись своим меню, между ним и криптографом справа от н е- го так, что только они двое могут видеть результат. Затем каждый криптограф громко объявляет, упаали ли две монеты - одна его и одна его левого соседа - на одну или на различные стороны. Если плательщик - один из криптографов, то его утвержд е- ние противоположно тому, что он видит. Нечетное число заявленных различий за столом указывает, что обед оплачивает криптограф; четное число различий - что NSA (при условии, что обед может быть оплачен только один раз). Однако, если обед оплачивает криптограф, никто из двух других не узнает из сделанных заявлений, кто же конкретно опл атил обед. Чтобы увидеть, как это работает, вообразите, что Алиса пытается понять, кто из двух других криптографов заплатил за обед (при условии, что не она и не NSA). Если она видит две различных монеты, то либо оба других криптографа (Боб и Кэрол) сказали, "одинаковые" или оба сказали, "разные". (Помните, нечетное число кри п- тографов, говорящих "разные" указывает, что оплатил кто-то из них.). Если оба сказали "разные", то плател ь- щик - криптограф, сидящий ближе всего к монете, результат броска которой тот же, что и у скрытой монеты (брошенной между Бобом и Кэрол). Если оба сказали "одинаковые", то плательщик - криптограф, сидящий ближе всего к монете, результат броска которой отличается от результата броска скрытой монеты. Однако, если Алиса видит две одинаковых монеты, то или Боб сказал, "одинаковые", а Кэрол - "разные", или Боб сказал "разные", а Кэрол - "одинаковые". Если ли скрытая монета - такая же как и видимые ей две монеты, то пл а- тельщик - криптограф, который сказал, "разные". Если скрытая монета отлична от видимых ей двух монет, то плательщик - криптограф, который сказал "одинаковые". Чтобы определить, кто платил, во всех этих случаях Алиса должна знать результат броска монеты между Бобом и Кэрол. Этот протокол может быть обобщен на любое количество криптографов, которые сидят по кругу и бросают монеты между собой. Каждая пара криптографов выполняет протокол . Конечно, они знают, кто платит, но кто- то, наблюдающий за протоколом может сказать только, что заплатил один из криптографов или 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 1 , I 2 , ..., I n . (Именно так, n различных пар на каждом чеке.) Каждая из этих пар генерируется следующим образом : Алиса создает строку, со- держащую ее имя, адрес и прочие сведения, требуемые банком . Затем она делит эту строку на две части, используя протокол деления секрета (см. раздел 3.6) и вручает каждую часть, используя протокол вруч е- ния битов. Например, I 37 состоит из двух частей: I L 37 и I R 37 . Каждая часть представляет собой пакет врученных б и- тов, который Алису могут попросить открыть, и чье открытое содержание может быть мгновенно пров е- рено. Любая пара (например, I L 37 и I R 37 , но не I L 37 и I R 38 ), раскрывает личность Алисы. Каждый из чеков выглядит следующим образом: Сумма Уникальная строка: : Строки идентификации: I I I L R 1 1 1 = ( , ) I I I L R 2 2 2 = ( , ) I I I n n n L R = ( , ) (2) Алиса маскирует все n чеков с помощью протокола слепой подписи и относит чеки в банк. (3) Банк просит Алису снять маскировку с n-1 денежных чеков и убеждается, что все они правильно офор м- лены. Банк проверяет сумму, уникальную строку и просит Алису раскрыть все строки идентификации. (4) Если банк удовлетворен, не обнаружив попыток мошенничества, он подписывает оставшийся замаскир о- ванный денежный чек. Банк возвращает замаскированный чек Алисе и списывает сумму с ее счета. (5) Алиса снимает маскировку с чека и тратит его у продавца. (6) Продавец проверяет банковскую подпись, убеждаясь в законности денежного чека . (7) Продавец случайным образом просит Алису раскрыть либо левые, либо правые половины всех строк идентификации на чеке. По сути, продавец выдает Алисе случайную n-битовую строку-селектор, b 1 , b 2 , ..., b n . Левую или правую половину I i откроет Алиса, зависит от значения b i , 0 или 1. (8) Алиса выполняет это. (9) Продавец относит денежный чек в банк. (10) Банк проверяет свою подпись и по своей базе данных убеждается, что денежный чек с такой уникальной строкой ранее не депонировался. Если это так, банк начисляет указанную сумму на счет продавца и запи- сывает уникальную строку в базу данных. (11) Если уникальная строка уже есть в базе данных, банк отказывается принять денежный чек и сравнивает идентификационную строку на денежном чеке с хранимой в базе данных. Если они совпадают, то банк убеждается, что чек был скопирован продавцом. Если идентификационные строки различны, то банк зн а- ет, что чек был скопирован человеком, который готовил этот денежный чек. Так как второй продавец, п о- лучивший чек, выдал Алисе другую, чем первый, строку-селектор, банк обнаружит, что для какой-то из позиций Алиса открыла левую половину одному продавцу, а правую - другому. Выполнив над этими п о- ловинами строки идентификации операцию XOR, банк определит личность Алисы. Это весьма интересный протокол, поэтому посмотрим на него с разных сторон . Может ли Алиса смошенничать? Ее электронные деньги представляют собой просто строку битов, которую она легко может скопировать. Потратить их в первый раз - не проблема, она просто выполнит протокол, и все пройдет без проблем. Продавец выдаст ей на этапе (7) случайную n-битовую строку-селектор, и Алиса откроет либо левую, либо правую половину каждой I i на этапе (8). На этапе (10) банк запишет все эти данные вместе с уникальной строкой денежного чека. Когда она попытается использовать те же электронные деньги второй раз, продавец (тот же или иной) вы- даст ей на этапе (7) другую случайную n-битовую строку-селектор. Алиса должна выполнить этап (8), ее отказ немедленно встревожит продавца. Теперь, когда продавец приносит деньги в банк на этапе (10) , банк немед- ленно заметит, что денежный чек с этой уникальной строкой уже был депонирован . Банк сравнивает открытые половины строк идентификации. Вероятность совпадения двух случайных строк-селекторов составляет один шанс из 2 n , этого не случится до следующего оледенения . Теперь банк находит пару, первая половина которой была открыта в первый раз, а вторая - во второй, выполняет над этими половинами операцию 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, Nethe rlands. Другие протоколы электронных наличных Существуют и другие протоколы электронных наличных, см. [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]. Если все не сговар и- ваются против клиента, его анонимность гарантирована. Однако, это не электронные наличные, банк слишком легко может мошенничать. Протокол позволяет клиентам пользоваться преимуществами кредитных карточек, не раскрывая своей личности. Часть 2 Криптографические методы Глава 7 Длина ключа 7.1 Длина симметричного ключа Безопасность симметричной криптосистемы является функцией двух факторов: надежности алгоритма и длины ключа. Первый более важен, но роль второго легче продемонстрировать . Пусть надежность алгоритма совершенна. На практике этого чрезвычайно трудно достигнуть, но в примере - достаточно легко. По совершенством я подразумеваю отсутствие лучшего пути взлома криптосистемы, чем вскрытие грубой силой с помощью перебора всех возможных ключей . Для выполнения такого вскрытия криптоаналитику требуется кусочек шифротекста и соответствующего о т- крытого текста, вскрытие грубой силой представляет собой вскрытие с известным открытым текстом . Для блоч- ного шифра криптоаналитику понадобится блок шифротекста и соответствующий открытый текст : обычно 64 бита. Заполучить такие кусочки открытого текста и шифротекста легче, чем можно себе представить . Криптоа- налитик может получить каким-то образом копию открытого текста сообщения и перехватить соответствующий шифротекст. Он может знать что-то о формате шифротекста : например, что это файл в формате WordPerfect, или у него есть стандартный заголовок сообщения электронной почты , или файл каталога UNIX, или изображе- ние в формате TIFF, или стандартная запись в базе данных клиентов . Все эти форматы содержат некоторые предопределенные байты. Криптоаналитику для такого вскрытия не нужно много открытого текста . Рассчитать сложность вскрытия грубой силой нетрудно . Если используется 8-битовый ключ, то существует 2 8 , или 256, возможных ключей. Следовательно, для обнаружения правильного ключа потребуется, самое бол ь- шее, 256 попыток, с 50-процентной вероятностью найти нужный ключ после половины попыток . Если длина ключа равна 56 битам, то существует 2 56 возможных ключей. Если компьютер может проверить миллион кл ю- чей в секунду, поиск нужного ключа займет в среднем 2285 лет. Если используется 64-битовый ключ, то тому же суперкомпьютеру понадобится около 585000 лет, чтобы найти правильный ключ среди 2 64 возможных клю- чей. Если длина ключа равна 128 битам поиск ключа займет 10 25 лет. Возраст вселенной составляет всего 10 10 лет, поэтому 10 25 лет - это большое время. При 2048-битовом ключе миллион компьютеров, работая параллел ь- но и проверяя миллион ключей в секунду, потратят 10 587 лет в поисках ключа. К этому времени вселенная давно расширится, превратившись в ничто или сожмется. Прежде чем кидаться изобретать криптосистему с 8-килобайтным ключом, вспомните, что другой стороной является надежность: алгоритм должен быть настолько безопасен, чтобы лучшего способа, чем вскрывать его грубой силой, не существовало. Это не так просто, как может показаться. Криптография - это тонкое искусство. Выглядящие совершенными криптосистемы часто оказываются чрезвычайно слабыми . Пара изменений, вне- сенных в сильные криптосистемы, может резко ослабить их . Криптографам-любителям следует подвергать по ч- ти параноидальному сомнению каждый новый алгоритм. Лучше доверять алгоритмам, над которыми годами бились профессиональные криптографы, не сумев взломать их, и не обольщаться утверждениями конструкторов алгоритмов об их грандиозной безопасности. Вспомните важный момент из раздела 1.1: безопасность криптосистем должна основываться на ключе, а не особенностях алгоритма. Предположим, что криптоаналитику известны все подробности вашего алгоритма . Предположим, что у него есть столько шифротекста, сколько ему нужно, и что он попытается выполнить инте н- сивное вскрытие с использованием только шифротекста . Предположим, что он попытается выполнить вскрытие с использованием открытого текста, имея в своем распоряжении столько данных, сколько ему нужно . Предпо- ложим даже, что он попытается выполнить вскрытие с использованием выбранного открытого текста . Если ва- ша криптосистема останется безопасной даже перед лицом всех подобных опасностей, то... у вас действительно что-то есть. Несмотря на это предупреждение пространство, предоставляемое криптографией для маневра, достаточно велико. В действительности, безопасность такого типа во многих практических ситуациях не нужна . У боль- шинства врагов нет таких знаний и вычислительных средств, как у больших правительств, а тем, кто обладает такими возможностями, может оказаться ненужным взламывать вашу криптосистему . Если вы организуете за- говор с целью свергнуть большое правительство, проверенные и правильные алгоритмы, приведенные в конце этой книги, будут для вас жизненно необходимы. А все остальные пусть просто получат удовольс твие. Оценки времени и стоимости вскрытия грубой силой Вспомните, что вскрытие грубой силой обычно является вскрытием с использованием известного открытого текста, для этого нужно немного шифротекста и соответствующего открытого текста . Если вы предполагаете, что наиболее эффективным способа взлома алгоритма является вскрытие грубой силой - большое допущение - то ключ должен быть достаточно длинным, чтобы сделать вскрытие невозможным . Насколько длинным? Скорость вскрытия грубой силой определяется двумя параметрами : количеством проверяемых ключей и скоростью проверки одного ключа. Большинство симметричных алгоритмов в качестве ключа могут использ о- вать в качестве ключа любую битовую последовательность фиксированной длины. Длина ключа DES составля- ет 56 бит, всего может быть 2 56 возможных ключей. Длина ключей для ряда алгоритмов, обсуждаемых в этой книге, равны 64 битам, всего может быть 2 64 возможных ключей. Другие алгоритмы используют 128-битовые ключи. Скорость, с которой может быть проверен каждый ключ, имеет менее важное значение . Для проводимого анализа я предполагаю, что скорость проверки ключа для каждого алгоритма примерно одинакова. В действ и- тельности скорость проверки одного алгоритма может быть в два, три или даже десять раз выше чем другого . Но так как для тех длин ключей, для которых мы проводим поиск, время поиска в миллионы раз больше, чем время проверки одного ключа, небольшие отличия в скорости проверки не имеют значения . В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В 1977 году Уитфилд Диффи и Мартин Хеллман [497] сформулировали условия существования специализированной машины по взлому DES. Эта машина состоит из миллионов микросхем, каждая из кот о- рых проверяет миллион ключей в секунду . Такая машина за два часа сможет проверить 2 56 за 20 часов. При вскрытии алгоритма с 64-битовым ключом проверка всех 2 64 потребует 214 дней. Задача вскрытия грубой силой как будто специально придумана для параллельных процессоров . Каждый процессор проверяет подмножество пространства ключей . Процессорам не нужно обмениваться между собой информацией, единственным используемым сообщением будет сообщение, сигнализирующее об успехе . Не тре- буется и доступ к одному участку памяти. Сконструировать машину с миллионом процессоров, каждый из кот о- рых работает независимо от других, нетрудно. Сконструировать машину для взлома грубой силой Майкл Винер решил [1597, 1598]. (Он сконструировал машину для DES, но анализ может быть выполнен почти для всех алгоритмов .) Он разработал специализиро- ванные микросхемы, платы и стойки, оценил затраты и сделал вывод, что за миллион долларов можно постр о- ить машину, которая сможет взломать 56-битный ключ DES key в среднем за 3.5 часа (и наверняка за 7 часов). Соотношение стоимость/скорость является линейным . Для ряда длин ключей эти значения обобщены в 6-й. Вспомните о законе Мура: мощь вычислительных средств приблизительно каждые 18 месяцев . Это означает, что затраты будут уменьшаться на порядок каждые пять лет, и то, что в 1995 году стоит миллион долларов, в 2000 году будет стоить около 100000 долларов. Еще более упростить процесс вычислений могла бы конвейер и- зация [724]. Для 56-битовых ключей эти суммы оказываются вполне по карману большинству крупных корпораций и многим криминальным организациям. Военные бюджеты большинства промышленно развитых стран могут позволить взламывать и 64-битные ключи. Вскрытие 80-битного ключа все еще за пределами возможного , но если текущая тенденция сохранится, то через каких-нибудь тридцать лет все может измениться . Конечно, нелепо прогнозировать компьютерную мощь на 35 лет вперед . Технологические прорывы, попу- лярные в научной фантастике, могут сделать эти прогнозы смешными . С другой стороны, неизвестные в на- стоящее время физические ограничения могут сделать эти прогнозы нереально оптимистичными . В криптогра- фии умнее быть пессимистом. Применение в алгоритме 80-битного ключа кажется недостаточно дальновидным . Используйте ключ, длина которого, по меньшей мере, 112 бит. Табл. 7-1. Оценки среднего времени для аппаратного вскрытия грубой силой в 1995 году. Длина ключей в битах Стоимость 40 56 64 80 112 128 $100 К 2 секунды 35 часов 1 год 70000 лет 10 14 лет 10 19 лет $1 М 0.2 секунды 3.5 часа 37 дней 7000 лет 10 13 лет 10 18 лет $10 M 0.02 секунды 21 минута 4 дня 700 лет 10 12 лет 10 17 лет $100 M 2 миллисекунды 2 минуты 9 часов 70 лет 10 11 лет 10 16 лет $1 Г 0.2 миллисекунды 13 1 час 7 лет 10 10 лет 10 15 лет $10 Г 0.02. миллисекунды 1 секунда 5.4 минуты 245 дней 10 9 лет 10 14 лет $100 Г 2 микросекунды 0.1 секунды 32 секунд 24 дня 10 8 лет 10 13 лет $1 Т 0.2 микросекунды 0.01 секунды 3 секунды 2.4 дня 10 7 лет 10 12 лет $10 Т 0.02 микросекунды 1 миллисекунда 0.3 секунды 6 часов 10 6 лет 10 11 лет Если взломщик очень сильно хочет взломать ключ, все, что ему нужно, это потратить деньги . Следовательно, стоит попытаться определить минимальную "цену" ключа: в пределах какой стоимости сведе- ний можно пользоваться одним ключом прежде, чем его вскрытие станет экономически выгодным ? Крайний случай: если шифрованное сообщение стоит $1.39, то нет финансового смысла устанавливать аппаратуру сто и- мостью 10 миллионов долларов для взлома этого ключа. С другой стороны, если стоимость открытого текста - 100 миллионов долларов, то дешифрирование этого одиночного сообщения вполне окупит стоимость аппарат у- ры взлома. Кроме того, стоимость многих сообщений со временем очень быстро падает . Программное вскрытие Без специализированной аппаратуры и огромных параллельных машин вскрытие грубой силой намного сложнее. Программное вскрытие в тысячи раз медленнее, чем аппаратное . Реальная угроза программного вскрытия грубой силой страшна не своей неизбежностью, а тем, что такое вскрытие "свободно". Ничего не стоит загрузить простаивающий микрокомпьютер проверкой возможных кл ю- чей. Если правильный ключ будет найден - замечательно, если нет - ничего не потеряно . Ничего не стоит ис- пользовать для этого целую сеть микрокомпьютеров . В недавних экспериментах с DES 40 рабочих станций в течение одного дня сумели проверить 2 34 ключей [603]. При этой скорости для проверки всех ключей потреб у- ется четыре миллиона дней, но если попытки вскрытия будут предприняты достаточным количеством людей , то кому-нибудь где-нибудь повезет. Как было сказано в [603]: Основной угрозой программного вскрытия является слепое везение . Представьте себе университетскую сеть из 512 объ е- диненных в сеть рабочих станций. Для некоторых университетских городков это сеть весьма среднего размера . Такие сети могут даже расползтись по всему миру, координируя свою деятельность по электронной почте . Пусть каждая рабочая станция способна работать (с алгоритмом) со скоростью 15000 шифрований в секунду. ... С учетом накладных расходов на проверку и смену ключей уменьшим скорость до . . . 8192 проверок в секунду на машину. Чтобы, используя описанную систему, исче р- пать пространство (56-битовых) ключей потребуется 545 лет (в предположении, что сеть тратит на эту задачу 24 часа в сутки). Заметим, однако, что с помощью таких вычислений сторонники нашего студента получают один шанс из 200000 рас- крыть ключ в течение одного дня. За долгий уикенд их шансы возрастают до одного из шестидесяти шести тысяч . Чем быст- рее их аппаратура, или чем больше задействовано машин, тем лучше становятся их шансы . Вероятность заработать на жизнь, выигрывая на скачках, невысока, но разве не эти выигрыши заполняют собой пресс-релизы . К примеру, это гораздо большая вероятность, чем возможность выигрыша в правительственных лотереях . "Один на миллион"? "Один раз за тысячу лет "? |