Sibecrypt'12. Обзор докладов | ПДМ. 2012. № 4(18).

Sibecrypt'12. Обзор докладов

Приводится аналитический обзор лекций и докладов, представленных на Sibecrypt'12 — XI Всероссийской конференции «Сибирская научная школа-семинар с международным участием „Компьютерная безопасность и криптография"», состоявшейся 3-8 сентября 2012 г. в Институте динамики систем и теории управления СО РАН (г.Иркутск).

Sibecrypt'12 review.pdf Введение Sibecrypt — это Всероссийская конференция под названием «Сибирская научная школа-семинар с международным участием „Компьютерная безопасность и криптография"». Её ежегодно, начиная с 2002 г., организует и в первой трети сентября проводит кафедра защиты информации и криптографии Национального исследовательского Томского государственного университета в сотрудничестве с кафедрой программирования и компьютерной безопасности Института криптографии, связи и информатики (ИКСИ, г. Москва) на базе того или иного вуза или научного учреждения Сибири. Конференция посвящена одному из важнейших направлений в области информационной безопасности — математическому и программному обеспечению компьютерной безопасности (КБ). В последние годы в этом направлении наблюдается высокая активность исследовательской работы молодых ученых, и возникает настоятельная необходимость в организации их научного общения друг с другом и с известными специалистами в данной области. Именно эту цель и преследует школа-семинар, имея в виду, в первую очередь, интересы молодых ученых Сибири и крупных учёных европейской части России, Беларуси, Украины. Цель достигается путём организации и проведения обсуждений на её заседаниях фундаментальных проблем защиты информации в компьютерных системах и сетях и обмена научными результатами по их решению методами прикладной дискретной математики (ПДМ). Кроме докладов, на конференции Sibecrypt для её участников, а также для сотрудников и студентов принимающей организации (вуза, НИИ) ведущими специалистами в данной области (из числа участников конференции) читаются лекции по математическим проблемам компьютерной безопасности, защиты информации, информатики и криптографии. Материалы конференции публикуются в приложении к журналу «Прикладная дискретная математика», ставшем с 2012 г. самостоятельным журналом «Прикладная дискретная математика. Приложение». В 2012 г. конференция состоялась в 11-й раз — с аббревиатурой Sibecrypt'12, на этот раз — 3-8 сентября в Иркутске на базе Института динамики систем и теории управления СО РАН. Тезисы докладов, представленных в её программу, опубликованы в [1]. Аналитический обзор в форме аннотаций их содержания, а также содержания лекций, прочитанных на конференции, является целью данной статьи. В соответствии с тематикой Sibecrypt'12 аннотации докладов разбиты по следующим её направлениям: теоретические основы ПДМ, математические методы криптографии и стеганографии, математические основы КБ, прикладная теория графов, математические основы информатики и программирования, вычислительные методы в дискретной математике. 1. Лекции по криптографии и информатике О содержании понятия «электронная подпись» в Директиве 1999/93/ЕС от 1999г. (далее Директива) и в Федеральном законе РФ от 2011г. (далее ФЗ), регламентирующих порядок использования электронных подписей в Европейском сообществе и в России соответственно, рассказано в лекции А. В. Черёмушкина. Основные выводы докладчика следующие: 1) имеются принципиальные отличия определений основных понятий и систем технических требований в Директивах и ФЗ; 2) определения электронной подписи в Директивах и ФЗ ориентированы в основном на применение в юридической сфере и расходятся с математическим определением этого понятия. Полностью доклад опубликован в [2]. Обстоятельный обзор применения латинских квадратов в криптографии для построения шифров, схем аутентификации, однонаправленных функций, схем разделения секрета, криптографических хеш-функций и протоколов с нулевым разглашением представлен в лекции М. Э. Тужилина. Полностью текст опубликован в [3]. Одной из важнейших научных проблем, если не самой важной проблемой, современной теоретической информатики и компьютерной математики, будь то алгебра, теория чисел, дискретная математика, криптография или информационная безопасность, является сложность алгоритмов решения NP-трудных задач. Её математическое исследование предполагает построение подходящей модели вычислительной сложности и решение в рамках этой модели задач анализа и синтеза алгоритмов. В ряду первых важное место занимают задачи классификации алгоритмов по вычислительной сложности и построения для алгоритмов точных, рекуррентных или асимптотических оценок сложности. Важны также задачи разработки алгоритмов, решающих те или иные NP-трудные задачи с как можно меньшей сложностью. Именно о решении этих задач шла речь на конференции в лекции В. В. Быковой. В ней за сложность алгоритма принята его эластичность, а точнее, эластичность функции его временной сложности от размера входных данных и, возможно, параметра задачи [4]. Так назван предел отношения относительного приращения этой функции к относительному приращению аргумента. Он характеризует коэффициент пропорциональности между темпами роста его временной сложности и размера входных данных или параметра задачи. Понятие эластичности заимствовано из экономики, где оно относится к производственным функциям. Это не единственный пример полезного заимствования математикой понятий из других областей науки. Достаточно вспомнить понятие энтропии состояния информационной системы по Шеннону как аналога энтропии состояния физической системы. Свойства эластичности алгоритма в теории сложности оказались столь же продуктивными, сколь и свойства энтропии в теории информации. И это открытие не может не восхищать математиков. Эластичность алгоритма легко вычисляется и выражается более простой формулой, чем соответствующая логарифмически-экспоненциальная функция временной сложности, а построенная классификация по ней алгоритмов — от субполиномиальных до гиперэкспоненциальных — более прозрачна, нежели её прообраз. В части, касающейся анализа алгоритмов, в лекции построены нижние и верхние асимптотические оценки временной сложности рекурсивных алгоритмов, решающих задачи путём последовательного уменьшения размера входных данных на некоторую константу. Из этих оценок следует, что такие алгоритмы могут быть только субполиномиальные, полиномиальные и экспоненциальные. Первые возможны лишь при одной подзадаче и беззатратном рекурсивном переходе, вторые — лишь в случае полиномиальной сводимости задачи к одной подзадаче меньшего размера, а третьи — всегда при числе подзадач больше 1 и только. Параметризация задач — самый «молодой» из известных подходов к преодолению проблемы вычислительной сложности. Несмотря на его сравнительно малую изученность, его перспективность доказана в исследованиях многих зарубежных и отечественных учёных, в том числе и В. В. Быковой [4, 5]. В её лекции дана исчерпывающая двумерная классификация параметризированных и, в частности, FPT-алгоритмов по эластичности от размера данных и параметра задачи; в терминах эластичностей охарактеризованы параметризированные алгоритмы с низкой, равносильной и доминирующей зависимостями от параметра и установлены альтернативные формы характери-зации FPT-разрешимости — аддитивная и смешанная, равносильные исходной — мультипликативной. Кроме того, рассказано о технологии построения FPT-алгоритмов для решения задач выбора (поиска и оптимизации в конечной области) методом динамического программирования на графах и гиперграфах с ограниченной древовидной шириной. В частности, осуществлена алгоритмизация этого метода на базе бинарного сепараторного дерева декомпозиции, позволившего решить присущую ему проблему памяти. Продемонстрированы FPT-алгоритмы решения задач SAT и о наименьшем вершинном покрытии графа, построенные на этой базе, и полиномиальные алгоритмы вычисления верхних и нижних оценок древовидной ширины графа и гиперграфа. Использование сепараторного дерева декомпозиции позволило для вычисления таблиц динамического программирования привлечь аппарат реляционной алгебры и ациклических баз данных и тем самым существенно снизить теоретическую и практическую сложность получаемых FPT-алгоритмов. 2 ноября 2012 г. В. В. Быкова успешно защитила докторскую диссертацию на тему «Методы анализа и разработки параметризированных алгоритмов» в совете Сибирского федерального университета по теоретическим основам информатики. От имени участников школы-семинара Sibecrypt поздравляем Валентину Владимировну с этим замечательным событием в её научной жизни и желаем ей дальнейших успехов в нашем общем деле. В лекции А. А. Евдокимова рассмотрены свойства дискретных метрических пространств и метрик, которые возникают в исследовании вложений конечных пространств и графов. Отображения, в классе которых исследуются вложения, являются изометрическими, локально изометрическими и параметрическим семейством отображений ограниченного искажения. Последние при малых значениях параметров могут рассматриваться как дискретные аналоги непрерывных отображений, сохраняющих метрические свойства близости и отделимости элементов [6, 7]. Свойство k-продол-жения метрики для связных графов с обычной метрикой пути означает, что любые две вершины графа, расстояние между которыми меньше k, принадлежат некоторой кратчайшей цепи длины k. Второе свойство связано с характеризацией комбинаторной структуры шаров в графе, когда их радиусы последовательно возрастают от единицы до диаметра графа (раздувающиеся шары). Точнее, свойство r-разнообразия шаров означает, что шары одного радиуса с центрами в любых двух вершинах графа не равны (как множества вершин), если этот радиус не превосходит r (значение r не больше эсцентриситета графа). Приведены теоремы о значении рассмотренных свойств в вопросах вложений и классификации графов, а также некоторые нерешённые задачи. Лекция А. А. Семенова посвящена основам структурной теории сложности алгоритмов и использованию различных формальных вычислительных моделей для определения классов двоичных языков, распознаваемых этими моделями. Рассмотрены: полиномиальная детерминированная машина Тьюринга и класс P, полиномиальная недетерминированная машина Тьюринга и класс NP, полиномиальная вероятностная машина Тьюринга и определяемые с её помощью классы (RP, co-RP, BPP), а также класс P/poly, образованный языками, распознаваемыми при помощи семейств схем полиномиальной сложности. Кроме этого, рассмотрена полиномиальная иерархия (иерархия Стокмейера), образованная языками, для определения которых используется оракульная машина Тьюринга. Приведены результаты, касающиеся аргументации сложности задач обращения ряда криптографических функций, базирующиеся на принятых предположениях относительно взаимосвязи между основными сложност-ными классами. В частности, в краткой форме приведено известное доказательство У. Шенинга того факта, что задача определения изоморфности пары простых графов не может быть NP-полной в предположении, что полиномиальная иерархия не стабилизируется на третьем уровне. 2. Теоретические основы прикладной дискретной математики Дискретные функции по-прежнему находятся в центре внимания теоретических исследований, ориентированных на криптографические приложения. В докладе А. М. Зубкова и А. А. Серова построены нижние и верхние оценки числа булевых функций, отстоящих по Хэммингу от аффинных и квадратичных функций на ограниченном расстоянии. Оценки получены с использованием формул включения-исключения и оценок хвостов биномиального распределения. Приведены условия, при которых они асимптотически эквивалентны. Н. А. Коломеец доказал, что нелинейность всякой булевой функции от чётного числа п переменных, равной 0 (1) на наборах веса меньше (больше) п/2, не превосходит fn — 1\ 2«.-i — | |, и эта оценка точная. Примечательно, что все эти функции обладают n/2 максимально возможной алгебраической иммунностью n/2, но их нелинейность, как видим, заметно отличается от максимально возможной 2n-1 — 2n/2-1. Продолжая представление результатов исследования по проблеме статистической независимости суперпозиций булевых функций, начатое на предыдущей школе-семинаре, О. Л. Колчева и И. А. Панкратова на этот раз показали, что 1) если функции f1(x,y), f2(x,y) и f1(x,y) ф f2(x,y) статистически не зависят от переменных в x, то этим свойством обладает и любая суперпозиция вида g(f1(x,y), f2(x,y),z), и 2) если f (x, y) статистически не зависит от переменных в x, то f (x,y) ф g(x) тоже обладает этим свойством тогда и только тогда, когда f уравновешена или g = const. В этих утверждениях x, y, z — произвольные наборы значений булевых переменных. Булева функция называется почти уравновешенной, если в любой грани области её определения количество элементов, на которых она равна 1, отличается от половины мощности грани не более чем на 1. В своём докладе В. Н. Потапов предложил некоторые конструкции почти уравновешенных функций и установил некоторые свойства этих функций и нижнюю границу их числа. Он показал, в частности, что класс почти уравновешенных булевых функций является наследственным (содержит вместе с любой функцией и все её подфункции) с бесконечным набором минимальных запретов (функций не из класса, все подфункции которых принадлежат классу) и что булева функция f почти уравновешена, если и только если f — h Е B0, где h — булева функция со значением 1 на всех наборах нечётного веса (и только) и g Е B0, если g : {0,1}n ^ { — 1, 0,1}, g-1(1) и g-1(—1) —подмножества наборов соответственно чётного и нечётного веса и абсолютная величина суммы значений g на любой грани области её определения не превышает 1. В текущем году С. В. Смышляев доказал гипотезу Голича о перестановочности (линейности) по первой или последней существенной переменной любой сильно совершенно уравновешенной булевой функции. В докладе на школе-семинаре он представил обобщение этой гипотезы как условие Голича в формулировке: «Сильная совершенная уравновешенность в Pk (для любого k ^ 2) эквивалентна перестановочности по первой или последней существенной переменной» и в свою очередь выдвинул гипотезу: «Условие Голича выполнено тогда и только тогда, когда k простое», доказав её в части необходимости простоты k и установив некоторые утверждения, косвенно подтверждающие эту гипотезу и в части достаточности. В своё время, в 2011г., Н. Н. Токарева сформулировала гипотезу о возможности разложения любой булевой функции от чётного числа n переменных степени не более n/2 в сумму двух бент-функций от n переменных. В докладе на школе-семинаре она доказала ослабленный вариант этой гипотезы, показав, что при чётном n любая булева функция от n переменных степени d ^ n/2 может быть представлена суммой не более чем 2( ) бент-функций от n переменных, где b — наименьшее целое, такое, А что b ^ d и (2b)|n. Булева функция f от чётного числа переменных n называется функцией Касами, если для некоторого Л Е GF(2n) и любого в Е GF(2n) имеет место f (в) = tr(A^k), где k = 22d — 2d + 1, (n, d) = 1, 0 < d < n. При Л, не равном кубу элемента в GF(2n), она является бент-функцией. Булева функция s-существенно зависима, если любое произведение s её переменных входит в моном её АНФ. В докладе А. А. Фроловой показано, что для любого чётного n ^ 8 функция Касами степени t является s-существенно зависимой, а её кратная производная по s линейно независимым направлениям не равна тождественно 0, если s = t — 3, 4 ^ t ^ n/2, или s = t — 2, 4 ^ t ^ (n + 3)/3. Кроме того, она 2-существенно зависима, если t ^ 4. В докладе К. Л. Глуско и С. С. Титова предложен метод решения квадратного уравнения x2 + x = а в поле GF(2n) путём разложения его в систему булевых уравнений x2_i + Xi + а^ = 0, i = 0,1,... , n — 1, связывающих компоненты векторов x2, x и а. В докладе В. А. Едемского и О. В. Антоновой предложен метод анализа линейной сложности последовательностей с периодом 2mpn, построенных на основе обобщённых циклотомических классов. Метод позволяет для рассматриваемых последовательностей вычислять линейную сложность, получать её оценки, строить минимальный многочлен и определять последовательности с заведомо высокой линейной сложностью. Эти возможности метода продемонстрированы на ряде последовательностей, построенных на основе классов квадратичных и биквадратичных вычетов. Полностью доклад опубликован в [8]. Формулы для среднего и дисперсии числа векторов веса s или не больше s в случайном линейном двоичном (N, к)-коде, имеющем равномерное распределение на множестве всех таких кодов, выведены в докладе А. М. Зубкова и В. И. Круглова. Приведены формулы для среднего и дисперсии веса w покомпонентной суммы по модулю 2 двух независимых случайных булевых векторов длины N, имеющих вес s и t соответственно и равномерные распределения на множествах таких векторов, а также для вероятности равенства w = m. Дана также оценка сверху для вероятности линейной зависимости n независимых случайных булевых векторов длины N и веса s, имеющих равномерное распределение на множестве таких векторов. В докладе А. С. Кузнецовой и К. В. Сафонова указано решение комбинаторной задачи, в которой для последовательности первых n натуральных чисел, записанных в произвольном порядке по окружности, требуется вычислить наименьшее число d транспозиций соседних чисел, чтобы все числа в окружности оказались записанными в естественном порядке: 1, 2,... ,п — 1, п, и приведены значения d для п = 2, 3,..., 12. Свойства наборов натуральных чисел с наибольшим общим делителем 1 изучены и алгоритм их перечисления предложен в докладе С. Н. Кяжина и В. М. Фомичёва. Полностью доклад опубликован в [9]. Вектор a из различных натуральных чисел, упорядоченных по возрастанию, называется инъективным, если для любого натурального числа а существует не более одного подмножества компонент этого вектора, сумма которых равна а. Вектор a сверх-растущий, если любая его компонента больше суммы всех предыдущих его компонент. Говорят также, что вектор b = b1b2 ... bn получен из вектора a = a1a2 ... an операцией сильного модульного умножения относительно модуля m и множителя t, если m больше суммы компонент в a и bi = ait mod m, i = 1, 2,... , п. В докладе Д. М. Мурина показано, что количества инъективных векторов и сверхрастущих векторов с числом компонент (размерностью) п и наибольшим значением компоненты M ведут себя как полиномы степени п — 1 от M, а пределы их отношений к числу всех векторов с теми же параметрами п и M при M ^ то и фиксированном п существуют, конечны и не равны 0. На основании результатов компьютерных экспериментов установлено, что при фиксированном натуральном п и значениях натурального M, близких к 22n, отношение количества различных инъективных векторов размерности п, полученных из сверхрастущих векторов размерности п с наибольшей компонентой меньше M с поn мощью сильного модульного умножения относительно модуля m ^ min(M, 2^2 ai) и i= 1 всевозможных значений множителя t = 2,33,... ,m — 1, к числу всех инъективных векторов размерности п с наибольшей компонентой меньше M достигает величины 0,9 и что операция сильного модульного умножения в применении к сверхрастущим векторам приводит чаще всего к векторам с малой евклидовой длиной. Множество мобильных точек подстановки G Е Sn обозначается r(G), а множество всех подстановок с q мобильными точками — Г^(q). Здесь T(G) С {1,... , N}, 2^q^N. В докладе А. Б. Пичкура доказано, что если N ^ 8, 3 ^ q ^ N/2 и 1 < |T(G)| < 2q — 1 или N > 10, 2 ^ t < N — 2, 2 ^ q < (N — t)/2 + 1 и t ^ |r(G)| ^ 2q + t — 2, то существуют подстановки H1 Е rN (q), H2 Е rN (q +1) или H1 Е rN (q), H2 Е rN (q + t) соответственно, такие, что G = H1 • H2. Показано также, что при N ^ 4, 2 ^ q < N/2 подстановка из Г^(2q +1) принадлежит множеству Г^(q) • Г^(q +1), если и только если среди её неединичных циклов есть такие, сумма длин которых равна q, а при N ^ 4, 2 ^ q ^ N/2 подстановка из (2q) принадлежит множеству (q) • Г^(q + 1), если и только если среди её неединичных циклов есть цикл длины mo > 2 и циклы длин m1, ..., mk, таких, что q — m1 + ... + mk Е {2,..., m0 — 1}. Аналогичные характери-зации имеются для подстановок из Г^ (2q + t — 1) и из Г^ (2q + t), принадлежащих произведению rN (q) ■ rN (q + t). В совместном докладе Б. А. Погорелова с М. А. Пудовкиной и в отдельном докладе М. А. Пудовкиной изучены свойства групп преобразований векторного пространства над полем GF(2), порождённых парами операций, в которых одна операция — наложение вектора, а вторая — соответственно линейное преобразование и замена вектора по блокам. Декомпозиции и аппроксимации недоопределённых данных посвящён доклад Л. А. Шоломова. Первая заключается в представлении, а вторая в реализации каждого недоопределённого символа набором символов 0,1,* (неопределённость). Доказаны теоремы их существования и алгоритмов их эффективного построения для любого источника недоопределённых данных. Показана также возможность эффективного построения безызбыточных (тупиковых) декомпозиций и аппроксимаций и эффективной проверки равносильности двух разложений; построена полная система равносильных преобразований различных разложений недоопределённого источника. Алгоритм с субэкспоненциальной сложностью для вычисления изогений (алгебраических морфизмов, являющихся групповыми гомоморфизмами) большой степени между эллиптическими кривыми предложен в устном докладе В. Г. Сухарева. Он построен по схеме алгоритма BCL (Broker — Charles — Lauter), в котором для более быстрой факторизации идеала в кольце изогений кривой используются идеи из субэкспоненциального алгоритма дискретного логарифмирования в классических группах (Hafner and McLurley). 3. Математические методы криптографии и стеганографии В докладе А. В. Волгина и А. В. Иванова рассматривается генератор, порождающий последовательность u0u1... над полем P = GF(ps) по рекуррентному соотношению un+1 = aun + b, n ^ 0, усложнённый маской (e0e1... es) Е Ps+1, где все 6i представимы линейными комбинациями одних и тех же k элементов базиса поля P и k < s. Известно, что при известных разностях u — e^ i = 0,... , t — 1, для k + 1 ^ t > 2 и известных параметрах a, b, где a не принадлежит фиксированному подмножеству в P мощности меньше 2pCTt + ^ 2^Р2к~*+2 — наибольший из делителей s, меньших t), значение u0 находится с полиномиальной сложностью. Утверждается, что это верно и при неизвестном b и прежних остальных условиях. В 2001 г. М. М. Глухов-мл. построил класс алгебро-геометрических кодов {Cr : [768, 3r — 57, 768 — 3r]256, 39 ^ r ^ 255} на кривой, заданной над P = GF(28) уравнением y3 = x60 + x57 + x54 + ... + x3 + 1. Из каждого кода Cr путём вычёркивания в его порождающей матрице любых (768 — m) столбцов можно получить код Cr m, который при условии 114 < 3r < m ^ 768 будет [m, 3r — 57, m — 3г]-кодом. В своём докладе на школе-семинаре автор этих кодов показал, что при r ^ 127 и фиксированном m число различных кодов СГ т равно — . Доказательство утверждения конструктивно и r,m 1------- 1 о \ 18 m даёт возможность выбора столбцов порождающей матрицы так, чтобы все получаемые коды были различны. Этим результатом фактически заявлена новая идея образования порождающей матрицы кода в кодовых криптосистемах с открытым ключом. Изучены также условия на выбор столбцов в порождающей матрице кода Cr для получения кода СГ m с тривиальной группой автоморфизмов. Доказано, что если композиция автоморфизма и покомпонентного умножжения всех кодовых векторов кода Cr т на вектор k Е Pm является автоморфизмом этого кода, то все компоненты в k одинаковы. В докладе А. А. Камаевой рассматриваются упрощённые варианты хэш-функции Whirpool, в которых блочный шифр последней усечён до одного (двух) раундов, и показывается, что наибольшая вероятность найти коллизию для них равна 2-115 (2-225). Г. А. Карпунин и Е. З. Ермолаева результатами компьютерного эксперимента показывают, что трудоёмкость известного алгоритма построения коллизии для хэш-функции RIPEMD в квадрат раз выше заявленной его авторами (X. Wang, X. Lai, D. Feng, et al.). В докладе Д. С. Ковалёва сообщается об аппаратной реализации на базе ПЛИС шифра FAPKC-4 и о его программных реализациях на языках Perl и PHP. Приведены результаты экспериментов с этими реализациями. Показано в частности, что в среднем ПЛИС-реализация на Virtex-5 XCVLX330T работает в 1,34 раза быстрее, чем PHP-реализация на компьютере с процессором Intel Core i5-2300, которая, в свою очередь, в 2,6 раза быстрее, чем Perl-реализация на том же компьютере. В докладе К. Г. Когоса и В. М. Фомичёва обсуждается хорошо известная проблема разложения системы дискретных уравнений путём фиксации значений некоторых переменных на подсистемы, обладающие полезными свойствами (линейность, треуголь-ность и т.п.), облегчающими их решение. Полностью доклад опубликован в [10]. В докладе А. М. Кореневой и В. М. Фомичёва описан итеративный блочный шифр, построенный путём конкретизации параметров обобщённой схемы Фейстеля, рассматриваемой как регистр сдвига длины m над множеством п-мерных булевых векторов с обратной связью — функцией от раундового ключа и компонент регистра. Шифр представлен как иллюстрация к этому обобщению схемы Фейстеля. В нём m = 4, п =16 и функция обратной связи регистра выбрана так, что шифру обеспечивается свойство инволютивности. В докладе С. Д. Лошкарёва с целью выяснения влияния булевых функций и констант циклических сдвигов в MD5 на стойкость этой хэш-функции к дифференциальному анализу построены разностное уравнение для каждого шага преобразования в ней и формула для среднего значения вероятности угадать решение этого уравнения при случайном и равновероятном выборе значений переменных и различных фиксациях значений параметров. Путём сравнения этих значений для разных булевых функций или разных величин циклических сдвигов можно сравнивать последние по степени их влияния на исследуемую стойкость MD5. Так, показано, что использование функции XOR в MD5 оптимально с точки зрения устойчивости MD5 к дифференциальной атаке и что для каждой булевой функции в MD5 все значения циклических сдвигов с этой точки зрения эквивалентны. В связи с возможностью задания структур доступа, реализуемых в совершенных идеальных схемах разделения секрета, матроидами в докладе Н. В. Медведева и С. С. Титова вводится понятие почти порогового матроида. В нём все циклы имеют некоторую одну и ту же мощность п, но возможны подмножества мощности п, которые не являются циклами. Утверждается, что для п = 1, 2, 3 связного почти порогового, но не порогового матроида не существует. Матроид называется разделяющим, если для любых двух его элементов в нём есть цикл с одним из этих элементов, не содержащий другого. Утверждается, что бинарные (в GF(2m)) связные разделяющие почти пороговые матроиды исчерпываются кодами Рида — Маллера первого порядка. В докладе Е. Л. Столова предложена последовательностная схема генератора случайных чисел, состоящая из конечного числа одинаковых комбинационных блоков, работающих асинхронно и реализующих функцию 3-значной логики от двух переменных. Утверждается, что последовательность состояний схемы является марковским процессом с единственным финальным распределением вероятностей и с равномерным распределением на выходе каждого блока. Один из видов цифровой подписи — кольцевая — позволяет любому участнику группы подписать сообщение от имени всей группы, а проверяющему убедиться, что подпись сделана участником действительно этой группы, но кем именно — ему не дано знать. В докладе Г. О. Чикишева кольцевая подпись наделяется свойством одноразово-сти: при подписании двух сообщений одним и тем же участником группы его личность становится известной. Это свойство требуется во многих приложениях, в том числе для электронного голосования, для обеспечения неотслеживаемости платежей в системах электронных денег и др. В предложенной кольцевой подписи оно достигается благодаря тому, что каждый участник имеет две пары (открытый ключ, закрытый ключ), и подписывающий использует оба закрытых ключа так, что повторное применение второго из них приводит к некоторому одному и тому же значению одной из компонент в разных кольцевых подписях, указывающему на соответствующие два открытых ключа и тем самым идентифицирующему подписавшего. В докладе Г. И. Шушуева утверждается, что уравнение (a,x0) ф (a,x5) = (c, k4) ф ф(с, k5), где x0 — блок открытого текста, xi и k для i > 0 — соответственно блок шифр-текста на выходе i-го раунда и раундовый ключ этого раунда, a = (032, 032, 032,c) и c = 0x0011ffba, является оптимальным линейным приближением пяти раундов SMS4 (стандарта блочного шифра КНР для беспроводных сетей). Утверждается также, что минимальная трудоёмкость линейного криптоанализа девяти раундов SMS4 составляет 2115 операций зашифрования. Результат обнаружения цифровых водяных знаков на основе модифицированной контрольной карты Хотеллинга существенно зависит от содержимого обучающей выборки. Опыт показывает, что лучшие результаты получаются, когда значения соответствующих пикселей изображений обучающей выборки и тестируемого контейнера близки, или, говоря другими словами, изображения в выборке и контейнере подобные. Задача автоматизации поиска подобных изображений решается в докладе Б. Б. Борисенко, предложившего считать изображение I более подобным изображению I1, чем изображению I2, если для некоторой хэш-функции h значение h(I) ближе к h(I1), чем к h(I2), в некоторой метрике. В качестве h предложено использовать вей-влет-преобразование Хаара, последний уровень в котором определяется как первый из тех, на которых хотя бы один из размеров матрицы коэффициентов аппроксимации не превышает 32. 4. Математические основы компьютерной безопасности Как и прежде на школе-семинаре, в проблематике этого направления важнейшее место занимают разработка и исследование математических моделей безопасности компьютерных систем (КС). В докладе Д. М. Бречки представлен алгоритм поиска мостов в графе доступов модели Take-Grant между известными островами графа. Алгоритм основан на поиске в глубину, имеет полиномиальную сложность, предназначен для применения в анализе безопасности КС. Достаточные условия для реализации информационного потока по памяти в операционных системах (ОС) семейства Linux сформулированы в докладе П. Н. Девянина. Их проверка заключается в установлении истинности некоторого предиката ролевой ДП-модели управления доступом и информационными потоками в таких ОС. Нередко реализация запрещённых информационных потоков по времени в ОС осуществляется с использованием интерфейса сокетов: наличие или отсутствие слушающего сокета на некотором порту может служить посылкой одного бита информации — соответственно 1 или 0. Некоторые известные методы предотвращения подобных информационных потоков проанализированы в докладе А. Н. Долгих. Предложен механизм регистрации событий с целью идентификации таких потоков. В известных ролевых моделях управления доступом (RBAC и др.) отсутствуют средства задания и контроля прав доступов, учитывающие иерархию сущностей в КС. Модель иерархического ролевого управления доступом, RBAC-H, предложена в докладе Д. Н. Колегова. В ней, кроме всего прочего, введены типы сущностей, верхняя полурешётка (L, уровней иерархии сущностей, функция fe, задающая для каждой сущности её уровень в этой полурешётке, и предикат, истинный для тех и только тех субъект-сессий s, сущностей e и прав доступа p, для которых fe(e) ^ fe(s) и право доступа p к сущности типа e принадлежит множеству прав доступа ролей субъект-сессии s. Это существенно расширяет класс компьютерных систем, в которых ролевое управление доступом адекватно выражается в математической модели. Ещё одно расширение языковых средств ДП-моделей предложено в докладе П. Ю. Свиридова с целью адекватного описания мандатных и ролевых механизмов системы управления доступом RSBAC в ОС GNU/Lunux. А именно, в ДП-модель вводятся: множества атрибутов, ассоциируемых с сущностями и учитываемых при проверке прав доступа к последним; новые права и виды доступа и типы сущностей, характерные для RSBAC — право доступа на создание (клонирование) процесса, доступ для изменения рабочей директории, тип сущностей межпроцессорного обмена и т. п.; вместо линейной — произвольная решётка уровней доступа; множество прав доступа к сущностям определённого типа и функция прав доступа ролей к таким сущностям, как в RBAC-H. Для анализа безопасности систем управления базами данных В. Ю. Смольянинов построил СУБД ДП-модель как модификацию известной РОСЛ ДП-модели и сформулировал в ней достаточные условия похищения прав доступа. В докладе Н. О. Ткаченко показывается, как в СУБД MySQL (с дискреционным управлением доступом) может быть реализовано мандатное управление доступом путём использования механизма расширения безопасности системы SELinux. Для этого надо для каждой сущности СУБД MySQL задать контекст безопасности в виде набора атрибутов — пользователя, роли, типа и уровня безопасности, создать модуль политики безопасности средствами системы SELinux и разработать для СУБД MySQL компоненту с функциями Object Manager. Сообщается, как это сделано в конкретной реализации данного метода. Обзор шести публикаций последних лет, посвящённых моделям атрибутного управления доступом в КС, дан в докладе Д. В. Чернова, сделавшего попытку изложить их основные свойства в терминах языка ДП-моделей. Информация о лабораторном практикуме «Основы построения защищённых компьютерных сетей» на платформе Cisco Packet Tracer содержится в докладе Д. Н. Колегова и Б. Ш. Хасанова. Его целью является привлечение студентов к исследовательской работе по разработке архитектуры и методов проектирования защи-щённых компьютерных сетей, планированию и построению подсистем защиты информационных технологий, настройке механизмов и средств защиты сетевой инфраструктуры, поиску и устранению неисправностей в системах защиты компьютерных сетей. Кроме традиционной формы обучения практикум позволяет проводить многопользовательские и ролевые игры студентов по проектированию и анализу защищённых компьютерных сетей. 5. Прикладная теория графов Много докладов на школе-семинаре было посвящено приложениям теории графов к синтезу отказоустойчивых управляющих и вычислительных систем. Традиционно сильно в данном направлении выступает Саратовская научная школа, от которой в этом году было представлено 6 докладов. В 1995 г. Ф. Харари и М. Хурум высказали утверждение о том, что минимальное вершинное 1-расширение сверхстройного дерева с k цепями и p сложными вершинами содержит в точности k + p +1 дополнительных ребер, и предложили метод построения такого расширения. Здесь вершина сверхстройного дерева T, расположенная на ярусе j > 1 в цепи длины m, называется сложной, если в T нет концевых вершин на (j — 1)-м и (m — j)-м ярусах. В докладе М. Б. Абросимова и Д. Д. Комарова отмечается, что в общем случае построенное 1-расширение не обязательно является минимальным; приводятся примеры сверхстройных деревьев, имеющих 1-расширения с меньшим, чем k + p + 1, числом дополнительных рёбер. В докладе М. Б. Абросимова и Н. А. Кузнецова сообщается о вычислительном эксперименте с использованием распределённых вычислений, в рамках которого удалось построить все минимальные вершинные (МВ-1Р) и рёберные (МР-1Р) 1-расширения циклов с числом вершин до 17; приводятся данные о количестве таких расширений. В докладе М. Б. Абросимова и О. В. Моденовой изучаются орграфы, имеющие минимальные вершинные 1-расширения с одной и двумя дополнительными дугами; доказано, что 1) объединения нескольких двухвершинных цепей с одной или более изолированными вершинами, и только они, имеют МВ-1Р с одной дополнительной дугой; 2) среди связных орграфов гамильтоновы цепи, и только они, имеют МВ-1Р с двумя дополнительными дугами; 3) среди несвязных орграфов без изолированных вершин только орграфы, являющиеся объединением гамильтоновой цепи Pn с несколькими контурами Cn+1 при n > 2, имеют в своём МВ-1Р две дополнительных дуги; при n = 2 добавляется ещё один случай: вместо контура С3 можно взять транзитивную тройку. Представлен вид всех этих расширений. Расширения неориентированных графов, вершинам которых могут быть приписаны различные типы, рассматриваются в докладе П. П. Бондаренко. Описаны все МВ-1Р и МР-1Р цепей Pn, концевые вершины которых считаются принадлежащими одному типу, а неконцевые — другому. Доказано, что МВ-1Р таких цепей имеют 3k рёбер при n = 2k и 3k + 2 рёбер при n = 2k + 1, а МР-1Р имеют 3k — 1 рёбер при n = 2k и 3k + 1 рёбер при n = 2k + 1. Индексом состояния динамической системы называется расстояние от этого состояния до аттрактора. В докладе А. В. Жарковой предложен алгоритм вычисления индекса состояния динамической системы булевых векторов (Bn, 0), где для вектора v в Bn, рассматриваемого как цикл, в котором первая компонента следует за последней, 0(v) получается заменой в векторе v каждой биграммы 10 биграммой 01. Доказано, что максимальный индекс состояния в такой системе равен (n — 1)/2 — 1 для нечётного n и n/2 — 1 для чётного. В докладе Е. О. Кармановой рассматриваются конгруэнции цепей, т. е. такие отношения эквивалентности на множестве вершин цепи, все классы которых являются независимыми множествами. Доказано, что количество конгруэнций m-рёберн

Ключевые слова

прикладная дискретная математика, криптография, компьютерная безопасность, защита информации, applied discrete mathematics, computer security, cryptography

Авторы

ФИООрганизацияДополнительноE-mail
Панкратова Ирина АнатольевнаНациональный исследовательский Томский государственный университетдоцент, кандидат физико-математических наук, доцент кафедры защиты информации и криптографииpank@isc.tsu.ru
Агибалов Геннадий ПетровичНациональный исследовательский Томский государственный университетпрофессор, доктор технических наук, заведующий кафедрой защиты информации и криптографииagibalov@isc.tsu.ru
Всего: 2

Ссылки

Тезисы докл. Всерос. конф. «XI Сибирская научная школа-семинар с международным участием „Компьютерная безопасность и криптография"» — Sibecrypt'12 (Иркутск, 3-8 сентября 2012 г.) // Прикладная дискретная математика. Приложение. 2012. № 5. 135 с.
Черёмушкин А. В. О содержании понятия «электронная подпись» // Прикладная дискретная математика. 2012. №3(17). С. 53-69.
Тужилин М. Э. Латинские квадраты и их применение в криптографии // Прикладная дискретная математика. 2012. №3(17). C. 47-52.
Быкова В. В. FPT-алгоритмы и их классификация на основе эластичности // Прикладная дискретная математика. 2011. №2(12). C. 40-48.
Быкова В. В. FPT-алгоритмы на графах ограниченной древовидной ширины // Прикладная дискретная математика. 2012. №2(16). C. 65-78.
Евдокимов А. А. Вложения графов в n-мерный булев куб и интервальное кодирование табло // Вестник Томского госуниверситета. Приложение. 2006. №17. С. 15-19.
Евдокимов А. А. Вложения в классе параметрических отображений ограниченного искажения // Ученые записки Казанского госуниверситета. Сер. Физико-математические науки. 2009. Т. 151. №2. С. 72-80.
Едемский В. А., Антонова О. В. Линейная сложность обобщённых циклотомических последовательностей с периодом 2npm // Прикладная дискретная математика. 2012. № 3(17). C. 5-12.
Кяжин С. Н., Фомичёв В. М. О примитивных наборах натуральных чисел // Прикладная дискретная математика. 2012. №2(16). C. 5-14.
Когос К. Г., Фомичёв В. М. О разветвлениях криптографических функций на преобразования с заданным признаком // Прикладная дискретная математика. 2012. №1(15). C. 50-54.
 Sibecrypt'12. Обзор докладов | ПДМ. 2012. № 4(18).

Sibecrypt'12. Обзор докладов | ПДМ. 2012. № 4(18).

Полнотекстовая версия