Читайте также:
|
|
Для того чтобы иметь возможность доказывать в криптографии точные результаты, нужны математические модели основных исследуемых объектов, к которым относятся в первую очередь шифр и открытый текст. Введем сначала алгебраическую модель шифра (шифрсистемы), предложенную К. Шенноном. С моделями открытых текстов мы познакомимся ниже.
Как мы уже знаем, криптография защищает информацию с помощью шифрования — процедуры, использующей некое обратимое преобразование. При этом преобразование открытого текста в шифрованный называется зашифрованием, а обратный процесс - расшифрованием. Шифрование предполагает наличие множества обратимых преобразований. Выбор преобразования из указанного множества для зашифрования данного сообщения осуществляется с помощью ключа. Имеется однозначное соответствие между множеством ключей и множеством преобразований.
Выбор ключа естественным образом определяет функцию (вообще говоря, многозначную), отображающую множество возможных открытых текстов в множество возможных шифрованных текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть правилом зашифрования. Выбранный ключ будем называть ключом зашифрования. Требование однозначности расшифрования определяет обратную функцию, отображающую множество возможных (при выбранном ключе) шифрованных текстов в множество возможных открытых текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть правилом расшифрования. Ключ, определяющий выбор правила расшифрования, будем называть ключом расшифрования.
Формализуем сказанное.
Пусть X,K,Y — конечные множества возможных открытых текстов, ключей и шифрованных текстов соответственно; Ek : X —> Y — правило зашифрования на ключе k К. Множество {Еk: k
К} обозначим через Е, а множество {Еk (х): х
Х} — через Еk (X). Пусть Dk: Еk (X) —> X — правило расшифрования на ключе k
К, и D — это множество {Dk: k
К}.
Здесь и далее мы будем предполагать, что если k К представляется в виде k= (k3,kp), где k3 — ключ зашифрования, а kр— ключ расшифрования (причем k3
kр), то Еk понимается как функция Еk3 ,а Dk — как функция Dkp.
Определение . Шифром (шифрсистемой) назовем совокупность
A=(X,K,Y,E,D)
введенных множеств, для которых выполняются следующие свойства:
1) для любых х X и k
К выполняется равенство Dk(Ek(x)) = x;
2)
Неформально, шифр — это совокупность множеств возможных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифр-текстов (то, во что шифруется), правил зашифрования и правил расшифрования.
Отметим, что условие 1) отвечает требованию однозначности расшифрования. Условие 2) означает, что любой элемент у Y может быть представлен в виде Еk (х) для подходящих элементов х
X и k
К. Отметим также, что в общем случае утверждение "для любых k
К и у
Еk (X) выполняется равенство Еk (Dk (у)) = у" является неверным.
Легко проверить, что из условия 1) следует свойство инъективности функции Еk. Другими словами, если x1, x2 X, причем х1
х2, то при любом k
К выполняется неравенство Еk(х1)
Еk(х2).
По сути дела определение 1 вводит математическую модель, отражающую основные свойства реальных шифров. В силу этого мы будем отождествлять реальный шифр с его моделью А, которую будем называть алгебраической моделью шифра. Для подавляющего большинства известных шифров несложно составить такую модель.
Дата добавления: 2015-01-30; просмотров: 33 | Нарушение авторских прав