Файл: MethodFull.doc

Головоломки Меркла

Ральф Меркл (Ralph Merkle) изобрел первую схему криптографии с открытыми ключами. В 1974 году он за­писался на курс по компьютерной безопасности в Калифорнийском университете, Беркли, который вел Ланс Хоффман (Lance Hoffman). Темой его курсовой работы, поданной раньше срока, была "Безопасная передача данных по небезопасным каналам". Хоффман не понял предложения Меркла, и в конце концов Меркл прекратил занятия. Он продолжал работать над проблемой несмотря на продолжающееся непонимание его результатов.

Техника Меркла основывалась на головоломках ("puzzle"), которые отправителю и получателю решить легче чем злоумышленнику. Вот как Василиса может послать шифрованное сообщение Ивану, не обмениваясь с ним ключом до того:

1. Иван создает 2²⁰(другими словами, больше миллиона) сообщений типа: "Это головоломка номер х. Этосекретный ключ номер у.", где х - случайное число, а у – случайный секретный ключ. И х, и у отличаются в каждом сообщении. Используя симметричный алгоритм, он шифрует каждое сообщение своим 20 битным ключом и все их отправляет Василисе.

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

3. Василиса шифрует свое секретное сообщение при помощи некоторого симметричного алгоритма полученным ею ключом и посылает это сообщение Ивану вместе с х.

4. Иван знает, какой секретный ключ у он использовал в сообщении х, следовательно он может расшифровать сообщение Василисы.

Бессмертник может взломать эту систему, но ей придется выполнить гораздо больше работы чем Василисе и Ивану. Для раскрытия сообщения на этапе (3) она должна будет вскрыть грубой силой каждое из 2²⁰сообщений, отправ­ленных Иваном на этапе (1). Сложность этого вскрытия составит 2⁴⁰. Значения х также не помогут Кащееву, ведь они на этапе (1) присвоены случайным образом. В общем случае, вычислительные затраты Бессмертника Кащеева будут равны возве­денным в квадрат вычислительным затратам Василисы.

Это выигрыш (nпо отношениюn²) невелик по криптографическим стандартам, но при определенных уcловиях может быть достаточен. Если Василиса и Иван могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Ивана к Василисе по линии связи 1.544 Мбит/с. Если эквивалентные вычислительные мощности находятся в распоряжении Кащеева, ему потребуется около года для взлома системы. Другие алгоритмы еще более устойчивы к вскрытию.

Цифровые подписи

Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи?

1. Подпись достоверна.Она убеждает получателя документа в том, что подписавший сознательно подписал документ.

2. Подпись неподдельна.Она доказывает, что именно подписавший, и никто иной, сознательно подписалдокумент.

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

4. Подписанный документ нельзя изменить.После того, как документ подписан, его невозможно изменить.

5. От подписи не возможно отречься.Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.

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

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

Подпись документа с помощью симметричных криптосистем и посредника

Василиса хочет подписать цифровое сообщение и отправить его Ивану. Она может это сделать с помощью Ягуси и симметричной криптосистемы.

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

1. Василиса шифрует свое сообщение Ивану ключом К_Ви посылает его Яге.

2. Яга, зная ключ К_В, расшифровывает сообщение.

3. Яга добавляет к расшифрованному сообщению утверждение, что он получил это сообщение от Василисы, ишифрует это новое сообщение ключом К_И.

4. Бабуся посылает новое сообщение Ивану.

5. Иван расшифровывает сообщение ключом К_И. Он может прочитать и сообщение Василисы, и подтверждение Ягуси, что сообщение отправлено именно Василисой.

Откуда Баба-Яга узнает, что сообщение пришло именно от Василисы, а не от какой-то любовницы Кащеева? Она делает этот вывод из шифрования сообщения.

Также ли это хорошо, как подпись на бумаге? Посмотрим на требуемые свойства:

1. Эта подпись достоверна.Яга – это заслуживающий доверия посредник, и она знает, что сообщение получено от Василисы. Подтверждение Бабушки служит доказательством для Ивана.

2. Эта подпись неподдельна.Только Василиса (и Яга, но ей все верят) знает К_В, поэтому только Василисамогла послать Бабусе сообщение, зашифрованное ключом К_В. Если кто-нибудь попытается выдать се­бя за Василису, Яга сразу заметит это на этапе (2) и не заверит подлинность. И, в целях предотвращения рецедива, пригласит Илью Муромца для раздавания тумаков.

3. Эту подпись нельзя использовать повторно.Если Иван попытается взять подтверждение Бабы-Яги и присоединить его к другому сообщению, Василиса закричит "Караул! Насилуют!" Посредник (Яга или кто-то совсем другой, имеющий доступ к той же информации) попросит Ивана предъявить его сообщение и шифрованное сообщение Василисы. Затем посредник зашифрует сообщение ключом К_Ви увидит, что оно не со­ответствует шифрованному сообщению, переданному Иваном. Иван, конечно же, не сможет создать правильное шифрованное сообщение, потому что он не знает ключа К_В. Тут уж Ивану не избежать разговора по душам с Ильей Муромцем в темном переулке.

4. Подписанный документ нельзя изменить.Если Иван попытается, получив документ, изменить его, Бабуся обнаружит мошенничество уже описанным способом.

5. От подписи невозможно отказаться.Если впоследствии Василиса заявит, что она никогда не посылаласообщение, подтверждение Яги докажет обратное. Помните (все доверяют Яге) все, сказанное ей – чистая правда.

Если Иван захочет показать Лешему документ, подписанный Василисой, он не сможет раскрыть ей свой секретный ключ. Ему придется снова обратиться к Яге (которая не забудет получить с него мзду):

Иван берет сообщение и утверждение Бабушки, что сообщение получено от Василисы, шифрует их ключом К_Иипосылает обратно Яге.

Яга расшифровывает полученный пакет с помощью ключа К_И.

Яга проверяет свою базу данных и подтверждает, что отправителем оригинального сообщения была Василиса.

Ягуся шифрует полученный от Ивана пакет ключом К_Л, который она выделила для Лешего, и посылает шифрованный пакет Лешему.

Леший расшифровывает полученный пакет с помощью ключа К_Л. Теперь он может прочитать и сообщение, и подтверждение Яги, что сообщение отправлено Василисой.

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

Такого посредника как Бабуля, которому будут доверять все корреспонденты, тяжело найти и тяжело сохранить (несмотря на долгий срок жизни). Яга должна быть непогрешима (местный авторитет), если она сделает хотя бы одну ошибку на миллион подписей, никто не будет верить ей (дело может дойти даже до тухлых помидоров). Яга должен быть абсолютно безопасен. Если его база данных с секретными ключами когда-нибудь раскроется, или кто-нибудь сможет перепрограммировать его, все подписи станут бесполезными. Поя­вятся документы будто бы подписанные годы назад. Это приведет к хаосу. Правительства падут, и станет пра­вить анархия (ну или Бессмертник Кащеев). Такая схема теоретически может работать, но она недостаточно хороша для практического применения.

Деревья цифровых подписей

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

Подпись документа с помощью криптографии с открытыми ключами

Существуют алгоритмы с открытыми ключами, которые можно использовать для цифровых подписей. В некоторых алгоритмах – примером является RSA - для шифрования может быть использован или открытый, или закрытый ключ. Зашифруйте документ своим закрытым ключом, и вы получите надежную цифровую подпись. В других случаях – примером является DSA - для цифровых подписей исполь­зуется отдельный алгоритм, который невозможно использовать для шифрования. Эта идея впервые была изо­бретена Диффи и Хеллманом и в дальнейшем была расширена и углублена в других работах. Основной протокол прост:

1. Василиса шифрует документ своим закрытым ключом, таким образом подписывая его;

2. Василиса посылает подписанный документ Ивану;

3. Иван расшифровывает документ, используя открытый ключ Василисы, таким образом проверяя подпись.

Этот протокол гораздо лучше предыдущего. Баба-Яга не нужен ни для подписи документов, ни для ее проверки. (Она нужна для подтверждения, что открытый ключ принадлежит именно Василисе.) Ягуся не нужна сторонам даже для разрешения споров: Если Иван не смог осуществить этап (3), то он знает, что подпись неправильна. Такая подпись соответствует всем требованиям:

1. Эта подпись достоверна.Когда Иван расшифровывает сообщение с помощью открытого ключа Василисы, он знает что она подписала это сообщение.

2. Эта подпись неподдельна.Только Василиса знает свой закрытый ключ.

3. Эту подпись нельзя использовать повторно.Подпись является функцией документа и не может быть перенесена на другой документ.

4. Подписанный документ нельзя изменить.После любого изменения документа подпись не сможет больше подтверждаться открытым ключом Василисы.

5. От подписи невозможно отказаться.Ивану не требуется помощь Василисы при проверке ее подписи.