Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Формальные модели шифров

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

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

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

Формализуем сказанное.

Пусть X,K,Y — конечные множества возможных от­крытых текстов, ключей и шифрованных текстов соответст­венно; E_k : X —> Y — правило зашифрования на ключе k К. Множество {Е_k: k К} обозначим через Е, а мно­жество {Е_k (х): х Х} — через Е_k (X). Пусть D_k: Е_k (X) —> X — правило расшифрования на ключе k К, и D — это множество {D_k: k К}.

Здесь и далее мы будем предполагать, что если k К представляется в виде k= (k₃,k_p), где k₃ — ключ зашифро­вания, а k_р— ключ расшифрования (причем k₃ k_р), то Е_k понимается как функция Е_k3 ,а D_k — как функция D_kp.

Определение . Шифром (шифрсистемой) назовем сово­купность

_A=(X,K,Y,E,D)

введенных множеств, для которых выполняются следующие свойства:

1) для любых х X и k К выполняется равенство D_k(E_k(x)) = x;

2)

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

Отметим, что условие 1) отвечает требованию однознач­ности расшифрования. Условие 2) означает, что любой элемент у Y может быть представлен в виде Е_k (х) для под­ходящих элементов х X и k К. Отметим также, что в общем случае утверждение "для любых k К и у Е_k (X) выполняется равенство Е_k (D_k (у)) = у" является неверным.

Легко проверить, что из условия 1) следует свойство инъективности функции Е_k. Другими словами, если x₁, x₂ X, причем х₁ х₂, то при любом k К выполняется неравен­ство Е_k(х₁) Е_k(х₂).

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

Дата добавления: 2015-01-30; просмотров: 33 | Нарушение авторских прав