58) Односторонние функции. Ключевой обмен Диффи-Хеллмана.

Проблема распределения ключей

Серьезной проблемой является распределение и управление ключами. В крип­тосистеме с частными ключами каждое коммуникационное звено требует отдельного ключа. Для двух пользователей требуется только один ключ, но когда к системе с уже существующими пользователями каждый раз до­бавляется по одному пользователю, то требуется дополнительных клю­чей. Это означает, что система с пользователями требует различных ключей. Система, показанная на рис.1, имеет 8 пользователей, так что для нее требуются 28 ключей.

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

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

Рис.1. Ключи для системы с частными ключами (а) и системы с общим ключом (б)

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

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

Односторонние функции

Односторонняя (one-way) функция — это функция, которую просто вычислять, но трудно обращать. Пример — умножение больших чисел. Мы можем вычислить без слишком больших трудностей произведение:

но обратный процесс — факторизация (разложение на множители) числа 8 616 460 799 существенно труднее. В.С. Джевонс (W.S. Jevons), рассматривавший эту проблему в 1873 г., резю­мировал, что "мы можем легко... сделать некоторую вещь, но можем иметь много неприятностей, если попытаемся разделить ее".

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

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

Система работает следующим образом.

1. Каждый пользователь имеет пару ключей и .

2. Сообщение шифруется с помощью функции .

3. Выполняется дешифрация с помощью функции .

4. и проектируются так, чтобы:

   1. для заданных и , можно было легко находить ;

   2. для заданного было бы нереально найти (то есть функция должна быть односторонней);

   3. для заданных и , можно было легко найти (то есть функция должна иметь "лазейку", задаваемую параметром ).

Для использования в криптосистемах были предложены различные функции.

1. Ключевой обмен Диффи-Хеллмана (Diffie-Hellman). Основан на трудности вычисления дискретных логарифмов полей, которая возрастает по сравнению с вычислениями на основе степенных функций. Это не совсем шифр, но это первая опубликованная система с общим ключом.

2. RSA (криптосистема Райвеста, Шамира, Альдемана). Основана на трудности факторизации (разбиения на множители) произведения по сравнению с операцией умножения. Это наиболее популярная система с общим ключом, используемая, например, для почтовой программы, реали­зующей протокол POP (Post Office Protocol). Но в вычислительном отно­шении она довольно дорогая, и коммерческое ее использование в США подлежит патентованию.

3. Knapsack. Методика с таким странным названием основана на трудности разделения суммы на индивидуальные элементы по сравнению с добавлением этих элементов в начало суммы. Было много успешных атак на эту систему и в результате она используется довольно редко. Однако, она ме­нее сложна, чем RSA, и до появления более современных систем с эллиптическими кривыми ее считали системой, вполне оправдывающей свои обещания, т.е. обладающей низкой сложностью и относительной безопасностью.

4. Эллиптические кривые. Эллиптические кривые — это специальные ли­нии, определенные над первичным полем. Задав некоторую точку на этой линии, легче вычислять и все другие ее точки. Без генерации всех возмож­ных точек (что не практично, если поле достаточно велико) обращение операции довольно затруднительно. Эти схемы являются довольно много­обещающими, потому что кодирование и декодирование в них не очень-то сложное. Если не касаться защиты, то эта схема обладает всеми преиму­ществами предыдущей.

5. Коды с исправлением ошибок. Хотя код с исправлением ошибок способен исправлять до (d - l)/2 ошибок, но без набора декоди­рующих правил единственный способ реализовать эту возможность со­стоит в том, чтобы сравнивать полученный вектор с каждым кодовым сло­вом и выбирать тот, который находится на расстоянии (d- l)/2 от него. Для длинных кодов это практически невозможно. Поэтому можно сформировать криптосистему, использующую код с исправлением ошибок, выполняя перестановки генерирующей матрицы. Исходный генератор формирует частный ключ, позволяющий декодировать сообщения, а гене­ратор с перестановками используется в качестве общего ключа. Посылае­мые сообщения маскируются добавлением ошибок, которые подслуши­вающий не может удалить, т.к. генератор с перестановками не позволяет выполнить простое декодирование.

Ключевой обмен Диффи-Хеллмана

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

Протокол выполняет обмен секретом между двумя сторонами по опасному каналу, не требуя ни знания, ни даже существования этого секрета. Работает это следующим образом.

1. Алиса и Боб соглашаются использовать генератор и простой модуль .

2. Алиса генерирует случайное число . Это ее частный ключ. Она вычисля­ет свой общий ключ , который равен .

3. Подобным же образом Боб генерирует случайный частный ключ и общий ключ . Алиса и Боб обмениваются их общими ключами и .

4. Алиса принимает ключ и использует свой частный ключ для следую­щего вычисления: .

5. Боб также может вычислить по ключу , который он принимает от Али­сы, и своему частному ключу , т.к. .

6. И Алиса и Боб теперь знают , но подслушивающий не может вычислять по наблюдениям и .

В качестве примера такого обмена рассмотрим следующую процедуру:

1. и .

2. Алиса получает случайный , Боб выбирает .

3. Алиса вычисляет .

4. Боб вычисляет .

5. Алиса посылает Бобу число 5, а Боб посылает Алисе число 9.

6. Алиса вычисляет .

7. Боб вычисляет .

8. Поэтому .

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

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

76