Глава 6. Введение в криптографию.

Введение.

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

Все мы знаем о различных формах криптографии или тайнописи, — спе­циальных способах шифровки сообщений для того, чтобы оградить информа­цию от нежелательного (говорят, от несанкционированного) разглашения. По "Золотому жуку" Эдгара По и "Пляшущим человечкам" Артура Конана Дойла мы знакомились с "подстановочным шифром", в котором каждая буква доку­мента заменяется однозначно определяемой другой буквой или специальным знаком из другого алфавита.

Криптография широко применяется и становится все более популярной из-за распространения информационных систем. Чем же привлекательна крип­тография? Тем, что зашифрованные сообщения можно пересылать по откры­тым каналам связи, не боясь "прочтения" этой информации третьими лицами.

До недавнего времени криптография оставалась привилегией исключительно государственных и военных учреждений. Ситуация резко изменилась после публикации в 1949 году книги К. Шеннона "Работы по теории информации и кибернетике". Криптография стала объектом пристального внимания многих ученых. Кроме того, в настоящее время глобального внедрения персональных компьютеров, уже практически невозможно помешать распространению таких программ, как например PGP, обеспечивающих приватность частной электронной переписки. Этому мешают как демократические принципы, так и недостаточная способность контролировать все каналы распространения информации.

Защита информации криптографическими методами заключается в преобразовании ее основных частей с помощью специальных алгоритмов или аппаратных решений и кодов ключей, т.е. в приведении ее у неявному виду. Для ознакомления с шифрованной информацией применяется обратный процесс: дешифрование.

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

Наиболее продуктивным является использование криптографических методов защиты при передаче данных в компьютерных сетях, данных, хранящихся в удаленных устройствах памяти, и при обмене информацией между удаленными объектами. Это и накладывает на используемые алгоритмы специфические требования:

ТРЕБОВАНИЯ К МЕТОДАМ ШИФРОВАНИЯ

ü метод шифрования должен быть устойчивым к попыткам узнать исходный текст только по зашифрованному.

ü объем ключа не должен затруднять его пересылку и запоминание

ü затраты на защитные преобразования должны быть приемлемы при данном уровне секретности

ü ошибки в шифровании или при передаче сообщения не должны приводить к потери информации

ü объем зашифрованных не должен превышать объема исходных данных

Рис 18. Классическая схема шифрования

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

КЛАССИФИКАЦИЯ КРИПТОГРАФИЧЕСКИХ МЕТОДОВ

Разделить методы защиты можно и по принципу количества используемых ключей:

ü симметричное шифрование (1 ключ)

ü асимметричное шифрование (2 ключа)

Множество методов защитных преобразований можно разделить на следующие группы (см. рис. 19):

 

 

Рис. 19. Методы преобразование информации.

Методы перестановки

Суть методов перестановки в том, что входной поток исходного текста делится на блоки, в каждом из которых выполняется перестановка символов.

При таком методе преобразования информации, как правило, шифрование строится на том, что чтение исходных данных и запись преобразованных производится по различным путям геометрической фигуры.

Матрицы

Простейшим примером перестановки является случай, когда текст разбивается на участки определенной длины и чтение производится по строкам некоторой матрицы, а запись — по ее столбцам. Последовательность чтения строк и заполнения столбцов, определяемая ключом, может быть совершенно разной. Так для матрицы размерностью 8х8 (длина блока 64 символа) возможно 1.6 х 109 ключей. Однако для современных ЭВМ можно расшифровать исходное сообщение просто путем перебора такого количества ключей. Для матрицы размером 16x16 (длина блока 256 символов) имеется 1.4 х 1026 ключей. Перебор такого количества ключей при помощи современных средств по меньшей мере затруднителен.

Маршруты Гамильтона

Еще одним примером реализации метода перестановки являются маршруты Гамильтона (рис 20). Последовательность заполнения таблицы каждый раз соответствует нумерации ее элементов. Если длина шифруемого текста не кратна числу элементов, то при последнем заполнении в свободные элементы заносится произвольный символ. Выборка из таблицы для каждого заполнения может выполняться по своему маршруту, при этом маршруты могут использоваться как последовательно, так и в порядке, задаваемом ключом.

 

Рис 20. Маршруты Гамильтона

Электрический монтаж

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

Особенности перестановки

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

Методы подстановки

Методы шифрования заменой (подстановкой) заключаются в том, что символы исходного текста, записанные в одном алфавите, заменяются символами другого алфавита в соответствии с принятым ключом преобразования.

Вектор замен

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

Таблицы Вижинера

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

 

Рис 21. Таблица Вижинера

 

Для шифрования текста устанавливается ключ, представляющий собой некоторое слово или набор букв. Далее из полной матрицы выбирается подматрица шифрования, включающая, например первую строку и строку матрицы, начальной буквой которой являются последовательно буквы ключа. Выберем в качестве ключа слово "ЖРЕЦ". Зашифруем текст "УТОМЛЕННЫИ ГЛАЗИК".

Шифруемый текст:	УТОМЛЕННЫИ ГЛАЗИК
Ключ:	ЖРЕЦ
Текст после замены:	ЩБУБСХТВБШ ИАЖЧОЯ
Зашифрованный текст:	ЩБУБ СХТВ БШИА ЖЧОЯ

 

Алгоритм шифрования следующий:

ü под каждой буквой шифруемого текста записываются буквы ключа, повторяющие ключ требуемое число раз;

ü шифруемый текст по подматрице заменяется буквами, расположенными на пересечениях линий, соединяющих буквы ключа, находящиеся под ней;

Так, под первой буквой шифруемого текста "У" оказалась буква "Ж" ключа. Из этого в первой строчке подматрицы находим букву "У" и выбираем из данной колонки подматрицы букву в той строке, которая соответствует букве "Ж" ключа. По данному адресу находится буква "Щ". Она и будет первой буквой шифрованного текста.

Из общих соображений и из рис 23 видно, что в предельном случае, когда ключ состоит из одной буквы, алгоритм вырождается в замену одного определенного символа алфавита на строго определенный другой. Такой алгоритм можно легко взломать на основе статистических методов языка.

Рис 23. Ключ шифрования

Особенности метода

Раскрыть зашифрованный текст, основываясь на статистических характеристиках языка (частота повторения символов, длина слов и т.д.) практически невозможно, т.к. одни и те же символы открытого текста могут соответствовать различным символам зашифрованного и наоборот: различные буквы открытого текста могут быть заменены одинаковыми знаками шифрованного текста.

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

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

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