close

Вход

Забыли?

вход по аккаунту

?

2 (2)

код для вставкиСкачать

Лабораторная работа №2. Дешифрование, частотный анализ. Маскировка длины символа
Дешифрование
Процесс нахождения открытого сообщения, соответствующего заданному закрытому, при неизвестном криптографическом преобразовании называется дешифрованием. Исследованием возможности дешифрования информации без знания ключей занимается криптоанализ.
Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования. Диффузия - это рассеяние статистических особенностей и закономерностей незашифрованного текста в широком диапазоне статистических особенностей и закономерностей зашифрованного текста. Это достигается тем, что значение каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, что то же самое, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста. Конфузия - это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом. Если Х - это исходное сообщение и K - криптографический ключ, то зашифрованный передаваемый текст можно записать в виде Y = EK [X].
Получатель, используя тот же ключ, расшифровывает сообщение X = DK [Y].
Противник, не имея доступа к K и Х, должен попытаться узнать Х, K или и то, и другое. Частотный анализ
Шифры простой замены легко поддаются дешифровнию методом частотного анализа встречаемости букв и пар букв. Все естественные языки и большинство искусственных имеют характерное частотное распределение букв и других знаков. Например, в английском языке буква E встречается наиболее часто, а буква Z - наиболее редкая (рис. 2). Если подсчитать в зашифрованном сообщении частоты встречаемости символов и сопоставить их с характерными частотами для данного языка, то сообщение довольно легко может быть прочитано. Чем больше длина шифротекста, тем легче его дешифровать. Так же можно определить вероятности появления пар букв. Окажется, что для многих пар вероятность почти равна нулю. При дешифровании текста если встречается такая пара, то такой вариант отбрасывается. Криптоаналитики часто используют индекс соответствия текстов, вычисляемый по формуле
где fi - общее число встречаемости буквы i в тексте;
N - общее число букв в тексте;
A - первая буква в алфавите;
z - последняя буква в алфавите.
По определению ИС представляет собой оценку суммы квадратов вероятностей каждой буквы. При многоалфавитной подстановке для английского языка, в зависимости от количества используемых при шифровании алфавитов (m), ИС ожидается:
m:1234510
ИС:0,0660,0520,0470,0450,0440,041
При гаммировании криптостойкость определяется размером ключа. Покажем это на примере:
C1 = P1  K
С2 = P2  K
C1  С2 = P1  P2 ,
где K - символ гаммы;
P1 и P2 - символы разных открытых текстов, зашифрованных на одной гамме;
C1 и С2 - зашифрованные символы, соответствующие P1 и P2.
Далее, применяя к полученной сумме метод вероятностных слов или статистического анализа, есть вероятность найти оба открытых сообщения. На одном ключе может быть выработано конечное число символов гаммы, поскольку через определенное количество символов она начнет повторяться, то есть генератор гаммы всегда имеет некоторый период. Поэтому необходимо добиваться как можно большего периода или чаще менять секретный ключ.
Маскировка длины символа
Чтобы усложнить задачу криптоаналитиков, для изменения длины каждого символа применяют сжатие. Для тех же целей иногда зашифрованный текст по определеному закону "разбавляют мусором", а при расшифровании этот "мусор" по этому же закону "выбрасывается".
Выполнение битовых операций
Для выполнения заданий по данной лабораторной работе могут потребоваться операции с битами. Ниже приводятся некоторые простейшие манипуляции с битами на языке Pascal.
Младший (самый правый) разряд считается нулевым. 1. Выделить i-й бит из переменной A:
(A shr i) AND $01.
Распечатать содержимое переменной A как последовательность битов:
for i:=7 downto 0 do
write ((A ShR i) AND $01).
2. Установить i-й бит
а) в 1:A OR ($01 ShL i);
б) в 0:A AND NOT ($01 ShL i).
3. Обнулить A:
A XOR A.
4. Поменять местами i-й и j-й биты целого числа:
type bitik = 0..14;
bin = 0..1;
var i,J : bitik;
bi,bj : bin;
X,a,ap: Integer;
...
bi:=(a ShR i) AND $01; bj:=(a ShR J) AND $01;
if bi<>bj then
if bi=1
then begin ap:=a-(1 ShL i); ap:=ap+(1 ShL j) end
else begin ap:=a-(1 ShL j); ap:=ap+(1 ShL i) end;
5. Циклический сдвиг содержимого n-разрядной переменной A на i битов
а) влево: ROL (A, i)или(A shl i) OR (A shr (n-i));
б) вправо: ROR (A, i) или(A shr i) OR (A shl (n-i)).
Сжатие методом Хаффмана
При сжатии этим методом 8-битовый код каждого символа заменяется на код, у которого разрядность зависит от частоты встречаемости данного символа.
Допустим, алфавит, для которого мы хотим применить сжатие, содержит всего шесть символов. Возьмем файл с текстом из этих символов и подсчитаем, сколько раз каждый символ встретился в этом файле. Отсортируем символы по возрастанию их встречаемости в тексте. R N O A T E
5 6 7 8 9 13
Возьмем два символа с наименьшей частотой: R (5) и N (6). Сформируем из узлов R и N новый узел, частота вхождения для которого будет равна сумме частот R и N (11). После этого снова ищем два узла с самыми низкими частотами вхождения, исключая из просмотра R и N и рассматривая вместо них новый узел с суммарной частотой вхождения. И так продолжаем до тех пор, пока не получим вершину дерева с общим количеством символов. В результате получится дерево для генерации кодов (рис. 3).
Рис. 3. Дерево кодов для сжатия по методу Хаффмана
Спускаясь по дереву из корневого узла до терминального символа, мы пишем 0, если проходим по левой ветви, и пишем 1 - если по правой. Таким образом для символов нашего алфавита получим следующие коды:
E - 11А - 101N - 001Т - 01O - 100R - 000
Для наиболее часто встречающихся символов мы получили более короткие коды. Сжатый файл вместо 48 байт будет занимать 16 байт [(53+63+73+83+92+132) / 8].
Задания
6 Напишите программы шифрования и расшифрования с использованием тюремной азбуки. Азбука устроена следующим образом: в прямоугольную матрицу 6 х 5 вписываются по строкам буквы русского алфавита в обычном порядке следования, кроме букв ё, й, ъ. Код каждой буквы теперь можно определить парой чисел - номером строки и столбца. Для каждого числа используйте по три бита. Для обозначения пробела - 000. Оставшиеся в конце закодированного сообщения биты заполните нулями.
14 Напишите программы шифрования и расшифрования с использованием файла с ключевым текстом, который будет использоваться следующим образом: очередной символ исходного текста ищется в ключевом тексте; смещение от текущей позиции файла до позиции с найденным символом и будет кодом зашифрованного символа. Поиск следующего символа начнется от только что найденного. По достижении конца ключевого файла поиск продолжите с начала файла. Есть ли возможность дешифровать с помощью статистических методов зашифрованный таким образом текст? Открытый, ключевой и зашифрованный тексты должны находиться в текстовых файлах.
2
Документ
Категория
Рефераты
Просмотров
51
Размер файла
88 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа