Первые алгоритмы с открытым ключом стали известны в то же время, когда проходило DES обсуждение как предполагаемого стандарта. Это привело к известной партизанщине в криптографическом сообществе . Как это описывал Диффи [494]:
Прекрасные криптосистемы с открытым ключом, обсуждаемые в популярной и научной печати, тем не менее, не нашли соответствующего отклика среди криптографических чиновников . В том же году, когда была открыта криптография с откр ы-тыми ключами, Агентство национальной безопасности (NSA) предложило удобную криптографическую систему, разработанную фирмой IBM, в качестве федерального Стандарта шифрования данных (Data Encryption Standard, DES). Марта Хеллман и я критиковали это предложение из-за недостаточной длины ключа, но производители подготовились поддержать стандарт, и наша критика была воспринята многими как попытка помешать введению стандарта ради продвижения нашей собственной работы. Криптография с открытым ключом, в свою очередь, также подвергалась критике в популярной литер а-туре [1125] и технических статьях [849, 1159], словно это был конкурирующий продукт, а не недавнее научное открытие . Это, однако, не помешало NSA объявить о своих заслугах в этой области. Его директор в одной из статей Encyclopedia Bri-tannica [1461] указал, что "двухключевая криптография была открыта в Агентстве на десять лет раньше ", хотя доказательства этого утверждения не были публично представлены.
В реальном мире алгоритмы с открытыми ключами не заменяют симметричные алгоритмы и используются не для шифрования сообщений, а для шифрования ключей по следующим двум причинам :
1. Алгоритмы с открытыми ключами работают медленно. Симметричные алгоритмы по крайней мере в 1000 раз быстрее, чем алгоритмы с открытыми ключами. Да, компьютеры становятся все быстрее и быстрее и лет через 15 криптография с открытыми ключами достигнет скоростей, сравнимых с сег о-дняшней скоростью симметричной криптографии. Но требования к объему передаваемой информации также возрастают, и всегда будет требоваться шифровать данные быстрее, чем это сможет сделать криптография с открытыми ключами.
2. Криптосистемы с открытыми ключами уязвимы по отношению к вскрытию с выбранным открытым текстом. Если С = Е(Р), где Р - открытый текст из п возможных открытых текстов, то криптоаналити-ку нужно только зашифровать все п возможных открытых текстов и сравнить результаты с С (помните, ключ шифрования общедоступен). Он не сможет раскрыть ключ дешифрирования, но он сможет определить Р.
Вскрытие с выбранным открытым текстом может быть особенно эффективным, если число возможных шифрованных сообщений относительно мало. Например, если Р - это денежная сумма в долларах, меньшая чем $1000000, то такое вскрытие сработает, криптоаналитик переберет весь миллион значений. (Эта проблема решается с помощью вероятностного шифрования, см. раздел 23.15.) Даже если Р не так хорошо определено, такое вскрытие может быть очень эффективно. Полезным может быть простое знание, что шифротекст не соответствует конкретному открытому тексту. Симметричные криптосистемы не чувствительны к вскрытиям такого типа, так как криптоаналитик не может выполнить тестовых дешифровок с неизвестным ключом .
В большинстве реализаций криптография с открытыми ключами используется для засекречивания и распр о-странения сеансовых ключей, которые используются симметричными алгоритмами для закрытия потока сообщений [879]. Иногда такие реализации называются смешанными (гибридными) криптосистемами
(1) Боб посылает Алисе свой открытый ключ
(2) Алиса создает случайный сеансовый ключ, шифрует его с помощью открытого ключа Боба и передает его Бобу.
ЕВ(К)
(3) Боб расшифровывает сообщение Алисы, используя свой закрытый ключ, для получения сеансового ключа. DB(EB(K))=K
(4) Оба участника шифруют свои сообщения с помощью одного сеансового ключа.
Использование криптографии с открытыми ключами для распределения ключей решает очень важную пр о-блему распределения ключей. В симметричной криптографии ключ шифрования данных, если он не использ у-ется, валяется без дела. Если Ева заполучит его, она сможет расшифровать все закрытые этим ключом сообщ е-ния. С помощью приведенного протокола при необходимости зашифровать сообщения создается сеансовый ключ, который уничтожается по окончании сеанса связи. Это значительно уменьшает риск компрометации с е-ансового ключа. Конечно, к компрометации чувствителен и закрытый ключ, но риска значительно меньше, так как в течение сеанса этот ключ используется только один раз для шифрования сеансового ключа . Подробно связанные с этим вопросы обсуждаются в разделе 3.1.
Головоломки Меркла
Ральф Меркл (Ralph Merkle) изобрел первую схему криптографии с открытыми ключами . В 1974 году он записался на курс по компьютерной безопасности в Калифорнийском университете, Беркли , который вел Ланс Хоффман (Lance Hoffman). Темой его курсовой работы, поданной раньше срока, была "Безопасная передача данных по небезопасным каналам" [1064]. Хоффман не понял предложения Меркла, и в конце концов Меркл прекратил занятия. Он продолжал работать над проблемой несмотря на продолжающееся непонимание его р е-зультатов.
Техника Меркла основывалась на головоломках ("puzzle"), которые отправителю и получателю решить лег-
че чем злоумышленнику. Вот как Алиса может послать шифрованное сообщение Бобу, не обмениваясь с ним ключом до того.
(1) Боб создает 22С (другими словами, больше миллиона) сообщений типа: "Это головоломка номер х. Это секретный ключ номер у.", где х - случайное число, а у - случайный секретный ключ. И х, и у отличаются в каждом сообщении. Используя симметричный алгоритм, он шифрует каждое сообщение своим 20 би т-ным ключом и все их отправляет Алисе.
(2) Алиса выбирает одно сообщение и приступает к вскрытию грубой силой,пытаясь получить открытый текст. Эта работа является объемной, но не невозможной.
(3) Алиса шифрует свое секретное сообщение при помощи некоторого симметричного алгоритма полученным ею ключом и посылает это сообщение Бобу вместе с х.
(4) Боб знает, какой секретный ключ у он использовал в сообщении х, следовательно он может расшифровать сообщение Алисы.
Ева может взломать эту систему, но ей придется выполнить гораздо больше работы чем Алисе и Бобу . Для раскрытия сообщения на этапе (3) она должна будет вскрыть грубой силой каждое из 220 сообщений, отправленных Бобом на этапе (1). Сложность этого вскрытия составит 2 40. Значения х также не помогут Еве, ведь они на этапе (1) присвоены случайным образом. В общем случае, вычислительные затраты Евы будут равны возведенным в квадрат вычислительным затратам Алисы.
Это выигрыш (я по отношению к п2) невелик по криптографическим стандартам, но при определенных уел о-виях может быть достаточен. Если Алиса и Боб могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Боба к Алисе по линии связи 1.544 Мбит/с. Если вычислительные возможности Евы сравнимы с приведенными, ей потребуется около года для взлома системы. Другие алгоритмы еще более устойчивы к вскрытию .
2.6 Цифровые подписи
Рукописные подписи издавна используются как доказательство авторства документа или, по крайней мере, согласия с ним. Что же так притягательно в подписи [1392]?
1. Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подп и-сал документ.
2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.
3. Подпись не может быть использована повторно. Она является частью документа, жулик не сможет перенести подпись на другой документ.
4. Подписанный документ нельзя изменить. После того, как документ подписан, его невозможно изм е-нить.
5. От подписи не возможно отречься. Подпись и документ материальны. Подписавший не сможет вп о-следствии утверждать, что он не подписывал документ.
В действительности, ни одно из этих утверждений не является полностью справедливым . Подписи можно подделать, свести с одного листа бумаги на другой, документы могут быть изменены после подписания . Однако, мы миримся с этими проблемами из-за того, что мошенничество затруднительно и может быть обнар ужено.
Хотелось бы реализовать что-нибудь подобное и на компьютерах, но есть ряд проблем . Во первых, компьютерные файлы скопировать не просто, а очень просто . Даже если подпись человека трудно подделать (например, графическое изображение рукописной подписи), можно легко вырезать правильную подпись из одного докуме н-та и вставить в другой. Простое наличие такой подписи ничего не означает. Во вторых, компьютерные файлы очень легко можно изменить после того, как они подписаны, не оставляя ни малейшего следа изменения .