Лекция 3.Модели шифров doc

Лекция 2. Модели шифров по К. Шеннону. Способы представления реализаций шифров.
Одним из первых ввел и систематически исследовал простую и естественную математическую модель шифра К. Шеннон в книге «Работы по теории информации и кибернетике», 1963 (раздел «Теория связи в секретных системах»). Он рассматривал так называемые «секретные системы», в которых смысл сообщения скрывается при помощи шифра или кода, но само шифрованное сообщение не скрывается, и предполагается, что противник обладает любым специальным оборудованием, необходимым для перехвата и записи передаваемых сигналов.
Рассматривается только дискретная информация, то есть считается, что сообщение, которое должно быть зашифровано, состоит из последовательности дискретных символов, каждый из которых выбран из некоторого конечного множества. Эти символы могут быть буквами или словами некоторого языка, амплитудными уровнями квантованной речи или видиосигнала.
Ядром секретной системы является собственно шифр.
Алгебраическая модель шифра. Пусть Х, К, У – некоторые конечные множества, которые названы, соответственно, множеством открытых текстов (открытых сообщений), множеством ключей и множеством шифрованных сообщений (криптограмм). На прямом произведении Х(К множеств Х и К задана функция (отображение) f: Х(К(У (f(х,()=у, х(Х, ((К, у(У). Функции f соответствует семейство отображений f(: Х(У, ((К, каждое отображение задано так: для х(Х
f((х)=f(х,().
Таким образом, f( - ограничение f на множестве Х({(}. Здесь {(} – множество состоящее из одного элемента. Заметим, что задание семейства отображений (f()((К , f(:Х(У однозначно определяет отображение f:Х(К(У, f(х,()=f((х).
Введенная четверка А=(Х,К,У,f) определяет трехосновную универсальную алгебру, сигнатура которой состоит из единственной функциональной операции f.
Определение. Введенная тройка множеств Х,К,У с функцией f:Х(К(У
А=(Х,К,У,f)
называется шифром (алгебраической моделью шифра), если выполнены два условия: 1) функция f – сюрьективна (осуществляет отображение «на» У);
2) для любого ((К функция f( инъективна (образы двух различных элементов различны).
Из 2) вытекает, что |Х|(|У|.
Запись f(х,()=у называется уравнением шифрования. Имеется в виду, что открытое сообщение х зашифровывается шифром на ключе ( и получается шифрованный текст у. Уравнением расшифрования называют запись f(-1(у)=х (f-1(у,()=х), подразумевая, что шифрованный текст у=f(х,() расшифровывается на ключе ( и получается исходное открытое сообщение х. Для краткости, в ряде случаев, используют и более простые обозначения уравнений шифрования и расшифрования, а именно, соответственно: (х=у и (-1у=х.
Требование инъективности отображений (f()((К в определении шифра равносильно требованию возможности однозначного расшифрования криптограммы (однозначного восстановления открытого текста по известным шифрованному тексту и ключу). Требование же сюрьективности отображения f не играет существенной роли и оно обычно вводится для устранения некоторых технических, с точки зрения математики, дополнительных неудобств, то есть для упрощения изложения. В ряде случаев мы будем отказываться от этого требования, если его наличие будет усложнять описание или анализ шифра. Таким образом, наличие или отсутствие сюрьективности отображения f в используемом определении шифра будет следовать из текста.
Введенная модель шифра отражает лишь функциональные свойства шифрования и расшифрования в классических (с точки зрения истории криптографии) системах шифрования (в системах с симметричным ключом). В этой модели открытый текст (или шифрованный текст) – это лишь элемент абстрактного множества Х (или У), не учитывающий особенностей языка, его статистических свойств, вообще говоря, не являющийся текстом в его привычном понимании. При детализации модели шифра в ряде случаев указывают природу элементов множеств.
Рассмотрим примеры.
Обозначим через I некоторый алфавит, а через I* -множество всех слов в алфавите I, то есть множество конечных последовательностей (i1,i2,,iL), ij(I, j({1,,L}, L({1,2,.}
Шифр простой замены. Пусть Х=М – некоторое подмножество из I*, а К – множество всех подстановок на I (К=S(I) - симметрическая группа подстановок на I). Для каждого g(К определим fg , положив для (i1,i2,,iL) из М
fg( i1,i2,,iL)=g(i1),g(i2),,g(iL). Положем дополнительно
f(i1,i2,,iL, g)= fg( i1,i2,,iL)
и У=f(М)={f(i1,i2,,iL,g): g(S(I), (i1,i2,,iL)(М}. Таким образом, нами определен шифр А=(М, S(I), У, f) простой замены, более точно: алгебраическая модель шифра простой замены с множеством открытых текстов Х=М. Иногда в качестве шифра простой замены выступает шифр, в котором Х(I(I2(...(IL и для шифрования открытых текстов длины k слов выбирается подстановка gk из S(I).
Шифр перестановки. Положим Х – множество открытых (содержательных) текстов в алфавите I длины кратной Т. К=SТ – симметрическая группа подстановок степени Т, для g(SТ определим fg положив для (i1,i2,,iТ)(Х
fg(i1,i2,,iТ)=(ig(1),ig(2),,ig(Т));
доопределим fg на остальных элементах из Х по правилу: текст х(Х делится на отрезки длины Т и каждый отрезок длины Т шифруется на ключе g по указанному выше закону шифрования. Последовательность, составленная из букв образов зашифрованных слов является шифрованным текстом, соответсветсвующим открытому тексту х и ключу g. Таким образом, нами определена функция f:Х(К(У и шифр перестановки (Х,SТ,У,f). Для шифрования текста длины не кратной Т его дополняют буквами до длины кратной Т.
Шифр гаммирования. Пусть буквы алфавита I упорядочены в некотором естественном порядке. «Отождествим» номера этих букв с самими буквами. То есть формально положим I={1,2,,n}, |I|=n. Положим Х – некоторое подмножество множества IL, К(IL. Для ключа (=(1,(2,,(L из К и открытого текста х= i1,i2,,iL их Х положим f((i1,i2,,iL)=y1,y2,,yL, где yj=ij+(j mod(n), j({1,,L}. Часто под шифром гаммирования понимают и следующие способы шифрования: yj=ij-(j; yj=(j- ij mod(n).


Поточный шифр. Шифр поточной замены. Введем сначала вспомогательный шифр (I,Г,У,f) для шифрования букв алфавита I. Для ключа (1(Г, и буквы (открытого текста) i(I шифрованный текст имеет вид f(1(i)=у. Обозначим через К – множество ключей поточного шифра. Для натурального числа L введем отображение Ф: К(ГL, для фиксированного ключа ((К положим Ф(()=(1,(2,,(L. Поточный шифр (IL,К,F,У`) для вспомогательного шифра (Х=I,К=Г,У,f) шифрует открытый текст i1,i2,,iL на ключе ((К по правилу
F((i1,i2,,iL)= f(1(i1), f(2(i2),, f(L(iL),
где f((i)=f(i,().
Поточным шифром замены мы называем поточный шифр, для которого опорный шифр имеет вид (Х=I,К=Г,У=I,f ), а (f()((Г – семейство подстановок на I. Примерами поточных шифров служат шифры гаммирования, шифры простой замены. Поточный шифр с опорным шифром вида: I=К={1,2,,n}, f(i, ()=i+( mod |I| так же называют шифром гаммирования. При этом условно различают программный шифр гаммирования, в случае |К|<|I|L, и случайный шифр гаммирования, в случае К=IL, Ф – тождественное отображение.
Более общее понятие поточного шифра состоит в том, что в качестве множества открытых текстов рассматриваются все последовательности алфавита I длины не превосходящей некоторого L(0). Для шифрования текстов длины L изпользуется гамма ФL(()=(1,(2,,(L. Таким образом, используются L функций Фj, j({1,,L(0)}.
Произведение шифров.
Произведением шифров А1=(Х1,К1,У1,f1), А2=(Х2,К2,У2,f2), У1(Х2 называют шифр А=(Х1,К1хК2,У2,f), для которого f(х,((1,(2))=f2(f1(х,(1),(2), ((1,(2)(К1хК2.
Транзитивность шифра.
Шифр А=(Х,К,У,f) называют транзитивным, если при любых х(Х и у(У найдется ((К, при котором f(х,()=у. Исходя из введенных определений легко доказывается, что для транзитивного шифра
|Х|(|У|(|К|.
Основные параметры шифра (/Про/ и др.). Ряд требований к шифрам формулируется с использованием понятий, точное определение которых будет дано позднее. Тем не менее, на качественном уровне понимания, эти параметры можно трактовать следующим образом.
Стойкость шифра. Ряд шифров являются совершенными в том смысле, что положение противника, стремящегося к их дешифрованию, не облегчается в результате перехвата шифртекста, то есть наличие криптограммы не уменьшает неопределенности в возможном выборе открытого текста. Такие шифры относят к так называемому классу теоретически стойких шифров. Ряд шифров, а это многие практически используемые шифры, таковы, что эта неопределенность при перехваченной криптограмме полностью исчезает, то есть становится известным, что данная криптограмма может быть получена шифрованием только единственного открытого текста (неизвестно только какого). Уровень стойкости таких систем оценивается по затратам времени и сил, необходимых для получения этого единственного открытого текста. При больших затратах или малой вероятности успеха в дешифровании, говорят, что шифр практически стойкий.
Объем ключа. Ключ шифрования (он же ключ расшифрования) должен быть неизвестен противнику и находиться как в передающем пункте связи, так и в приемном пункте. Обычная практика использования ключа состоит в том, что он используется как одноразовый шприц – единожды, при шифровании лишь одного открытого текста. Для регулярной связи корреспондентов, следовательно, надо иметь в их пунктах связи достаточно большое количество ключей, то есть должна решаться задача секретной доставки ключей. Эта задача решается более просто, если объем каждого ключа сравнительно небольшой.
Сложность выполнения операций шифрования и расшифрования. Эти операции должны быть по способу выполнения по возможности простыми. Если они выполняются вручную, то их сложность приводит к большим затратам времени на их выполнение и появлению ошибок. При использовании шифровальной аппаратуры возникают вопросы о простоте технической реализации аппаратуры, ее стоимости и о достижении необходимой скорости выполнения операций, связанных с процессами шифрования и расшифрования.
Разрастание числа ошибок. В некоторых типах шифров ошибка в одной букве, допущенная при шифровании, приводит к большому числу ошибок в расшифрованном тексте. Такие ошибки разрастаются в результате операций расшифрования, вызывая значительную потерю информации, и часто требует повторного зашифрования текста и передачи новой криптограммы. Естественно, при выборе шифра для связи стараются минимизировать это возрастание числа ошибок.
Помехоустойчивость шифра. При действии помех в линиях связи происходит искажение текста криптограммы, что приводит при расшифровании к искажениям открытого текста, а зачастую и к нечитаемости текста. Свойство шифра противостоять разрастанию ошибок при расшифровании текстов называют его помехоустойчивостью.
Имитостойкость шифра. К активным действиям противника в канале связи относят его попытки навязать абоненту сети связи ложную информация путем искажения шифрованного текста в канале связи, либо его замене на ранее переданный шифртекст, а также и другие действия противника, ведущие к принятию ложной информации. Шифры обладающие свойством противостоять таким попыткам навязывания ложной информации называются имитостойкими.
Увеличение объема сообщения. Для некоторых шифров объем сообщения увеличивается в результате операции шифрования. Этот нежелательный эффект проявляется, например, при попытке выровнить статистику сообщения путем добавления некоторых вспомогательных симолов (“пустышек”), или при рандомизации открытого сообщения, то есть, по сути, применения к нему некоторого пропорционального кода.
Основные свойства модели шифра.
Важным классом шифров является введенные выше так называемые транзитивные шифры, то есть шифры, для которых уравнение f(х,()=у разрешимо относительно ((К при любых парах (х,у)(Х(У и так называемые t-транзитивные шифры, шифры, для которых система уравнений f(х(j),()=у(j) , j({1,,t} имеет решение относительно ((К для любых подмножеств {х(1),х(2),,х(t)}(Х мощности t и любых подмножеств {у(1),у(2),,у(t)}(У мощности t .
Эндоморфный шифр.
Другой важный класс шифров представляют так называемые эндоморфные шифры (термин предложил К. Шеннон), то есть шифры (Х,К,У,f), для которых множество открытых текстов Х совпадает с множеством криптограмм У. Для таких шифров (Х,К,У,f) каждое преобразование f(, ((К является биекцией Х в Х (подстановкой на Х). Множество таких биекций обозначают через П(К,f)={f(: ((К}, а сам эндоморфный шифр - через А=(Х,П(К,f)) и называют подстановочной моделью эндоморфного шифра. При этом под ключом этого шифра понимают биекцию ((П(К,f). Уравнение шифрования записывают в виде (х=у, уравнение расшифования записывают в виде (-1у=х.
Групповой шифр.
Эндоморфный шифр, у которого множество подстановок П(К,f) является смежным классом по некоторой подгруппе из S(Х) называют групповым шифром.
Транзитивный шифр, для которого |Х|=|К| называют минимальным шифром.
Для эндоморфных шифров А1=(Х,П(К1,f1)) А2=(Х,П(К2,f2)) используют введенное ранее понятие произведения шифров А1(А2=(Х, П(К1,f1)( П(К2,f2), где П(К1,f1)( П(К2,f2)={(1(2: (1(П(К1,f1), (2(П(К2,f2)}. Очевидно, произведение эндоморфных шифров будет транзитивным шифром, если таковым яаляется хотя бы один из них.
Эквивалентные ключи шифра.
Определение. Ключи (, (` шифра (Х,К,У,f) называются эквивалентными, если при любом х(Х
f(х,()= f(х,(`).
Вероятностная модель шифра. Одно из важнейших предположений К.Шеннона при исследовании секретных систем состояло в том, что каждому возможному передаваемому сообщению (открытому тексту) соответствует априорная вероятность, определяемая вероятностным процессом получения сообщения (см. ниже параграф 2.3 и главу 4) Аналогично, имеется и априорные вероятности использования различных ключей шифра. Эти вероятностные расределения на множестве открытых текстов и множестве ключей характеризуют априорные знания криптоаналитика противника относительно используемого шифра. При этом Шеннон предполагал, что сам шифр известен противнику.




13PAGE 14115


13PAGE 14315


13PAGE 15











Заголовок 2 Заголовок 4 Заголовок 515

Приложенные файлы

  • doc 8680299
    Размер файла: 63 kB Загрузок: 0

Добавить комментарий