WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«ВЫРОЖДЕННЫЕ ПОДСТАНОВКИ Введение Одним из основных положений, развиваемых в новой методологии оценки показателей стойкости блочных симметричных шифров (БСШ) к атакам дифференциального и ...»

УДК 621. 3.06

И.В. ЛИСИЦКАЯ, д-р техн. наук

ВЫРОЖДЕННЫЕ ПОДСТАНОВКИ

Введение

Одним из основных положений, развиваемых в новой методологии оценки показателей

стойкости блочных симметричных шифров (БСШ) к атакам дифференциального и линейного

криптоанализа, является положение, состоящее в том, что все БСШ после определенного индивидуального для каждого БСШ числа циклов приходят по дифференциальным и линейным

показателям к свойствам случайных подстановок соответствующей степени. В концентрированном виде эти идеи выражены в работе [1] следующим образом .

Все современные блочные симметричные шифры через определенное число циклов независимо от используемых в шифрах S блоков (здесь идет речь не о вырожденных их конструкциях) приходят к свойствам случайных подстановок, то есть по комбинаторным показателям (числу инверсий, циклов и возрастаний), а также по законам распределения переходов XOR таблиц (таблиц полных дифференциалов) и законам распределения смещений таблиц линейных аппроксимаций (линейных корпусов) повторяют соответствующие показатели случайных подстановок. Вследствие этого значения максимумов полных дифференциалов и линейных корпусов могут быть получены расчетным путем из формул для законов распределения вероятностей переходов XOR таблиц и смещений таблиц линейных аппроксимаций случайных подстановок .

При этом проверка показателей случайности больших шифров может быть выполнена на основе разработки и последующего анализа показателей случайности уменьшенных моделей, которые допускают проведение вычислительных экспериментов в реальные временные сроки .



В качестве возражений выдвинутому положению существует мнение о том, что это вс частные результаты, и можно без труда найти подстановки, которые не укладываются в его рамки .

Проведенные многочисленные эксперименты свидетельствуют, однако, о том, что сформулированное положение выполняется практически для всех известных шифров, а подстановки, его не подтверждающие, – это ограниченное множество по сравнению с общим числом возможных подстановок, существенно не влияющее на достоверность сформулированного утверждения .

Из сказанного следует, что предлагаемая методология работает для произвольных S-блоковых конструкций, исключая вырожденные подстановки. Возникает вопрос, а какие же S-блоки считать вырожденными ?

Одним из простых ответов на этот вопрос может стать следующее: вырожденными S-блоками следует считать те, которые либо не позволяют шифру в пределах ограниченного числа циклов, однозначно определенного для каждого шифра, достичь показателей случайной подстановки, либо стационарное значение, к которому приходит шифр, не соответствует ожидаемому, свойственному случайной подстановке .

Эта работа посвящена изучению представителей множества вырожденных подстановок, а также оценке мощности этого множества, что позволит удостовериться в выполнении сформулированного положения с весьма высоким уровнем доверия .

Примеры вырожденных подстановок Здесь представляются результаты экспериментов с малыми (16-битными) моделями шифров. Подтверждение адекватности малых моделей своим большим прототипам можно найти в [2, 3 и др.]. Соответственно разговор будет идти о полубайтовых S-блоках, изученных наиболее всесторонне [4, 5 и др.] .

–  –  –

В качестве первого примера взята тождественная подстановка (единичная подстановка симметрической группы). Результаты е применения для построения процедуры зашифрования (шифра) приведены в верхней части табл. 1 (первый пример). Этот пример свидетельствует, что без применения подстановочной нелинейной операции шифр (любой) просто разваливается (он далк от случайной подстановки) .



Второй и третий примеры подстановок взяты из работ [5, 7]. Они свидетельствуют, что действительно существуют и нетождественные подстановки со значением показателя максимума смещения линейной аппроксимационной таблицы (ЛАТ), равным 8 (максимально возможным значением для полубайтовой подстановки), которые также не позволяют реализовать эффективную процедуру зашифрования. Заметим, что вторая подстановка приходит к асимптотическому значению максимума таблицы дифференциалов (ТД) равному 24, отличающемуся от теоретического значения максимума дифференциала для случайной подстановки (18 – 20) .

В табл. 2 представлены результаты поцикловой оценки максимумов смещений таблиц линейных аппроксимаций (линейных оболочек) шифра Хеуса с этими же подстановками. И в этом случае результаты свидетельствуют о практической непригодности рассмотренных первых двух подстановок для построения шифрующих преобразований. Последняя подстановка приходит после семи циклов к показателям случайной подстановки, однако для достижения необходимых дифференциальных свойств (см. табл. 1) ей требуется более 11 циклов зашифрования. В то же время здесь можно сослаться на результаты работ [7, 8 и др.], из которых следует, что случайно взятые подстановки с большой вероятностью приводят к эффективному шифрующему преобразованию (число циклов, необходимое для перехода к случайной подстановке для шифра Хеуса, не превышает шести) .

–  –  –

В табл. 3 приведены поцикловые распределения максимумов числа переходов XOR таблиц для шифров с сильным линейным преобразованием. Они реализуются с помощью уменьшенной (16-битной) конструкции шифра baby-Rijndael, в котором используются те же S-блоки, что и в предыдущих экспериментах. Первая вырожденная подстановка (тождественная) конечно и в этом случае приводит к развалу процедуры шифрования. В то же время другие две подстановки (по крайней мере, последняя на 11-ти циклах выходит к свойствам случайной подстановки). В то же время по линейным свойствам (см. табл. 4) вторая подстановка повторяет показатели, продемонстрированные шифром Хеуса (см. табл. 3). Она явно не подходит для построения шифра .

Далее было изучено влияние на качество шифрующего преобразования и дифференциальных свойств S-блоков. В табл. 5 приведены примеры подстановок с предельными (по максимуму) дифференциальными показателями. По результатам табл. 5 можно сделать

–  –  –

Результат говорит о том, что этот S-блок нельзя применять для построения шифра .

Оценка доли вырожденных подстановок среди подстановок симметрической группы Здесь покажем, что вероятность попасть на вырожденную подстановку при их случайном формировании весьма мала. Начнм с того, что вероятность получения подстановки с показателем нелинейности равным нулю, можно определить из формулы для соответствующего закона распределения вероятностей из работы [9].





В соответствии с этой работой для случайной подстановки степени 2 n справедлива теорема:

Теорема 1. Пусть * (, ) будет случайным значением смещения линейной аппроксимационной таблицы LAT (, ) для пары е входов и, когда подстановка выбрана * равновероятно из множества 2 n и, не нулевые .

Тогда смещения * (, ) принимают только четные значения и для l 2 n2

–  –  –

ISSN 0485-8972 Радиотехника. 2012. Вып. 171 35 т.е. как показывают расчты, эта вероятность меньше одной десятитысячной .

Эти расчты сделаны для вероятности соответствующего заполнения одной ячейки таблицы, а таких ячеек в таблице (исключая нулевые маски по входу и выходу) (2 n 1) 2. Поэтому для вероятности получить полубайтовую подстановку со значением смещения k = 2 3 = 8 приходим к результату 7,65 10 5 (2 4 1) 2 0,0172 .

Для генерации байтовой подстановки с таким же (нулевым) показателем нелинейности соответственно приходим к вероятности

–  –  –

2,97 10 7 (2 4 1) 2 0,000067, т.е. вероятность получить вырожденную полубайтовую подстановку путм отбора получается менее семи десятитысячных .

Для байтовой подстановки соответственно получаем

–  –  –

ISSN 0485-8972 Радиотехника. 2012. Вып. 171 37 Выводы К вырожденным S-блокам мы отнесли подстановочные конструкции с дифференциальными и линейными показателями (максимумами XOR таблиц и смещений таблиц линейных аппроксимаций) близкими к предельно возможным .

Результатами работы подтверждено, что получение вырожденных S-блоков при случайном порождении подстановок является маловероятным событием. Особенно это относится к байтовым S-блокам. Для этих S-блоков получение подстановок с максимумами XOR таблиц и смещений таблиц линейных аппроксимаций, близкими к предельно достижимым, является практически невозможным событием. Реальные наиболее вероятные значения максимумов, которые удатся получить в экспериментах (34 для ЛАТ и 10-12 для ТР) оказываются далкими от значений 2 81 128 (для ЛАТ) и 2 8 256 (для ТР). При этом с увеличением значений максимумов линейных и дифференциальных показателей вероятности отбора подстановок с такими значениями очень быстро уменьшаются. Таким образом, доля вырожденных подстановок в общем множестве подстановок симметрической группы оказывается незначительной .

Это значит, что положение, сформулированное в начале работы, состоящее в том, что все шифры независимо от используемых в них S-блоков после небольшого начального числа циклов шифрования становятся случайными подстановками, выполняется с высоким уровнем доверия. Порождение вырожденных S-блоков является маловероятным событием, и самое главное – они всегда могут быть обнаружены и исключены на основе результатов экспериментов .

Список литературы: 1. Лисицкая, И.В. Методология оценки стойкости блочных симметричных шифров / И.В. Лисицкая // Автоматизированные системы управления и приборы автоматики. – 2011 .

– № 163. – C. 123-133. 2. Лисицкая, И.В. Большие шифры случайные подстановки / И.В. Лисицкая, А.А. Настенко // Радиотехника. – 2011. – Вып. 166. – С. 50-55.6. 3. Лисицкая, И.В. Дифференциальные свойства шифра FOX / И.В. Лисицкая, Д. С. Кайдалов // Прикладная радиоэлектроника. 2011 .

Т.10, №2. С. 122-126. 4. Markku-Juhani O. Saarinen Cryptographic Analysis of All 44-Bit S-Boxes // IACR Cryptology ePrint Archive Vol. 2011 (2011), p. 218. 5. Токарева, Н. Н. Квадратичные аппроксимации специального вида для четырхразрядных подстановок в S-блока // Прикладная дискретная математика. – 2008. – Т. 1, N 1. – С. 50-54. 6. H. M. Heys. A Tutorial on Linear and Differential Cryptanalysis, CRYPTOLOGIA, v 26, N 3, 2002, p 189-221. 7. Лисицкая, И.В. Об участии S-блоков в формировании максимальных значений линейных вероятностей блочных симметричных шифров / И.В. Лисицкая, В.В. Ковтун // Радиотехника. 2011. Вып. 166. – С. 17-25. 8. Лисицкая, И.В. Об участии Sблоков в формировании максимальных значений дифференциальных вероятностей блочных симметричных шифров / Лисицкая И.В., Казимиров А.В. // Proceedings International Conference SAIT 2011, Kyiv, Ukraine, May 23-28. – 2011. – С. 459. 9. Долгов, В.И. Свойства таблиц линейных аппроксимаций случайных подстановок / В.И. Долгов, И.В. Лисицкая, О.И. Олешко // Прикладная радиоэлектроника .

– 2010. – Т. 9, № 3. С. 334-340. 10. Joan Daemen. Probability distributions of Correlation and Differentials in Block Ciphers / Joan Daemen, Vincent Rijmen // April 13, 2006, pp. 138. 11. Олейников, Р.В .

Дифференциальные свойства подстановок / Р.В. Олейников, О.И. Олешко, К.Е. Лисицкий, А.Д. Тевяшев // Прикладная радиоэлектроника. 2010. Т.9. № 3. С. 326-333. 12. Долгов, В.И. Исследование криптографических свойств нелинейных узлов замены уменьшенных версий некоторых шифров / В.И. Долгов, А.А. Кузнецов и др. // Прикладная радиоэлектроника. – 2009. – Т. 8, № 3. С. 268

–  –  –






Похожие работы:

«1 УДК 004(075.3=161.3=161.1) ББК 32.81я721 П88 Пупцев, А. Е. Мультимедиа в современной жизни: 11-й кл. : пособие П88 для учащихся учреждений общ . сред. образования с белорус. и рус. яз. обучения / А. Е. Пупцев, А. А. Козинский. — 2-е изд. — Минск : Адукац...»

«АГРОИНФО'2018 Секция 4 УДК 504.3.054 Потапов В.П., Счастливцев Е.Л., Быков А.А., Юкина Н.И., Институт вычислительных технологий Сибирского отделения Российской академии наук, Кемеровский филиал, Кемерово ОЦЕНКА ВОЗДЕЙСТВИ...»

«Суперкомпьютерный консорциум университетов России Труды Международной научной конференции (Электронное издание) ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ (ПаВТ'2009) г. Нижний Новгород, 30 марта– 3 апреля 2009 г. Челябинск, Издательство ЮУрГУ УДК 004.75 П 18 Параллельные вычислительные технологии (ПаВТ'2009): Труды меж...»

«69 А.Ш.Ревишвили, Г.Ю.Симонян, А.Г.Севоян ИНТЕРВЕНЦИОННОЕ ЛЕЧЕНИЕ ЖЕЛУДОЧКОВОЙ АРИТМИИ С ИСПОЛЬЗОВАНИЕМ НЕИНВАЗИВНОГО ЭЛЕКТРОФИЗИОЛОГИЧЕСКОГО КАРТИРОВАНИЯ У ПАЦИЕНТКИ С ЖЕЛУДОЧКОВОЙ ЭКСТРАСИСТ...»

«Учреждение образования "Белорусский государственный университет информатики и радиоэлектроники" УТВЕРЖДАЮ Проректор по учебной работе Е.Н. Живицкая 19.05.2017 Регистрационный № УД-5-717/уч. "Проектирование вычислительных средств с д...»

«vr_roller_coaster_na_android.zip Выпасы • 500 лотосов тыквы; • 6 песочин муки; • 3 ст. Итак восторженнее дьяки околачивали преодоление на домохозяйствах новолуния примитивности посредством набожных дел (духовных дисциплин) и дел милосердных (добра поправленного таким людям)40 то наизнанку они облегчали верующи...»

«встраиваемые системы Микропроцессоры с функциональностью промышленных компьютеров Промышленные компьютеры получают широкое распространение в том случае, если проект требует высокой вычислительной мощности и слож ного пользова...»

«Список слушателей ЦДО, успешно сдавших вступительные экзамены в 2015 году и представленных к зачислению в РАУ Направление "Туризм" Госзаказ 1. Амирханян Анжела Самвеловна 54303.02011 48,32 балла 2. Аристакесян Наре Жирайровна 543.03.02013 46,98 балла 3. Геворгян Софья Кареновна 543.03.02007 46,47 балла 4. Джараян Арме...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.