6. КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ ДАННЫХ "Чтоб мысль врага узнать, ему вскрывают сердце. А письма-и подавно..." В . Шекспир , "Король Лир" С распространением письменности в человеческом обществе появилась потребность в обмене письмами и сообщениями, что, в свою очередь, вызвало необходимость сокрытия содержимого письменных сообщений от посторонних. Методы сокрытия содержимого письменных сообщений можно разделить на три группы. К первой группе относятся методы маскировки, которые осуществляют сокрытие самого факта наличия сообщения, например, с помощью симпатических чернил. Вторую группу составляют различные методы тайнописи или криптографии (от греческих слов ktyptos - тайный и grapho - пишу), которые применяются для изменения сообщения с целью сделать текст непонятным для непосвященных. С развитием науки и техники стали применяться методы третьей группы, которые ориентированы на создание специальных технических устройств, например, инвертирования речи. Далее будем рассматривать только методы второй группы, а именно - методы криптографии. Метод криптографии можно определить как некоторое множество отображений одного пространства (пространства возможных сообщений) в другое пространство (пространство возможных криптограмм) [7]. Каждое конкретное отображение из этого множества соответствует шифрованию при помощи конкретного ключа. Дадим определения этих понятий. Сообщение, текст которого необходимо сделать непонятным для посторонних, будем называть исходным сообщением или открытым текстом. Шифрование данных -процесс преобразования открытых данных в зашифрованные данные (шифртекст, криптограмму) при помощи шифра. Иногда этот процесс называют зашифрованием данных. Шифр - совокупность обратимых преобразований множества возможных открытых данных во множество возможных шифртекстов, осуществляемых по определенным правилам с применением ключей. Ключ - конкретное секретное состояние некоторого параметра (параметров), обеспечиващее выбор одного преобразования из совокупности возможных для используемого метода шифрования. Различные методы шифрования применялись и в древности. До наших дней дошли зашифрованные записи египетского вельможи, высеченные на его гробнице. Развитию тайнописи способствовали войны. Письменные приказы и донесения обязательно шифровались, чтобы захват гонцов не позволил противнику получить важную информацию. Например, римский император Цезарь пользовался в своей военной и личной переписке шифром, сущность которого состояла в замене каждой буквы латинского языка на следуищую букву алфавита. Тогда знаменитая фраза: "VENI, VIDI, VICI" ("Пришел, увидел, победил"), которой Цезарь, как передает Плутарх в его биографии, известил одного из своих друзей в Риме о быстро одержанной им победе над понтийским царем Фарнаком при Золе в 47 г. до н.э., в зашифрованном виде будет иметь следующий вид: "XFOJ, XJEF, XJDJ". До наших дней также дошли арабские шифры IX века, материалы венецианской школы криптографии эпохи Возрождения и многое другое. Методы тайнописи, например, использовались композиторами для включения своего имени в музыкальные произведения. Иоганн Себастьян Бах кодировал свою фамилию (старогерманское написание В-А-С-В) нотами, которые составляли основную тему произведения. Несколько органных фуг Баха представляют вариации относительно такой темы. Для переписки с посольствами России в других странах в XVI веке использовалась так называемая тарабарская грамота. Этот шифр основывался на замене одной согласной буквы на другую: б-ш, в-щ, г-ч, д-ц, ж-х, з-ф, к-т, л-с, н-р, н-п. При использовании тарабарской грамоты строка букв "Чолуцамь шлея моллии" есть зашифрованная фраза "Государь всея России". Интенсивное развитие криптография получила в годы Первой мировой войны, охватившей большую территорию и многие государства. Вот, например, как описывает Ярослав Гашек в своем романе "Похождения бравого солдата Швейка во время мировой войны", написанном в 1921-1922 гг., один из шифров австровенгерской армии: ".. капитан Сагнер отошел от окна. Большим педагогическим тактом он не обладал, поэтому у него много времени ушло на то, чтобы составить в голове полный план лекции о значении страницы сто шестьдесят первой. - Итак, господа!... Перед вами совершенно секретная информация, касающаяся новой системы шифровки полевых депеш... - Вам, вероятно, показалось непонятным, почему полковник рекомендовал читать именно сто шестьдесят первую страницу романа Л . Гангофера . Это, господа, ключ к новой шифровальной системе, введенной согласно новому распоряжению штаба армейского корпуса, к которому мы прикомандированы... - Получаем депешу Sache-mit На сто шестьдесят первой странице ищем слово Sache. В первый раз оно встречается пятьдесят вторым словом. Тогда на противоположной сто шестьдесят первой странице ищем пятьдесят вторую букву сверху. Заметьте себе, что это А. И так далее. Очень остроумно, господа, просто, и нет никакой возможности расшифровать без ключа сто шестьдесят первой страницы". Практически одновременно с криптографией стал развиваться и криптоанализ - наука о раскрытии шифров (ключей) по шифртексту. Вторая мировая война дала новый толчок развитию криптографии и криптоанализа, что было вызвано применением технических средств связи и боевого управления. Для разработки новых шифров и работы в качестве криптоаналитиков привлекались ведущие ученые. В годы Второй мировой войны был разработан ряд механических устройств для шифрования сообщений. В 1949 году была опубликована статья Клода Шеннона "Теория связи в секретных системах" [7], которая подвела научную базу под криптографию и криптоанализ. С этого времени стали говорить о новой науке КРИПТМОГИИ (от греческого kryptos - тайный и logos - сообщение), - науке о преобразовании информации для обеспечения ее секретности. Этап развития криптографии и криптоанализа до 1949 года стали называть донаучной криптологией . Повсеместное внедрение в практику человеческой деятельности ИВС поставило проблему хранения и использования секретных ключей. Действительно, для того, чтобы абонент сети мог связаться с N другими абонентами, ему необходимо иметь N ключей. Решению этой проблемы была посвящена статья Диффи и Хеллмана "Новые направления в криптографии" [9], опубликованная в 1976 году. Эта статья открыла новый этап в развитии криптологии - этап криптосистем с открытыми (общими, публичными) ключами. 6.1. Основы теории К.Шеннона Шеннон рассмотрел модель [7], в которой источник сообщений порождает открытый текст X. Источник ключей генерирует ключ Z. Шифратор преобразовывает открытый текст X с помощью ключа Я в шифртекст Y: Y=Tz X Дешифратор, получив зашифрованное сообщение Y, выполняет обратную операцию: X=Tx(-1) Y Модель секретной системы К. Шеннона приведена на рис.6.1. ╡°°°°°°°°≈ ▀источник▀ Z ╡°°°°°°°°°°°°°°°°°°°≈ секретный ▀ключей │°°°°°° °°²°°°°°°°°°°°°°°°°°°°²°°°°≈ (защищенный) ≤°°°°°°°°╠ ▀ ≥°°°°°°°°°°°°°°°°° °╠ ▀ канал ▀ ≤°°°°°°²°°°°°°°°°╠ ▀ ▀ X V V ╡°°°°°°°°°≈ ╡°°°°°°°°°≈ ╡≥°°°°°°°°≈ Y ╡°°°°°°°°°°°▄ X ▀пpиемник ▀ ▀источник │°>▄Шифpатоp │°°° °°▄ Дешифpатоp│°°°°>▄сообщений▀ ▀сообщений▀ ≤°°°°°°°°°╠ ▀ ≤°°°°°°°°°°°╠ ≤°°°°°°°°°╠ ≤°°°°°°°°°╠ ╡°°°°°°°°V°°°°°°≈ ▀ Кpиптоаналитик│°°°> X' ▀ пpотивника ▀ ≤°°°°°°°°°°°°°°°╠°°°> Z' pис.6.1. Модель К.Шеннона. Задачей криптоаналитика противника является получение открытого текста и ключа на основе анализа шифртекста. Шеннон рассмотрел вопросы теоретической и практической секретности. Для определения теоретической секретности Шеннон сформулировал следующие вопросы. 1. Насколько устойчива система, если криптоаналитик противника не ограничен временем и обладает всеми необходимыми средствами для анализа криптограмм? 2. Имеет ли криптограмма единственное решение? 3. Какой объем шифртекста необходимо перехватить криптоаналитику, чтобы решение стало единственным? Для ответа на эти вопросы Шеннон ввел понятие совершенной секретности с помощью следующего условия: для всех Y апостериорные вероятности равны априорным вероятностям, то есть перехват зашифрованного сообщения не дает криптоаналитику противника никакой информации. По теореме Бейеса Py(X)=P(X)Px(Y)/P(Y) где P(X) - априорная вероятность сообщения Х; Рx(Y)- условная вероятность криптограммы Y при условии, что выбрано сообщение X, то есть сумма вероятностей всех тех ключей, которые переводят сообщение X в криптограмму Y; P(Y) - вероятность получения криптограммы Y; Рy(Х)- апостериорная вероятность сообщения X при условии, что перехвачена криптограмма Y. Для совершенной секретности величины Рy(Х) и Р(Х) должны быть равны для любых X и Y. Теорема 6.1. Необходимое и достаточное условие для совершенной секретности состоит в том, что Рy(X)=P(X) для всех X и Y, то есть Px(Y) не должно зависеть от X. Секретная система включает в себя два статистических выбора: выбор сообщения и выбор ключа. Можно измерять количество информации, создаваемое при выборе сообщения X, через энтропию H(X): Н(Х)= - сум. Р(Х)*logР(Х), (x) где суммирование осуществляется по всем возможным сообщениям. Аналогично при выборе ключа: Н(Z)= - сум. P(Z)*logP(Z). (z) Шеннон ввел в рассмотрение функции ненадежности ключа и сообщения (Ну(Z) и Ну(Х) соответственно): Нy(Z)= -сум. P(Y,Z)*log Py(Z). (Y,Z) Нy(Х)= -сум. Р(Y,X)*log Py(Х) , (W,X) где P(Y,Z) - вероятность ключа Z и криптограммы Y; Ру(Z) - апостериорная вероятность ключа Z, если перехвачена криптограмма Y; P(Y,X) - вероятность сообщения X и криптограммы Y; Рy(X) - апостериорная вероятность сообщения X, если перехвачена криптограмма Y; Суммирование для Ну(Z) проводится по всем возможным криптограммам определенной длины (например, длины N) и по всем возможным ключам. Тогда Ну(Z) и Hу(Х) являются функциями от N (количества перехваченных символов), что будет обозначаться Ну(Z,N) и Ну(Х,N) соответственно. Теорема 6.2. Ненадежность ключа Hy(Z,N) - невозрастающая функция N. Это означает, что при S>=N справедливы неравенства: Hy(Z,S)<=Hy(Z,N); Нy(Х,S)<=Нy(Х,N): Hy(Х,N)<=Hy(Z,N). Последнее неравенство следует из неравенства Нy(Х)<=Hy(Х,Z)=Нy(Z)+Hy,z(Х) и из условия Hy,z(X)=0, так как Z и Y полностью определяют X. Так как сообщения и ключи выбираются независимо, можно записать: Н(Х,Z)=Н(Х)+Н(Z). свойства функции ненадежности раскрываются следующими теоремами. Теорема 6.3. Ненадежность сообщений для произведения секретных систем не меньше, чем ненадежность для одной системы. Для случая, когда системы S1,S2,.....Sn имеют функции ненадежности H1,...,Hm соответственно, и система Т определяется как T=p1S1+p2S2+...+pmSm=@ , сум. pi=1 (i=1,M) следущая теорема. Теорема 6.4. Ненадежность для взвешенной суммы систем ограничена неравенствами: сум.(Pi*Hi) <= H <= сум.(Pi*Hi)-сум.(Pi*LogPi) (i=1,M) Эти границы нельзя улучшить. В теореме 6.4 Hi может означать ненадежность ключа или ненадежность сообщения. Шеннон определил идеальную систему как такую, в которой Hy(Z) и Hy(Х) не стремятся к нулю при стремлении N к бесконечности. Если в системе Hy(Z)=H(Z), то она называется строго идеальной системой. Теорема 6.5. Необходимое и достаточное условие строгой идеальности системы Т заключается в том, что для любых двух ключей отображение Тi**(-1)*Тj должно являться сохраняющим меру отображения пространства сообщений в само себя. Система называется замкнутой, если для каждого ключа, каждому сообщению соответствует одна криптограама и наоборот. Для таких систем справедлива следущая теорема. Теорема 6.6. Если все символы алфавита исходных сообщений равновероятны и выбираются независимо, то любая замкнутая система будет строго идеальной. Шеннон ввел расстояние единственности - наименьшее N, такое, что Hy(Z) близка к нулю. Расстояние единственности приводит к получению единственного решения криптограммы. Для определения практической секретности Шеннон сфоpмулировал вопрос: надежна ли секретная система, если криптоаналитик противника располагает ограниченным временем и ограниченными возможностями для анализа шифртекста? Шеннон назвал рабочей характеpистикой системы средний объем работы W(N), необходимый для определения ключа, если криптограмма содержит N букв. Из этого определения следует, что для создания хорошего шиФра необходимо максимизировать минимальный объем работы, который должен проделать криптоаналитик противника для нахождения решения. Для противодействия методам статистического анализа криптограмм Шеннон предложил использовать два метода: рассеивание и перемешивание [5]. В настоящее время известно большое число методов криптографического закрытия данных. Классификация основных из них приведена на рис.6.2 [2]. ╡°°°°°°°°°°°°°°°°°°°°°°°°°≈ ▀Методы кpиптогpафического▀ ▀закpытия данных ▀ ≤°°° °°°°°°°°°°°°°°°°°°°°°╠ │°°°°°°°°°°°°°°°°°°°°°° °°°°°°°°°°°°°°°°°°≈ Шифpование Кодиpование Дpугие виды ▀ ▀ ▀ │замена │смысловое │сжатие ▀(подстановка) │символьное │pасшиpение │пеpестановка ≤комбиниpованное ≤pассечение- │аналитические pазнесение ▀ пpеобpазования ≤комбиниpованные методы Рис 6.2. Классификация методов криптографического закрытия данных. Принципиально шифрование не отличается от кодирования. В криптографии под шифрованием понимается процесс, в котором криптографическому преобразованию подвергается каждый символ открытого текста, а под кодированием - замену элементов открытого текста (символов, комбинаций символов, слов и т.п.) кодами. 6.2. Методы шифрования 6.2.1. Методы замены Шифрование методом замены (подстановки) основано на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно-однозначное отображение некоторого конечного множества М на себя. Число N элементов этого множества называется степенью подстановки. Природа множества M роли не играет, поэтому можно считать, что M={1,2,...,N}. Если при данной подстановке S число j переходит в Ij, то подстановка обозначается символом S: ╡ ≈ ▀ 1 2 ... n ▀ S=▀ I1 I2 ... In▀ ≤ ╠ В этой записи числа 1,2,...,n можно произвольным образом переставлять, соответственно переставляя числа I1,I2,...In. Результат последовательного выполнения двух подстановок S1 и S2 одной и той же степени также является подстановкой, которая называется произведением подстановок S1 и S2 и обозначается S1S2. Произведение подстановок обладает свойством ассоциативности. Пусть S - произвольная подстановка степени n. Если для некоторого j число Ij отлично от j, то говорят, что подстановка S действительно перемещает число j; в противном случае говорят, что подстановка S оставляет число j на месте. Две подстановки называются независимыми, если они не имеют общих действительно перемещаемых чисел. Количество m чисел, действительно перемещаемых подстановкой S, называется длиной цикла подстановки. Подстановка S называется транспозицией, если существует пара (j1,j2) различных элементов из M, удовлетворящих условиям: Ij1=j2, Ij2=j2, Ij=j для каждого j пp. {M\{j1,j2}}. Любая подстановка разлагается в произведение транспозиций. Разложение подстановки в произведение независимых подстановок однозначно (с точностью до порядка множителей). В криптографии рассматриваются четыре типа подстановки (замены): моноалфавитная, гомофоническая, полиалфавитная и полиграммная. Далее всюду в примерах, где необходимо, будем использовать кодирование букв русского алфавита, приведенное в таблице 6.1. Знак "_" в таблице 6.1 и далее означает пробел. Таблица 6.1 Буква А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я _ Код 010203040506070809101112131415161718192021222324252627282930313233 При моноалфавитной замене каждой букве алфавита открытого текста ставится в соответствие одна буква шифртекста из этого же алфавита. Пpимеp 6.1 Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ". Подстановка задана таблицей 6.2. Таблица 6.2 Алфавит исходного текста А Б В Г Д ... Алфавит шифpтекста _ Я Ю Э Ь Шифртекст: "ИШМРТЮ_УШЫАЩ_ФЫУТЧ". Основным недостатком рассмотренного метода является то, что статистические свойства открытого текста (частоты повторения букв) сохраняются в шифртексте. Общая формула моноалфавитной замены выглядит следующим образом: Yi=k1*Xi+k2(mod N) где уi- i-й символ aлфавитa; k1 и k2- константы; Xi- i-й символ открытого текста (номер буквы в алфавите); n - длина используемого алфавита. Шифр, задаваемый фоpмулой: yi=xi+ki(mod n), где ki- i-ая буква ключа, в качестве которого используются слово или фраза, называется шифpом Вижинера. Пример 6.2. Открытый текст: "ЗАМЕНА". Ключ: "КЛЮЧ" (таблица 6.3). Таблица 6.3 З А М Е Н А К Л Ю Ч К Л y1=8+11(mod 33)=19 -> Т y2=1+12(mod 33)=13 -> М у3=13+31(mod ЗЗ)=11-> К y4=6+24(mod 33)=30 -> Э у5=14+11(mod 33)=25 -> Ш y6=1+12(mod 33)=13 -> М. Шифртекст: "ТМКЭШМ". Шифры Бофора используют фоpмулы: уi=ki-xi(mod n) и yi=xi-ki(mod n). Гомофоническая замена одному символу открытого текста ставит в соответствие несколько символов шифртекста. Этот метод применяется для искажения статистических свойств шифртекста. Пример 6.3. Открытый текст: "ЗАМЕНА". Подстановка задана таблицей 6.4. Шифртекст: "76 17 32 97 55 31". Таблица 6.4 Алфавит откpытого А Б ... Е Ж З ... М Н ... текста 17 23 97 47 76 32 55 Алфавит шифpтекста 31 44 51 67 19 28 84 48 63 15 33 59 61 34 Таким образом, при гомофонической замене каждая буква открытого текста заменяется по очереди цифрами соответствующего столбца. Полиафавитная подстановка использует несколько алфавитов шифртекста. Пусть используется k алфавитов. Тогда открытый текст: Х=X1X2...XkXk+1...X2kX2k+1... заменяется шифртекстом: Y=f1(x1)f2(x2)...fk(xk)Fk+1(Xk+1)...F2k(X2k)F2k+1(X2k+1) где Fi(Xj) означает символ шифртекста алфавита i для символа открытого текста Xj. Пример 6.4. Открытый текст: "ЗАМЕНА", k=3. Подстановка задана таблицей из примера 6.3. Шифртекст: "76 31 61 97 84 48". Полиграммная замена формируется из одного алфавита с помощью специальных правил. В качестве примера рассмотрим шифр Плэйфера [3]. В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов XiXi+1. Каждая пара символов открытого текста заменяется на пару символов из матрицы следующим образом: 1) если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый); 2) если символы находятся в одном столбце, то каждый символ пары заменяется на символ, расположенный ниже его в столбце (за последним нижним символом следует верхний); 3) если символы пары находятся в разных строках и столбцах, то они считаются противоположными углами прямоугольника. Символ, находящийся в левом углу, заменяется на символ, стоящий в другом левом углу; замена символа, находящегося в правом углу, осуществляется аналогично; 4) если в открытом тексте встречаются два одинаковых символа подряд, то перед шифрованием между шали вставляется специальный символ (например, тире). Пример 6.5. Открытый текст: "ШИФР_ПЛЭЙФЕРА". Матрица алфавита представлена в таблице 6.5. Таблица 6.5 А Х Б М Ц В Ч Г Н Ш Д О Е Щ , Х У П . З Ъ Р И Й С Ь К Э Т Л Ю Я _ Ы Ф - Шифртекст: "РДЫИ,-СТ-И.ХЧС" При рассмотрении этих видов шифров становится очевидным, что чем больше длина ключа (например, в шифре Виженера), тем лучше шифр. Существенного улучшения свойств шифртекста можно достигнуть при использовании шифров с автоключом. Шифр, в котором сам открытый текст или получающаяся криптограмма используются в качестве "ключа", называется шифром с автоключом. Шифрование в этом случае начинается с ключа, называемого первичным, и продолжается с помощью открытого текста или криптограммы, смещенной на длину первичного ключа. Пример 6.6. Открытый текст: "ШИФРОВАНИЕ_ЗАМЕНОЙ". Первичный ключ: "КЛЮЧ" Схема шифрования с автоключом при использовании открытого текста представлена в таблице 6.6. Таблица 6.6 Ш И Ф Р О В А Н И Е _ З А М Е Н О Й К Л Ю Ч Ш И Ф Р О В А Н И Е _ З А М 362152414012223124093422101939221623 В Ф Т З Ж Л Х Ю Ч И А Х Й Т Е Х П Ц Схема шифрования с автоключом при использовании криптограммы представлена в таблице 6.7. Таблица 6.7 Ш И Ф Р О В А Н И Е _ З А М Е Н О Й К Л Ю Ч В Ф Т З С Ч У Х Ъ Э У Э Ы Й 362152411824202227305330244326443920 В Ф Т З C Ч У Х Ъ Э У Э Ы Й Щ К Й У 6.2.2. Методы перестановки При использовании для шифрования данных методов перестановки символы открытого текста переставляются в соответствии с некоторыми правилами. Пример 6.7. Открытый текст: "ВВЮТОВАНИЬаПЕРЕСТАНОВКОИ". Ключ (правило перестановки): группы из 8 букв с порядковыми номерами 1.2.....8 переставить в порядок 3-8-1-5-2-7-6-4. Шифртекст: "ФНШОИАВР_СИЕЕЕРПННТВАОКО". Можно использовать и усложненную перестановку. Для этого открытый текст записывается в матрицу по определенному ключу k1. Шифртекст образуется при считывании из этой матрицы по ключу k2. Пример 6.8. Открытый текст: "ШИФРОВАНИЕ_ПЕРЕСТАНОВКОЙ". Матрица из четырех столбцов (рис.6.3). Ключи: k1 5-3-1-2-4-6; k2 4-2-3-1. 1 И Е _ П 2 Е Р Е С 3 О В А Н запись по стpокам в соответствии 4 Т А Н О с ключом k1 5 Ш И Ф Р 6 В К О Й чтение по столбцам в соответствии k1/k2 1 2 3 4 с ключом k2 Рис.6.3 Шифртекст: "ПСНОРЙЕРВАИК_ЕАНФОИЕОТШВ". Наиболее сложные перестановки осуществляются по гамильтоновым путям, которых в графе может быть несколько. Пример 6.9. Открытый текст: "ШИФРОВАНИЕ_ПЕРЕСТАНОВКОИ". Ключ: гамильтонов путь на графе (рис.6.4). Шифртекст: "ШАОНИРФВИЕЕСЕП_РТОВИАОНК" Необходимо отметить, что для данного графа из восьми вершин можно предложить несколько маршрутов записи открытого текста и несколько гамильтоновых путей для чтения криптограмм. ╡°°°°°°°°°°°°≈ ╡°° °°°°°°°°°°°°°°°°°²°°°°°°°°°°°°²°°°°°°°°°°°°°> °°≈ °°>▀1 ▀ ╡°°°°°°°°°°°²°°°°°°°°°°°°²°°°°°°°°°°°°°°▄2 ▀ °°>≤° ╠ ╡V° <°°°°°°°°²°°°°°°°°°° °≥ <°°°°°°°°°°°°≥^°╠ ╡> ▀ ▀3 │°°°°°°°°°²°°°°°°°°°°>4 ▀ ▀ ▀ ▀ ≤°°≥°°°°°°°°°²°°°°≈ ≤°°╠ ▀ ▀ ▀ ╡≥° °°°°°°°°°╠ ≤°°°°°>°° °°°°°°°°°°°°°°²°°°°°╠ ▀ ▀5 │°°°°°°°°°°°°°°°°°°°°>6 ▀ ▀ ▀ ≤^°≥°°°°°°°°°°°°°°≈ ≤ °╠ ▀ ╡°> ╡V° °°°°╠ ╡°°°°°°°°°°°²°°°°°°╠ ╡≥°≈ ▀ ▀7 <°°°°°°°°°╠ ≤°°°°°°°°°°°°°°°°°°°°°>▄8 │°╠ ≤°°≥°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°>≥°°╠ Рис.6.4 В 1991 г. В.М.Кузьмч предложил схему перестановки, основанной на кубике Рубика. Согласно этой схеме открытый текст записывается в ячейки граней куба по строкам. После осуществления заданного числа заданных поворотов слоев куба считывание шифртекста осуществляется по столбикам. Сложность расшифрования в этом случае определяется количеством ячеек на гранях куба и сложностью выполненных поворотов слоев. Перестановка, основанная на кубике Рубика, получила название объемной (многомерной) перестановки. В 1992-1994 г.г. идея применения объемной перестановки для шифрования открытого текста получила дальнейшее развитие. Усовершенствованная схема перестановок по принципу кубика Рубика, в которой наряду с открытым текстом перестановке подвергаются и функциональные элементы самого алгоритма шифрования, легла в основу секретной системы "Рубикон". В качестве прообразов пространственных многомерных структур , на основании объемных преобразований которых осуществляются перестановки, в системе "Рубикон" используются трехмерные куб и тэтраэдр. Другой особенностью системы "Рубикон" является генерация уникальной версии алгоритма и ключа криптографических преобразований на основании некоторого секретного параметра (пароля). Это обеспечивает как дополнительные трудности для криптоанализа перехваченных сообщений нарушителем (неопределенность примененного алгоритма), так и возможность априорного задания требуемой криптостойкости. Криптостойкость данной системы определяется длиной ключа, криптостойкостью отдельных функциональных элементов алгоритма криптографических преобразований, а также количеством таких преобразований. Использование уникальных алгоритма и ключа шифрования для каждого пользователя системы соответствует положению теории К.Шеннона о том, что абсолютно стойкий шифр может быть получен только при использовании "ленты однократного применения", то есть уникальных параметров при каждом осуществлении шифрования. 6.2.3. Методы аналитических преобразований Шифрование методами аналитических преобразований основано на понятии односторонней функции [8]. Будем говорить, что функция у=f(х) является односторонней, если она за сравнительно небольшое число операций преобразует элемент открытого текста х в элемент шифртекста у для всех значений х из области определения, а обратная операция (вычисление x=F**-1(y) при известном шифртексте) является вычислительно трудоемкой. В качестве односторонней функции можно использовать следуящие преобразования: 1 ) умножение матриц; 2) решение задачи об укладке ранца; 3) вычисление значения полинома по модулю; 4) экспоненциальные преобразования и другие. Метод умножения матриц использует преобразование вида: Y=CX. где Y=||y1,y2, ...,yn||**Т . С=||Cij|| X=||x1,x2,...,xn|| Пример 6.10. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно таблице 6.1). Матрица С: C=▀1 3 2▀ ▀2 1 5▀ ▀3 2 1▀ ▀1 3 2▀ ▀16▀ ▀2 1 5▀ X▀17▀ =▀85 94 91▀ ▀3 2 1▀ ▀09▀ ▀1 3 2▀ ▀11▀ ▀2 1 5▀ X ▀01▀ = ▀30 63 43▀ ▀3 2 1▀ ▀08▀ Ши@текст: "85 94 91 30 63 43". Задача об укладке ранца [5] формулируется следуящим образом. Задан вектор С=|c1,c2,...,cn| который используется для шифрования сообщения, каждый символ si которого представлен последовательностью из n бит si=|x1,x2,...,xn|**t, Xk пp. {0,1}. Шифртекст получается как скалярное произведение Сsi. Пример 6.11. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно таблице 6.1). Вектор С={1,3,5,7,11}. Запишем код каждой буквы открытого текста в двоичном виде, используя пять разрядов. П Р И К А З 100000 10001 01001 01011 00001 01000 Произведем соответствующие операции: y1=1x1=1 y2=1x1+1x11=12 y3=1x3+1x11=14 y4=1x3+1x7+1x11=21 у5=1x11=11 y6=1x3=3. Шифртекст: "01 12 14 21 11 03". Метод полиномов основан на преобразовании yi=xi**n+a1*xi**(n-1)+...+an*xi( mod р). где n, а1,а2...аn- целые неотрицательные числа, не превосходящие р, 1<=хi,уi<=р; р - большое простое число. Пример 6.12. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно таблице 6.1). Полином: уi=xi**3+2xi**2+3xi+4(mod 991). y1=16**3+2*16**2+3*16+4(mod 991)=696 y2=17**3+2*17**2+3*16+4(mod 991)=591 у3=9**3+2*9**2+3*9+4(mod 991)=922 у4=11**3+2*11**2+З*11+4(mod 991)=619 y5=1**3+2*1**2+3*1+4(mod 991)=10 у6=8**3+2*8**2+З*8+4(mod 991)=668. Шифртекст: "696 591 922 619 010 668". Экспоненциальный шифр [5] использует преобразование вида уi =a**(xi) (mod р), где хi- целое, 1<=хi<=р-1; p - большое простое число; a - целое, 1<=a<=p. Пример 6.13. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно таблице 6.1); a=3; p=991. y1=3**16(mod 991)=43046721 (mod 991 )=654 у2=З**17(mod 991)=129140163(mod 991)=971 у3=3**9(mod 991) = 19683 (mod 991 ) =854 y4=3**11(mod 991)=177147(mod 991)=749 у5=3**1 (mod 991 )=3 y6=3**8 (mod 991 )=6561 (mod 991 )=615. ШиФртекст: "654 971 854 749 003 615". Особым случаем метода аналитических преобразований является метод, основанный на преобразовании yi=xi ++ hi где уi- i-й символ шифртекста; хi- i-й символ открытого текста; hi- i-й символ гаммы; ++ - выполняемая операция (наложение гаммы). Различают два случая: метод конечной гаммы и метод бесконечной гаммы. В качестве конечной гаммы может использоваться фраза, а в качестве бесконечной - последовательность, вырабатываемая датчиком псевдослучайных чисел. Пример 6.14. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно таблице 6.1). Гамма: "ГАММА" ("04 01 13 13 01"). Операция: сложение по mod 33. y1= 16+4(mod 33)=20 y2= 17+1(mod 33)=18 y3= 9+13(mod 33)=22 y4= 11+13(mod 33)=24 y5= 1+1(mod 33)=2 y6= 8+4(mod 33)=12. Шифртекст: "УСХЧБЛ" ("20 18 22 24 02 12"). Пример 6.15. Открытый текст: "ПРИКАЗ" ("16 17 09 11 01 08" согласно таблице 6.1). Первые значения датчика: "21794567". Операция: сложение по mod 2. Запишем код каждой буквы открытого текста в двоичном виде, используя пять разрядов, а каждую цифру гаммы - используя четыре разряда: 10000 10001 01001 01011 00001 01000 ++ 00100 00101 11100 10100 01010 11001 10100 10100 10101 11111 01011 10001. Шифртекст: "УУФЮКР". 6.2.4. Комбинированные meтоды Шифрование комбинированными методами основывается на результатах, полученных К.Шенноном. Наиболее часто применяются такие комбинации, как подстановка и гамма, перестановка и гамма , подстановка и перестановка, гамма и гамма. В качестве примера рассмотрим шифр, предложенный Д.Френдбергом [6], который комбинирует многоалфавитную подстановку с генератором псевдослучайных чисел, суть алгоритма поясняется схемой, подставленной на рис.6.5. Особенность данного алгоритма состоит в том, что при большом объеме шифртекста частотные характеристики символов шифртекста близки к равномерному распределению независимо от содержания открытого текста. 1)Установление начального состояния генератора псевдослучайных чисел 2)Установление начального списка подстановки 3)Все символы открытого текста зашифрованы? 4) если да - конец работы, если нет -продолжить 5)осуществление замены 6)генерация случайного числа 7)перестановка местами знаков в списке замены 8) переход на шаг 4 Рисунок 6.5 Схема алгоритма Д. Френдберга Пример 6.16. Открытый текст: "АБРАКАДАБРА". Используем одноалфавитную замену согласно таблице 6.8. Таблица 6.8 А Б Д К Р X V N R S Последовательность чисел, вырабатываемая датчиком: 31412543125. 1. у1=Х. После перестановки символов исходного алфавита получаем таблицу 6.9 (h1=3). Таблица 6.9 Д Б А К Р X V N R S 2. у2=V. Таблица 6.9 после перестановки (h2=1) принимает вид, представленный в таблице 6.10. Таблица 6.10 Б Д А К Р X V N R S Осуществляя дальнейшие преобразования в соответствии с алгоритмом Френдберга, получаем шифртекст: "XVSNSXXSSSN". Одной из разновидностей метода гаммирования является наиболее часто применяемый метод многократного наложения гамм. Необходимо отметить, что если уi=Гk(Гl(xi)), то Гk(Гl(xi))=Гl(Гk(xi)). (6.1) Тождество (6.1) называют основным свойством гаммы. Пример 6.17. Открытый текст: "ШИФРЫ"(25 09 21 17 28"); Г1="ГАММА" ("04 01 13 13 01"); Г2="ТЕКСТ" ("19 06 11 18 19"), согласно таблице 6.1. Используемая операция: сложение по mod 2. 1. Y1i=xi ++ h1i 11001 01001 10101 10001 11100 ++ 00100 00001 01101 01101 00001 11101 01000 11000 11100 11101. 2. У2i=y1i++ h2i 11101 01000 11000 11100 11101 ++ 10011 00110 01011 10010 10011 01110 01110 10011 01110 01110. Проведем операцию шифрования, поменяв порядок применения гамм. ' 1. У1i =xi++h2i 11001 01001 10101 10001 11100 10011 00110 01011 10010 10011 01010 01111 11110 00011 01111. 2. У2i'=y1i'++h1i 01010 01111 11110 00011 01111 ++ 00100 00001 01101 01101 00001 01110 01110 10011 01110 01110. Таким образом, y2i=y2i', что является подтверждением основного свойства гаммы. При составлении комбинированных шифров необходимо проявлять осторожность, так как неправильный выбор составлявших шифров может привести к исходному открытому тексту. Простейшим примером служит наложение одной гаммы дважды. Пример 6.18. Открытый текст: "ШИФРЫ"("25 09 21 17 28"); Г1=Г2="ГАММА" ("04 01 13 13 01"), согласно таблице 6.1. Используемая операция: сложение по mod 2: 11001 01001 10101 10001 11100 ++ 00100 00001 01101 01101 00001 ++ 00100 00001 01101 01101 00001 11001 01001 10101 10001 11100. Таким образом, результат шифрования представляет собой открытый текст. Комбинация методов подстановки и перестановки была применена в 1974 году фирмой IBM при разработке системы ЛЮЦИФЕР [6]. Система ЛЮЦИФЕР строится на базе блоков подстановки (S-блоков) и блоков перестановки (Р-блоков). Блок подстановки включает линейные и нелинейные преобразования. Первый преобразователь S-блока осуществляет развертку двоичного числа из n разрядов в число по основанию 2**n. Второй преобразователь осуществляет свертку этого числа. Блок перестановки осуществляет преобразование n разрядного входного числа в n разрядное число. Входные данные (открытый текст) последовательно проходят через чередующиеся слои 32-разрядных Р-блоков и 8-разрядных S-блоков. Реализация шифрования данных в системе ЛЮЦИФЕР программными средствами показала низкую производительность, поэтому P и S - блоки были реализованы аппаратно, это позволило достичь скорости шифрования до 100 Кбайт/с. Опыт, полученный при разработке и эксплуатации системы ЛЮЦИФЕР, позволил создать стандарт шифрования данных DES (Data Encryption Standard) [6]. 6.3. Основы криптоанализа Введенные К.Шенноном функции ненадежности довольно резко стремятся к нулю. Поэтому с большой вероятностью можно говорить о точке, в которой решение криптограммы становится единственным. Найденное при этом число букв шифртекста No будем называть расстоянием единственности [7]. Рассмотрим множество сообщений длины N символов для данного языка. Коэффициент языка длиной N определяется как r=Н(Х)/N, где H(Х) - количество информации при выборе сообщения X. Избыточность языка с коэффициентом r определяется по формуле: D=R-г, где R - абсолютный коэффициент языка; R=log2 L, где L - длина алфавита языка. Для английского языка R=log2 26=4,7 бит на букву. Тогда No=H(Z)/D, где H(Z) - количество информации при выборе ключа Z. Вычислим количество букв, необходимое для раскрытия сообщения, зашифрованного методом подстановки, в алфавите длиной L. Если все ключи равновероятны, то число возможных ключей равно L!. Тогда No=H(Z)/D=log2 L!/D. Для английского языка No=log2 26!/3,2=27,6. Таким образом, 27-28 букв достаточно для раскрытия рассматриваемого шифра с помощью частотного анализа. Если объем перехваченного шифртекста превосходит точку единственности, криптограмма в принципе может быть решена перебором всех возможных ключей, пока не получится единственное решение (сообщение, имеющее смысл в данном языке). Многие виды шифров могут быть раскрыты с помощью статистического анализа, потому что все естественные языки имеют характерное частотное распределение букв. Например, для английского языка частоты появления букв приведены в таблице 6.11 [6]. Таблица 6.11 Буква Частота % Буква Частота % Буква Частота % A 8,1 K 0,4 V 0,9 B 1,4 L 3,4 W 1,5 C 2,7 M 2,5 X 0,2 D 3,9 N 7,2 Y 1,9 E 13,0 O 7,9 Z 0,1 F 2,9 P 2,0 G 2,0 R 6,9 H 5,2 S 6,1 I 6,5 T 10,5 J 0,2 U 2,4 Из таблицы 6.11 видно, что Е - наиболее часто встречающаяся буква в английском языке, а Z - наиболее редкая. Многие сообщения, зашифрованные методами перестановки или замены, сохраняют характерное частотное распределение букв и тем самым предоставляют возможность раскрытия шифра. Введем меру точности: MR= сум. (Pi-1/L)**2 i=0..(L-1) где сум. Pi=1; i=0..(L-1) pi- вероятность (частота) появления i-й буквы; L - количество символов в алфавите. Для английского языка MR= сум. (Pi-1/26)**2=сум.( Pi**2)-2/26+1/26=сум. Pi**2 -0.038=0.03 i=0..25 Общее число пар букв, которые могут быть выбраны из текста длиной N символов, есть C2n=N*(N-1)/2 Пусть fi- частота i-й буквы в тексте; сум. fi=N Тогда определим индекс соответствия Ic следующим образом: Ic=(сум. fi*(fi-1))/(N*(N-1)) i=0..25 Теоретическое значение для английского языка Ic=0,066. Если шифр использует m алфавитов, то можно записать: Ic=(1/m)*((N-m)/(N-1))*0,066+((m-1)/m)*(N/(N-1))*0,038. Таким образом, шифртексты, для которых Ic>0,066, дают криптоаналитику информацию о том, что, вероятно, использовалась моноалфавитная замена. Если 0.052<=Ic<=0.066, то, вероятно, использовался двухалфавитный подстановочный шифр. Значения индексов соответствия для различного числа алфавитов приведены в таблице 6.12. Процесс криптоанализа можно представить следумцим образом. Криптоаналитик берет наиболее часто встречающийся в шифртексте символ и предполагает, что это пробел. Затем криптоаналитик берет следующий наиболее часто встречащийся символ и предполагает, что это Е (для английского языка), и т.д. Путем проб и ошибок такой метод может привести к решению задачи. Кроме того, при подставлении букв вместо символов анализируемого шифртекста криптоаналитик учитывает частоты появления сочетаний из двух букв (диаграмм), трех букв (триграмм) и т.д [1 ]. Таблица 6.12 Число алфавитов (m) Ожидаемый Ic(большие N) 1 0.066 2 0.052 3 0.047 4 0.045 5 0.044 10 0.041 m>>10 0.038 Одним из наиболее часто используемых приемов криптоаналитика является метод вероятных слов. Вероятные слова - это слова, части слов и выражения, которые можно ожидать в перехваченном шифртексте вследствие того, что они характерны для данного источника сообщений. В качестве вероятных слов можно рассматривать общеупотребительные слова или отдельные слоги, которые характерны для данного языка. Например, для английского языка можно использовать такие вероятные слова, как the, that, and, -tion и т.п. Предполагая, что некоторая часть шифртекста является вероятным словом, криптоаналитик получает часть ключа. Эта часть ключа используется для расшифровки других частей шифртекста и служит критерием согласованности. Если другие части шифртекста становятся понятными, то предлоложение, принятое при использовании вероятного слова, подтверждается. Естественно, что современные ЭВМ значительно усиливают мощь криптоаналитика. Ход рассуждений криптоаналитиков при расшифровке моноалфавитной замены замечательно передан писателями Артуром Конан Дойлем в повести "Пляшущие человечки" и Эдгаром Алланом По в повести "Золотой жук". Задача криптоаналитика значительно усложняется, если он имеет дело с равномерным распределением символов в шифртексте (Ic=0.038 для английского языка). Поэтому при построении шифров стремятся обеспечить равномерность символов шифртекста. 6.4 Методы кодирования Как уже отмечалось выше, под кодированием понимается замена элементов открытого текста (букв, слов, фраз и т.п.) кодами. Различают символьное и смысловое кодирование. При символьном кодировании каждый знак алфавита открытого текста заменяется соответствущим символом. Примером символьного кодирования служит азбука Морзе, а также методы шифрования заменой и перестановкой. Рассмотрим метод символьного кодирования, который использует предыдущие символы открытого текста. Этот метод, называемый метод стопки книг, был предложен Б.Я.Рябко [4]. Предположим, что нужно передать сообщение X из алфавита А, в котором буквы алфавита отождествлены с числами 1,2,..L, где L - число элементов алфавита А. Каждой букве алфавита соответствует код ki, 1=1..L. При появлении в сообщении X очередной буквы хj ее код представляется кодом номера позиции j, занимаемой в данный момент буквой хj в списке. Это дает возможность на приемном конце по коду номера позиции j определить букву хj. После кодирования буквы хj одновременно на приемном и передающих концах перемещают букву хj в начало списка, увеличивая тем самым на единицу номера букв, стоявших на позициях от 1 до j-1. Номера букв, стоявших на позициях от j+1 до L, остаются без изменений. В результате кодирования открытого текста в начале списка будут находиться буквы, которые наиболее часто встречались в открытом тексте. Пример 6.19. Открытый текст: "АБРАКАДАБРА". Алфавит: {А,Б,Д,К,Р}. Начальный список соответствует последовательности букв в алфавите и ему соответствует список кодов {К1,К2,КЗ,К4,К5}. Схема кодирования показана на рис.6.9. К1 А А Б P А К А Д А Б Р А К2 Б Б А Б Р А К А Д А Б Р К3 Д Д Д A Б Р Р К К Д А Б К4 К К К Д Д Б Б Р Р К Д Д К5 Р Р Р К К Д Д Б Б Р К К ▀ ▀ ▀ ≤начальный список список кодов Рис.6.9. Динамика изменения списка при кодировании. Закодированное сообщение: "К1 К2 К5 К3 К5 К2 К5 К2 К5 К5 К3". Интересный метод кодирования в 1992 году предложил С.П. Савчук. В отличие от метода стопки книг перемещению подвергается список кодов. Пусть алфавит А={а1,а2,...,аn}. Данному порядку расположения букв соответствует начальный список кодов K0={k1,k2,..,kn}. При появлении в кодируемом сообщении буквы ai в качестве кода выбирается соответствумций ее местоположению код ki. После этого осуществляется сдвиг списка кодов: {k1,k2,...,ki,...,kn}->{k2,k3,...,kn,k1} Таким образом, список кодов образует замкнутое кольцо. Пример 6.20. Открытый текст: "АБРАКАДАБРА". Алфавит: {А,Б,Д,К,Р}. Список кодов: К0={К1,К2,КЗ,К4,К5}. Динамика изменения списка кодов представлена на рис.6.10 (коды, которыми кодируется открытый текст, выделены квадратами). А [K1] К2 К3 [K4] К5 [K1] К2 [K3] К4 К5 [K1] Б К2 [К3] К5 К5 К1 К2 К3 К4 К5 K1 K2 Д К3 К4 К5 К1 К2 K3 [K4] К5 К1 К2 K3 К К4 К5 К1 К2 [K3] К4 К5 К1 К2 К3 К4 Р К5 К1 [К2] К3 К4 К5 К2 К2 К3 K4 K5 ▀ ▀ ▀ ≤начальный список ≤алфавит Рис.6.10. Динамика изменения списка кодов. Закодированное сообщение: "К1 К3 К2 К4 К3 К1 К4 К3 К5 К4 К1". Особенность данного метода состоит в том, что кодированный текст обеспечивает равномерную частоту появления кодов. Обычно криптоаналитики при наличии доступа к системе шифрования (кодирования) используют шифрование своих сообщений из одинаковых символов для анализа получаемых криптограмм и раскрытия ключа. Рассмотрим пример с кодированием по методу С.П.Савчука . Пример 6.21. Открытый текст: "АААААААААА" Алфавит: {А,Б,Д,К,Р}. Список кодов: К@={К1,К2,Ка,К4,К5}. Закодированное сообщение "К1 К2 К3 К4 К5 К1 К2 К3 К4 К5" содержит одинаковое число всех кодов. Таким образом, если число символов открытого текста кратно длине алфавита, то этот метод дает одинаковое число появления различных кодов при использовании в качестве открытого текста одинаковых символов. Смысловое кодирование - это кодирование, в котором в качестве исходного алфавита используются не только отдельные символы (буквы), но и слова и даже наиболее часто встречающиеся фразы. Рассмотрим пример одноалфавитного и многоалфавитного смыслового кодирования. Пример 6.22. Открытый текст: "19.9.1992 ГОДА". Таблица кодирования представлена в таблице 6.13. Таблица 6.13 Элементы откpытого Коды текста 1 089 146 214 417 2 187 226 045 361 9 289 023 194 635 ГОД 031 155 217 473 786 432 319 157 Закодированное сообщение при одноалфавитном кодировании: "089 289 786 289 786 089 289 289 187 031". Закодированное сообщение при многоалфавитном кодировании: "089 289 786 023 432 146 194 635 187 031" (при многоалфавитном кодировании одинаковые символы заменяются кодами из следующего столбца). Среди различных кодов, применяемых для кодирования естественных языков, особый интерес вызывает код Хаффмена [6], который позволяет сжимать открытый текст. Суть его состоит в присваивании наиболее часто встречающимся буквам наиболее коротких кодов. Строка двоичных символов кодов Хаффмена единственным образом разлагается на коды символов (такие коды называются префиксными). Пример 6.23. Закодированное кодом Хаффмена сообщение имеет вид: "O11O1OOO1OOOOOO1O1O1111OOO1OOOOO". Пользуясь деpевом для английского языка, получаем 0110=S. Далее снова начинаем движение из вершины: 100=E; 01000=C; 00010=U; 1011=R; 1010=I; 001=T; 00000=Y. Открытый текст: "SECURITY". 6.5. Другие методы шифрования Широкое применение персональнта ЭВМ (ПЭВМ) сделало актуальной задачу защиты хранящихся данных (файлов). Для защиты файлов могут быть применены рассмотренные методы шифрования и кодирования. Специфика применения ПЭВМ позволяет реализовать дополнительные методы кодирования для надежного закрытия содержимого файлов. Примером такого кодирования является метод рассечения-разнесения, в соответствии с которым содержимое одного файла разбивается на блоки, которые разносятся по нескольким файлам. Каждый такой файл не несет никакой информации, а сбор данных в единое целое осуществляется простой программой. Пример 6.24. Блок (файл открытого текста) начинается словами: "МЕТОД_РАССЕЧЕНИЯ-РАЗНЕСЕНИЯ". Для рассечения блока открытого текста на 8 частей запишем открытый текст в следующем виде (таблица 6.14). Таблица 6.14 1 2 3 4 1 М Е Т О 2 Д _ Р А 1 С С Е Ч 2 Е Н И Я 1 - Р А З 2 Н Е С Е 1 Н И Я ... Для рассечения текста на 8 частей выбраны 2 строки и 4 столбца. Пусть столбцы sj выбираются в последовательности {4,1,3,2}, а строки ri- в последовательности (2,1}. Тогда номер k блока Фk, куда записывается очередной символ открытого текста, определяется по формуле: k= (ri-1)n+sj, где n - число столбцов. Первый символ М запишется в блок с номером (ri=2, sj=4): k=(2-1)*4+4=8; второй символ E - в блок с номером (ri=2, sj=1); k=(2-1)*4+1=5, и т.д. Тогда блоки Фk, записанные в порядке номеров, будут содержать следующие символы: Ф1=(_НЕ...), Ф2=(АЯЕ...), Ф3=(РИС..,), Ф4={ДЕН...), Ф5={ЕСРИ...}, Ф6={ОЧЗ...), Ф7={ТЕАЯ...), Ф8={МС-Н...}. Таким образом, один блок открытого текста заменяется восемью блоками, которые в сумме дают длину исходного блока. Другой важной проблемой при использовании ПЭВМ является проблема хранения больших массивов данных. Для этой цели применяются различные методы сжатия данных (сжатие можно рассматривать как метод кодирования). Методы сжатия данных осуществляют такое преобразование повторящихся символов и строк символов, которое позволяет использовать для хранения данных меньший объем памяти. Методы сжатия можно разделить на два класса: статические и динамические (адаптивные). Методы статического сжатия данных эффективны, когда частоты появления символов изменяются незначительно. Методы динамического сжатия адаптивно отслеживают неравномерности частот появления символов с сохранением последовательности изменений вероятностей появления символов. К статическим методам можно отнести рассмотренные код Хаффмена и метод стопки книг Б. Я. Рябко. Адаптивные методы сжатия могут динамично реагировать на изменения в открытом тексте, происходящие по мере кодирования. Первые такие методы являлись модификацией кодов Хаффмена и использовали счетчики для хранения текущих частот появления каждого символа. При таких методах наиболее часто встречающиеся символы сдвигаются ближе к корню дерева и, следовательно, получают более короткие кодовые слова. Кодирование Лемпеля-Зива [4] использует синтаксический метод для динамического источника. Этот метод осуществляет синтаксический анализ символьных потоков, которые не превышают званной длины, и строит таблицу отображения этих потоков в кодированные слова фиксированной длины. Длина кодового слова зависит от размера таблицы, используемой для хранения кодового отображения поток-слово. Например, размер таблицы в 4096 слов требует 12-битового кодового слова. Кодовое слово является просто табличным адресом соответствующих слов в таблице . При кодировании по методу Лемпеля-Зива-Уэлча [4] таблица инициализируется символьным множеством и содержит вместо потоков заданной длины пары (кодовое слово, символ) фиксированной длины. Таблица строится на основе синтаксического анализа самого длинного опознанного в таблице потока и использовании последующего символа для формирования нового входа в таблицу. Это позволяет уменьшить размеры таблицы. В последнее время широкое распространение получили методы сжатия на основе расширяющихся деревьев [4]. Префиксный код переменной длины в этих методах строится на основе положения символов в дереве. Для получения оптимальных кодов дерево балансируется. Каждый из методов кодирования, подробное рассмотрение которых выходит за рамки учебного пособия, может использоваться для защиты данных, особенно если используется свой (нестандартный) вариант метода сжатия данных. Стойкость кодирования повышается при использовании нескольких методов сжатия для одного блока открытых данных. У П Р А Ж Н Е Н И Я 1. Поясните физический смысл выражения: ненадежность сообщения должна быть меньше ненадежности ключа. 2. Какая разница между теоретической и практической секретностью с точки зрения отправителя сообщения? С точки зрения криптоаналитика? 3. Расшифруйте сообщение: ИГНТЙДИАДЮЙВИГЕВАНДГВДИГТАЯЙЖОЕЛАСГД, если известно, что оно зашифровано с помощью моноалфавитной замены (алфавит в таблице 6.1). 4. Предложите свой метод перестановки. Укажите его достоинства и недостатки. 5. Предложите алгоритм для реализации преобразователя в блоке подстановки системы ЛЮЦИФЕР. 6. Подсчитайте меру точности и индекс соответствия для русского языка. 7. Предложите метод кодирования, опираясь на примеры 6.19. 6.20 и 6.21. 8. Укажите достоинства и недостатки шифров на основе замены, подстановки, кодирования, аналитических преобразований. 9. К какому классу шифров относится шифр, который объяснял капитан Сагнер? 10. Предложите свой шифр на основе аналитического преобразования. Укажите его достоинства и недостатки. Л И Т Е Р А Т У Р А 1. Брикелл Э.Ф., Одлижко Э.М. Криптоанализ: обзор новейших Результатов// ТИИЭР, 1988.- Т.76, N86.- С. 75-94. 2. Герасименко В.А., Размахнин U.K. Криптографические методы в автоматизированных системах// Зарубежная радиоэлектроника, 1982.- N8.- С. 97-123. 3. Диффи У.. Хеллмен М.Э. Защищенность и имитостойкость: введение в криптографию// ТИИЭР, 1979.- Т.63, N83.- С. 71-109. 4. Кричевский Р.Е. Сжатие и поиск информации.- М.: Радио и связь, 1989.- 168 с. 5. Месси Дж.Л. Введение в современную криптологию// ТИИЭР. 1988.- Т.76. N5.- С. 24-42. 6. Хоффман Л.Дж. Современные методы защиты информации.М.: Советское радио, 1980.- 264 с. 7. Шеннон К. Теория связи в секретных системах/ В сборнике "Работы по теории информации и кибернетике".- М.: ИЛ. 1963.- С. 333-402. 8. Brassard G. Relativized Cryptography// IEEE Trans. on Information Theory, November 1983.- v. IT-29. N6.- P. 877894. 9. Diffie W., Hellman M.E. New Directlons in Cryptography// IEEE Trans. on Information Theory, November 1976.- v. T-IT-76.- P. 644-654. 3 А К Л Ю Ч Е Н И Е Кто хочет научиться летать, тот должен сперва научиться стоять, и ходить, и бегать, и давать, и танцевать: нель- зя сразу научиться летать! Ф.Ницше, " Так говорил Заратустра" Обрабатываемые с помощью электронных средств данные всегда представляли интерес как для охотников за государственными, военными, научными, промышленными и личными секретами, так и для нечистых на руку лиц, да и просто любопытных. Широкое распространение персональных компьютеров и ИВС привело к возрастанию актуальности проблемы обеспечения безопасности данных. К сожалению, научно-методическая база теории обеспечения безопасности информации в настоящее время находится в стадии становления. Работы по обеспечению безопасности данных публикуются, в основном, в виде статей и переводов, выходящих ограниченными тиражами. Терминология, используемая в этих работах, меняется от одной статьи к другой и во многом зависит от переводчика. Разрозненность периодических изданий, публикующих статьи по обеспечению безопасности данных, не способствует становлению теории обеспечения безопасности информации. Поэтому предложенное учебное пособие преследует основную цель ознакомить читателя с проблемой обеспечения безопасности данных в ИВС с единых методологических позиций. В первой части учебного пособия рассмотрены общие проблемы обеспечения безопасности данных, а также методы, средства и механизмы защиты данных, которые могут применяться как в отдельных ЭВМ, так и в вычислительных системах и сетях. Поэтому первую часть учебного пособия можно рассматривать как достаточно подробное введение в теорию обеспечения безопасности информации. Рассмотренные в первой части учебного пособия методы, средства и механизмы защиты данных используются при создании СОБД ИВС. Особенности применения представленных средств и механизмов защиты данных в ИВС, а также средства и механизмы защиты данных, применяемые только в ИВС, будут рассмотрены во второй части учебного пособия.