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.


 

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

36560. Аппаратное и программное обеспечение компьютера 32 KB
  Программное обеспечение включает в себя прежде всего операционную систему такую как MS DOS Windows 3.1 или Windows 95. Одной из первых систем графического интерфейса была Windows 3. Так в системе Windows вы можете одновременно выводить информацию на принтер и редактировать какойлибо файл информации.
36561. Программы, управляемые событиями 28.5 KB
  Для реакции такой программы на внешние события например сигналы таймера ошибки в устройствах компьютера и др. аппаратные переключения с выполнения исходной программы на специальную программу обработки прерывания. Средства прерывания широко применяли в рамках концепции последовательной программы при организации многозадачных режимов и эффективного использования процессора компьютера. Однако концепция последовательной программы несмотря на свою универсальность оказывается неэффективной для современного персонального компьютера имеющего...
36562. Принцип программного управления 45 KB
  Всё что способен делать компьютер это выполнять программы. Процессор â€движущая сила†исполнитель точно выполняющий команды программы. а также операции копирования перемещения информации из одних ячеек памяти в другие ввода данных в оперативную память например символов набранных на клавиатуре вывода информации например на экран дисплея или на диск окончания программы и другие.  Процессор выполняет команды начиная с первой команды программы.
36563. Структурный тип запись 45 KB
  Например анкета служащего содержит такие данные как фамилия имя отчество строковый тип год рождения целый тип разряд целый тип и многие другие данные. Объединение таких данных общий структурный типанкета затруднительно сделать в рамках массива или множества. Естественным средством структурирования в этом и подобных случаях является структурный тип Запись.
36564. Структурный тип множество 41.5 KB
  Понятие о типе Множество в Турбо Паскале. Множество является ещё одним структурным типом Турбо Паскаля служащим для объединения однородных однотипных элементов. Однако форма объединения в Множество существенно отличается от типа Массив.
36565. Особенности разработки программы с подпрограммой 35.5 KB
  Практически все используемые прикладные программы это программы с подпрограммами процедурами и функциями. Подпрограммы как уже указывалось позволяют преодолевать сложность обеспечивая декомпозицию программы на более простые составные части. Разработка программ на ТурбоПаскале с подпрограммами имеет ряд отличий от той методики которая изложена выше применительно с простым программам.
36566. Область действия имен в программе 29 KB
  В программах не использующих подпрограммы имена описанные в разделе описаний действуют во всей программе не вызывая какихлибо проблем. В подпрограммах могут использоваться свои локальные внутренние имена и кроме того она может также использовать глобальные внешние для неё имена из других подпрограмм или основной программы. Локальными именами подпрограммы называются те имена которые описаны в этой подпрограмме в её разделе описаний. Все остальные используемые в подпрограмме имена являются глобальными именами данной...
36567. Параметры-процедуры и параметры-функции. Процедурный тип 30.5 KB
  Описание процедурных типов имеет форму заголовка процедуры или функции с опущенным её именем: type имя процедурытипа = procedure список формальных параметров ; type имя функциитипа = function список формальных параметров : тип ; Например: type fun =function x:rel:rel; При описании подпрограммы с процедурными параметрами такие параметры указываются формальным именем и соответствующим процедурным типом. Пример процедуры использующей описанный выше процедурный тип fun: procedure print_f n:byte; f:fun; const count = 20; vr X:rel;...
36568. Особенности использования параметров в процедурах и функциях 30 KB
  Это означает что нельзя использовать описание типа rry непосредственно в списке формальных параметров. Например: procedure sttem:rry [1.8] of byte; {Неправильное описание параметра m} type byte_st = rry [1. type rry10 = rry[0.