Здавалка
Главная | Обратная связь

ШИФРОВАНИЕ МЕТОДОМ СКОЛЬЗЯЩЕИ ПЕРЕСТАНОВКИ



Цель работы: исследование шифра скользящей перестановки с ис­пользованием программной реализации ХУ - Mover.

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

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

 

Таблица 2.3

а - 0,062 л - 0,035 ц - 0,004
б - 0,014 м - 0,026 ч - 0,012
в - 0,038 н - 0,053 ш - 0,006
г - 0,013 0-0,090 щ - 0,003
д - 0,025 п - 0,023 ы - 0,016
е,е - 0,072 р - 0,040 ъ.ь - 0,014
ж- 0,077 с - 0,045 э - 0,003
з - 0,016 т - 0,053 ю - 0,006
и - 0,062 у - 0,021 я - 0,018
й - 0,010 Ф - 0,002 - 0,175
К-_ 01028 х - 0,009    

 

Например, в слове СЕНОВАЛИТР содержатся 10 наиболее часто встречающихся букв.

Частоты знаков алфавита зависят не только от языка, но и от характера текста. Так, в тексте по криптографии будет повышена вероятность букв «Ф», «Ш» из-за часто встречающихся слов «шифр», «криптогра­фия». В некоторых математических текстах может быть завышена часто­та буквы «Ф» из-за слов «функция», «функционал» И Т.П. В стандартных текстовых файлах наиболее частым является символ «пробел». Частот­ная диаграмма содержательных текстов является устойчивой характе­ристикой текста. Из теории вероятностей следует, что при достаточно слабых ограничениях на вероятностные свойства случайного процесса справедлив закон больших чисел, Т.е. относительные частоты Vk/N знаков сходятся по вероятности к значениям их вероятностей Pk

 

 

Шифры перестановки и простой замены не полностью разруша­ют вероятностно-статистические свойства, имеющиеся в открытом сообщении.

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

Конечно, если текст не очень длинный, то не обязательно полное совпадение. Может оказаться на втором месте «О», а на третьем «Е», но в любом случае в первых и вторых рядах одинаковые буквы будут располагаться недалеко друг от друга, и чем ближе к началу (чем больше вероятность знаков), тем меньше будет расстояние между знаками.

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

Видели ли вы когда-нибудь в открытом тексте биграмму «ЪЬ» или биграммы вида «гласная» Ь, «пробел» Ь? Знание и использование ука­занных особенностей открытого текста значительно облегчает дешифрование шифра перестановки и замены.

Шифр перестановки. Положим Х - множество открытых (содержа­тельных) текстов в алфавите 1. Длины всех возможных открытых тек­стов кратны величине Т. Множеством ключей является симметриче­ская группа подстановок ST степени Т, для ge ST определим функцию шифрования fg, положив для(i1, i2, …, iT) X

 

fg(i1, i2, …, iT) = (ig(1), ig(2), ... ,ig(T))

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

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

Рассмотрим пример дешифрования шифра перестановки восьми столбцов. Пусть шифротекст имеет следующий вид (табл. 2.4).

 

Таблица 2.4

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

 

Сопоставим перестановке столбцов таблицу 8х8, при этом поставим на пересечении i-й строки и j-й столбца единицу, если j-я колонка после обратной перестановки должна следовать за i-й. Наша задача - восста­новить таблицу, отвечающую правильной перестановке столбцов.

Давайте теперь попарно пристраивать один столбец к другому. Если при этом в некоторых строках появляются запретные биграммы, то столбцы не могут в открытом тексте следовать друг за другом и соот­ветствующая клеточка зачеркивается. В нашем примере шестой стол­бец не может следовать за четвертым, так как иначе в тексте в первой строке будет подряд два пробела. Посмотрим, например, шестую стро­ку. Если бы четвертый столбец следовал за первым, то в тексте были бы слова, начинающиеся с «Ь».

После просмотра всех строк получим табл. 2.5.

 

Таблица 2.5

 
х х   х х х   х
  х   х   х    
    х         х
х х   х   х х х
х       х х х х
х х   х   х х  
х     х х х х х
х х     х х х х

 

Если бы текст был подлиннее и строк было бы побольше, то в каж­дой строке и в каждом столбце осталось бы ровно по одной не зачерк­нутой клеточке и перестановка была бы восстановлена.

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

 

Нам надо рассмотреть оба и постараться отсеять ложный вари­ант. Если отсеять ложный вариант не удастся, то надо продолжать оба варианта

 

 

В итоге получаем некоторое дерево возможного следования столбцов в открытом тексте

 

 

Каждой ветви дерева соответствует некоторая перестановка столбцов.

Далее проверяем каждый вариант на осмысленность и получаем правильный вариант

 

 

Заметим, что не обязательно было строить дерево до конца. Например, ветвь 3 6 8 4 5 можно было отсеять сразу. Разве можно признать осмысленным фрагмент текста, приведенный в табл. 2.6?

 

Таблица 2.6

я   м   в
ш у е г  
ж е о л  
ч т я   о
г у щ е
к а т ь е
е а т   а

 

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

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

2. Предварительная работа. Составить словарь всех возможных v-грамм для v= 2,3, ... , d, которые могут встретиться в открытом тексте. Число d выбирается исходя из возможностей вычислительной техники.

Построить таблицу 8х8. При этом перебираются последовательно все запретные биграммы и для каждой опробуемой биграммы - последовательно все строки. Если хотя бы в одной строке первый символ биграммы встречается в i-м столбце; а второй – в j-M, то клеточка i x j таблицы зачеркивается.

3. Выбрать некоторый столбец в качестве начального.

4. Начать процедуру построения дерева путем пристраивания к исходному столбцу всех вариантов столбцов.

5. Lля каждого полученного варианта добавить еще один из оставшихся столбцов. Если хотя бы в одной из строк таблицы встретится: 3-грамма, которая отсутствует в словаре размещенных 3-грамм, то вариант отсеивается.

6. Для каждого из неотсеянных вариантов добавляем еще один столбец и проводим отсев ложных вариантов по словарю разрешенных 4-грамм.

Если словарь был построен только для d≤ 3, то отсев проводится: путем проверки на допустимость 3-грамм, встретившихся в последних трех столбцах каждой строки. Продолжаем этот процесс до получения: полной перестановки.

В таблице 2.7 приведен восстановленный для нашего примера текст.

 

Таблица 2.7

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

 

Дальнейшее развитие шифры перестановки получили осущест­влением идеи непрерывной локальной перестановки символов от­крытого текста под действием управляющей последовательности. для осуществления перемешивания знаков открытого текста в па­мяти шифратора запоминаются отдельные знаки текста и прово­дится задержка их передачи в дискретном времени. Введем параме­тры n1 и n2 так, что п = n1 + n2. В этих шифрах i-й знак передаваемого сообщения переставляется в шифрованном сообщении на j - e место, где i n1 ≤ j ≤ i + n2 .

Управляющую последовательность временем задержки стараются выбрать так, чтобы время задержки каждого символа было случайной величиной с равномерным распределением, т.е. вероятность каждого фиксированного значения времени задержки должна быть близка к 1/n.

Шифрующий автомат скользящей перестановки.Рассмотрим схему шифрующего автомата, позволяющего при подходящей управляющей последовательности реализовать произвольный шифр скользящей пе­рестановки (рис. 2.5).

На вход узла формирования задержки (УФЗ) в каждом такте t по­дается вектор

Узел формирования задержки является конечным автоматом (F2n, F2n, {1, ... , n}, δ, λ), множеством состояний которого является множе­ство всевозможных двоичных векторов - заполнений (t) = 1t, ... , xnt) нижнего накопителя. В такте t вырабатывается натуральное число – значение γt задержки

γt = mах j : {xji = yji= 1, j = }.

 

Рис. 2.5. Схема реализации шифрующего автомата скользящей перестановки

 

При этом автомат переходит в следующее состояние:

 

где

Знаки открытого текста записываются на нижний накопитель. В линию в t-мтакте посылается знак открытого текста, записанный в ячейке с номером γt. Состояния автомата (t)являются индикаторами, показывающими, какие из знаков открытого текста еще не считаны с нижнего накопителя.

Для зашифрования последовательности tN , …,t2, t1 поступают следующим образом. Сначала записываем в нижний накопитель первые п1 знаков открытого текста

(tn1, …, t1, 0, …,0).

Одновременно автомат устанавливается в начальное состояние

(1)=(0, …, 0)

После этого автомат УФЗ начинает работать по описанном/ выше закону до тех пор, пока в накопитель не поступит последний знак tN открытого текста. С прекращением подачи на накопитель знаков открытого текста происходит прекращение подачи единиц на накопитель-индикатор. В оставшиеся в, тактов про изводится счи­тывание записанной в накопителе информации.

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

Рассмотрим особенности работы УФЗ. В каждом такте t (за исключением последних n, тактов) в накопителе-индикаторе (t)записано ровно n1 единиц. Поэтому в такте t величина задержки может принимать только одно из n1 значений в интервале {1, ... , n}. В частном случае, когда п = 1 либо п1 = п, УФЗ вырабатывает постоянно значения задержки γt, = 1 и γt = п соответственно. Легко видеть, что результирующее преобразование открытого текста действительно будет шифром скользящей перестановки. Условие у1t = 1, t = 1, 2, ... обеспечивает постоянное считывание во всех тактах, а условие γt= 1 ограничивает величину задержки γt ≤п.

Пример2.2

Принем п = 7, nl = 3, n2 = 4. На вход УФЗ на каждом шаге t работы шифрующего автоматa подается вектор = (y1t , …, y1t), получаемый в линейном регистре сдвига (ЛРС) (рис. 2.6)

 

Рис. 2.6. Линейный регистр сдвига

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

Будем обозначать на каждом шаге работы шифрующего автомата последовательность y1, y2, ... ,yn (в нашем случае y1, y2, ... ,yγ), поступающую с ЛРС, как «Y» , а последовательность единиц x1, x2, … , xn(в нашем случае x1, x2, … , xγ) как «1». В нижней строке будем записывать знаки открытого текста, находящиеся на данном шаге в нижнем накопителе шифрующего автомата t1, t2, …, tn (в нашем случае t1, t2, …, tγ). Рассмотрим пошагово работу шифратора при конкретных условиях.

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

t2, t4, t5, t6, t1, t7, t3, t8.

Описание программной реализации. Для выполнения лабораторной работы на компьютере необходимо установить программный модуль XY-Mover. Ниже представлены основные элементы программы.

1. Строка меню. В данной программе меню состоит из трех пунктов: ШИФРОВАНИЕ, ВИД, ПОМОЩЬ. Необходимый пункт меню можно выбрать, щелкнув по нему левой кнопкой мыши, или с помощью кнопок клавиатуры «вправо», «влево», нажав перед этим функциональную клавишу F10. После того как пользователь выбрал необходимый ему пункт меню, откроется ниспадающее подменю. Рассмотрим пункты меню подробнее .

• ШИФРОВАНИЕ - пункты ниспадающего меню можно выбрать либо левой кнопкой мыши, либо кнопками клавиатуры « », « ». Рассмотрим подробнее пункты подменю:

- РЕДАКТИРОВАНИЕ ПАРАМЕТРОВ - позволяет задать необходимые параметры в поле окна программы «параметры шифратора»,

- ШИФРОВАТЬ - запускает процесс шифрования,

- ДЕШИФРОВАНИЕ - запускает процесс дешифрования,

- ВЫХОД - завершение работы программы;

• ВИД - этот пункт меню позволяет выбрать внешний вид программы. Ниже приводятся пункты подменю:

- ПАРАМЕТРЫ - позволяет использовать поле «Параметры шифратора», описанную ниже;

- СХЕМА ШИФРАТОРА - позволяет наблюдать структурную схему шифрующего автомата;

- СТРОКА СОСТОЯНИЯ - выбор этого пункта меню позволяет наблюдать строку состояния, описанную ниже.

2. Панель инструментов. Возможно, пользователю будет удобнее воспользоваться панелью инструментов (так называемыми кнопками) вместо работы с меню. Кнопки дублируют некоторые пункты меню, ко выбрать кнопку гораздо удобнее, чем пункт подменю. Для этого необходимо щелкнуть по выбранной кнопке левой кнопкой мыши. Рассмотрим кнопки слева направо:

• А, позволяет получить результат, аналогичный пункту меню: ВИД/ПАРАМЕТРЫ;

• схема шифратора - позволяет получить результат, аналогичный пункту меню ВИД/СХЕМА шифратора; •

• строка состояния - позволяет получить результат, аналогичный пункту меню: ВИД/СТРОКА СОСТОЯНИЯ;

• редактирование параметров - позволяет получить результат, аналогичный пункту меню ШИФРОВАНИЕ/РЕДАКТИРОВАНИЕ ПАРАМЕТРОВ;

• шифровать - позволяет получить результат, аналогичный пункту меню ШИФРОВАНИЕ/ШИФРОВАТЬ;

• «дешифровать» - позволяет получить результат, аналогичный пункту меню ШИФРОВАНИЕ/ДЕШИФРОВАТЬ;

• «прервать» - позволяет прервать процесс обработки данных (шифрование или дешифрование).

3. Строка состояния. Строка состояния находится в нижней части окна программы. На ней выводится информация о состоянии программы:

• шифрование методом скользящей перестановки - это сообщение указывает на то, что программа готова к работе.

• завершено ... % - индикация объема выполненной работы при зашифровании или расшифровании.

4. Описание полей окна программы:

• параметры шифратора:

- nl - число знаков, которые записываются в нижний накопитель первыми,

- n2 - остальные знаки (всего их 127),

- отводы регистра - точки съема ЛРС,

- начальное заполнение - начальное заполнение ЛРС, которое пользователь может изменять;

• входной поток:

- поле, в котором отражается имя текстового файла, содержание которого нужно шифровать/расшифровать,

- кнопка «Открыть» - при нажатии на эту кнопку открывается стандартное для Windows окно «ОТКРЫТИЕ ФАЙЛА»,

- текст - содержимое файла, открытого для шифрования/рас_ шифрования,

- битовый поток - побитное представление символов выбранного файла;

• выходной поток:

- поле, в котором отражается имя текстового файла, содержание которого нужно расшифровать/шифровать,

- кнопка «Открыть» - при нажатии на эту кнопку открывается стандартное для Windows окно «ОТКРЫТИЕ ФАЙЛА»,

- текст - содержимое файла, открытого для расшифрования/ шифрования,

- битовый поток - побитное представление символов выбранного файла.

 

Задание

 

1. Для выполнения лабораторной работы на КОМПЬ1Отере необходимо установить программный модуль ХУ-Моvег.

2. Выполнить начальные установки шифратора согласно примеру.

3. Загрузить файл для шифрования.

4. Произвести шифрование информации с использованием шифра скользящей перестановки, сохранить шифротекст в файле.

5. Описать в отчете процесс шифрования и расшифрования данных с использованием программы-эмулятора XY-Mover. Проанализировать полученные данные.

6. Включить в отчет о лабораторной работе ответы на контрольные вопросы, выбранные в соответствии с номером варианта (табл. 2.8).

 

Таблица 2.8

Номер варианта Контрольные вопросы
1, 5, 7, 3, 9, 18, 28 Почему шифрование методом гаммирования является наиболее подходящим для высокоскоростных линий телекоммуникационной связи?
2, 4, 6, 8, 20, 22, 24, 26, 30 Какие общие требования предъявляются к гамме шифра?  
11, 13, 15, 10, 17, 19, 27 Приведите пример, поясняющий работу шифрующего автомата скользящей перестановки при n = 5, nl = 2, n2 = 3  
12, 14, ,16, 21, 23, 25, 29 Кратко опешите работу схемы реализации шифра скользящей перестановки  

 








©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.