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.


 

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

29152. Обращение взыскания на заложенное имущество 25 KB
  По общему правилу требования залогодержателя удовлетворяются из стоимости заложенного недвижимого имущества по решению суда. Без обращения в суд это можно сделать на основании нотариально удостоверенного соглашения залогодержателя с залогодателем заключенного после возникновения оснований для обращения взыскания на предмет залога. В отличие от этого за счет заложенного движимого имущества требования залогодержателя обычно удовлетворяются по решению суда лишь если иное не предусмотрено соглашением залогодателя с залогодержателем.
29153. Реализация заложенного имущества 26.5 KB
  Реализация заложенного имущества. Реализация продажа заложенного имущества на которое обращено взыскание осуществляется в порядке установленном законом об ипотеке или законом о залоге если иное не предусмотрено законом. Если сумма вырученная при реализации заложенного имущества недостаточна для покрытия требования залогодержателя он имеет право при отсутствии иного указания в законе или договоре получить недостающую сумму из прочего имущества должника не пользуясь преимуществом основанным на залоге. Если сумма вырученная при...
29154. Прекращение залога 25 KB
  Залог – способ обеспечения обязательства при котором кредитор залогодержатель приобретает право в случае неисполнения должником обязательства получить удовлетворение за счет заложенного имущества. Залог прекращается: 1 с прекращением обеспеченного залогом обязательства; 2 по требованию залогодателя; 3 в случае гибели заложенной вещи или прекращения заложенного права если залогодатель не воспользовался правом; 4 в случае реализации продажи заложенного имущества в целях удовлетворения требований залогодержателя. При прекращении залога...
29155. Поручительство 25.5 KB
  По договору поручительства поручитель обязывается перед кредитором другого лица отвечать за исполнение последним его обязательства полностью или в части. Договор поручительства может быть заключен также для обеспечения обязательства которое возникнет в будущем. Договор поручительства должен быть совершен в письменной форме. Несоблюдение письменной формы влечет недействительность договора поручительства.
29156. Прекращение поручительства 25.5 KB
  Поручительство поручитель обязывается перед кредитором другого лица отвечать за исполнение последним его обязательства полностью или в части. Поручительство прекращается с прекращением обеспеченного им обязательства в случае изменения этого обязательства влекущего увеличение ответственности или иные неблагоприятные последствия для поручителя без согласия последнего с переводом на другое лицо долга по обеспеченному поручительством обязательству если поручитель не дал кредитору согласия отвечать за нового должника. если кредитор в...
29157. Банковская гарантия 27 KB
  В силу банковской гарантии банк иная кредитная или страховая организация гарант дают по просьбе другого лица принципала письменное обязательство уплатить кредитору принципала бенефициару в соответствии с условиями даваемого гарантом обязательства денежную сумму по представлении бенефициаром письменного требования о ее уплате. По получении требования бенефициара гарант должен без промедления уведомить об этом принципала и рассмотреть приложенные к требованию документы. Решив отказать в удовлетворении требования гарант обязан немедленно...
29158. Прекращение банковской гарантии 25 KB
  Прекращение банковской гарантии. В силу банковской гарантии банк иная кредитная или страховая организация гарант дают по просьбе другого лица принципала письменное обязательство уплатить кредитору принципала бенефициару в соответствии с условиями даваемого гарантом обязательства денежную сумму по представлении бенефициаром письменного требования о ее уплате. Обязательство гаранта перед бенефициаром по гарантии прекращается: 1 уплатой кредитору суммы на которую выдана гарантия; 2 окончанием определенного в гарантии срока на который...
29159. Задаток 25 KB
  Задаток Задаток признается денежная сумма выдаваемая одной из договаривающихся сторон в счет причитающихся с нее по договору платежей другой стороне в доказательство заключения договора и в обеспечение его исполнения. Соглашение о задатке независимо от суммы задатка должно быть совершено в письменной форме в связи с этим задаток одновременно служит и доказательством заключения договора и средством обеспечения его исполнения. Если за неисполнение договора ответственна сторона давшая задаток он остается у другой стороны. В противном...
29160. Удержание в гражданском праве 22 KB
  Кредитор у которого находится вещь подлежащая передаче должнику либо лицу указанному должником вправе в случае неисполнения должником в срок обязательства по оплате этой вещи или возмещению кредитору связанных с нею издержек и других убытков удерживать ее до тех пор пока соответствующее обязательство не будет исполнено. Требования кредитора удерживающего вещь удовлетворяются из ее стоимости в объеме и порядке предусмотренном законом для удовлетворения требований обеспеченных залогом. Кредитор может удерживать находящуюся у него вещь...