Взгляните на симметричный алгоритм как на сейф. Ключ является комбинацией. Знающий комбинацию человек может открыть сейф, положить в него документ и снова закрыть. Кто-то другой при помощи той же комбинации может открыть сейф и забрать документ. Тем, кто не знает комбинации, придется научиться взламывать сейфы.
В 1976 году Уитфилд Диффи и Мартин Хеллман изменили эту парадигму криптографии. Они описали криптографию с открытыми ключами, используя два различных ключа - один открытый и один закрытый. Определение закрытого ключа по открытому требует огромных вычислительных затрат. Кто угодно, используя открытый ключ, может зашифровать сообщение, но не расшифровать его. Расшифровать сообщение может только владелец закрытого ключа. Это похоже на превращение криптографического сейфа в почтовый ящик. Шифрование с открытым ключом аналогично опусканию письма в почтовый ящик, любой может сделать это, опустив письмо в прорезь почтового ящика. Дешифрирование с закрытым ключом напоминает извлечение почты из почтового ящика. Обычно это гораздо сложнее - вам может понадобиться сварочный агрегат. Однако, если вы знаете секрет (у вас есть ключ от почтового ящика), вы без труда достанете вашу почту.
Математической основой процесса являются ранее обсуждавшиеся однонаправленные хэш-функции с лю ком. Шифрование выполняется в прямом направлении. Указания по шифрованию открыты, каждый может зашифровать сообщение. Дешифрирование выполняется в обратном направлении. Оно очень трудоемко без знания секрета. Секретом, или люком, и служит закрытый ключ, он делает дешифрирование таким же простым, как и шифрование. Вот как, используя криптографию с открытыми ключами, Алиса может послать сообщение Бобу:
(1) Алиса и Боб согласовывают криптосистему с открытыми ключами.
(2) Боб посылает Алисе свой открытый ключ.
(3) Алиса шифрует свое сообщение и отправляет его Бобу.
(4) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа.
Обратите внимание, что криптография с открытыми ключами устраняет проблему распределения ключей, присущую симметричным криптосистемам. Раньше Алиса и Боб должны были тайно договориться о ключе. Алиса могла выбрать любой ключ, но ей нужно было передать его Бобу. Она могла сделать это заранее, но это требует от нее определенной предусмотрительности. Она могла бы послать ключ с секретным курьером, но для этого нужно время. Криптография с открытыми ключами все упрощает. Алиса может отправить Бобу секретное сообщение без каких-либо предварительных действий. У Евы, подслушивающей абсолютно все, есть открытый ключ Боба и сообщение, зашифрованное этим ключом, но она не сможет получить ни закрытый ключ Боба, ни текст сообщения.
Обычно целая сеть пользователей согласовывает используемую криптосистему. У каждого из них есть открытый и закрытый ключ, открытые ключи помещаются в общедоступной базе данных. Теперь протокол выглядит еще проще:
(1) Алиса извлекает открытый ключ Боба из базы данных.
(2) Алиса шифрует свое сообщение с помощью открытого ключа Боба и посылает его Бобу.
(3) Боб расшифровывает сообщение Алисы с помощью своего закрытого ключа.
В первом протоколе Боб должен был послать Алисе ее открытый ключ прежде, чем она могла отправить ему сообщение. Второй протокол больше похож на обычную почту. Боб не участвует в протоколе до тех пор, пока он не начнет читать сообщение.
Смешанные криптосистемы
В реальном мире алгоритмы с открытыми ключами не заменяют симметричные алгоритмы и используются не для шифрования сообщений, а для шифрования ключей по следующим двум причинам:
1. Алгоритмы с открытыми ключами работают медленно. Симметричные алгоритмы по крайней мере в 1000 раз быстрее, чем алгоритмы с открытыми ключами. Да, компьютеры становятся все быстрее и быстрее и лет через 15 криптография с открытыми ключами достигнет скоростей, сравнимых с сегодняшней скоростью симметричной криптографии. Но требования к объему передаваемой информации также возрастают, и всегда будет требоваться шифровать данные быстрее, чем это сможет сделать криптография с открытыми ключами.
2. Криптосистемы с открытыми ключами уязвимы по отношению к вскрытию с выбранным открытым текстом. Если С = Е(Р), где Р - открытый текст из n возможных открытых текстов, то криптоаналитику нужно только зашифровать все n возможных открытых текстов и сравнить результаты с С (помните, ключ шифрования общедоступен). Он не сможет раскрыть ключ дешифрирования, но он сможет определить Р.
Вскрытие с выбранным открытым текстом может быть особенно эффективным, если число возможных шифрованных сообщений относительно мало. Например, если Р ‑ это денежная сумма в долларах, меньшая чем $1000000, то такое вскрытие сработает, криптоаналитик переберет весь миллион значений. Даже если Р не так хорошо определено, такое вскрытие может быть очень эффективно. Полезным может быть простое знание, что шифротекст не соответствует конкретному открытому тексту. Симметричные криптосистемы не чувствительны к вскрытиям такого типа, так как криптоаналитик не может выполнить тестовых дешифровок с неизвестным ключом.
В большинстве реализаций криптография с открытыми ключами используется для засекречивания и распространения сеансовых ключей, которые используются симметричными алгоритмами для закрытия потока сообщений. Иногда такие реализации называются смешанными (гибридными) криптосистемами.
(1)Боб посылает Алисе свой открытый ключ.
(2)Алиса создает случайный сеансовый ключ, шифрует его с помощью открытого ключа Боба и передает его Бобу.
ЕB(К)
(3)Боб расшифровывает сообщение Алисы, используя свой закрытый ключ, для получения сеансового ключа.
DB(EB(K))=K
(4)Оба участника шифруют свои сообщения с помощью одного сеансового ключа.
Использование криптографии с открытыми ключами для распределения ключей решает очень важную проблему распределения ключей. В симметричной криптографии ключ шифрования данных, если он не используется, то он просто хранится. Если Ева заполучит его, она сможет расшифровать все закрытые этим ключом сообщения. С помощью приведенного протокола при необходимости зашифровать сообщения создается сеансовый ключ, который уничтожается по окончании сеанса связи. Это значительно уменьшает риск компрометации сеансового ключа. Конечно, к компрометации чувствителен и закрытый ключ, но риска значительно меньше, так как в течение сеанса этот ключ используется только один раз для шифрования сеансового ключа.
Головоломки Меркла
Ральф Меркл (Ralph Merkle) изобрел первую схему криптографии с открытыми ключами. В 1974 году он записался на курс по компьютерной безопасности в Калифорнийском университете, Беркли, который вел Ланс Хоффман (Lance Hoffman). Темой его курсовой работы, поданной раньше срока, была "Безопасная передача данных по небезопасным каналам". Хоффман не понял предложения Меркла, и в конце концов Меркл прекратил занятия. Он продолжал работать над проблемой, несмотря на продолжающееся непонимание его результатов.
Техника Меркла основывалась на головоломках ("puzzle"), которые отправителю и получателю решить легче чем злоумышленнику. Вот как Алиса может послать шифрованное сообщение Бобу, не обмениваясь с ним ключом до того.
(1)Боб создает 220 (другими словами, больше миллиона) сообщений типа: "Это головоломка номер х. Это секретный ключ номер у ", где х - случайное число, а у - случайный секретный ключ. И х, и у отличаются в каждом сообщении. Используя симметричный алгоритм, он шифрует каждое сообщение своим 20 битным ключом и все их отправляет Алисе.
(2)Алиса выбирает одно сообщение и приступает к вскрытию грубой силой, пытаясь получить открытый текст. Эта работа является объемной, но не невозможной.
(3)Алиса шифрует свое секретное сообщение при помощи некоторого симметричного алгоритма полученным ею ключом и посылает это сообщение Бобу вместе с х.
(4)Боб знает, какой секретный ключ у он использовал в сообщении х, следовательно, он может расшифровать сообщение Алисы.
Ева может взломать эту систему, но ей придется выполнить гораздо больше работы, чем Алисе и Бобу. Для раскрытия сообщения на этапе (3) она должна будет вскрыть грубой силой каждое из 220 сообщений, отправленных Бобом на этапе (1). Сложность этого вскрытия составит 240. Значения х также не помогут Еве, ведь они на этапе (1) присвоены случайным образом. В общем случае, вычислительные затраты Евы будут равны возведенным в квадрат вычислительным затратам Алисы.
Это выигрыш (n по отношению к n2) невелик по криптографическим стандартам, но при определенных условиях может быть достаточен. Если Алиса и Боб могут проверить десять тысяч ключей в секунду, каждому из них потребуется минута для выполнения своих действий и еще одна минута для передачи головоломок от Боба к Алисе по линии связи 1.544 Мбит/с. Если вычислительные возможности Евы сравнимы с приведенными, ей потребуется около года для взлома системы. Другие алгоритмы еще более устойчивы к вскрытию.
Висновки
Контрольні питання
1. Определение, общие характеристики и возможности криптопротоколов.
2. Суть и особенности протоколов с посредником.
3. Суть и особенности арбитражных протоколов.
4. Суть и особенности попыток вскрытия (взлома) протоколов.
5. Изложите простой протокол безопасной передачи информации, основанный на симметричной криптографии.
6. Какое число ключей симметричной криптографии необходимо, если каждая пара пользователей сети использует отдельный ключ?
7. Изложите простой протокол безопасной передачи информации, основанный на асимметричной криптографии.
8. По каким причинам криптографические алгоритмы с открытыми ключами полностью не заменяют симметричные алгоритмы?
9. Изложите простой протокол безопасной передачи информации, основанный на смешанной криптографии.
10. Изложите протокол безопасной передачи информации Головоломки Меркла.
Задачі