Laby_MiSZI / Лабораторная работа 5
.docЛабораторная работа № 5
Цель работы: освоить криптосистемы с общим ключом.
Криптосистемы с общим ключом
Проблема распределения ключей
Серьезной проблемой является распределение и управление ключами. В криптосистеме с частными ключами каждое коммуникационное звено требует отдельного ключа. Для двух пользователей требуется только один ключ, но когда к системе с уже существующими пользователями каждый раз добавляется по одному пользователю, то требуется дополнительных ключей. Это означает, что система с пользователями требует различных ключей. Система, показанная на рис.1, имеет 8 пользователей, так что для нее требуются 28 ключей.
Криптосистема с общим ключом, как подсказывает название, имеет ключ, который является общим и поэтому доступным для всех сторон, которые желают поддерживать связь. Это решает проблему распределения ключей — они могут быть опубликованы в чем-то похожем на телефонную книгу, например. Устраняется также потребность для поддерживающих связь сторон в заблаговременном согласовании ключей. Алиса может посылать зашифрованное сообщение Бобу, даже если она никогда не имела никакого предыдущего контакта с ним, что важно для таких приложений, как электронная торговля, где требуется безопасная связь с незнакомцами.
Однако опубликованный ключ вводит новую проблему. Раз сообщение было зашифровано с ключом, то не должно быть возможности восстанавливать сообщение из закодированного текста даже со знанием ключа, который, как сказано, является доступным каждому. Это требует введения концепции односторонней функции, функции, которая не может быть (легко) обратимой, но должна обладать некоторой "лазейкой", чтобы с помощью некоторого секретного знания получатель мог обращать процесс получения сообщения.
Рис.1. Ключи для системы с частными ключами (а) и системы с общим ключом (б)
На первый взгляд, это выглядит так, как если бы система с общим ключом требовала большего количества ключей, т.к. каждая дуплексная связь требует двух ключей, по одному для каждого направления. Однако в системе с общим ключом, хотя имеется 56 коммуникационных связей, каждая связь с одним и тем же адресатом использует один и тот же ключ (общий ключ этого адресата), так что фактически требуется только 8 ключей. Кроме того, каждая связывающаяся сторона должна хранить только один ключ — свой секретный частный ключ, вместо ключей в случае системы с частными ключами.
Системы с общим ключом также называют асимметричными системами, потому что процесс, используемый для декодирования, не является простым обращением процесса кодирования. В этом состоит их главное отличие от систем с частными ключами, которые называют симметричными системами, потому что функция дешифрования является обратной по отношению к функции шифрования (и наоборот).
Односторонние функции
Односторонняя (one-way) функция — это функция, которую просто вычислять, но трудно обращать. Пример — умножение больших чисел. Мы можем вычислить без слишком больших трудностей произведение:
но обратный процесс — факторизация (разложение на множители) числа 8 616 460 799 существенно труднее. В.С. Джевонс (W.S. Jevons), рассматривавший эту проблему в 1873 г., резюмировал, что "мы можем легко... сделать некоторую вещь, но можем иметь много неприятностей, если попытаемся разделить ее".
В качестве операции факторизации для системы с общим ключом нам бы хотелось иметь такую функцию, которая при работе на сообщении давала бы в результате криптограмму , по которой практически невозможно раскрыть . Другими словами, мы должны быть способны легко выполнять функцию (так, чтобы криптосистема оставалась реализуемой), но реализовать было бы практически невозможно. Заметим, что обращение функции теоретически всегда возможно (скажем, просто путем вычисления для каждого возможного сообщения до тех пор, пока результат не совпадет с ). Однако стоимость выполнения таких вычислений была бы значительно выше, чем значимость информации, которая могла быть получена таким способом, или время, затраченное на это было бы так велико, что полученная информация оказалась бы устаревшей.
Односторонние функции, используемые для криптографических целей, должны обладать еще одним свойством — они должны иметь специальную "лазейку", т.е. способ, с помощью которого некто, обладающий специальным знанием, смог бы восстановить по , затратив разумное количество усилий. Это секретное знание формирует частный ключ, который тайно хранится получателем, позволяя ему расшифровывать сообщения.
Система работает следующим образом.
-
Каждый пользователь имеет пару ключей и .
-
Сообщение шифруется с помощью функции .
-
Выполняется дешифрация с помощью функции .
-
и проектируются так, чтобы:
-
для заданных и , можно было легко находить ;
-
для заданного было бы нереально найти (то есть функция должна быть односторонней);
-
для заданных и , можно было легко найти (то есть функция должна иметь "лазейку", задаваемую параметром ).
-
Для использования в криптосистемах были предложены различные функции.
-
Ключевой обмен Диффи-Хеллмана (Diffie-Hellman). Основан на трудности вычисления дискретных логарифмов полей, которая возрастает по сравнению с вычислениями на основе степенных функций. Это не совсем шифр, но это первая опубликованная система с общим ключом.
-
RSA (криптосистема Райвеста, Шамира, Альдемана). Основана на трудности факторизации (разбиения на множители) произведения по сравнению с операцией умножения. Это наиболее популярная система с общим ключом, используемая, например, для почтовой программы, реализующей протокол POP (Post Office Protocol). Но в вычислительном отношении она довольно дорогая, и коммерческое ее использование в США подлежит патентованию.
-
Knapsack. Методика с таким странным названием основана на трудности разделения суммы на индивидуальные элементы по сравнению с добавлением этих элементов в начало суммы. Было много успешных атак на эту систему и в результате она используется довольно редко. Однако, она менее сложна, чем RSA, и до появления более современных систем с эллиптическими кривыми ее считали системой, вполне оправдывающей свои обещания, т.е. обладающей низкой сложностью и относительной безопасностью.
-
Эллиптические кривые. Эллиптические кривые — это специальные линии, определенные над первичным полем. Задав некоторую точку на этой линии, легче вычислять и все другие ее точки. Без генерации всех возможных точек (что не практично, если поле достаточно велико) обращение операции довольно затруднительно. Эти схемы являются довольно многообещающими, потому что кодирование и декодирование в них не очень-то сложное. Если не касаться защиты, то эта схема обладает всеми преимуществами предыдущей.
-
Коды с исправлением ошибок. Хотя код с исправлением ошибок способен исправлять до (d - l)/2 ошибок, но без набора декодирующих правил единственный способ реализовать эту возможность состоит в том, чтобы сравнивать полученный вектор с каждым кодовым словом и выбирать тот, который находится на расстоянии (d- l)/2 от него. Для длинных кодов это практически невозможно. Поэтому можно сформировать криптосистему, использующую код с исправлением ошибок, выполняя перестановки генерирующей матрицы. Исходный генератор формирует частный ключ, позволяющий декодировать сообщения, а генератор с перестановками используется в качестве общего ключа. Посылаемые сообщения маскируются добавлением ошибок, которые подслушивающий не может удалить, т.к. генератор с перестановками не позволяет выполнить простое декодирование.
Ключевой обмен Диффи-Хеллмана
Протокол обмена ключей Диффи-Хеллмана в действительности не является обычной системой с общим ключом, т.к. передаваемый секрет случаен, но его можно использовать для передачи информации, применяя общий секрет для шифрования передаваемых данных. Это была первая опубликованная система с общим ключом. В ней возникают трудности, связанные с вычислениями логарифмов первичных полей, которые значительно выше, чем при вычислениях с помощью экспоненциальных функций.
Протокол выполняет обмен секретом между двумя сторонами по опасному каналу, не требуя ни знания, ни даже существования этого секрета. Работает это следующим образом.
-
Алиса и Боб соглашаются использовать генератор и простой модуль .
-
Алиса генерирует случайное число . Это ее частный ключ. Она вычисляет свой общий ключ , который равен .
-
Подобным же образом Боб генерирует случайный частный ключ и общий ключ . Алиса и Боб обмениваются их общими ключами и .
-
Алиса принимает ключ и использует свой частный ключ для следующего вычисления: .
-
Боб также может вычислить по ключу , который он принимает от Алисы, и своему частному ключу , т.к. .
-
И Алиса и Боб теперь знают , но подслушивающий не может вычислять по наблюдениям и .
В качестве примера такого обмена рассмотрим следующую процедуру:
-
и .
-
Алиса получает случайный , Боб выбирает .
-
Алиса вычисляет .
-
Боб вычисляет .
-
Алиса посылает Бобу число 5, а Боб посылает Алисе число 9.
-
Алиса вычисляет.
-
Боб вычисляет .
-
Поэтому .
Обратите внимание, что общий секрет случаен, т.к. , так что его нельзя использовать, чтобы напрямую посылать информацию. Если Алиса и Боб не выбирают свои частные ключи чисто случайно, то это знание можно использовать для нападения на систему.
Когда и опубликованы, то нападение на эту систему становится эффективным с помощью задачи дискретного логарифмирования. означает, что . Поэтому Ева может находить , вычисляя . В вышеупомянутом примере нахождение тривиально, но очень трудно, если велико.