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

На правах рукописи

ооз172зиъ

Фомичев Николай Владимирович

ИССЛЕДОВАНИЕ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ СИСТЕМ ЗАЩИТЫ ИНФОРМАЦИИ С ПОМОЩЬЮ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ПРИЗНАКОВ В КОНЕЧНЫХ ПОЛУГРУППАХ И ГРУППАХ ПРЕОБРАЗОВАНИЙ

Специальность 05 13 19 — методы и системы защиты информации,

информационная безопасность (физико-математические науки)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Автор

1 е ню-} 2сса

Москва-2008

003172305

Работа выполнена в ГОУВПО Московском инженерно-физическом институте (государственном университете)

Научный руководитель доктор физ.-мат наук, доцент

Фомичев Владимир Михайлович

Официальные оппоненты

доктор физ -мат наук, доцент Физули Камилович Алиев, в/ч 45807-Т

кандидат физ -мат наук, с н с Солодовников Владимир Игоревич, в/ч 71330

Ведущая организация

Институт проблем информационной безопасности МГУ им М В Ломоносова

Защита состоится " 1 " ЦЮЛЯ_2008 г в -76 00 часов

на заседании диссертационного совета ДМ 212 130 08 в ЦИТиС по адресу 123557, г Москва, Пресненский Вал, 19.

С диссертацией можно ознакомиться в библиотеке ГОУВПО Московского инженерно-физического института (государственного университета)

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу 115409, Москва, Каширское ш, 31, диссертационные советы МИФИ (тел 323-95-26)

Автореферат разослан " 30 " МАЯ_2008 года

Ученый секретарь диссертационного совета

к т н, доцент Горбатов В С

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Основополагающим документом, регламентирующим политику России в области информационной безопасности, является Доктрина информационной безопасности Российской Федерации, утвержденная в сентябре 2000 года Президентом Российской Федерации Секция Научного совета при Совете Безопасности Российской Федерации на основе Доктрины разработала Перечень приоритетных научных проблем в области информационной безопасности, включающий ряд междисциплинарных проблем Решение этих проблем требует совместных усилий различных специалистов математиков, физиков, специалистов по информационным технологиям, юристов, социологов, экономистов Среди проблем Перечня, включающих математические задачи, особое место занимает «Разработка фундаментальных проблем теоретической криптографии и смежных с ней областей математики» (п 54 Перечня) В основных документах ведущих международных и российских конференций и форумов по информационной безопасности подчеркивается, что криптографические методы защиты занимают важное место в системе методов обеспечения информационной безопасности

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

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

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

К настоящему времени известно несколько классов систем уравнений (линейные, треугольные и др.), разрешимых со сложностью, полиномиальной от (п+т), где п - количество уравнений в системе, a m - количество неизвестных. Список эффективно решаемых классов систем уравнений со временем расширяется в результате прогресса, как в развитии вычислительных средств, так и в расширении класса исследуемых в криптографии систем уравнений, а также в развитии методов их решения Криптосистема защиты информации признается ненадежной, если соответствующая ей система уравнений эффективно решается с использованием подходящих средств вычислений

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

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

реализации

Таким образом, композиции обратимых и необратимых отображений сочетаются при построении криптографических алгоритмов защиты информации Это обуславливает необходимость изучения криптографических свойств композиций преобразований информации, построенных с использованием как групповых, так и полугрупповых преобразований Базовые критерии качества шифрующих отображений были сформулированы еще Клодом Шенноном в известном докладе 1949 года. Дальнейшая их конкретизация применительно к различным классам шифров привела к исследованию разнообразных криптографических свойств отображений информации. Результаты этих исследований нашли отражение в многочисленных работах как отечественных, так и зарубежных специалистов (М М Глухов, Б А Погорелов, В Н Сачков, А Шамир, М Хеллман, Р Рюппель и многие другие)

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

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

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

В 2005 г. было сформулировано новое алгебраическое направление исследований, связанное с дифференциацией элементов конечных групп по заданным признакам, и представлены первые результаты В 2006 году это направление получило активное продолжение в ряде публикаций В М Фомичева, в которых общий подход к дифференциации по наследственным признакам был развит для конечных групп, групп подстановок и отображений конечных автоматов Получены результаты для ряда частных классов

наследственных признаков, в том числе, связанных со свойством линейности и аффинности подстановок векторного пространства

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

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

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи-

• Развитие математического аппарата исследования признаков в конечных группах для конечных полугрупп, в том числе, для полугрупп преобразований

• Исследование свойств наследственных признаков в группах подстановок, обобщающих свойство треугольно-ступенчатости для подстановок векторного пространства

• Исследование свойств линейного признака в полугруппах и в группах преобразований векторного пространства

• Разработка математических моделей и исследование способов реализации криптографических протоколов, построенных с использованием наследственных признаков в полугруппах и в группах преобразований. Методы исследования; теоретическая криптография, теория групп,

полугрупп, комбинаторный анализ, теория графов, теория решеток

Научная новизна работы характеризуется следующими результатами

1. Математический аппарат исследования признаков в конечных группах обобщен на конечные полугруппы Дано описание признака в циклической полугруппе (§) через характеристики определяющего соотношения

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

3 Установлено, что линейная подполугруппа полугруппы преобразований С содержится в пересечении шести наследственных подмножеств полугруппы (7 Дано описание этих наследственных подмножеств циклической полугруппы {¿) через характеристики графа преобразования §

4 Исследован линейный признак в полугруппе генератора гаммы с неравномерным движением типа [1,2]-самоусечения, используемого при построении криптосистем защиты информации

5 Разработаны математические модели криптографических протоколов аутентификации пользователей в информационных системах на базе структурного наследственного признака в полугруппах линейных

преобразований векторного пространства, предложен вариант реализации протокола на интеллектуальных картах.

На защиту выносятся следующие результаты

1 Описание в конечной циклической (моногенной) полугруппе (¿) наследственных признаков с использованием циклической глубины и периода порождающего элемента §

2 Описание в циклических группах подстановок наследственных признаков, определяемых л-конгруэнтностью подстановок

3 Теоретико-множественное включение линейной подполугруппы полугруппы преобразований б векторного пространства над конечным полем в пересечение ряда наследственных признаков в полугруппе С, уточняющее известное включение для случая групп.

4 Доказательство отсутствия линейного признака в циклической полугруппе, порождаемой генератором гаммы [1,2]-самоусечения

5 Разработка математических моделей криптографических протоколов аутентификации пользователей в информационных системах с использованием наследственного признака, основанного на неинъективности полугрупповых преобразований.

Практическая значимость результатов определяется следующим.

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

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

Результаты по исследованию криптографических протоколов могут быть использованы для создания программного обеспечения с целью решения ряда задач информационной безопасности в информационно-

телекоммуникационных сетях пользователей К таким задачам относятся, например, аутентификация пользователей сети и распределение секретной ключевой информации между пользователями сети

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

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

Внедрение результатов исследований. Результаты диссертации использованы во ФГУП "НТЦ Атлас"

1) при построении методов аутентификации информации, хранящейся на интеллектуальных картах,

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

Публикации и апробация работы. Результаты диссертации изложены в 10 публикациях и докладывались на конференциях и семинарах различного уровня

■ в МГУ им. М В Ломоносова на конференции с международным участием «Математика и безопасность информационных технологий» (МаБИТ-2005),

■ на Седьмом Всероссийском Симпозиуме по прикладной и промышленной математике (весенняя сессия) в г Кисловодске, 2006 г,

■ на V Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» в Шушенском -БШЕСЛУРТОб,

■ на научных семинарах МИФИ и ИПИБ МГУ им М В. Ломоносова в 20052007 г.г

■ на научных семинарах МГТУ им. Баумана в 2007 году

Структура и объём работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 54 наименований Работа изложена на 137 страницах с вычислительными примерами, таблицами и исходными текстами программ

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации, выделяются и формулируются цели и задачи исследования, отражена научная новизна результатов, описывается структурно-логическая схема диссертационного исследования

В первой главе развивается и распространяется математический аппарат для исследования признаков в конечных группах на конечные полугруппы.

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

Пусть Ф — конечная полугруппа, Я— подмножество полугруппы Ф или, иначе говоря, множество элементов полугруппы Ф с признаком Я, G=(S) и 0*Qç:G, где - система образующих элементов полугруппы

G, eeS.

Определим, что элемент g полугруппы G имеет Я-признак, если ge# Полугруппа G (множество Q) имеет Я-признак, если GnH*<25 (QnH*0), при этом Я-признак называется тривиальным (нетривиальным), если GnH (QnH) -одноэлементное множество (содержит более одного элемента)

Показателем Я-признака в полугруппе G (во множестве Q), обозначаемым рок$Я (рок5{£?пЯ)), назовем натуральное число, равное

gTa^H ( g где L&S) ~ Длина элемента g в системе

образующих S Показатель Я-признака в циклической полугруппе (g), обозначаемый рок^Я, равен наименьшему натуральному числу t, при котором g'eH

Важными задачами исследования признаков в полугруппе являются распознавание наличия Я-признака в полугруппе G, описание множества GnH и определение его алгебраических характеристик (показатель в заданной системе образующих, условия тривиальности и др )

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

Я-признак в полугруппе G называется полугрупповым (групповым), если GnH—подполугруппа (подгруппа) полугруппы G (обозначается GnH<G)

Наследственный признак Я является обобщением полугруппового признака и определяется условием если элемент g полугруппы G принадлежит Я, то ig)oH Для определения множества GnH рассмотрим полугруппу G как множество с квазипорядком g<g' для g^eG о (g)<(g) Фактормножество G/~, где для g,g' б G о (g)=(g'), частично упорядочено, поэтому наследственное подмножество Q полугруппы G определено как наследственное подмножество фактормножества GI- Следовательно, из теории решёток следует, что

множество 2 имеет единственное представление в виде объединения всех максимальных в £) циклических подполугрупп (полугруппа (#) максимальна в (2, если и (¿) не является собственной подполугруппой циклической

полугруппы, содержащейся в 0 0= У где вр - система элементов

полугруппы С, порождающих максимальные в <2 циклические подполугруппы Систему Вд назовем с-базисом множества <2, а величину Лс(2), равную назовем с-шириной множества ()

Таким образом, по аналогии с конечными группами получаем способ определения множества всех элементов полугруппы (7 с заданным наследственным признаком Я, основанный на определении элементов из Я во всех максимальных в полугруппе б циклических подполугруппах.

Теорема 1.5. Если полугруппа С имеет наследственный //-признак, то

а)ВСглЯ и В{е)г,„ >

б)К{СглН)< 1Х({£)пЯ),

в) равенства ВСы1= и и Ас(СпЯ)= Г> Я) выполнены тогда

и только тогда, когда для любого £е/?с и любого циклическая

подгруппа (&') максимальна во множестве ОглН, \>

Описание наследственного подмножества циклической

полугруппы порядка п равносильно описанию с-базиса (#'',.. множества {¿)(лН. Эта задача сводится к задаче определения соответствующего подмножества наименьших натуральных чисел Л}, названного

множеством (Я,^-пороговых чисел (обозначается П(Я,^))

Обозначим через (У решетку всех циклических подполугрупп полугруппы {¿> относительно теоретико-множественного включения

Назовем порядком элемента % полугруппы С (обозначается огф?) наименьшее натуральное / такое, что ¿=е, где <? — идемпотент.

Пусть /V - множество натуральных чисел, //„={1,. ,л}, где ле/У Рассмотрим на множестве N¿+„.1 квазипорядок рг /ргт (иначе говоря, / не превышает т в смысле квазипорядка р^) о

Обозначим через /= фактормножество множества ь где т=/ для тогда и только тогда, когда (¿)=(^) Через [т] обозначим класс эквивалентности из N¿+„.^1=, содержащий элемент х из Система

представителей классов эквивалентности фактормножества состоящая

из наименьших представителей классов эквивалентности относительно естественного порядка натуральных чисел, называется каноническим трансверсаяом и обозначается

Теорема 1.7. а) Канонический трансверсал есть решетка по отношению р, антиизоморфная решетке С®, огс!^ и 1 суть соответственно максимальный и минимальный элементы решетки (Л^р), и при с1> 1

Ndn = { 1, ,d-\,mm[d], ,min[rf+«-l]},

где min[x]=mm{ie {d, ,d+n-1 }• (t,n)=(x,n)} при z=d, ,d+n-l

б) Если в полугруппе (g) имеется наследственный Я-признак, то П(Я^) есть множество минимальных элементов t решетки (Д/,,„р) таких, что g'eH t> Следствие 1. Если полугруппа (g) имеет наследственный Я-признак, то f mmiI(H,g), если ¿>1 и штП(Я,^)<с/,

j min ^(d + (t -d)modrl), если штП(H,g)>d, где r,={t,n) t>

Следствие 2. Циклическая полугруппа {g) имеет тривиальный наследственный Я-признак тогда и только тогда, когда множество П(Я^) состоит из единственного числа, равного ordg Е>

Во второй главе исследуются наследственные признаки в группах подстановок, связанные со свойствами треугольно-ступенчатых подстановок Пусть Ф(Х) - группа всех подстановок множества X, и подстановка имеет цикловую структуру C(g), записываемую таблицей чисел C(g)={l\[q\\, AM), то есть g имеет q, циклов длины /„ г=1, ,к

Обозначим через РаЛ(А) множество всех разбиений множества X на непустые блоки Подстановка g однозначно определяет разбиение л=(Х0, Хт i) множества X на блоки, из элементов которых составлены циклы подстановки g. Это разбиение обозначим %c(g) и назовем g^-разбиением Рассмотрим 7rc(g) как монотонную функцию и обозначим g-подфункцию функции 7rc(g) через Tg(t), те 7Гг(0=7Г,(я'), t=\, ,п

Принадлежность элементов хпх' множества X одному блоку разбиения 71

обозначим х=х' Разбиение л назовем g-конгруэнцией, а подстановку g

я я

назовем тг-конгруэнтной, если из х=х' следует g(x)=g(x')

Для любого разбиения и из Part(X) множество всех л-конгруэнтных подстановок есть подгруппа полной симметрической группы S(X) (обозначим эту подгруппу S(A7л)) Следовательно, S(X/n) можно рассматривать как групповой признак в любой группе подстановок G множества X Получим условия, при которых подстановка g является я-конгруэнтной

Пусть Q - конечное множество, Q - множество слов в алфавите П, leN и слово co=(cöo,coi, ,Им)еГ2/ Длиной периода слова ш назовем наименьший делитель т числа I такой, что т</ и ю,=со,+т для /=0,1, ,/-т-1, если такой существует В противном случае длиной периода слова со полагается I Слова со и о' из П циклически эквивалентны, если они совпадают с точностью до циклического сдвига Будем говорить, что слово со имеет бесповторный период, если период слова © есть бесповторная выборка из алфавита Q Слова шиш' называются совместимыми, если они имеют такие бесповторные периоды, которые либо циклически эквивалентны, либо не содержат общих элементов Множество из двух и более слов совместимо, если любые два слова множества совместимы, а множество из одного слова с бесповторным периодом полагается совместимым

Пусть gc-разбиение 7tc(g)=(Ci, ,СГ), где длина цикла Су равна lpj= 1, ,г Рассмотрим отображение a^JC-^Z/m, где и^дг) для хеХ есть номер блока разбиения к, содержащего х. Отображение соя индуцирует отображение col Z/т , где (й*п(Х[^2, )=(0„(*1),со,г(*2), • ) Таким образом, со*(С,) есть слово длины lj в алфавите Z/m,je {1, /}

Теорема 2.1. Подстановка g является я-конгруэнтной тогда и только тогда, когда совместимо множество слов м*(С7,),у=1, ,r t>

Данный критерий позволяет получить ряд необходимых условий п-конгруэнтности подстановки g, выраженных через характеристики цикловой структуры подстановки g, разбиения тс, и через частотные характеристики слов и* (С) для циклов С подстановки g. Проверка невыполнения этих условий для многих подстановок и разбиений требует существенно меньше вычислений, чем проверка условий критерия

Пусть tiс (g)=(Ci, , Ch) - разбиение множества циклов подстановки g на классы я-эквивалентных циклов, то есть лс (g)ePart(7tc(g)), и ту - длина периода слова со*(С) для любого цикла С из класса С¡,j=1, ,h Пусть также X Nr->N¡, -сюръекция, определяемая тем, что цикл С7,е Сад, 7=1,. ,,г Пусть qv - частота номера i в слове со*(С,), i=0,. .,т-1, 7=1,. .,г, и равенство M{qÜJ,.. ,qm.

означает, что в слове со*(С7) номер 0 содержится к0 раз, ., номер т-1 содержится кт.\ раз

Утверждение 2.1. Если подстановка g является л-контруэнтной, то

1) 7tc(g)<7ic (g)<7t и выполнены свойства

a) k<h<r, и имеется сюръекция е N^N^, определяемая тем, что С7 еЛ"^/, 7=1,. .,h, и композиция сюръекций \sNr->N¡¡, определяемая тем, что цикл С, принадлежит блоку X'UU) разбиения n,j=1, ,г,

с) |С;| делится на be(j),j= 1,. .,h\

2) ti+ +тh=m, откуда следует, что d¡+ +dh>m, где d, - наибольший общий делитель длин всех циклов из класса Cj,j= 1,.. ,Л,

3) для частот q,j выполнены свойства:

а)M(qQj,. .,qn.\j)={Q[m-Xj],— [t,])j=1, ,r,

xj

б) все ненулевые числа набора {q,t\, ,ql>r) прямо пропорциональны длинам соответствующих циклов/ь. ,/„¡=0,.. ,т-1 1>

Обозначим В^ \ множество всех наборов из X", у которых значение

компонент с номерами ..,i¡ фиксировано и равно a], ,as соответственно При любом фиксированном наборе {ib ,is} система множеств

{в;; ,(аь ,а;)еХ) образует множество блоков разбиения множества X",

обозначим это разбиение ЛОь

Пусть 7д($,л) - множество треугольно-ступенчатых преобразований, у которых первые 5 координатных функций зависят от х\, л

Утверждение 2.6. Подстановка g множества X" принадлежит ТА{5,п) тогда и только тогда, когда g является 1,. ^-конгруэнтной !>

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

Преобразование g конечного множества X назовем ¿-циклическим, если в его графе имеется в точности к циклических точек, Обозначим через

СУС(к,0) множество всех ¿-циклических преобразований из полугруппы С, где С<Е(Х)

Утверждение 3.5 Для любой полугруппы <7 и для произвольного натурального числа к, где

множество СТС(£;£7) является наследственным Для любого преобразования циклическая полугруппа

(¿) есть подмножество одного из блоков разбиения С=СГС(1,С)и. ^СУС0Х\,СГ) >

Рассмотрим граф преобразования g векторного пространства Р Для циклической вершины х графа Гг обозначим через Тх(л) дерево подхода к вершине х„ и через — количество вершин на 1-м уровне дерева Тх(£), где I - целое неотрицательное число Нулевым уровнем является корень дерева, т.е. пх$=\. Обозначим через Л (я) наибольшую из длин подходов в графе преобразования g

Пусть Н(д\п) - множество преобразований g из таких, что величина

к

делится на Ц для любой циклической вершины х графа Ге и при любом к=\, Л

Утверждение 3.6. Множество Н(д\п) является наследственным [> Стабилизатором элемента х векторного пространства Р в полугруппе преобразований <3 называется множество (полугруппа) преобразований g полугруппы С, относительно которых элемент х является неподвижным

Обозначим через gc ограничение преобразования § из Е(РГ) на множество циклических точек преобразования g Преобразование g из полугруппы С/ является унидоминантным (¿-замкнутым сверху, а -стабильным, р-нормально неподвижным), если унидоминантна (¿-замкнута сверху, а -стабильна, р-нормально неподвижна) подстановка gc

Обозначим через БСЦг,Р) полную линейную подполугруппу полугруппы Е(РГ) Назовем 501(г,Р)-признак линейным признаком

В любой полугруппе преобразований пространства Р признак 8Ы,{г,Р) является полугрупповым

Теорема 3.2. Справедливо включение

.ЧОЦгЛ с ~<)пСг\А1р*\Рг)г>ЧРг)пН(д\п)глНсус, где 9 — ноль пространства Р и Ее — стабилизатор нуля в полугруппе Е(РГ), множества С, Л[/ге](/у) и Е(РГ) суть множества соответственно всех ¿-замкнутых сверху, р-нормально неподвижных и а-стабильных преобразований пространства Р',

Я,ус= СЩ1,Н(Р0)иСЩд,ЩП)^- иСЩдг,Е(Л) > Исследована линейная подполугруппа генератора [¿,А:]-самоусечения, построенного на основе линейного регистра связи (ЛРС) с обратной связью /, реализующего подстановку А пространства Р. Если на выходе ЛРС ноль, то состояние х заменяется на ^(х), если единица - на Продвижка а ЛРС за один такт определяется формулой а=с1 {/[х)®1)+к/{х) Порождаемая генератором циклическая полугруппа есть (/¡"(.г))

Пусть генератор [¿ЗД-самоусечения имеет ненулевое начальное заполнение, а ЛРС имеет максимальный период

Известно, что период Тг [¿/,&]-самоусеченной последовательности,

порожденной ЛРС длины г, равен Тг =

f(2'-l)

, где [d,k]=t [1,2] mod 2г-1 и

НОД(Г, 2МН

Утверждение 3.8. Если преобразование g пространства Р реализует генератор [1,2]-самоусечения, то циклическая полугруппа (g) не имеет линейного признака t>

В четвертой главе исследованы наследственные признаки, связанные с неинъективностью полугрупповых преобразований, и использованы для разработки математических моделей протоколов аутентификации пользователей в информационных системах Описана реализация

разработанного протокола на базе технологии интеллектуальных карт

«

Рассмотрим отношение эквивалентности = на множестве X,

s

индуцируемое преобразованием g множества X х~х' тогда и только тогда, когда g(x)=g(x') Пусть p(g) - разбиение множества X, индуцируемое

s

отношением эквивалентности = Известно, что если h{g) — максимальная из длин подходов к циклам графа Гш полугруппового преобразования g, и я -наименьшее общее кратное длин всех циклов, то полугруппа (g) определяется соотношением gd-gd+n, где

Г 1, h(g)i 1, \h(g), h(g) > 1

Теорема 4.1. Пусть циклическая полугруппа (g) определяется соотношением gd=gd+", где d> 1, тогда p(£)<p(g'H) для всех /е {1, ,d-1} и p(g')=/)(g'+1) для любого t>d t>

Теорема позволяет каждому полугрупповому преобразованию g множества X поставить в соответствие цепь разбиений (p(g), ,p(gd)) из решетки Part (А"), которую назовем цепью g-разбиений Разбиение p(g) назовем

максимальным g-разбиением и обозначим его pmax(g). Обозначим для произвольного разбиения р<в?ъЛ(Х) E(p(g)>p)={geE(X) p{g)>p}\ Ep={geE(X) pmm(g)=p]

Следствие 1) E(p(g)>p) и 3" суть наследственные признаки в полугруппе Е(Х) при любом разбиенииреРаЛ(Х)

2) Если циклическая полугруппа {h) определяется соотношением hd=hd+n, где d> 1, то рок/,H(p(g)>p max (h))=d t>

Математическая идея предлагаемого протокола аутентификации заключается в использовании обеими сторонами секретного полугруппового преобразования g векторного пространства Рг, где Р - конечное поле порядка q Циклическая полугруппа (g) определяется соотношением gd~gd+", где d> 1

В ответ на запрос заявителя проверяющий отправляет заявителю случайно выбранный вектор х и получает от него вектор х', где х'Фх Аутентификация считается успешной, если gd(x)= gd(x')

Корректность протокола обеспечивается существованием указанного вектора х', так как для любой ациклической вершины х вектор gd(x) является циклическим, поэтому найдется хотя бы один (например, циклический) вектор х'&Р такой, что х'фх и g{x')=gd(x)

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

Семейство E={g) преобразований, отвечающих данным требованиям, имеет вид £={5 X 5"'}, где ô\Pr-»Pr — нелинейная биекция и "к РГ->РГ — линейное полугрупповое преобразование с длиной наибольшего цикла I и максимальной длиной подхода h Каждое преобразование из множества Е является нелинейным и подобно преобразованию к Например, в качестве биекции 6 при г=64 можно использовать алгоритм блочного шифрования DES, AES, ГОСТ-28147 и др Тогда выбор секретного полугруппового преобразования g сводится к совместному выбору ключа блочного шифра участниками протокола При неизменном преобразовании Я смена преобразования g равносильна смене ключа Для любого натурального t верно g'=5 А' 5"', что позволяет с невысокой сложностью вычислять g'.

Пусть злоумышленник случайным образом угадывает вектор х', чтобы получить полномочия законного пользователя информационной системы. Если все векторы из равновероятны, то вероятность Рх того, что gh(x')=gh(x)

при заданном векторе х и достаточно больших h оценивается величиной, обратной к числу циклических вершин графа rg

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

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

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

Действия в протоколе аутентификации со стороны пользователя реализованы как приложение защищенного хранилища данных для смарт карт, отвечающих стандарту Java Card v.2.2.1. Приложение хранит данные в виде файлов и разграничивает доступ к ним с помощью отдельного модуля, отвечающего за выполнение протокола. Создан стенд, в котором интеллектуальная карта со встроенным приложением выполняет протокол аутентификации с терминалом, осуществляющим доступ к данным, хранимым на карте,

В качестве блочного шифра, используемого как преобразование подобия 5 при формировании g, используется алгоритм 3DES со 128-битовым ключом, реализованный в смарт карте аппаратно и являющийся частью её операционной системы.

В приложении реализована матрица X размера 64x64, для которой вероятность угадывания злоумышленником вектора х' равна 2"32.

Центр регистрации

Ресурсы

Служба документов

Рис.1. Архитектура информационной системы

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

1 Математический аппарат исследования признаков в конечных группах обобщен на конечные полугруппы Исследование в полугруппах подмножеств элементов с заданным признаком моделирует в виде общей алгебраической задачи определение подмножеств слабых преобразований для криптосистем защиты информации, построенных с использованием полугрупповых преобразований Признаки в полугруппах классифицированы в зависимости от алгебраических свойств множества СпН на полугрупповые, групповые, наследственные, тривиальные

2 Задача описания наследственного признака в полугруппе сведена к задачам описания признака во всех максимальных циклических подполугруппах полугруппы С Сложность определения наследственного подмножества определяется числом максимальных циклических подполугрупп полугруппы С? (с-шириной полугруппы (7) и сложностью определения рассматриваемого наследственного признака Н в циклических полугруппах.

3 Существенно более сложно по сравнению с группами описывается наследственный признак в циклической полугруппе Описание признака в полугруппе (¿) дано через характеристики определяющего соотношения, получены условия тривиальности признака

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

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

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

7 Исследованы в полугруппе (7 преобразований векторного пространства над конечным полем полугрупповой линейный признак, важный для анализа многих криптосистем защиты информации, обрабатываемой в дискретном виде Установлено, что линейная подполугруппа полугруппы преобразований (7 содержится в пересечении шести изученных наследственных подмножеств полугруппы (7 Описание этих наследственных подмножеств циклической

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

8 Исследована линейная подполугруппа полугруппы генератора \djc\-самоусечения с неравномерным движением, используемого при построении криптосистем защиты информации Выделен широкий класс генераторов самоусечения с максимальным периодом и для него доказано, что линейный признак в полугруппе генератора отсутствует Полученные результаты позволяют сделать вывод, что в выходной гамме генератора самоусечения из исследованного класса не имеется участков, линейно зависящих от знаков начального заполнения

9 Исследованы наследственные признаки, основанные на неинъективности полугрупповых преобразований Эти признаки использованы для разработки математических моделей протоколов аутентификации пользователей в информационных системах Обоснованы положительные свойства разработанных математических моделей протоколов возможность обеспечения заданного уровня надежности за счет выбора параметров секретного преобразования, сравнительно невысокая вычислительная сложность реализации, удобство реализации на широком классе вычислительных платформ, в том числе, на интеллектуальных картах

10 Разработанный протокол аутентификации пользователей применен при исследовании систем защиты информации на базе технологии интеллектуальных карт Создано приложение интеллектуальной карты и реализован стенд, в котором выполняется протокол аутентификации карты терминалом В карте протокол реализован в виде модуля, способного встраиваться во все интеллектуальные карты, отвечающие спецификации Java Card 2 2 1 Функционирование модуля отлажено и протестировано на микроконтроллере производства NXP Характеристики секретного преобразования выбраны такими, что они предполагают удобную реализацию на выбранной вычислительной платформе

Данная реализация протокола предъявляет низкие требования к вычислительным ресурсам, и предоставляет возможность использования стандартных, хорошо изученных алгоритмов шифрования

Основные публикации по тема диссертации:

Основные положения диссертационной работы опубликованы в 10 печатных трудах, в том числе в 8 статьях в журналах, включенных ВАК РФ в перечень ведущих рецензируемых научных журналов и изданий-

1 НВ Фомичев Об аутентификации пользователей информационных систем // Безопасность информационных технологий - М. МИФИ, - 2007, №2,-С 50-52

2 H В Фомичев Признаки, определяемые Свойствами линейных полугрупповых преобразований // Вестник МГУ леса. Лесной вестник № 4 -M • МГУ леса -2007,- С 164-166

3. H В Фомичев Признаки, определяемые свойствами треугольно-ступенчатных подстановок векторного пространства // Вестник МГУ леса Лесной вестник. № 4 -М МГУ леса -2007 - С 166-167

4 H В Фомичев Свойства линейных признаков в полугруппах преобразований // Обозрение прикладной и промышленной математики -2007 -т 14, в 5 - С 941-942

5 H В Фомичев Признаки тг-конгруэнтности в группах подстановок // Обозрение прикладной и промышленной математики - 2007 - т 14, в 3 - С 568

6 В M Фомичев, H В Фомичев Исследование признаков элементов в конечных полугруппах и группах // Безопасность информационных технологий -М МИФИ -2006, №1 -С 97-100

7 В M Фомичев, H В Фомичев Общая алгебраическая задача различения элементов конечных полугрупп и групп // Обозрение прикладной и промышленной математики -2006 — т 13, в 1 -С 157-159

8 В M Фомичев, H В Фомичев Вычислительные аспекты исследования признаков в полугруппах и в группах // Обозрение прикладной и промышленной математики - 2006. - т 13, в 1 - С 155-157

9 H В Фомичев Наследственные признаки в конечных полугруппах // Математика и безопасность информационных технологий Материалы конференции в МГУ им Ломоносова 28-29 октября 2004 г - M МЦНМО, 2005 -С 194-197

10ВМ Фомичев, H В Фомичев Исследование наследственных признаков в конечных полугруппах и группах // Материалы докладов V Сибирской научной школы-семинара с международным участием "Компьютерная безопасность и криптография" - SIBECRYPT'06 в Шушенском 5-8 сентября 2006 г - Томск Вестник Томского гос университета - 2006 -Приложение №17 - С 81-86

Подписано в печать 29 05 2008 Тираж 80 экз Отпечатано в Печатном салоне «Оттиск» г Москва, ул Мясницкая, 17 Тел 621-27-17 623-22-31

СПИСОК ОБОЗНАЧЕНИЙ

ВВЕДЕНИЕ

ГЛАВА 1. ПРИЗНАКИ В КОНЕЧНЫХ ПОЛУГРУППАХ

1.1. Общие сведения и определяющие свойства признаков в конечных полугруппах

1.1.1. Общие сведения и исследовательские задачи, связанные с изучением признаков в конечных полугруппах

1.1.2. Определяющие свойства признаков в конечной полугруппе

1.1.3. О связи показателя //-признака в конечной полугруппе с характеристиками некоторых графов и матриц

1.2. Определяющие свойства полугрупп.

1.2.1. Свойства наследственных подмножеств конечной полугруппы и их покрытий циклическими полугруппами

1.2.2. Определяющие свойства циклических полугрупп.

1.3. Исследование полу групповых и наследственных признаков в конечных полугруппах.

1.3.1. Определяющие свойства наследственных признаков в полугруппе

1.3.2. Свойства наследственных признаков в циклической полугруппе

1.3.3. Свойства наследственных признаков в прямом произведении полугрупп

1.3.4. О распределении наследственного признака в циклической полугруппе

1.4. Свойства некоторых классов функций, определенных на полугруппах.

ГЛАВА 2. ИССЛЕДОВАНИЯ ПРИЗНАКОВ В ГРУППАХ ПОДСТАНОВОК, ОПРЕДЕЛЯЕМЫХ СОГЛАСОВАННОСТЬЮ С ЗАДАННЫМ РАЗБИЕНИЕМ

ОСНОВНОГО МНОЖЕСТВА

2.1. Наследственные признаки в полугруппах и группах преобразований, определяемых разбиенеиями основного множества.

2.1.1.71-конгруэнтность подстановок.

2.1.2. Сложность вычисления признака согласованности.

2.1.3. Необходимые условия я-конгруэнтности подстановок.

2.2. Наследственные признаки в полугруппах и группах преобразований, определяемые свойствами треугольно-ступенчатых преобразований.

2.2.1. Определяющие свойства треугольно-ступенчатых преобразований.

2.2.2. Критерий биективности треугольно-ступеньчатых преобразований.

2.2.3. Признак в группах подстановок, связанный с треугольно-ступенчатыми преобразованиями

ГЛАВА 3. ИССЛЕДОВАНИЯ ПРИЗНАКОВ В ПОЛУГРУППАХ ПРЕОБРАЗОВАНИЙ ВЕКТОРНЫХ ПРОСТРАНСТВ,

СВЯЗАННЫХ СО СВОЙСТВОМ ЛИНЕЙНОСТИ.

3.1. Свойства линейных преобразований, используемые для изучения линейного признака.

3.1.1. Естественная нормальная форма матрицы.

3.1.2. Структура обратимого линейного преобразования.

3.1.3. Структура линейного нильпотентного преобразования

3.1.4. Свойства числовых наборов в редукциях цикловых структур преобразований.

3.2. Наследственные признаки в полугруппе преобразований, определяемые количеством циклических и ациклических точек графа преобразования

3.3. О линейном признаке в полугруппе преобразований векторного пространства

3.4. Линейный признак в полугруппе генераторов гаммы типа «самоусечения»

ГЛАВА 4. АУТЕНТИФИКАЦИЯ ПОЛЬЗОВАТЕЛЕЙ В ИНФОРМАЦИОННЫХ СИСТЕМАХ НА БАЗЕ

НАСЛЕДСТВЕННЫХ ПРИЗНАКОВ В ПОЛУГРУППАХ

4.1. Наследственный признак в полугруппе преобразований, определяемый разбиением основного множества на полные прообразы.

4.2. Протокол аутентификации пользователей.

4.2.1. Описание протокола.

4.2.2. Корректность и эффективность протокола.

4.2.3. Построение множества преобразований Е.

4.2.4. Характеристики эффективности протокола.

4.3. Применение протокола аутентификации на базе интеллектуальных карт

4.3.1. Общее описание архитектуры информационной системы.

4.3.2. Общие сведения об интеллектуальных картах.

4.3.3. Технология Java карт.

4.3.4. Описание приложения, реализующего протокол

4.3.5. Параметры реализованного протокола аутентификации

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

Основополагающим документом, регламентирующим политику России в области информационной безопасности, является Доктрина информационной безопасности Российской Федерации, утверждённая в сентябре 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. Математический аппарат исследования признаков в конечных группах обобщен на конечные полугруппы. Исследование в полугруппах подмножеств элементов с заданным признаком моделирует в виде общей алгебраической задачи определение подмножеств слабых преобразований для криптосистем защиты информации, построенных с использованием полугрупповых преобразований. Признаки в полутруппах классифицированы в зависимости от алгебраических свойств множества Gr\H на полугрупповые, групповые, наследственные, тривиальные.

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. В целом результаты диссертации можно квалифицировать как существенный вклад в развитие математических принципов создания систем защиты информации на основе дифференциации полугрупповых преобразований по признакам, определяющим криптографические свойства систем защиты информации. Результаты выполненной работы позволяют для определенного класса криптографических систем выявить «слабые» преобразования с точки зрения защиты информации и обосновать рекомендации по выбору параметров криптосистем с целью предотвращения использования «слабых» преобразований для защиты информации.

ЗАКЛЮЧЕНИЕ

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

1. Айгнер М. Комбинаторная теория. - М.: Мир, 1982. - 558 с.

2. Алфёров А.П., Зубов А.Ю., Кузьмин А. С., Черёмушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2001. - 480 с.

3. Беряс К. Теория графов и её применение. М.: ИЛ, 1962. - 320 с.

4. Биркгоф Г. Теория решёто: Пер. с англ. — М.: Наука, Главная редакция физико-математической литературы, 1984. 567 с.

5. Доктрина информационной безопасности Российской Федерации. В сб. «Научные и методологические проблемы информационной безопасности» / Под ред. В.П. Шерстюка. М.: МЦНМО, 2004. - С. 149197.

6. Гантмахер Ф.Р. Теория матриц. 4-е изд. - М.: Наука, 1988. - 552 с.

7. Герасименко В.А., Малюк А.А. Основы защиты информации. М.: МИФИ, 1997.-539 с.

8. Гилл. А. Линейные последовательные машины. Пер. с англ. — М.: Наука, Главная редакция физико-математической литературы, 1974. — 288 с.

9. Глухое М.М. О числовых параметрах, связанных с заданием конечных групп системами образующих элементов. В сб. «Труды по дискретной математике», т.1, М.: «ТВП», 1997г., с. 43-66.

10. Глухое М.М., Елизаров В.П., Нечаев А.А. Алгебра, т.1. М.: Гелиос-АРВ, 2003. - 336 с

11. Гретцер Г. Общая теория решеток. Пер. с англ./ Под редакцией Д.М. Смирнова. -М.: Мир, 1981.

12. Гроссман И, Магнус В. Группы и их графы. М.: МИР, 1971. - 248 с.

13. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. М.: МИР, 1972. - Т. 1 - 285 е., т.2 - 422 с.

14. Кнут Д. Искусство программирования для ЭВМ, т. 3. Сортировка и поиск. — М.: Мир, 1978.

15. Коблнц Н. Курс теории чисел и криптографии. М.: Научное изд-во ТВП, 2001.-260 с.

16. Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит, 1994.-320 с.

17. Кострикин А.И. Введение в алгебру. Ч.Ш. Основные структуры алгебры. М.: Физматлит, 2000. - 272 с.

18. Курош А.Г. Теория групп. СПб.: «Лань», 2005. - 648 с.

19. Лаллеман Ж. Полугруппы и комбинаторные приложения: Пер. с англ. — М.: Мир, 1985. — 441с., ил.

20. Ленг С. Алгебра. М.: МИР, 1968. - 564 с.

21. Логачёв О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии М.: МЦНМО, 2004. - 470 с.

22. Ляпин Е.С. Полугруппы. М.: Физматлит, 1960. - 592 с.

23. Подуфалов И Д., Фомичёв В.М. Признаки элементов в конечных группах // Докл. РАН, т.404, №3, 2005. С. 308-311.

24. Роберт Дж. МакЭлис. Конечные поля для кибернетиков и инженеров. — М.: МЦНМО, 2004, 123 стр.

25. Струнков С.П. Введение в теорию линейных представлений конечных групп. М.: МИФИ, 1993. - 68 с.

26. Фомичёв В.М. О распознавании признаков элементов в конечных группах // Математика и безопасность информационных технологий.

27. Материалы конференции в МГУ 28-29 октября 2004 г. М.: МЦНМО, 2005.-С. 232-235.

28. Фомичев В.М. Дискретная математика и криптология. М.: ДИАЛОГ-МИФИ. - 2003. - 400 с.

29. Фомичёв В.М. Исследование признаков в конечных группах и в группах подстановок // Математические вопросы кибернетики. Вып. 14: Сборник статей / Под ред. О.Б. Лупанова. М.: Физматлит, 2005. - С. 161-260.

30. Фомичёв В.М. О линейной подгруппе группы преобразований некоторых генераторов гаммы с неравномерным движением // Вестник МГУ леса, препринт № 95. М.: МГУ леса. - 2006. - 7 с.

31. Фомичёв В.М., Фомичёв Н.В. Исследование признаков элементов в конечных полугруппах и группах // Безопасность информационных технологий. М.: МИФИ. - 2006, №1. - С. 97-100.

32. Фомичёв В.М., Фомичёв Н.В. Общая алгебраическая задача различения элементов конечных полугрупп и групп // Обозрение прикладной и промышленной математики. -2006. т. 13, в. 1. - С. 157-159.

33. Фомичёв В.М., Фомичёв Н.В. Вычислительные аспекты исследования признаков в полугруппах и в группах // Обозрение прикладной и промышленной математики. -2006. -т.13, в.1. С. 155-157.

34. Фомичёв Н.В. Наследственные признаки в конечных полугруппах. // Математика и безопасность информационных технологий. Материалыконференции в МГУ 28-29 октября 2004 г. М.: МЦНМО, 2005. - С. 194-197.

35. Фомичев Н.В. Об аутентификации пользователей информационных систем. // Безопасность информационных технологий. М.: МИФИ, -2007, №2 - С. 50-52.

36. Фомичев Н.В. Признаки, определяемые Свойствами линейных полугрупповых преобразований. // Вестник МГУ леса. Лестной вестник. № 4. М.: МГУ леса. - 2007. - С. 164-166.

37. Фомичев Н.В. Признаки, определяемые свойствами треугольно-ступенчатных подстановок векторного пространства. // Вестник МГУ леса. Лестной вестник. № 4. М.: МГУ леса. - 2007. - С. 166-167.

38. Фомичев Н.В. Свойства линейных признаков в полугруппах преобразований. // Обозрение прикладной и промышленной математики.- 2007. т. 14, в.5. - С.941-942.

39. Фомичев Н.В. Признаки тг-конгруэнтности в группах подстановок. // Обозрение прикладной и промышленной математики. — 2007. т. 14, в.З.- С. 568.

40. Харари Ф. Теория графов. М.: «МИР», 1973. - 304 с.

41. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: ТРИУМФ, 2002. - 816 с.

42. Application Programming Interface for the Java Card Platform, Version 2.2.2. Sun Microsystems, Inc., 2006.

43. Golic J.D. On the linear complexity of functions of periodic GF(q)-sequences. IEEE Trans. Inform. Theory, v. IT-35, 1989.

44. ISO 7816 Specification, Parts 1-6. (http://www.iso.org)

45. Java Card™ Platform Security. Technical White Paper. Sun Microsystems, Inc., October 2001.

46. Menezes, Oorschot P., Vanstone S. Handbook of Applied Cryptography. N.Y.: CRC Press, 1997

47. NIST Special Publication 800-63, Electronic Authentication Guideline, version 1.0.2. April 2006.

48. Nyjfeler P. Binare Automation und ihre linearen Rekursionen, Ph. D. thesis, University of Berne, 1975.

49. Runtime Environment Specification for the Java Card Platform, Version 2.2.2. Sun Microsystems, Inc., 2006.

50. Rueppel R.A. Analysis and Design of Stream Ciphers. Berlin: Springer Verlag, 1986.

51. Rueppel R.A. When shift registers clock themselves. Lecture Notes in Computer Science 304; Advances in Cryptology: Proc. EuroCrypt'87. Berlin: Springer Verlag, 1988.

52. U.S. General Services Administration. Government Smart Card Handbook, February 2004.http://www.smartcardalliance.org/resources/pdf/smartcardhandbook.pdf

53. Virtual Machine Specification for the Java Card Platform, Version 2.2.2. Sun Microsystems, Inc., 2006