Разработка алгоритмов защиты информации в сетях АТМ
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
.
Неформально под односторонней функцией понимается эффективно вычислимая функция, для обращения которой (то есть для поиска хотя бы одного значения аргумента по заданному значению функции) не существует эффективных алгоритмов. При этом, обратная функция может и не существовать.
Под функцией понимается семейство отображений {fn}, где fn: ?n>?m, m=m(n). Для простоты предполагают, что n пробегает натуральный ряд, а отображения fn определены всюду. Функция f называется честной, если существует полином q(x), такой что для любого n:
q(m(n))?n. (2.3.1.1)
Формально понятие односторонней функции описывается следующим образом: Честная функция f называется односторонней, если:
существует полиномиальный алгоритм, который для всякого x вычисляет f(x);
для любой полиномиальной вероятностной машины Тьюринга А выполнено следующее - пусть строка х выбрана случайным образом из множества ?n, тогда для любого полинома р и всех достаточно больших n:
P{f(A(F(x)))=f(x)}<1/p(n). (2.3.1.2)
Второе условие качественно означает следующее: любая полиномиальная вероятностная машина Тьюринга А может по данному y найти х из уравнения f(x)=y лишь с пренебрежимо малой вероятностью. При этом требование честности опустить нельзя. Поскольку длина входного слова f(x) машины А равна m, ей может не хватить полиномиального от m времени просто на выписывание строки х.
Существование односторонних функций является необходимым условием стойкости многих криптосистем.
Фунцкцией-ловушкой называется односторонняя функция, для которой обратную функцию вычислить просто, если имеется некоторая дополнительная информация, и сложно, если такая информация отсутствует.
Криптосистемы с открытым ключом основываются на односторонних функциях-ловушках. При этом открытый ключ определяет конкретную реализацию функции, а секретный ключ даёт информацию о ловушке. Любой, знающий ловушку, может легко вычислять функцию в обоих направлениях, но тот, у кого такая информация отсутствует, может производить вычисления только в одном направлении. Прямое направление используется для шифрования и для верификации цифровых подписей, а обратное - для дешифрования и выработки цифровой подписи.
Во всех криптосистемах с открытым ключом, чем больше длина ключа, тем выше различие между усилиями, необходимыми для вычисления функции в прямом и обратном направлениях (для того, кто не обладает информацией о ловушке).
Все практические криптосистемы с открытым ключом основываются на функциях, считающихся односторонними, но это свойство не было доказано в отношении ни одной из них. Это означает, что теоретически возможно создание алгоритма, позволяющего легко вычислить обратную функцию без знания информации о ловушке. В этом случае, криптосистема, основанная на этой функции, станет бесполезной. С другой стороны, теоретические исследования могут привести к доказательству существования конкретной нижней границы сложности обращения некоторой функции, и это доказательство будет существенным событием, которое окажет значительное позитивное влияние на развитие криптографии.
2.4 Электронные цифровые подписи
Передача сообщения отправителем (пользователь А) получателю (пользователь В) предполагает передачу данных, побуждающих пользователей к определённым действиям. Передача данных может представлять собой передачу фондов между банками, продажу акций или облигаций на автоматизированном рынке, а также передачу приказов (сигналов) по каналам электросвязи. Участники нуждаются в защите от множества злонамеренных действий, к которым относятся:
отказ - отправитель в последствии отказывается от переданного сообщения;
фальсификация - получатель подделывает сообщение;
изменение - получатель вносит изменения в сообщение;
маскировка - пользователь маскируется под другого.
Для верификации (подтверждения) сообщения М (пользователь А - пользователю В) необходимо следующее:
отправитель (пользователь А) должен внести в М подпись, содержащую дополнительную информацию, зависящую от М и, в общем случае, от получателя сообщения и известной только отправителю kA;
необходимо, чтобы правильную подпись М SIG{kA, M, идентификатор В} в сообщении для пользователя В нельзя было составить без kA;
для предупреждения повторного использования устаревших сообщений процедура составления подписи зависит от времени;
пользователь В должен иметь возможность удостовериться, SIG{kA, M, идентификатор В} - есть правильная подпись М пользователем А.
Рассмотрим эти пункты подробнее:
. Подпись сообщения - определённый способ шифрования М путём криптографического преобразования. Закрываемым элементом kA в преобразовании
>SIG{kA, M, Идентификатор В} (2.4.1)
является ключ криптопреобразования.
Во всех практических криптографических системах kA принадлежит конечному множеству ключей. Исчерпывающая проверка всех ключей, задаваемая соответствующими парами
>SIG{kA, M, Идентификатор В} (2.4.2)
в общем должна привести к определению ключа kА злоумышленником. Если множество К достаточно велико и ключ k определён методом случайного выбора, то полная проверка ключей невозможна. Г