Билет 9

Коды Малера.

Коды Рида-Маллера относятся к линейным двоичным кодам, имеющим большие кодовые расстояния и исправляющим благодаря этому много ошибок. Они пригодны для каналов с малым отношением сигнал/помеха. Кодовое слово длины   обычно рассматривается как булева функция (или ее инверсия), заданная в   точках, т.е. на наборах из   двоичных элементов. Можно многими способами нумеровать позиции кодового слова   -разрядными двоичными векторами. Ясно, что, как в случае кодов Хэмминга, такая перестановка не влияет на помехоустойчивость получаемых кодов. Будем нумеровать позиции кодового слова числами в двоичной системе счисления   , где   для   . Ввиду линейности кодов Рида-Маллера каждый символ кодового слова   представим линейной комбинацией

,

или ее инверсией

,

где   – известные информационные символы.

В соответствии с определением порождающей матрицы (5.16) и правилом покомпонентного сложения векторов элементы   являются столбцами матрицы   . Для   порождающая матрица размера   на   имеет вид:

.

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

,

(5.34)

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

2. Сжатие данных.

Сжатие данных (англ. data compression) — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных.  Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или белый шум, зашифрованные сообщения), принципиально невозможно без потерь.

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

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

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

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

Коэффициент сжатия — основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть:  , где k — коэффициент сжатия, S_o — объём исходных данных, а S_c — объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:

• если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному;

• если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

БИЛЕТ10

. Основные режимы шифрования алгоритма ГОСТ 28147-89.

симметричный, т.е. ключ зашифровки совпадает с ключом расшифровки. Длина ключа 256 бит, что обеспечивает очень большую криптостойкость алгоритма. По скорости алгоритм примерно равен скорости подобных алгоритмов (по крайней мере имеет тот же порядок) или немного быстрее их. ГОСТ 28147-89 относится к блочным шифрам.

Основные режимы шифрования

ГОСТ 28147-89 определяет три основных режима шифрования: простая замена, гаммирование и гаммирование с обратной связью и один дополнительный режим выработки имитовставки. Данные обрабатываются блоками по 64 бита, на которые разбивается массив, последний блок может быть неполным. В двух последних режимах имеется возможность обрабатывать неполный блок данных, в первом длина данных должна быть кратна 64-м битам.

Простая замена

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

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

Гаммирование

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

Гаммирование с обратной связью

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

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