Совершенствование режимов работы блочных шифров для полнодискового шифрования

Все выбранные режимы позволяют построить сохраняющий длину настраиваемый шифр с использованием симметричного блочного шифра.На рисунке 4 изображены нижние оценки уровня информационной безопасности для режимов XEH, HEHи CMCпри использовании блочного шифра с размером блока l=128 бит в логарифмическом масштабе в зависимости от суммарной сложности запросов - величины о, определяемой как количество блоков, зашифрованных нарушителем на одном ключе шифрования. В случае режима XEHσ=( n+1) q, так как на каждом запросе на ключе зашифровывается n+1 блок (nблоков маскированного открытого текста, а также номер сектора для выработки подключа τ1). Для режима XTSоценка уровня информационной безопасности на графике не показана, так как на данный режим была построена атака (теорема 1).По графику на рисунке 1.8видно, что режим XEHобеспечивает более высокую нижнюю оценку уровня информационной безопасности (чем выше оценка, тем больше данных необходимо зашифровать нарушителю для достижения величины преобладания, которое не может считаться пренебрежимо малым).На рисунке 1.9 изображена диаграмма усредненного относительного времени, необходимого на шифрование или расшифрование сектора размером 512 или 4096 байт при использовании режимов XTS, XEH, HEH и CMC. В качестве симметричного блочного шифра использовался шифр «Кузнечик». Так как время работы режима XTS принято за базовое значение, то соответствующие столбцы на диаграмме имеют высоту 1.Рисунок 1.8. Оценки уровня информационной безопасности режимов XEH, HEH и CMC в зависимости от суммарной сложности запросов при использовании блочного шифра с размером блока l=128 битПо графику видно, что режим XEH работает в среднем дольше, чем XTS, однако разница в затраченном времени не превышает 6 процентов (при расшифровании сектора размером 4096 байт проигрыш относительно XTS является наибольшим и составляет 5.3 процента). Объясняется это применением полиномиальной подстановки к блокам сектора и выработкой дополнительных подключей.Рисунок 1.9. Усредненное относительное время, затрачиваемое на шифрование и расшифрование сектора размером 512 или 4096 байт с использованием симметричного блочного шифра «Кузнечик» и режимов XTS, XEH, CMC и HEHНаименее производительным оказался режим CMC, который проигрывает48%по сравнению с режимом XTSпри расшифровании сектора размером 512 байт. Связано это с тем, что среднее значение полиномиальной подстановки для режимов XEHи HEHрассчитываются быстрее, чем происходит шифрование того же объема данных в режиме CBC. В режиме XTSрасчет полиномиальных подстановок не используется.Самым производительным является режим HEH, который выигрывает за счет меньшего количества умножений в поле GL(2l)по сравнению с режимами XEHи HEH.2. Обзор методов вычисления полиномов.Для работы с информацией при кодировании и декодировании данных все арифметические операции выполняются в полях Галуа. Применяется так называемая полиномиальная арифметика или арифметика полей Галуа.2.1 Алгоритмы умножения в полях Галуа и особенности их программной реализации. При построении современных систем обработки информации зачастую возникает необходимость эффективной реализации арифметических операций над элементами поля Галуа. Особый интерес представляет операция умножения в поле, как наиболее требовательная к аппаратным ресурсам и ограниченная с точки зрения быстродействия. При этом от эффективности реализации данной операции существенно зависят аппаратные и временные характеристики соответствующей системы обработки информации.2.1.1Алгоритм умножения двух элементов поля «сдвиг-со-сложением, справа-налево»Данный алгоритм реализует умножение двух элементов поляГалуа GF(2m), представленных в виде полиномов, образованных полиномом p(x). Приведенное название является калькой с англоязычного обозначения данного алгоритма: «right-to-leftshift-and-addfieldmultiplication» [5]. Этот алгоритм основан на том, чтоa·b = am—1xm-1b +... + a2x2b + a1xb + a0b.(2.1)На каждом шаге итерации iв этом алгоритме вычисляется произведение xibmodp(x),и полученное значение складывается с произведением при условии, что ai = 1, как показано в алг. 1.Алгоритм 1. Умножение двух элементов поля Галуа «сдвиг-со-сложением, справа-налево»В качестве примера рассмотрим перемножение двух элементов поля Галуа, представленных в виде полиномов a(x) и b(x), над полем GF(24), образованного полиномом: p(x) = x4+x+ 1:a(x) = x2 + 1 = 1010 = Ɛ8b(x) = x2 +x = 0110 = Ɛ5a0= 1, тогдаc(x) = b(x) = x2+ x.Шаг1:b(x)= x · b(x) mod p(x)= x3 + x2;a1= 0 следовательно переходим на следующий шагШаг 2:b(x)= x· b(x) mod p(x) = (x · (x3 + x2)) mod p(x)= x3 + x + 1;a1= 1 следовательно c (x) = c (x) + b (x) = (x2 + x) + (x3 + x + 1) = x3 + x2 + 1;Шаг3:b(x) = (x · (x3 + x + 1)) mod p(x)= x2 + 1;a1= 0 следовательно завершаем работу алгоритмаРезультат: c(x) = x3 +x2+ 1 = 1011 = Ɛ13.Данный алгоритм подходит для аппаратной реализации на логических элементах, в которых сдвиг вектора bреализуется за один такт работы процеессора, но не эффективен для программной реализации из-за дополнительной нагрузки на центральный процессор.2.1.2. Алгоритм Карацубы-Офмана умножения двух элементов поля ГалуаЭтот алгоритм позволяет уменьшить сложность умножения n-значных чисел с O(n2) до O(nlog23).Данный алгоритм может быть применимдля умножения элементов конечного поля, представленных в виде полиномов. Рассмотрим алгоритм умножения двух элементов поля.Обычно выделяют два варианта алгоритма Карацубы-Офмана. Первый вариант алгоритма — это так называемый 2kn-битный умножитель. Он предназначен для работы с элементами поля GF(2m), где m= rn, r= 2k.Множители Aи B, принадлежащие полю GF(2m), представляются в виде полиномов через левый степенной базис формулой: (2.2)Каждый из полученных полиномов AH(x), AL(x), BH(x),BL(x) имеет в два раза меньшуюстепень, нежели исходные множители A(x) и B(x).Тогда произведение C= A· Bможно представить в виде: (2.3)Полином-произведение C(x), полученный в результате вычисления по алгоритму Карацубы-Офмана, имеет длину до 2m- 1 двоичных элементов. Следовательно, чтобы определить элемент поля C∈GF(2m), равный A· B, необходимо привести полином C(x) по модулю образующего многочлена полиномаp(x).Введем две переменные, как показано в формуле: (2.4)Таким образом, в соответствии с вышеприведённой формулой 2.3, для вычисления произведения C необходимо провести четыре операции сложения:(2.5)и три операции умножения:AHBH,ALBL, (2.6)MAMBПроцедура умножения повторяется рекурсивно пока не будут получены однобитные множители, произведение которых вычисляется за одну операцию умножения. Количество итераций не превышает [log2(m)]. На практике для умножения элементов поля большой степени часто применяют схему, в которой алгоритм Карацубы-Офмана используется для уменьшения длины операндов до значения, при котором удобно применить какой-либо из быстрых алгоритмов умножения, который был бы слишком сложен для реализации при применении его к операндам большой длины.Алгоритм 2kn-битного умножителя Карацубы-Офмана представлен в алг.3Алгоритм 2. Алгоритм 2kn-битного умножителя Карацубы-ОфманаВторым вариантом использования алгоритма Карацубы-Офмана является так называемый двоичный умножитель Карацубы, предназначенный для работы с полями Галуа GF(2m) произвольной степени m.Алгоритм двоичного умножителя Карацубы представлен в алг.3. Необходимо заметить, что двоичный умножитель Карацубы использует внутри себя 2kn-битный умножитель (алг. 2)Алгоритм 3. Алгоритм двоичного умножителя Карацубы2.2 Методы вычисления полиномиальных функций и возможные варианты их оптимизации.Рассмотрим арифметику поля Галуа GF(28) на базе неприводимого многочлена p(x) = x8+ x4+ x3+ x+ 1, применяемого в усовершенствованном стандарте шифрования AES. Современные стандарты шифрования данных базируются на специализированных разделах математики, в частности, арифметике поля Галуа GF(28).Для разработки программных или аппаратных реализацийтребуются дополнительные исследования и выведение достаточно простых для понимания, высокопроизводительных вычислительныхсхем для конкретных стандартов шифрования информации.Арифметика поля Галуа GF(28) с применением логарифмов в стандарте шифрования данных AES. Поле Галуа GF(28) является частным случаем расширенных конечных полей GF(2m) характеристики 2 и имеет широкое применение не только в помехоустойчивом кодировании данных, но и криптографии для защиты информации.В частности, широко распространенное поле Галуа GF(28) используется в стандарте AES - AdvancedEncryptionStandard(усовершенствованный стандарт шифрования).Поле Галуа GF(28) по определению содержит 256 элементов:a(x):01x…X7+x6+x5+x4+x3+x2+x+1GF (28):(a)2:000000000000000100000010…11111111(a)10:012…255Поле Галуа GF(28), является полем многочленов вида a (x) = a7x7 + ... + a1x + a0, образуется на базе простого поля Галуа GF(2) и неприводимого многочлена 8-й степениp(x) = x8+ x4+ x3+ x+ 1.В стандарте шифрования AESприменяется неприводимый многочлен вида:p(x) = x8+ x4+ x3+ x+ 1.(2.7)Неприводимый многочлен двоичном представлении выглядит как (p)2= 100011011, а в десятичном представлении: ( p)10= 283.Наименьшим примитивным элементом поля GF(28) является элемент a(x) = x +1, на основе которого можнопостроить все ненулевые элементы поля. В двоичном представлении примитивный элемент поля выглядит как (а)2 = 11, десятичном (а)10 = 3.Для построения таблицы степеней примитивного элемента, а(x) = x+1 используется представленная ниже рекуррентная схема для случая поля ГалуаGF(28) с неприводимым многочленом p(x) = x8+ x4+ x3+ x+ 1.Формировать таблицу логарифмов, можно одновременно с формированием таблицы степеней, используя десятичное представление степеней примитивного элемента в качестве индексов таблицы логарифмов.Операцию умножения на (а)2 = 11 в поле Галуа GF(28) в двоичном представлении элементов поля можно свести к операции сдвига влево на один разряд и операции сложения («побитового» XOR), в случае если старший бит «предыдущей» степени был ненулевым, то еще выполняется «побитовый» XORс двоичным эквивалентом (р)2 = 100011011 неприводимого многочлена. (2.8)Под выражением (а k-1 << 1) а k-1 понимается сдвиг двоичного числа влево на один разряд с последующей операцией «побитового» XOR полученногорезультата с самим числом. Под выражением((а k-1 << 1) а k-1) (100011011)2(2.9)понимается сдвиг двоичного числа влево на один разряд. Последующая операция «побитового» XORрезультата сдвига с самим числом. После чего проводится операция «побитового» XORполученного результата с эквивалентом неприводимого многочленадвоичным представлении.Исходя из того, что в десятичном виде примитивный элемент поля GF(28) представлен как (а)10 = 3, то будем обозначать k-ую степень примитивного элементав виде3k, а логарифм от элемента aпо основанию 3 как log3a.Ниже на рис. 2.1 приведены степени примитивного элемента (а)10 = 3 поля Галуа GF(28), образованного основе неприводимого многочлена p(x) = x8+ x4+ x3+ x+ 1. Степени примитивного элемента приведены в десятичном представлении, и расположены построчно, начиная с 0-й, и заканчивая 255-йстепенью.Рис. 2.1. Таблица степеней 3kдля поля Галуа GF(28) для полинома p(x)Для того, чтобы выбрать в таблице требуемую степень 3k, необходимо выбрать строку и столбец таким образом, чтобы сумма индексов строки и столбца (индексы строк выбираютсяиз левого заголовочного столбца серого цвета, индексы столбцов - из верхней заголовочной строки) была равна необходимой степени k.Также ниже на рис. 2.2 в виде таблицы приведены логарифмы по основанию примитивного элемента (а)10 = 3 поля GF(28). Логарифмы расположены построчно (по 16 в строке) для всех элементов поля, начиная с (a)10= 0, заканчивая (a)10= 255. Заметим, что логарифм от 0 не существует (соответствующая ячейка «N/A»).Рис. 2.2. Таблица логарифмов log3aдля поля Галуа GF(28)для AESДля того, чтобы выбрать в таблице логарифм log3aзаданного элемента aполя GF(28), необходимо выбрать строку и столбец таким образом, чтобы сумма индексов строки и столбца была равна десятичному представлению элемента a.(2.10)Тогда с учетом вышеизложенного получим арифметику поля Галуа GF(28), на основе неприводимого многочлена p(x) = x8+ x4+ x3+ x+ 1 и логарифмов по основанию примитивного элемента поля (а)10 = 3:Если необходимо найти обратный элемент по умножению, то можно воспользоваться упрощенным вариантом формулы деления элементов: (2.11)Для возведения в степень vзаданного элемента aполя GF(28) можно применить формулу, применив операцию умножения по модулюлогарифмов:(2.12)Примеры применения данного метода приведены в проложении А.Схемы прямого умножение и инвертирование элементов поля Галуа GF(28) в криптографическом стандарте AES. При прямом умножения элементов aи bполе Галуа GF(28), можно использовать заранее подготовленную свертку многочленов a(x) и b(x) по модулю p(x) = x8+ x4+ x3+ x+ 1:Полученную схему умножения несложно построить на аппаратномуровне при помощи 64 двухвходовых логических элементов «И» и 8 многовходовых сумматоров по модулю 2.В случае нахождения высокопроизводительного вычислителя обратного элемента по умножению, можно применить заранее вычисленную таблицу обратных элементов поля Галуа GF(28), представленных в десятичном виде рис. 2.3 Рис. 2.3. Таблица обратных элементов по умножению для поля Галуа GF(28) для AESТаким образом, рассмотрено поле Галуа GF(28) на базе неприводимого многочлена p(x) = x8+ x4+ x3+ x+ 1. Рассмотрены схема формирования таблиц степеней и логарифмов на основе примитивного элемента (а)10 = 3, формулы сложения, умножения и деления, а также инвертирования элементов и возведения в заданную степень. Рассмотрены примеры выполнения арифметических операций с элементами поля. Рассмотрены высокопроизводительные схемы прямого умножения и инвертирования элементов поля.Список использованной литературыАлександр Пирожков.Полнодисковое шифрование для корпоративной безопасности 21/10/21 Сергей Матвеев Полнодисковое шифрованиеhttp://www.stargrave.org/Disk-encryption.htmlВладимир Безмалый “Шифрование в KasperskyEndpointSecurity 10” 22.04.2013https://www.osp.ru/winitpro/2013/05/13035377Фирсов Г. В., Коренева А. М. Об одном режиме работы блочных шифров, используемом для защиты информации на носителях с блочно-ориентированной структурой // Современные информационные технологии и ИТ-образование. 2022. Т. 18, № 3. С. 691-701. doi: https://doi.org/10.25559/SITITO.18.202203.691-701Математические основы теории помехоустойчивого кодирования: учебное пособие / С. С. Владимиров; СПбГУТ. — СПб, 2016. — 96 с. ISBN 978-5-89160-131-4Симонова О.Н. Особенности оценки качества и оптимизации алгоритмов симметричного шифрования // Молодой ученый. Международный научный журнал № 9 (113) / 2016 – 79-81сс.Удальцов В.А., Кармановский Н.С. Исследование способов скоростной реализации элементов симметричных алгоритмов шифрования при проведении вычислений на графическом процессоре // Научно-технический вестник информационных технологий, механики и оптики. 2018. Т. 18. № 4. С. 646-653. doi: 10.17586/2226-1494-2018-18-4-646-653Рахман П.А. Эффективные вычислительные схемы для арифметики поля Галуа GF(28) в усовершенствованном стандарте шифрования// международный журнал прикладных и фундаментальных исследований. ISSN 1996-3955 /№7 Часть 3/ 2016 –366-372сс В 2023 году количество утечек данных из российских компаний может вырасти на 20% - Rspectr.https://rspectr.com/novosti/v-2023-godu-kolichestvo-utechek-dannyh-iz-rossijskih-kompanij-mozhet-vyrasti-na-20. Дата обращения 26.04.2023.CMAC NIST- SP 800-38B.Рекомендации по режимам работы блочного шифрования: режим CMAC для аутентификацииhttps://csrc.nist.rip/external/nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-38B.pdf Поля Галуа (книга, которую посоветовал Михаил)Приложение АПримеры расчетов.Пример 1. Найти сумму элементов расширенного поля GF(28), представленных в виде соответствующих чисел «87» и «131» в десятичной системе представления. Имеем,Пример 2. Найти произведение элементов поля GF(28), представленных в виде чисел 87 и 131 в десятичной системе счисления. По таблице логарифмов для поля GF(28) находим логарифмы элементов: log3 (87)10=98 и log3(131)10= 80. В итоге получаем:По таблице степеней для поля GF(28) находим 3178 = (193)10. В итоге получаем:Пример 3. Найти отношение элементов поля GF(28), представленных в виде чисел 13110 и 19310. По таблице логарифмов для поля GF(28) находим логарифмы элементов: log3(131)10= 80 и log3(193)10 = 178. В итоге получаем:По таблице степеней находим значение 3157 = (191)10.В итоге имеем:Пример 4. Необходимо найти обратный элемент по умножению для элемента «191», представленного в десятичном виде. По таблице логарифмов находим логарифм элемента: log3(191)10= 157. Тогда обратный элемент:По таблице степеней находим 398 = (87)10. Таким образом:Пример 5. Необходимо возвестичисло «13», представленный в десятичном виде, в заданную степень v= 17. По таблице логарифмов для поля GF(28) находим логарифм элемента: log3(13)10= 238. Тогда по формуле рассчитываем:По таблице степеней находим 3221 = (81)10. Таким образом,