Рассмотрим некоторые основные методы построения криптографических кодов (шифров) в порядке возрастания их сложности и надежности закрытия информации.

Квадрат Полибия. В Древней Греции был известен шифр, называемый «квадрат Полибия». Это Устройство представляло собой квадрат 5х5, столбцы и строки которого нумеровали цифрами от 1 до 5.

В каждую клетку этого квадрата записывалась одна буква (I, J записывались в одной клетке). В результате каждой клетке отвечала пара чисел и шифрованное сообщение превращалось в последовательность пар чисел. Например,

Шифр замены. При использовании данного метода буквы кодируемого сообщения непосредственно заменяются другими буквами того же или дру­гого алфавита. Если сообщения составляются из алфавита, содержащего k различных букв, то существует N = k!способов выражения этого сообщения с помощью букв этого же алфавита, то есть существует N = k!различных ключей.

Пример. Рассмотрим русский алфавит (первая строка), причем знак "_" обозначает пробел. В качестве ключа выберем одну из возможных пере­становок его букв (вторая строка).

При использовании метода замены с данным ключом слово АЛГОРИТМ преобразуется в словосочетание И-КЫАЩРЪ Кодирование может осущес­твляться символами любого алфавита. Одним из примеров такого кодиро­вания являются "пляшущие человечки" из известного рассказа А. Конан Дойля.

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

Шифр Вижинера. Шифр Вижинера является одним из наиболее рас­пространенных криптографических кодов. Степень надежности его выше, так как нарушаются статистические закономерности появления букв исход­ного алфавита. Вместе с тем он достаточно прост для шифрования. Прежде всего буквы исходного N-буквенного алфавита нумеруются числами от О до N — 1включительно. Например, буквам русского алфавита ставятся в соответствие числа от 0 до 32.

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

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

Пример. Зашифруем слово АЛГОРИТМ по ключу ЩИТ.

Слову АЛГОРИТМ соответствует последовательность: 0 11 3 14 8 18 12.

Ключу ЩИТ соответствует последовательность: 25 8 18.

Записываем вторую последовательность под первой, повторяя ее необходимое число раз:

О 11 3 14 16 8 18 12

25 8 18 25 8 18 25 8

Результат обычного сложения:

25 19 21 39 24 26 43 20

Берем остатки по модулю N = 33:

25 19 21 6 24 26 10 20

Переводим полученную числовую последовательность в буквенную в со­ответствии с используемой нумерацией и получаем окончательное зашифрованное сообщение: ЩУХЖШЪАФ.

Для того чтобы расшифровать полученное сообщение, необходимо под числовыми эквивалентами сообщения записать числовые эквиваленты ключа (с необходимым числом повторений) и вычесть из каждого числа первой последовательности стоящее под ним число второй последовательности по модулю N. Вычитание по модулю N производится по правилам обычного вычитания, если уменьшаемое больше или равно вычитаемому. Если вычи­таемое больше уменьшаемого, то уменьшаемое увеличивается на' N и вычи­тание производится из увеличенного числа, то есть 6 - 25 по модулю 33 дает результат 6 + 33 - 25 = 14.

Частный случай шифра Вижинера, когда длина ключа равна 1 (то есть ключ состоит из одной буквы), называется шифром Цезаря. Если в качестве ключа выбрана k-я по счету буква алфавита, то при кодировании шифром Цезаря буква с номером i заменяется буквой с номером i + k, то есть производится сдвиг на k номеров.

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

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

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

В качестве примера генератора псевдослучайной последовательности при­ведем датчик Лемера, получивший название линейного конгруэнтного ме­тода. Для заданного начального числа a₀он вырабатывает бесконечную последовательность натуральных чисел по следующему рекуррентному закону:

a _k = d + a_k -1 • m(mod M),

где d, m, M - некоторые целые числа.

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

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

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

а)при любом k существует алгоритм вычисления значения F_k(x) с полиномиальной сложностью

б) при неизвестном k не существует алгоритма вычисления, обратной функции с полиномиальной сложности,

в) при известном k существует алгоритм обращения этой функции с полиномиальной сложностью.

Вычислительная сложность алгоритма, если допустить некоторую нестрогость, - это функция, выражающая зависимость времени работы алгорит­ма до получения результата от объема или величины входных данных. Вре­мя же работы алгоритма пропорционально числу элементарных операций, которые необходимо выполнить при его реализации. Реально выполнимыми при достаточно больших объемах данных являются только полиномиальные алгоритмы (то есть алгоритмы, в которых указанная зависимость имеет вид полинома некоторой степени от параметров, характеризующих объем и ве­личину входных данных). Отсутствие полиномиального алгоритма - веское основание отнести рассматриваемую задачу к числу трудно решаемых задач. Примером трудно решаемой задачи может являться задача фактори­зации чисел, заключающаяся в разложении заданного числа па простые множители. С одной стороны, ясно, что по набору простых множителей легко можно определить исходное число. Но обратная задача оказывается гораздо сложнее. Для примера приведем результат, полученный в 1990 году: 155-разрядное число было разложено на 3 простых числа. Для этого использовались 1000 объединенных ЭВМ и было затрачено 6 недель машинного времени.

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

Сжатие информации

Сжатие информации представляет собой операцию, в результате которой данному коду или сообщению ставится в соответствие более к­роткий код или сообщение.

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

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

Все методы сжатия данных делятся на два основных класса:

· Сжатие без потерь

· Сжатие с потерями

При использовании сжатия без потерь возможно полное восстановление исходных данных, сжатие с потерями позволяет восстановить данные с искажениями, обычно несущественными с точки зрения дальнейшего использования восстановленных данных. Сжатие без потерь обычно используется для передачи и хранения текстовых данных, компьютерных программ, реже — для сокращения объёма аудио- и видеоданных, цифровых фотографий и т. п., в случаях, когда искажения недопустимы или нежелательны(примеры форматов сжатия без потерь информации: gif, tiff – для графических данных; avi – для видеоданных; zip, arj, rar, cab, lh – для произвольных типов данных). Сжатие с потерями, обладающее значительно большей, чем сжатие без потерь, эффективностью, обычно применяется для сокращения объёма аудио- и видеоданных и цифровых фотографий в тех случаях, когда такое сокращение является приоритетным, а полное соответствие исходных и восстановленных данных не требуется (jpeg – для графических данных, mp3- для аудиоданных).

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

Не нашли, что искали? Воспользуйтесь поиском: