Файл: MethodFull.doc

Очень трудно поддерживать безопасность протокола, если большинство его участников – активные мошенники, но иногда активное мошенничество может быть обнаружено законными участниками. Конечно, протоко­лы должны быть защищены и от пассивного мошенничества.

Передача информации с использованием симметричной криптографии

Как двум сторонам безопасно обмениваться информацией? Конечно же, шифруя свои сообщения. Посмот­рим, что должно произойти, когда Василиса посылает шифрованное сообщение Ивану (полный протокол гораздо сложнее).

1. Василиса и Иван выбирают систему шифрования;

2. Василиса и Иван выбирают ключ;

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

4. Василиса посылает шифрованное сообщение Ивану;

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

Что может Бессмертник, находясь между Василисой и Иваном, узнать, подслушивая этот протокол? Если он может под­слушать только передачу на этапе (4), ей придется подвергнуть шифротекст криптоанализу. Это пассивное вскрытие представляет собой вскрытие с использованием только шифротекста, применяемые алгоритмы устойчивы (насколько нам известно) по отношению к любым вычислительным мощностям, который может заполучить Кащеев для решения проблемы.

Бессмертник, однако, не глуп (он же не Буратино). Он может также подслушать и этапы (1) и (2). Тогда ему станут известны алгоритм и ключ – также как и Ивану. Когда Кащеев перехватит сообщение на этапе (4), то ему останется только дешифровать его самостоятельно.

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

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

А Василиса? Что она может сделать, чтобы испортить протокол? Она может передать копию ключа Кащееву, и тогда он сможет читать все, что говорит Иван, и напечатать его слова в «Липецкой газете». Это серьезно, но проблема не в протоколе. Василиса и так может передавать Бессмертнику любые открытые тексты, передаваемые с использованием протокола. Конечно, то же самое может сделать и Иван. Протокол предполагает, что Василиса и Иван доверяют друг другу. Итак, симметричным криптосистемам присущи следующие проблемы:

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

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

В предположении, что каждая пара пользователей сети использует отдельный ключ, общее число ключей быстро возрастает с ростом числа пользователей. Сеть из nпользователей требуетn(n- 1)/2 ключей. На­пример, для общения 10 пользователей между собой нужно 45 различных ключей, для 100 пользователейпотребуется 4950 ключей. Решение проблемы – в уменьшении числа пользователей, но это не всегда возможно.

Однонаправленные функции

Понятие однонаправленной функции является центральным в криптографии с открытыми ключами. Не являясь протоколами непосредственно однонаправленные функции представляют собой краеугольный камень большинства протоколов.

Однонаправленные функции относительно легко вычисляются, но инвертируются с большим трудом. То есть, зная х просто рассчитать f(x), но по известному f(x) нелегко вычислить х. Здесь, "нелегко" означает, что для вы­числения х пo f(x) могут потребоваться миллионы лет, даже если над этой проблемой будут биться все компьютеры мира.

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

Это звучит красиво, но туманно и непонятно. Математически строгого доказательства существования однонаправленных функций нет, нет и реальных свидетельств возможности их построения. Не­смотря на это, многие функции выглядят в точности как однонаправленные: мы можем рассчитать их и, до сих пор, не знаем простого способа инвертировать их. Например, в ограниченной окрестности легко вычислить х², но намного сложнее х^1/2.

Итак, что же хорошего в однонаправленных функциях? Непосредственно их нельзя использовать для шифрования. Сообщение, зашифрованное однонаправленной функцией бесполезно – его невозможно дешифровать. (Упражнение: напишите на тарелке что-нибудь мелкими буквами, разбейте тарелку на качественные крошечные осколки (тарелку лучше завернуть при этом тряпку – чтобы осколки не летели из-под молотка в разные стороны) и затем отдайте их приятелю. Попросите его прочитать сообщение. Посмотрите, как он будет озадачен однонаправленной функци­ей.) Для криптографии с открытыми ключами нам нужно что-то другое.

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

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

Однонаправленные хэш-функции

У однонаправленной хэш-функции может быть множество имен: функция сжатия, функция сокращения (contraction function), краткое изложение, характерный признак, криптографическая контрольная сумма, код це­лостности сообщения (message integrity check, MIC) и код обнаружения манипуляции (manipulation detection code, MDC). Как бы она не называлась, эта функция является центральной в современной криптографии. Одно­направленные хэш-функции – это другая часть фундамента многих протоколов.

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

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

Однонаправленная хэш-функция – это хэш-функция, которая работает только в одном направлении: легко вычислить значение хэш-функции по прообразу, но трудно создать прообраз, значение хэш-функции которого равно заданной величине. Упоминавшиеся ранее хэш-функции, вообще говоря, не являются однонаправленны­ми: задав конкретный байт, не представляет труда создать строку байтов, XOR которых дает заданное значение. С однонаправленной хэш-функцией такого не выйдет. Хорошей однонаправленной хэш-функцией является хэш-функция без столкновений - трудно создать два прообраза с одинаковым значением хэш-функции.

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

Посмотрите на это как на способ получить характерные признаки файлов. Если вы хотите проверить, что у кого-то есть тот же файл, что и у вас, но вы не хотите, чтобы этот файл был передан вам, попросите послать вам значение хэш-функции. Если присланное значение хэш-функции совпадет с рассчитанным вами, то почти на­верняка чужой файл совпадает с вашим. Это особенно полезно при финансовых транзакциях, когда вы не хоти­те где-то в сети превратить снятие со счета $100 в снятие $1000. В обычных условиях вы можете использовать однонаправленную хэш-функцию без ключа, так что кто угодно может проверить значение хэш-функции.