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