Одной из приоритетных задач в международном сообществе является обеспечение информационной безопасности. Развивается сотрудничество между государствами в данной области. В Российской Федерации особое внимание уделяется вопросам защиты государственной тайны и конфиденциальной информации. В функционировании, как коммерческих организаций, так и государственных предприятий первостепенную роль играет обеспечение мер, необходимых для защиты информации, представляющей научно-техническую, технологическую, производственную и финансово-экономическую ценность. В последнее время проблемы информационной безопасности приобрели особую значимость в связи с необходимостью усиления борьбы с проявлениями терроризма, приобретающего международные масштабы.
Основополагающим документом, регламентирующим политику России в области информационной безопасности, является Доктрина информационной безопасности Российской Федерации, утверждённая в сентябре 2000 года Президентом Российской Федерации. Секция Научного совета при Совете Безопасности Российской Федерации на основе Доктрины разработала Перечень приоритетных научных проблем в области информационной безопасности, включающий ряд междисциплинарных проблем. Решение этих проблем требует совместных усилий различных специалистов: математиков, физиков, специалистов по информационным технологиям, юристов, социологов, экономистов. Среди проблем Перечня, включающих математические задачи, особое место занимает «Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики» (п. 54 Перечня). В основных документах международных и российских конференций и форумов по информационной безопасности подчёркивается, что криптографические методы защиты занимают ведущее место в системе методов обеспечения информационной безопасности.
Качество криптографических методов определяется в основном криптографической стойкостью системы защиты информации. Основной количественной мерой стойкости является вычислительная сложность решения задачи преодоления выстроенной защиты, то есть задачи дешифрования. Количественная оценка уровня защиты информации с использованием криптосистемы определяется как вычислительная сложность наиболее эффективного из известных алгоритмов дешифрования криптосистемы. Величина оценки измеряется, как правило, временными затратами или числом условных операций ЭВМ, необходимых для реализации алгоритма преодоления защиты.
Решение задач по преодолению криптографической защиты информации с использованием вычислительных алгоритмов основано на разработке математических моделей, адекватно описывающих функционирование криптографической системы защиты информации, а также моделей вычислительных алгоритмов вскрытия криптосистемы. Математическая формализация таких задач во многих случаях приводит к задачам решения систем уравнений в различных алгебраических структурах. В связи с этим одной из важнейших и активно развиваемых областей криптографии является разработка методов решения различных систем уравнений, связывающих элементы неизвестного ключа криптографической системы защиты информации с известными данными.
К настоящему времени известно несколько классов систем уравнений (линейные, треугольные и др.), разрешимых со сложностью, полиномиальной от (п+т), где п — количество уравнений в системе, am — количество неизвестных. Список эффективно решаемых классов систем уравнений со временем расширяется в результате прогресса, как в развитии вычислительных средств, так и в расширении класса исследуемых в криптографии систем уравнений, а также в развитии методов их решения. Криптосистема защиты информации признаётся ненадёжной, если соответствующая ей система уравнений эффективно решается с использованием подходящих средств вычислений.
При канонической записи системы уравнений, в которой все неизвестные элементы записаны в левой части системы, имеется биекция между всевозможными левыми частями систем уравнений и отображениями множеств. В криптографических задачах эти множества, как правило, конечны. Поэтому классам систем уравнений, решаемых на ЭВМ с невысокой трудоёмкостью, соответствуют классы отображений, которые характеризуются как слабые с точки зрения криптографической защиты информации. Таким образом, актуальной задачей при исследовании криптографических систем защиты информации является описание подмножества слабых отображений, реализуемых этими системами.
Криптосистемы защиты информации обычно построены на основе композиции нескольких отображений, допускающих удобную аппаратную и/или программную реализацию. При этом криптосистема в целом реализует некоторое множество подстановок, а в некоторых случаях — группу подстановок. В то же время во многих криптосистемах защиты информации можно выделить функциональную часть, множество реализуемых отображений которой образует полугруппу или некоторое подмножество полугруппы, так как при построении криптографических алгоритмов используются не только обратимые (групповые), но и необратимые (полугрупповые) отображения. Например, в блочных криптосистемах полугрупповые преобразования могут использоваться при построении раундовых отображений. В поточных шифрах полугрупповые преобразования нередко используются в алгоритмах выработки гаммы. Например, функционирование алгоритма Solitaire описывается математической моделью автомата с частичными функциями переходов, порождающими полугруппу. Существуют классы генераторов гаммы, построенных на основе необратимых преобразований (например, генераторы самоусечения). Принципиальной идеей построения таких генераторов является усложнение слабых, в частности, линейных преобразований с целью повышения уровня защиты информации при несущественном усложнении реализации.
Таким образом, композиции обратимых и необратимых отображений сочетаются при построении криптографических алгоритмов защиты информации. Это обуславливает необходимость изучения криптографических свойств композиций преобразований информации, построенных с использованием как групповых, так и полугрупповых преобразований. Базовые критерии качества шифрующих отображений были сформулированы еще Клодом Шенноном в известном докладе 1949 года. Дальнейшая их конкретизация применительно к различным классам шифров привела к исследованию разнообразных криптографических свойств отображений информации. Результаты этих исследований нашли отражение в многочисленных работах как отечественных, так и зарубежных специалистов (М. М. Глухов, Б. А. Погорелов, В. Н. Сачков, А. Шамир, М. Хеллман, Р. Рюппель и многие другие).
Имеется немало примеров, показывающих, что не всякая композиция отображений имеет хорошие криптографические свойства с точки зрения защиты информации. Поэтому для оценки уровня криптографической защиты информации важным является описание подмножеств слабых элементов полугруппы или группы, описывающей функционирование криптосистемы. Такое описание может быть использовано для построения тех или иных методов дешифрования. Подмножества слабых элементов полугруппы (группы), определенные в данной работе как подмножества элементов с заданным признаком, являются основным предметом исследования настоящей диссертации.
Одним из наиболее изученных классов криптографически слабых преобразований являются линейные и аффинные преобразования векторных пространств и преобразования, имеющие хорошие приближения в этих классах. В открытой литературе активно изучались многочисленные характеристики нелинейности отображений, связанные с их потенциальными слабостями ([21,46,48] и др.).
Вместе с тем, слабости криптографических преобразований не обязательно сводятся к их линейности. Например, система уравнений, в которой несколько уравнений несущественно зависят от определенной части переменных (треугольно-ступенчатая система уравнений, соответствующая несовершенному преобразованию), может эффективно решаться методами типа последовательного опробования. В связи с этим актуальными задачами являются как разработка общего подхода к исследованию различного вида слабых преобразований, так и развитие этого подхода на основе учета особенностей исследуемых признаков и полугрупп (групп) преобразований.
В 2005 г. в [23] было сформулировано новое алгебраическое направление исследований, связанное с дифференциацией элементов конечных групп по заданным признакам, и представлены первые результаты. В 2006 году это направление получило активное продолжение в ряде публикаций В. М. Фомичева, в которых общий подход к дифференциации по наследственным признакам был развит для конечных групп, групп подстановок и отображений конечных автоматов. Получены результаты для ряда частных классов наследственных признаков, в том числе, связанных со свойством линейности и аффинности подстановок векторного пространства.
В настоящей работе общий подход к изучению слабых отображений распространяется на полугрупповые преобразования. Актуальность данного направления исследований вытекает из необходимости исследования возможных слабостей отображений информации для широкого класса криптосистем с целью оценки уровня защиты информации.
Целью диссертационной работы является развитие математического аппарата создания перспективных средств защиты информации на основе исследования признаков в полугруппах и группах преобразований, определяющих криптографические свойства систем защиты информации.
В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:
• Развитие математического аппарата исследования признаков в конечных группах для конечных полугрупп, в том числе, для полугрупп преобразований.
• Исследование свойств наследственных признаков в группах подстановок, обобщающих свойство треугольно-ступенчатости для подстановок векторного пространства.
• Исследование свойств линейного признака в полугруппах и в группах преобразований векторного пространства.
• Разработка математических моделей и исследование способов реализации криптографических протоколов, построенных с использованием наследственных признаков в полугруппах и в группах преобразований.
Методы исследования: теория групп, полугрупп, комбинаторный анализ, теория графов, теория решеток.
Научная новизна работы характеризуется следующими результатами:
1. Математический аппарат исследования признаков в конечных группах обобщен на конечные полугруппы. Дано описание признака в циклической полугруппе (g> через характеристики определяющего соотношения.
2. Исследованы характеристики нового класса наследственных признаков-конгруэнтности в группах подстановок, обобщающего свойства треугольно-ступенчатых подстановок декартовой степени конечного множества.
3. Установлено, что линейная подполугруппа полугруппы преобразований G содержится в пересечении шести наследственных подмножеств полугруппы G. Дано описание этих наследственных подмножеств циклической полугруппы (g> через характеристики графа преобразования g.
4. Исследован линейный признак в полугруппе генератора гаммы с неравномерным движением типа [1,2]-самоусечения, используемого при построении криптосистем защиты информации.
5. Разработаны математические модели криптографических протоколов аутентификации пользователей в информационных системах на базе структурного наследственного признака в полугруппах линейных преобразований векторного пространства, предложен вариант реализации протокола на интеллектуальных картах.
На защиту выносятся следующие результаты:
1. Определение в конечной циклической (моногенной) полугруппе (g) наследственных признаков с использованием циклической глубины и периода порождающего элемента g.
2. Определение в циклических группах подстановок наследственных признаков, определяемых я-конгруэнтностью подстановок.
3. Теоретико-множественное включение линейной подполугруппы полугруппы преобразований G векторного пространства над конечным полем в пересечение ряда наследственных признаков в полугруппе G, уточняющее известное включение для случая групп.
4. Доказательство отсутствия линейного признака в циклической полугруппе, порождаемой генератором гаммы [1,2]-самоусечения.
5. Разработка математических моделей криптографических протоколов аутентификации пользователей в информационных системах с использованием наследственного признака, основанного на неинъективности полугрупповых преобразований.
Практическая значимость результатов определяется следующим.
Рассмотренные бинарные классификации элементов конечных полугрупп и групп преобразований имеют существенное значение для разделения на «сильные» и «слабые» множества функций, реализуемых в криптосистемах обеспечения целостности информации, шифрования, идентификации и имитозащиты. Использование «слабых» функций в системах защиты информации даёт возможность криптоаналитику вычислить ключ криптосистемы и получить доступ к ценной информации. Таким образом, разделение функций, реализуемых в криптосистемах, на «сильные» и «слабые» существенным образом определяет принципы создания перспективных средств защиты информации, направленные на устранение опасности обработки информации с помощью некоторых «слабых» функций.
Результаты диссертации по исследованию наследственных признаков в конечных полугруппах и группах могут использоваться для анализа конкретных криптографических систем защиты информации с помощью определения признаков в группах подстановок и в полугруппах преобразований, соответствующих итеративным блочным шифрам, генераторам гаммы (например, генераторам самоусечения) и другим криптографическим схемам. В частности, результаты описания в группах подстановок наследственных признаков, определяемых согласованностью подстановок с заданным разбиением основного множества, позволяют оценивать защищенность информации в криптографических системах относительно методов определения ключевой информации с помощью последовательного опробования.
Результаты по исследованию криптографических протоколов могут быть использованы для создания программного обеспечения с целью решения ряда задач информационной безопасности в информационно-телекоммуникационных сетях пользователей. К таким задачам относятся, например, аутентификация пользователей сети и распределение секретной ключевой информации между пользователями сети.
В рамках диссертации осуществлено применение полученных теоретических результатов. Построен криптографический протокол аутентификации пользователей сети на основе структурного наследственного признака в полугруппах преобразований. Проанализированы варианты реализации этого протокола и протоколов аутентификации и распределения ключей с использованием линейного признака в группах подстановок. Предложены варианты реализации протоколов на интеллектуальных картах.
Внедрение результатов исследований. Результаты диссертации использованы во ФГУП «НТЦ Атлас» :
1) при построении методов аутентификации информации, хранящейся на интеллектуальных картах;
2) при создании испытательного стенда, предназначенного для разработки методов аутентификации коммерческой информации, обрабатываемой в системах защиты информации, построенных на базе технологии интеллектуальных карт.
Публикации и апробация работы. Результаты диссертации изложены в 10 публикациях и докладывались на конференциях и семинарах различного уровня: в МГУ им. М. В. Ломоносова на конференции с международным участием «Математика и безопасность информационных технологий» (МаБИТ-2005), на Седьмом Всероссийском Симпозиуме по прикладной и промышленной математике (весенняя сессия) в г. Кисловодске, 2006 г., на V Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» в Шушенском — SIBECRYPT06, на научных семинарах МИФИ и ИПИБ МГУ им. М.В.
Ломоносова в 2005;2007 г. г. на научных семинарах МГТУ им. Баумана в 2007 году.
Структура и объём работы. Диссертация состоит из введения,.
Основные результаты работы состоят в следующем.
1. Математический аппарат исследования признаков в конечных группах обобщен на конечные полугруппы. Исследование в полугруппах подмножеств элементов с заданным признаком моделирует в виде общей алгебраической задачи определение подмножеств слабых преобразований для криптосистем защиты информации, построенных с использованием полугрупповых преобразований. Признаки в полутруппах классифицированы в зависимости от алгебраических свойств множества GrH на полугрупповые, групповые, наследственные, тривиальные.
2. Задача описания наследственного признака в полугруппе сведена к задачам описания признака во всех максимальных циклических подполугруппах полугруппы G. Сложность определения наследственного подмножества определяется числом максимальных циклических подполугрупп полугруппы G (с-шириной полугруппы G) и сложностью определения рассматриваемого наследственного признака Н в циклических полугруппах.
3. Существенно более сложно по сравнению с группами описывается наследственный признак в циклической полугруппе. Описание признака в полугруппе (g) дано через характеристики определяющего соотношения, получены условия тривиальности признака.
4. В группах подстановок исследовано свойство тг-конгруэнтности, то есть согласованности подстановок с заданным разбиением я основного множества, которое обобщает свойства треугольно-ступенчатых подстановок конечномерных векторных пространств.
5. Исследованы характеристики нового класса наследственных признаков 71-конгруэнтности в группах подстановок. Доказан критерий к-конгруэнтности подстановок, показано, что вычислительная сложность определения 71-конгруэнтности подстановок по порядку не меньше мощности основного множества подстановок. Получен ряд необходимых условий 71-конгруэнтности подстановок, позволяющих в некоторых случаях определять тривиальность признака тг-конгруэнтности с невысокой вычислительной сложностью.
6. Описание признака тс-конгруэнтности использовано для описания свойств признака треугольно-ступенчатости в группах подстановок множества X1, где X — конечное множество. Даны определяющие свойства треугольно-ступенчатых преобразований множества Х доказан критерий их обратимости. Полученные результаты исследования признака треугольно-ступенчатости являются существенными для оценки защищенности широкого класса криптосистем относительно методов последовательного опробования ключей.
7. Исследованы в полугруппе G преобразований векторного пространства над конечным полем полугрупповой линейный признак, важный для анализа многих криптосистем защиты информации, обрабатываемой в дискретном виде. Установлено, что линейная подполугруппа полугруппы преобразований G содержится в пересечении шести изученных наследственных подмножеств полугруппы G. Описание этих наследственных подмножеств циклической полугруппы (g) определяется характеристиками графа преобразования g. Для случая групп данная оценка уточняет ранее известную оценку. Полученное уточнение расширяет класс криптосистем, для которых с использованием доказанного теоретико-множественного включения можно обосновать высокий уровень защиты информации относительно метода линеаризации.
8. Исследована линейная подполугруппа полугруппы генератора [d, k~-самоусечения с неравномерным движением, используемого при построении криптосистем защиты информации. Выделен широкий класс генераторов самоусечения с максимальным периодом и для него доказано, что линейный признак в полугруппе генератора отсутствует. Полученные результаты позволяют сделать вывод, что в выходной гамме генератора самоусечения из исследованного класса не имеется участков, линейно зависящих от знаков начального заполнения.
9. Исследованы наследственные признаки, основанные на неинъективности полугрупповых преобразований. Эти признаки использованы для разработки математических моделей протоколов аутентификации пользователей в информационных системах. Обоснованы положительные свойства разработанных математических моделей протоколов: возможность обеспечения заданного уровня надежности за счет выбора параметров секретного преобразования, сравнительно невысокая вычислительная сложность реализации, удобство реализации на широком классе вычислительных платформ, в том числе, на интеллектуальных картах.
10. Разработанный протокол аутентификации пользователей применен при исследовании систем защиты информации на базе технологии интеллектуальных карт. Создано приложение интеллектуальной карты и реализован стенд, в котором выполняется протокол аутентификации карты терминалом. В карте протокол реализован в виде модуля, способного встраиваться во все интеллектуальные карты, отвечающие спецификации Java Card 2.2.1. Функционирование модуля отлажено и протестировано на микроконтроллере производства NXP. Характеристики секретного преобразования выбраны такими, что они предполагают удобную реализацию на выбранной вычислительной платформе.
Данная реализация протокола предъявляет низкие требования к вычислительным ресурсам, и предоставляет возможность использования стандартных, хорошо изученных алгоритмов шифрования.
11. В целом результаты диссертации можно квалифицировать как существенный вклад в развитие математических принципов создания систем защиты информации на основе дифференциации полугрупповых преобразований по признакам, определяющим криптографические свойства систем защиты информации. Результаты выполненной работы позволяют для определенного класса криптографических систем выявить «слабые» преобразования с точки зрения защиты информации и обосновать рекомендации по выбору параметров криптосистем с целью предотвращения использования «слабых» преобразований для защиты информации.
ЗАКЛЮЧЕНИЕ
.
В диссертации исследована математическая модель признаков в полугруппах и группах, позволяющая исследовать криптографические свойства систем защиты информации. Ранее предложенный алгебраический подход к изучению слабых подстановок в группах распространен на полугрупповые преобразования. Исследованная математическая модель позволяет анализировать возможные слабости преобразований информации для широкого класса криптосистем, а также позволяет глубже обосновать уровень защищенности информации.