Лаб 3 по кг. 6 Шифры AES и ГОСТ Р 34.12–2015 (1). Конкурс на новый стандарт ( Advanced Encryption Standard ) объявлен 12 сентября 1997 года институтом nist
 Скачать 2.85 Mb.
|
|
Алгоритм усовершенствованного стандарта шифрования AES Предпосылки: Недостаточная длина ключа DES (фактически 56 бит) Ориентация DES на аппаратную реализацию Уcпешные криптоатаки на DES Конкурс на новый стандарт ( Advanced Encryption Standard ) объявлен 12 сентября 1997 года институтом NIST (The National Institute of Standards and Technology, USA ): Заявки принимались от любой организация или группы исследователей Шифр-победитель должен распространяться по всему миру на не эксклюзивных условиях и без платы за пользование патентом Минимальные требования к новому стандарту касались типа алгоритм, длины блока обработки и допустимых размеров ключей Алгоритм должен быть симметричным шифром Алгоритм должен быть блочным шифром Алгоритм должен использовать длину блока 128 бит, и поддерживать три длины ключа : 128, 192 и 256 бит. Дополнительные требования: Использовать операции, легко реализуемые, как аппаратно (на микрочипах), так и программно Ориентироваться на 32-разрядные процессоры Не усложнять без необходимости структуру шифра для того, чтобы все заинтересованные стороны были в состоянии убедиться, что в нём не заложено каких-либо недокументированных возможностей Предварительный отбор: 20.08.1998 года на 1-й конференции AES был объявлен список из 15 кандидатов: CAST-256, CRYPTON , DEAL , DFC, E2, FROG , HPC , LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent, Twofish Первый раунд (128 битные ключи): Исследовались криптографическая стойкость, а также практические аспекты реализации: оптимизацию скорости выполнения и размера кода на различных архитектурах (от ПК до смарт-карт и аппаратных реализаций) В августе 1999 года были объявлены 5 финалистов: MARS, RC6, Rijndael, Serpent и Twofish Второй раунд (192-битные и 256-битные ключи ): Оценивалась пригодность финалистов для использования в качестве генераторов случайных чисел. Продолжительность статистических тестов NIST составила несколько месяцев По результатом полученных на обоих раундах характеристик шифров проведено голосование Rijndael Serpent TwoFish RC-6 MARS Аппаратная реализации ( эффективность ) + + Программная реализация (относительное быстродействие) 3.5 1 5.5 6 4 Этап расширения ключа + + Возможность распараллеливания + Запас криптостойкости Оптимум Завышен Завышен Оптимум Оптимум Кол-во голосов: ЗА/ПРОТИВ 86/10 59/7 31/21 23/37 13/83 Шифр RIJNDAEL официально объявлен победителем конкурса в день 02.10.2000 и получил второе наименование ADVANCED ENCRYPTION STANDARD Используется не сеть Фейстеля, а Square – like структуру( структуру «квадрат») Поддерживаются три версии ( с 10, 12 и 14 раундами). Каждая версия использует различный размер ключа шифра (128, 192 или 256) и имеет соответствующее название: AES-128, AES-196, AES-256 Ключи раунда имеют тот же самый размер, что и блоки зашифрованного или исходного текста - всегда 128 бит Байт ― последовательность из 8 битов . Операции над байтами производятся, как над элементами поля Галуа GF(2 8 ) , то есть байту {𝑏 7 𝑏 6 𝑏 5 𝑏 4 𝑏 3 𝑏 2 𝑏 1 𝑏 0 } соответствует полином 𝑏 7 𝑥 7 +𝑏 6 𝑥 6 +𝑏 5 𝑥 5 +𝑏 4 𝑥 4 +𝑏 3 𝑥 3 +𝑏 2 𝑥 2 +𝑏 1 𝑥 + 𝑏 0 Операция сложения полиномов выполняется, как XOR коэффициентов при одинаковых степенях (ХOR байтов) Операция умножения полиномов выполняется по модулю неприводимого полинома 𝑥 8 +𝑥 4 +𝑥 3 + 𝑥 + 1 (XOR c 11B 16 ) Блок ― последовательность из 16 байтов, над которой оперирует алгоритм Ключ ― последовательность из 16, 24 или 32 байтов Размер 4х4 байт Содержит промежуточные результаты обработки (состояния) блоков данных Раунд состоит из четырех различных обратимых преобразований, называемых слоями. Каждое преобразование модифицирует матрицу состояний Каждый слой разрабатывался с учетом противодействия линейному и дифференциальному криптоанализу: SubBytes - слой подстановок (замен) байтов для обеспечение нелинейных свойств шифра ShiftRows -cлой линейного перемешивания строк MixColums -слой линейного перемешивания столбцов AddRoundKey- слой рандомизации с выполнением XOR промежуточного состояния с ключом раунда. Процедура SubByte выполняет 16 независимых преобразований байта в байт ( если два байта имеют одинаковое значение, то они преобразуются одинаково) Содержание каждого байта изменяется, но расположение байтов в матрице остается тем же самым Допустимые реализации: Таблицей подстановки (S-блок) 16х16 Математическим вычислением -заменой байта аффинным преобразованием его мультипликативной инверсии в GF(2 8 ) по модулю неприводимого многочлена 𝑥 8 +𝑥 4 +𝑥 3 + 𝑥 + 1 В процессе расшифровки используется процедура InvSubByte – инверсная по отношению SubByte 𝒂 𝟏𝟔 =𝑩 𝟏𝟔 𝒃 𝟏𝟔 = 𝟑 𝟏𝟔 𝒄𝒅 𝟏𝟔 = 𝟔𝑫 𝟏𝟔 Обратная подстановка Прямая подстановка 10001111 11000111 11100011 11110001 11111000 01111100 00111110 00011111 1 1 0 0 0 1 1 0 cd = × 𝑎𝑏 −1 + (𝑎𝑏) × (𝑎𝑏 −1 ) ≡ 1 𝑚𝑜𝑑 (𝑥 8 +𝑥 4 +𝑥 3 + 𝑥 + 1) Операция ShiftRows производит циклический сдвиг влево Число сдвигов равно номеру обрабатываемой строки матрицы состояний Порядок битов в байте не меняется Для дешифрации используется процедура InvShiftRows – инверсная по отношению ShiftRows MixColumns преобразовывает каждый столбец матрицы состояний в новый столбец умножением на матрицу констант C Столбцы матрицы состояний рассматриваются как полиномы с коэффициентами в GF(2 8 ) и умножаются по модулю 𝑥 4 +1 на полином: ′03′𝑥 3 +′01′𝑥 2 + ′ 01 ′ 𝑥 + ′02′ Матрица констант С является циклической и реализует умножение полиномов по модулю 𝑥 4 +1 Для дешифрации используется процедура InvMixColumns ( c матрицей констант 𝐶 −1 ) – инверсная по отношению MixColumns С Ключ раунда рассматривается как четыре слова по 32 бита Операция AddRoundKey выполняет XOR каждой колонки матрицы состояний с соответствующим словом раундового ключа Процедура AddRoundKey инверсна сама себе Процедура расширения ключей ExpandKey создает последовательно (слово за словом) 128-битные ключи 𝑁 𝑟 раундов от единственного ключа шифра RotWord осуществляет циклический сдвиг байтов в слове влево SubWord осуществляет замену каждого байта в слове в соответствии с методом подстановок, использованном в SubByte . Rcon(i) формирует константу, i- номер раунда 𝑲 𝟎 𝑲 𝟏 𝑲 𝟐 𝑲 𝑵 𝒓 −𝟏 Пример генерации раундовых ключей для AES-128 Перед первым раундом применяется дополнительное забеливание с использованием ключа. Без этого любой слой до первого добавления ключа может быть просто снят без знания ключа, что не добавляет безопасности в алгоритм Для того чтобы сделать структуру алгоритма более простой, слой линейного перемешивания столбцов в последнем раунде отсутствует . Доказано, что это не повышает и не понижает безопасность. При расшифровании все преобразования производятся в обратном порядке Используются следующие обратные преобразования вместо соответствующих шифрующих: I nvSubBytes ― подстановка байтов с помощью обратной таблицы подстановок; I nvShiftRows ― циклический сдвиг строк матрицы состояния на различные величины; InvMixColumns ― смешивание столбцов внутри каждого столбца матрицы состояния Ключи раундов используются в обратном порядке Обеспечивает быстрое перемешивание информации, при этом за один раунд преобразованию подвергается весь входной блок Байт ориентированная структура удобна для реализации на восьмиразрядных микроконтроллерах Все раундовые преобразования – это операции в конечных полях, допускающие эффективную аппаратную и программную реализацию на различных платформах Преобразование раунда допускает параллельное выполнение, что является важным преимуществом для будущих процессоров и специализированной аппаратуры Overlay D2 Цель: Расшифровать 𝐶 2 , зная правило дополнения блока открытого текста 𝑃 2 Метод: Изменяем блок шифротекста, передаем измененный блок 𝐶 1 ′ и анализируем реакцию сервера- получателя на корректность дополнения: 𝑃 2 ′ = 𝐷 2 ⨁𝐶 1 ′ Знание реакции сервера-получателя позволяет восстановить 𝐷 2 = 𝑃 2 ′ ⨁𝐶 1 ′ Расшифровка производится по правилу 𝑃 2 = 𝐷 2 ⨁𝐶 1 См. детали в https://habrahabr.ru/post/247527/ Алгоритм стандарта шифрования ГОСТ Р 34.12–2015, ГОСТ Р 34.13–2015 ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ Р 34.12–2015 "Информационная технология. Криптографическая защита информации. Блочные шифры" (Утвержден и введен в действие Приказом Федерального агентства по техническому регулированию и метрологии от 19 июня 2015г. № 749-ст) ГОСТ Р 34.13–2015 "Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров" (Утвержден и введен в действие Приказом Федерального агентства по техническому регулированию и метрологии от 19 июня 2015г. № 750-ст) 22 Магма Кузнечик Это ГОСТ 28147-89 с фиксированным набором подстановок Узел замены, определенный Техническим комитетом по стандартизации "Криптографическая защита информации" (сокращенно - ТК 26) Росстандарта (Рекомендации по стандартизации "Задание узлов замены блока подстановки алгоритма шифрования ГОСТ 28147-89") Новый алгоритм, в основе которого SP-сеть: преобразование, состоящее из нескольких одинаковых раундов, при этом каждый раунд состоит из нелинейного и линейного преобразований, а также операции наложения ключа. В отличие от алгоритма AES у «Кузнечика» есть ряд своих особенностей: • линейное преобразование может быть реализовано в с помощью регистра сдвига; • Генерация раундовых ключей реализована с помощью сети Фейстеля, в которой в качестве функции используется раундовое преобразование алгоритма шифрования (Кузнечик) 23 Номер S- блока Подстановка 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 12 4 6 2 10 5 11 9 14 8 13 7 0 3 15 1 2 6 8 2 3 9 10 5 12 1 14 4 7 11 13 0 15 3 11 3 5 8 2 15 10 13 14 1 7 4 12 9 6 0 4 12 8 2 1 13 4 15 6 7 0 10 5 3 14 9 11 5 7 15 5 10 8 1 6 13 0 9 3 14 11 4 2 12 6 5 13 15 6 9 2 12 10 11 7 8 1 4 3 14 0 7 8 14 2 5 6 9 1 12 15 4 11 0 13 10 3 7 8 1 7 14 13 0 5 8 3 4 15 10 6 9 12 11 2 Раунд 1 Раунд 9 SP-сеть с набором преобразований L, S, X Количество раундов - 9 Длина блока – 128 бит Длина ключа – 256 бит Генерация (развертывание) раундовых ключей основана на сети Фейстеля X (XOR) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 252 238 221 17 207 110 49 22 251 196 250 218 35 19 4 77 1 233 119 240 219 147 46 153 186 23 54 241 187 20 205 95 193 2 249 24 101 90 226 92 239 33 129 28 60 66 139 1 142 79 3 5 132 2 174 227 106 43 160 6 11 237 152 127 212 211 31 4 235 52 44 81 234 200 72 171 242 42 104 162 253 58 206 204 5 181 112 14 86 8 12 118 18 191 114 19 71 156 183 93 135 6 21 161 150 41 16 123 154 199 243 145 120 111 157 158 178 177 7 50 117 25 61 255 53 138 126 109 84 198 128 195 189 13 87 8 223 245 36 169 62 168 67 201 215 121 214 246 124 34 185 3 9 224 15 236 222 122 148 176 188 220 232 40 80 78 51 10 74 10 167 151 96 115 30 0 98 68 26 184 56 130 100 159 38 65 11 173 69 70 146 39 94 85 47 140 163 165 125 105 213 149 59 12 7 88 179 64 134 172 29 247 48 55 107 228 136 217 231 137 13 225 27 131 73 76 63 248 254 141 83 170 144 202 216 133 97 14 32 113 103 164 45 43 9 91 203 155 37 208 190 229 108 82 15 89 166 116 210 230 244 180 192 209 102 175 194 57 75 99 182 L представимо в виде регистра сдвига с обратной связью, который движется 16 раз Регистр реализуется над полем Галуа по модулю неприводимого многочлена 𝑥 8 +𝑥 7 +𝑥 6 + 𝑥 + 1 28 Первые 2 ключа являются разбиением пополам основного ключа Каждая пара следующих ключей определяется с помощью пары предыдущих, прошедших через 8 раундов сети Фейстеля LSX XOR 𝑲 𝟐𝒊 𝑲 𝟐𝒊−𝟏 𝑲 𝟐𝒊−𝟏 LSX XOR Открытый текст Шифротекст Расшифрование реализуется применением преобразований инверсным к базовым Раундовые ключи применяются в обратном порядке Режим Mode Режим простой замены ECB Режим гаммирования CTR Режим гаммирования с обратной связью по выходу OFB Режим простой замены с зацеплением CBC Режим гаммирования с обратной связью по шифртексту CFB Режим выработки имитовставки MAC 32 Процедура 1: дополняем «0000000…0» (нулями). В общем случае получателю нужно знать длину сообщения. Процедура 2: дополняем «10000000…0» (единица с нулями) Процедура 3: НЕ дополняем, если длина сообщения кратна размеру блока, а иначе дополняем в соответствии с Процедурой 2 (обязательна для режима выработки имитовставки и не рекомендуется для других режимов) Electronic Codebook, ЕСВ ECB является самым простым и самым быстрым способом использования блочного шифра. ECB хорошо использовать для шифрования случайных данных, например, других ключей. Cipher Block Chaining, СВС CBC лучше всего подходит для шифрования файлов Output Feedback, OFB OFB чаще всего используется в высокоскоростных синхронных системах, где недопустимо распространение ошибки Cipher Feedback, CFB CFB обычно выбирается для шифрования потока символов, когда каждый символ может рассматриваться отдельно, как в линии связи между терминалом и главным компьютером Counter, CTR Для CRT свойства синхронизации и распространения ошибки такие же, как и для OFB Message Authentication Code (MAC) algorithm Используется для контроля целостности сообщения, а не для обеспечения сокрытия содержания Эталонная реализация шифров https://tc26.ru/standard/gost/PR_GOSTR-bch_v5.zip Текст стандарта шифров https://tc26.ru/standarts/nat sionalnye-standarty/ https://tc26.ru/standard/gost/ GOST_R_3412-2015.pdf Сайт ТК по стандартизации ГОСТ 34.12-2018 – Информационная технология. Криптографическая защита информации . Блочные шифры ГОСТ 34.13-2018 - Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров ОСНОВАНИЕ - терминологическая и концептуальная увязка с международными стандартами от ИСО |