12744

Криптоанализ блочного шифра тотальным перебором ключей

Лабораторная работа

Информатика, кибернетика и программирование

Описание лабораторной работы Криптоанализ блочного шифра тотальным перебором ключей Цель работы Целью данной работы является изучение структуры и основных свойств блочного шифра основанного на подстановочно перестановочной сети SubstitutionPermutation Network или SPN кр

Русский

2013-05-03

281 KB

26 чел.

Описание лабораторной работы

«Криптоанализ блочного шифра тотальным перебором ключей»
Цель работы
Целью данной работы является изучение структуры и основных свойств блочного шифра, основанного на подстановочно перестановочной сети (Substitution-Permutation Network или SPN), криптоанализа методом тотального перебора ключей и правила принятия решения о правильном ключе при переборе.
Задание
1. Изучить схему и принцип действия учебного шифра, используемого в данной работе.
2. Произвести шифрование открытого сообщения, представленного в виде произвольной двоичной последовательности длиной 16-бит (т.е. длиной равной одному блоку шифра), наблюдая результаты на каждом этапе шифрования. Сделать вывод об улучшении качества шифрования с увеличением числа раундов.
3. Произвести дешифрование криптограммы, полученной в п. 2, а также дешифрование  этой криптограммы при эмуляции ошибок в канале передачи. Сделать вывод о размножении ошибок в расшифрованном сообщении.
4. Произвести шифрование  смыслового текста.
5. Дешифровать полученный шифртекст на правильном и произвольном неправильном ключе.
6. Произвести криптоанализ зашифрованого смыслового текста при помощи метода тотального опробывания ключей.
Порядок выполнения работы
Изучите схему и принцип действия учебного шифра, используемого в данной работе по разделу 2 приложения.
Для выполнения работы перейдите в каталог, указанный преподавателем, содержащий рабочие программы, и запустите программу “перебор.exe” На экране монитора появится основное окно программы (Рис. 1).
 
Рис. 1 Основное окно программы
1. Введите управляющий ключ из 7-ми бит для генерации 5 раундовых ключей по 16 бит. Генерация происходит следующим образом: Семь бит управляющего ключа используются в качестве начального заполнения для семиразрядного линейного рекуррентного регистра (ЛРР). Этот формирует псевдослучайную последовательность длинной 27-1 = 127 бит. Первые 80 бит этой последовательности используются в качестве 5-ти раундовых ключей учебного шифра. Такой метод задания ключа был выбран по двум причинам. Первая – продемонстрировать необходимость исключения криптографически слабых раундовых ключей (например 0000… или 00110011… или 010101… и т.п.). Вторая – сократить количество вариантов для перебора. Так при переборе всех вариантов раундовых ключей (80 бит) потребуется 280 ≈ 1,2∙1024 расшифровок сообщения. При выбранном способе задания ключей, путем получения их из управляющего ключа длинной 7 бит, количество вариантов для перебора сокращается до 27 = 128, что является вполне переборной величиной.
Для ввода управляющего ключа следует кликнуть мышью кнопку «задать ключ» (если ключ был задан, кнопка будет называться «изменить ключ»). В появившемся диалоговом окне (Рис. 2) следует ввести ключ из семи бит (ноль или один) произвольным образом.
Рис. 2 Диалоговое окно задания ключа.
2. Произведите шифрование случайно выбранной двоичной последовательности длиной 16 бит с использованием выбранного в п.1 ключа. Наблюдайте результаты шифрования в каждом из 4-х раундов шифра SPN.
Для этого в окне ввода ключа кликните мышью кнопку «Исследовать раунды шифра». Откроется диалоговое окно исследования работы шифра (Рис. 3), содержащее схему учебного шифра,  поля для ввода двоичной последовательности 16 бит открытого сообщения, подлежащего шифрованию, и вывода 16-ти бит криптограммы. На схеме в местах, где применяются раундовые ключи, показаны последовательности бит, соответствующих этим ключам. Введите произвольную двоичную последовательность длинной 16 бит в соответствующее поле (Перемещаться между полями можно клавишами Tab и Shift+Tab). Затем следует кликнуть мышкой кнопку «зашифровать», которая находится левее схемы шифра.
Рис. 3 Диалоговое окно исследования работы шифра.
В нижней части схемы появятся 16 бит криптограммы, соответствующей введенному открытому сообщению, а правее схемы появится 11 последовательностей по 16 бит, соответствующих промежуточным результатам шифрования (Рис. 4).
Рис. 4 Диалоговое окно исследования работы шифра. Вывод промежуточных результаты шифрования.
Проверьте правильность выполнения шифрования для 1-го раунда шифра (биты ключа суммируются с битами шифруемого сообщения по модулю 2; таблица нелинейных преобразований s-box-ов приведена в приложении; порядок перестановок отображен на схеме).
3. Произведите дешифрование криптограммы, полученной на выходе шифра в п. 2 с использованием ключа, выбранного в п. 1. Для этого кликните мышью кнопку «расшифровать», расположенную ниже криптограммы. Убедитесь, что полученная последовательность совпадает с той, которая была выбрана в качестве «открытого текста» для шифрования в п. 2.
Расшифруйте  криптограмму при эмуляции ошибок в канале передачи. Для этого инвертируйте первый бит криптограммы, и расшифруйте ее. Подсчитайте количество позиций в которых расшифрованное сообщение отличается от исходного (выбранного в п. 2). Затем восстановите исходное значение первого бита криптограммы и инвертируйте второй. Произведите расшифровку и подсчет ошибок, также как и для первого бита криптограммы.
Проделайте эти действия поочередно инвертируя все 16 бит криптограммы. Результаты внесите в таблицу отчета. Подсчитайте среднее количество ошибок по формуле:
4. Произведите шифрование смыслового текста, на ключе, выбранном в п. 1. Для этого вернитесь в основное окно программы, нажав кнопку «выйти» в окне исследования работы шифра (Рис. 3) и в окне ввода ключа (Рис. 2). Основное окно предназначено для работы шифра со смысловым текстом или большими объемами данных (больше одного блока) и содержит два текстовых поля – левое и правое. Для отображения «открытого» смыслового текста, подлежащего шифрованию, служит левое поле (в него возможен ввод символов с клавиатуры), для отображения зашифрованного сообщения, подлежащего дешифрованию, служит правое поле (ввод символов с клавиатуры в это поле невозможен).
Поместите в левое поле смысловой текст. Это можно сделать несколькими способами: набрать текст с клавиатуры компьютера; вставить текст из буфера обмена комбинацией клавиш Ctrl+V (предварительно поместив его туда в любом текстовом редакторе или процессоре командой «копировать» Ctrl+C либо «вырезать» Ctrl+X); открыть  файл, содержащий текст, для этого необходимо кликнуть мышью кнопку «открыть файл», расположенную непосредственно под полем открытого сообщения (Рис. 1), и выбрать текстовый файл для открытия. В папку, содержащую рабочую программу, должны быть помещены текстовые документы для выполнения лабораторной работы. Текст, отображаемый в левом поле, при желании можно сохранить. Для этого следует кликнуть кнопку «сохранить в файл», расположенную под сохраняемым текстом (Рис. 1).
После появления в левом поле «открытого» текста кликните мышкой кнопку «зашифровать =>» (Рис. 1). В правом поле появится шифртекст -  набор символов кода ASCII, соответствующих значениям байтов зашифрованного сообщения. Предусмотрена возможность сохранить зашифрованное сообщение в файл данных с помощью кнопки «сохранить в файл», расположенной под правым полем (Рис. 1). Чтобы позднее открыть этот файл для расшифровки следует воспользоваться кнопкой «открыть файл», расположенной под правым полем (Рис. 1).
5. Произведите дешифрование криптограммы ,полученной в п. 5, на ключе, сгенерированном в пункте 1, и на произвольном, отличном от верного, ключе. Для этого необходимо записать или запомнить ключ шифрования из пункта 1.
Очистите левое поле от «открытого» текста, кликнув кнопку «очистить» под левым полем. Сгенерируйте новый ключ шифрования. Для этого кликните кнопку «изменить ключ» и в появившемся окне ввода ключа произвольным образом задайте новый управляющий ключ из 7-ми бит. Вернитесь в основное окно программы и нажмите кнопку «<=расшифровать» (Рис. 1). В левом поле появится «абракадабра» - бессмысленный набор символов, внешне похожий на набор символов в правом поле, но отличный от него.
Убедившись в том, что дешифрование на неверном ключе не дает результатов, вновь кликните кнопку «изменить ключ» и восстановите то значение ключа, на котором производилось шифрование. Снова расшифруйте криптограмму, содержащуюся в правом поле, но теперь на истинном ключе. Убедитесь в том, что расшифрованное сообщение совпадает с исходным.
6. Проведите криптоанализ криптограммы, полученной в п. 4, методом тотального перебора ключей. При этом правильный ключ определяется по статистике символов дешифрованного сообщения, которая должна быть близка к статистике смыслового сообщения. Для этого кликните мышью кнопку «подобрать ключ» (Рис. 1). На экране монитора появится окно задания параметров криптоанализа (Рис. 5).
Рис. 5 Окно задания параметров криптоанализа.
В появившемся окне следует задать допустимые интервалы отклонения частот появления символов в смысловом тексте. Если принять среднее значение частоты появления буквы в смысловом тексте за P [%] а отклонение за dP, то допустимый интервал анализируемых частот в процентах определяется как
(P-dp , P+dp). [%]
В программе реализован анализ частот по 6 буквам текста, трем русским: «О», «А», «И», и трем латинским: «E», «T», «O»  и символу «пробел». Средние значения  частот появления букв в русском и английском языках приведены в таблицах 1 и 2.
Таблица 1.
 Средние частоты появления букв русского алфавита в Русском языке.
Буква
Частота %
Буква
Частота %
Буква
Частота %
А
6,2
К
2,8
Ф
0,02
Б
1,4
Л
3,5
Х
0,9
В
3,8
М
2,6
Ц
0,4
Г
1,3
Н
5,3
Ч
1,2
Д
2,5
О
9,0
Ш
0,6
Е, Ё
7,2
П
2,3
Щ
0,3
Ж
0,7
Р
4,0
Ь, Ъ
1,4
З
1,6
С
4,5
Э
0,3
И
6,2
Т
5,3
Ю
0,6
Й
1,0
У
2,1
Я
1,8
Таблица 2.
Средние частоты появления букв латинского алфавита в Английском языке.
Буква
Частота %
Буква
Частота %
Буква
Частота %
A
8,1
K
0,4
V
0,9
B
1,4
L
3,4
W
1,5
C
2,7
M
2,5
X
0,2
D
3,9
N
7,2
Y
1,9
E
13,0
O
7,9
Z
0,1
F
2,9
P
2,0
G
2,0
R
6,9
H
5,2
S
6,1
I
6,5
T
10,5
J
0,2
U
2,4
Частота появления пробела 17,5%.
При криптоанализе программа последовательно расшифровывает и анализирует сообщение на всех ключах. При попадании частот символов дешифрованного сообщения в заданные интервалы программа примет решение о правильном ключе и остановится. (Следует выбрать режим анализа «Пробовать до совпадения стастистики»)
Рис. 6. Окно вывода результатов криптоанализа.
Предусмотрена возможность продолжить перебор в случае появления нескольких сообщений о ключе – одного правильного и  нескольких ложных. В этом случае следует уменьшить интервалы частот и повторить криптоанализ. При появлении сообщения о не обнаружении смыслового текста следует, напротив, увеличить интервалы частот.
7. Повторите пункт 6, выбирая различные исходные ключи для шифрования. Сохраните зашифрованное сообщение в виде файла и передайте его в соседнюю бригаду на дискете или по локальной сети. Получите аналогичную криптограмму от соседней бригады и проведите ее криптоанализ методом тотального опробования ключей. Расшифруйте сообщение на ключе шифрования и прочитайте зашифрованный текст.
Отчет по лабораторной работе
«Криптоанализ блочного шифра тотальным перебором ключей»
(пример оформления)
Выполнил студент:  Петров В.В.
Группа:  МТ-000
Преподаватель: Яковлев В.А.
1. Генерация раундовых ключей.
Выбран управляющий ключ из 7-ми бит: 1111111
Cгенерированы раундовые ключи:
K1= 1111 1111 1111 1111
K2= 1111 1111 1111 1111
K3= 1111 1111 1111 1111
K4= 1111 1111 1111 1111
K5= 1111 1111 1111 1111
2. Анализ преобразований шифра.
Произвольно выбранная двоичная последовательность длиной 16 бит для шифрования («открытый текст»):
  
0000 0000 0000 0000
Полученная криптограмма:     1100 0101 1011 0111
Промежуточные результаты.
Раунд 1
подмешивание ключа:                            1111 1111 1111 1111
нелинейное преобразование s-box-ов:  0111 0111 0111 0111
перестановка:                                          0000 1111 1111 1111
Раунд 2
подмешивание ключа:                            1111 0000 0000 0000
нелинейное преобразование s-box-ов:  0111 1110 1110 1110
перестановка:                                          0111 1111 1111 1000
Раунд 3
подмешивание ключа:                            1000 0000 0000 0111
нелинейное преобразование s-box-ов:  0011 1110 1110 1000
перестановка:                                          0111 0110 1110 1000
Раунд 4
подмешивание ключа:                            1000 1001 0001 0111
нелинейное преобразование s-box-ов:  0011 1010 0100 1000
Раунд 5
подмешивание ключа:                            1100 0101 1011 0111
3.Исследование влияния ошибок в канале передачи.
Исходная криптограмма:         1100 0101 1011 0111
Расшифровка криптограммы: 0000 0000 0000 0000
Расшифровка криптограммы при эмуляции ошибки
в 1-м бите
криптограмма с ошибкой:       0100 0101 1011 0111
расшифровка криптограммы: 1100 0011 0010 0000
количество ошибок в расшифровке: 5
во 2-м бите
криптограмма с ошибкой:       1000 0101 1011 0111
расшифровка криптограммы:  0000 1110 0011 0100
количество ошибок в расшифровке: 6
в 3-м бите
криптограмма с ошибкой:       1110 0101 1011 0111
расшифровка криптограммы: 0111 1111 0111 1110
количество ошибок в расшифровке: 13
в 4-м бите
криптограмма с ошибкой:        1101 0101 1011 0111
расшифровка криптограммы:  1001 0011 0111 1010
количество ошибок в расшифровке: 9
в 5-м бите
криптограмма с ошибкой:       1100 1101 1011 0111
расшифровка криптограммы:  0010 1011 0010 1001
количество ошибок в расшифровке: 7
в 6-м бите
криптограмма с ошибкой:       1100 0001 1011 0111
расшифровка криптограммы:  0001 1001 0001 1001
количество ошибок в расшифровке: 6
в 7-м бите
криптограмма с ошибкой:       1100 0111 1011 0111
расшифровка криптограммы:  1000 1111 0001 0000
количество ошибок в расшифровке: 6
в 8-м бите
криптограмма с ошибкой:       1100 0100 1011 0111
расшифровка криптограммы:  0001 1011 0001 1001
количество ошибок в расшифровке: 7
в 9-м бите
криптограмма с ошибкой:       1100 0101 0011 0111
расшифровка криптограммы:  1010 1010 0000 0100
количество ошибок в расшифровке: 5
в 10-м бите
криптограмма с ошибкой:       1100 0101 1111 0111
расшифровка криптограммы:  1111 1011 1110 1100
количество ошибок в расшифровке: 12
в 11-м бите
криптограмма с ошибкой:       1100 0101 1001 0111
расшифровка криптограммы:  0011 0010 0000 1011
количество ошибок в расшифровке: 6
в 12-м бите
криптограмма с ошибкой:       1100 0101 1010 0111
расшифровка криптограммы:  0011 0110 1010 0111
количество ошибок в расшифровке: 9
в 13-м бите
криптограмма с ошибкой:       1100 0101 1011 1111
расшифровка криптограммы:  1001 1101 1001 1101
количество ошибок в расшифровке: 10
в 14-м бите
криптограмма с ошибкой:       1100 0101 1011 0011
расшифровка криптограммы:  1111 0111 1010 0101
количество ошибок в расшифровке: 11
в 15-м бите
криптограмма с ошибкой:       1100 0101 1011 0101
расшифровка криптограммы:  1001 1011 0110 0101
количество ошибок в расшифровке: 9
в 16-м бите
криптограмма с ошибкой:       1100 0101 1011 0110
расшифровка криптограммы:  1111 0000 1111 1011
количество ошибок в расшифровке: 11
Среднее значение ошибок в дешифрованном сообщении при ошибочном приеме одного бита криптограммы.
Nош.ср. = (5 + 6 + 13 + 9 + 7 + 6 + 6 + 7 + 5 + 12 + 6 + 9 + 10 + 11 + 9 + 11) / 16 =8,25
Криптоанализ перебором всех возможных ключей
При отклонении в 6% частотные интервалы равны:
P(«о»)=  ( 3 , 15) %  
P(«а»)=  ( 0.2 , 12.2)  %
P(«и»)= (0.2 , 12.2 )  %
проверялись ключи:
ключ=1110001 P(«о»)=2,4%   P(«а»)=0,4%   P(«и»)=0,2%
ключ=1111111 P(«о»)=10,5%   P(«а»)=5,2%   P(«и»)=5,7%
При отклонении в 5% частотные интервалы равны:
P(«о»)=  ( 4 , 14) %  
P(«а»)=  ( 1.2 , 11.2)  %
P(«и»)= (1.2 , 11.2 )  %
проверялись ключи:
ключ=1111111 P(«о»)=10,5%   P(«а»)=5,2%   P(«и»)=5,7%
минимальные частотные интервалы, на которых извлекается ключ соответствуют отклонению в 1%
P(«о»)=  ( 8 , 10) %  
P(«а»)=  ( 5.2 , 7.2)  %
P(«и»)= (5.2 , 7.2 )  %
Контрольные вопросы
1.Принципы построения  SPN-шифра.
2.Зачем нужны перестановки , подстановки и итерации для построения стойкого шифра?
3.Является ли свойство “размножения” ошибок положительным или отрицательным свойством блоковых шифров?
4.Что такое расстояние единственности?
5.Каким может быть признак выбора правильного ключа при автоматическом переборном методе криптоанализа?
Литература
1.В.И.Коржик , В.П.Просихин, “Основы криптографии”’, Учебное пособие ,
Линк”,2008.
2.В.И.Коржик , Д.В.Кушнир “Теоретические основы информационной безопасности телекоммуникационных систем”.(Учебное пособие , ГУТ ,2000)
3.H.Heys “A Tutorial on Linear and Differential Cryptanalysis”, Manuscript.


 

А также другие работы, которые могут Вас заинтересовать

30250. WinSock или Windows socket 275.57 KB
  Существуют две версии WinSock: WinSock 1.1 поддерживает только протокол TCP IP; WinSock 2. WinSock 1.1 состояла в решении проблемы то цель WinSock 2.
30251. Виды сетей 629.35 KB
  Используя единый кабель каждый компьютер требует только одной точки подключения к сети при этом он может полноценно взаимодействовать с любым другим компьютером в группе. Геометрически ЛВС всегда ограничена по размерам небольшой площадью в силу электрических свойств кабеля используемого для построения сети и относительно небольшим количеством компьютеров которые могут разделять одну сетевую среду передачи данных. Для поддержки вычислительных систем большего размера были разработаны специальные устройства которые позволили объединять две...
30252. Эталонная модель взаимодействия открытых систем 347.85 KB
  Каждый уровень предоставляет услуги уровням расположенным непосредственно ниже и выше его в стеке. Служебная информация представляет собой заголовки и иногда постинформацию которые обрамляют данные полученные с вышележащего уровня. В известном смысле форма состоящая из заголовков и хвостов это оболочка которая является носителем сообщения полученного от вышележащего уровня. В сущности протоколы выполняющиеся на различных уровнях взаимодействуют с протоколами расположенными на точно таком же уровне другого компьютера.
30253. Ethernet 1.3 MB
  Хотя оба эти типа фреймов формально содержат поле “типа†оно применяется только для обозначения обшей длины пакета а не типа используемого протокола поэтому фреймы этих двух типов подходят только для протоколов 1PX SPX. С этого момента переходим к описанию полей фрейма канального уровня перечень которых приведен ниже. В этом поле находится МАСадрес получателя. В этом поле находится МАСадрес отправителя.
30254. Основные методы (школы) литературоведения. Мифологический метод 37.5 KB
  Мифологический метод Мифологическое литературоведение. Как особый метод мифологическое литературоведение сформировалось в 30ые г. в Западной Европе хотя еще со времен Средневековья существовала герменевтика истолкование священных изотерических текстов которая имела филологическое и мифологическое понимание. Философская основа классической мифологической школы стала эстетика Шеллинга братьев Шлегеллей которые утверждали что в основе всякой культуры литературы оказывается мифология.
30255. Основные методы (школы) литературоведения. Мифологический метод в русском литературоведении 37.5 KB
  Мифологический метод в русском литературоведении Мифологическое литературоведение. Как особый метод мифологическое литературоведение сформировалось в 30ые г. в Западной Европе хотя еще со времен Средневековья существовала герменевтика истолкование священных изотерических текстов которая имела филологическое и мифологическое понимание. Философская основа классической мифологической школы стала эстетика Шеллинга братьев Шлегеллей которые утверждали что в основе всякой культуры литературы оказывается мифология.
30256. Основные методы (школы) литературоведения. Основные методы (школы) литературоведения. Психоаналитический метод 31 KB
  Психоаналитический метод Эта влиятельная в литературоведении школа возникла на основе учения австрийского психиатра и психолога Зигмунда Фрейда 1856 – 1939 и его последователей.
30257. Основные методы (школы) литературоведения. Формальный метод 26.5 KB
  Формальный метод Общество изучения поэтического языка научное объединение созданное в 1916 18 группой лингвистов Е. Печатный орган Сборники по теории поэтического языка в. были теория поэтического языка и стиха Поливанов Якубинский Брик; Эйхенбаум Мелодика русского лирического стиха 1922; Тынянов Проблема стихотворного языка 1924 2 изд.
30258. Цели и задачи теории литературы 45 KB
  Цели и задачи теории литературы Литературоведение – наука о литературе. Она охватывает различные области изучения литературы и на современном этапе научного развития делится на такие самостоятельные научные дисциплины: теория литературы изучает социальную природу специфику закономерности развития и общественную роль художественной литературы и устанавливает принципы рассмотрения и оценки литературного материала история литературы исследует процесс литературного развития и определяет место и значение в этом процессе различных литературных...