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

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

1 :. й -

СЕМЕНОВ Александр Анатольевич

ОЦЕНКИ СТОЙКОСТИ СИСТЕМ ЗАЩИТЫ ДИСКРЕТНЫХ ДАННЫХ

05.13.16 — Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

Иркутск — 1998

Работа выполнена на кафедре информатики и кибернетики Иркутской государственной экономической академии

Научные руководители — доктор физико-математических наук, профессор А.И. Москаленко кандидат физико-математических наук В.Н. Логачев

Официальные оппоненты — доктор технических наук, профессор Г.П. Агибалов кандидат физико-математических наук, доцент А.И. Труфанов

Ведущая организация — Новосибирский государственный технический университет

Защита состоится " ^ " 1998 года в часов на

заседании диссертационного совета К 064.28.04 в Иркутской государственной экономической академии по адресу : 664015, ул. Ленина, 11, ауд. 308, корп. 3

С диссертацией можно ознакомиться в библиотеке Иркутской государственной экономической академии.

Автореферат разослан "3"_ноября 1998 года.

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

кандидат экономических наук, доцент Амбросов

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

АКТУАЛЬНОСТЬ ТЕМЫ. С развитием информационных технологий особую важность приобретают способы и средства защиты информации. Наиболее математически строгим является подход к данной проблеме в рамках криптологии. Согласно классической работе Шеннона, в качестве меры раскрываемости криптограммы используется вероятность события: "выбранная оценка открытого текста, при условии известной криптограммы, совпала с истинным открытым текстом". Однако при этом не определяется строго вероятностное пространство, элементом которого является такое событие, что не позволяет построить единообразную процедуру получения содержательных оценок стойкости криптосистем. Таким образом, всякая оценка стойкости той или иной криптосистемы, полученная методами известными на сегодняшний день, не гарантирует, что не найдется новый способ (алгоритм) ее раскрытия, действующий быстрее, чем известные. Существующие методы получения оценок стойкости криптосистем с секретным ключом являются, главным образом, развитием идей Шеннона и носят эмпирический характер. При этом часто относительно возможности криптоаналитика приходится делать предположения, что он обладает неограниченными вычислительными и временными ресурсами, что, само по себе, далеко от реальности.

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

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

ЦЕЛЬ РАБОТЫ. Разработка единообразного подхода к получению содержательных оценок стойкости криптосистем с секретным ключом и описание общих конструкций систем аутентификации, обеспечивающих совершенную аутентичность.

Для достижения поставленной цели решаются следующие задачи:

- формализация и обобщение понятия криптосистем, данное Шенноном;

единообразное описание вероятностного эксперимента "раскрытие криптограммы" в рамках аксиоматики Колмогорова;

- определение стойкости криптосистем с позиции теории вычислительной сложности с использованием вероятностного пространства, описывающего раскрытие криптограммы;

- получение оценок стойкости некоторых классов практически используемых криптосистем;

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

МЕТОДЫ ИССЛЕДОВАНИЯ. Для решения поставленных задач использован аппарат теории вероятностей, алгебры, теории вычислительной сложности, теории кодов, исправляющих ошибки, комбинаторики, теории конечных геометрий.

НАУЧНАЯ НОВИЗНА. Предложено общее определение крип-тологических структур, в рамках которого дается формальное определение секретных систем Шеннона; дано единообразное определение вероятностного эксперимента "раскрытие криптограммы" в рамках аксиоматики Колмогорова; на основе этого предложен единый подход к получению оценок стойкости криптосистем с позиции теории вычислительной сложности; получены оценки стойкости некоторых практически используемых классов криптологи-ческих структур, таких как блочные шифры и системы защиты сетей, основанные на паролях; на базе некоторых экстремальных кодовых конструкций описан класс систем аутентификации, асимптотически обладающих совершенной аутентичностью.

ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. В работе получены методы, позволяющие оценивать стойкость широкого класса криптосистем с секретным ключом. Теоретические результаты работы могут использоваться при создании новых криптоалгоритмов и анализе стойкости известных. Рассмотрена стратегия проникновения в вычислительную сеть с множеством терминалов и

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

АПРОБАЦИЯ РАБОТЫ. Теоретические и практические результаты работы докладывались и обсуждались на X (1995 г.) и XI (1998 г.) сессии международной Байкальской школы-семинара, на семинаре Иркутского Вычислительного Центра СОР АН, семинаре кафедры алгебры, логики, кибернетики Иркутского Государственного Университета, а также на конференции молодых ученых Иркутской Государственной Экономической Академии.

ПУБЛИКАЦИИ. По теме диссертации опубликовано 6 печатных работ (1-6).

СОДЕРЖАНИЕ РАБОТЫ

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

В ПЕРВОЙ ГЛАВЕ вводится общее определение криптологи-ческих структур, позволяющее получить формальное определение криптосистем с секретным ключом.

Рассматриваются непустые конечные или счетные множества Х,У,2 соответственно открытых текстов, криптограмм и секретных ключей. Скажем, что произошло событие В = {х = х()},

если выбранная некоторым (быть может случайным) образом оценка открытого текста х е X совпала с наперед заданным истинным открытым текстом Хд е X (или просто "открытым текстом"). Кроме того предполагается, что задана некоторая функция /: X х 2 —> У, всякой паре (х, ¿) сопоставляющая элемент у е У, причем определена обратная функция /,2—>Х, любой паре (у,г) сопоставляющая элемент х е X. Событие, состоящее в том,

что для фиксированного у0 б7 и выбранного некоторым (быть может случайным) образом г е2 значение функции g(yo,z) совпало с наперед заданным истинным открытым текстом: х = £(}'о, = , обозначаем далее {х = Хо|_у = . Относительно последнего события будем также говорить, что произошло раскрытие криптограммы у - • Под криптосистемой понимается кортеж

(1)

В более общем виде криптоструктура описывается следующим образом:

{(X,Г,г,у,/,Чу е 7,7*0

Задачей криптоаналитика является нахождение единственного х е X такого, что х = Хо, из условий, заданных набором (1). Однако такую задачу нельзя назвать математически точно сформулированной. Поэтому необходимо ввести некоторые дополнительные условия, делающие постановку задачи корректной. Это делается при помощи введения индикаторов событий В = {х = Хф} . Объект (2) в этом случае превращается в:

| (Х,1о(х)),У^0 здесь (х) представляет собой индикатор события

Б - {х = Х0}. Если такой индикатор есть эффективно-вычислимая функция за количество шагов реалистического вычислительного устройства, ограниченное некоторым полиномом (р -эффективно-вычислимая), то обозначаем его 8{Щ и называем проверкой. Наличие р -эффективно-вычислимого индикатора (проверки) позволяет построить общую процедуру анализа криптосистем. Показано, что такая процедура может быть реализована в виде автомата с конечным числом состояний. В качестве функций перехода автомата из одного состояния в другое выступают

индикаторы событий {тГ 2{ = г0} , где 20—истинный секретный

г,-

ключ (знание которого определяет раскрытие криптограммы), множество: 2^ для которого справедливо:

X = 2 И)... з з ..., то есть, подмножество множест-

ва секретных ключей, соответствующее 2 -тому шагу криптоана-литического автомата А, а г,-—некоторое специальным образом

заданное отношение порядка (вообще говоря, частичного) на .

Следующий шаг — это построение вероятностного пространства, описывающего эксперимент по раскрытию криптограммы с помощью криптоаналитического автомата. Любое возможное (то есть такое, которому сопоставима ненулевая мера) элементарное событие Д- (означающее раскрытие криптограммы на /-том

шаге работы автомата А) имеет место в том и только том случае, когда истинно следующее высказывание

(Ех з Е[) & ЫЕ{ V... V Еы)&£*), где высказывание Е£ истинно тогда и только тогда, когда

тíZi Пусть I — число шагов автомата А до момента Ч

раскрытия криптограммы. Множеству высказываний {Е{ со*

поставляется система интервалов, длины которых обозначаем р1 .

Доказывается, что справедлива следующая теорема. Теорема 1

Для того чтобы события , г е {1,...,1у}, в случае если 1у

неограниченно возрастает, образовывали вероятностное пространство и, вероятность события I),- при этом считалась согласно формуле

Р1 = Р{А) = 0 -Еуи^у)-Р*> Р\ = Р*> (4)

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

*

Игл рI = 1.

/—»со

Далее предлагается общий подход к определению сложности криптосистем. Наиболее естественной мерой сложности криптограммы является среднее ожидаемое число шагов работы криюпгоа-

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

криптоаналитического автомата раскрывающего у, как Мг = Р{ • г—математическое ожидание числа шагов автомата при фиксированной программе и известных вероятностях р^ событий 1)[ (которые целиком определяются набором {р*}\^ )•

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

{А'}/=Г ® качестве меры сложности криптограммы выбирается сложность наилучшей в смысле наименьшего количества шагов (оптимальной) программы криптоаналитического автомата А:

Сотр1(у, Д)= М (5)

где индекс 5 соответствует 5 -тому вероятностному пространству (из $ возможных), описывающему эксперимент по раскрытию криптограммы у автоматом А . Сложность криптосистемы, определяется, как следующая величина:

Сотр1(¥,А) = тГ Сотр1(у,А) (6)

уеУ

Проверкой корректности предложенного подхода стали совершенно-секретные криптосистемы. В теории Шеннона соотношение совершенной секретности

Р{х = х01у = у0} = Р{х = х0} означает, что наличие криптограммы не изменяет вероятности успеха криптоаналитика при ее раскрытии. Применительно к рассмотренному выше подходу данное условие эквивалентно тому, что вероятность раскрытия криптограммы у на произвольном шаге криптоаналитического автомата не должна изменяться и должна оставаться постоянной (то есть, каждый последующий шаг автомата не приближает криптоаналитика к ее раскрытию). Далее показывается, что для некоторого подкласса класса совершенно секретных систем Шеннона это справедливо и их сложность в смысле

I 2 I

выражения (6) есть--, где | Z | -мощность множества ключей

(этот факт в форме недоказанного предположения был высказан еще Шенноном).

Далее на базе понятия сложности криптосистем предложен подход к определению криптостойкости систем с секретным ключом. При этом исходным является следующее очевидное положение: в распоряжении криптографа всегда имеется явно заданная функция I£) (х), в то время как криптоаналитик вынужден ее угадывать, вообще говоря, для каждой криптограммы у е Г; таким образом, криптограф находится в более выгодном положении и, если сложность (б) раскрытия криптосистемы для автомата

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

ВО ВТОРОЙ ГЛАВЕ развивается практическая сторона подхода, описанного в первой главе диссертации. В начале главы дается определение семантичности криптограммы над некоторым языком. Уровень семантичности является тем критерием, согласно которому анализируемая криптограмма может считаться раскрытой. Семантичность представляет собой некоторую аналогию с введенной Шенноном ненадежностью, но шире этого понятия, поскольку не предполагает какого либо специального подхода к неопределенности (энтропии) сообщений.

Определение.

Рассмотрим последовательность экспериментов, заключающихся в раскрытии криптограммы некоторой криптосистемы. Для каждого такого эксперимента предполагаем, что криптограмме у е Г сопоставляется некоторая оценка секретного ключа ге2 и вычисляется соответствующая оценка открытого текста х = g(y,z) 6 Xу . Также полагаем, что в вероятностном пространстве, соответствующем фиксированному эксперименту, задан индикатор I£) (х) события В = {х = х0}, (где х0—истинный открытый текст)—р -эффективно-вычислимая функция. Предположим, что каждый такой эксперимент не учитывает результаты предыдущих. Пусть Р{ —вероятность успеха в г -том эксперименте. Тогда если для каждого эксперимента из данной последовательности существует множество Zг• с: X такое, что:

1 „

11т ~ ¿¿м^*«' = х0 I У = Уое 2х) = 1

скажем, что криптограмма у е Г семантична.

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

Далее ставится и решается задача оценки стойкости (в смысле результатов первой главы) некоторого класса блочных шифров. Блочный шифр описывается следующим образом. Исходный открытый текст—двоичная последовательность длины к делится на блоки длины /. Секретный ключ представляет собой некоторую двоичную последовательность длины к, также разбитую на блоки длины /. Каждый блок (сегмент) ключа есть выход некоторого алгоритма генерации последовательностей длины I. Количество сегментов (блоков) обозначаем т = к П.

Одна из возможных моделей криптоаналитического автомата может быть построена в виде т -ленточной машины Тьюринга Тт, которая анализирует каждый сегмент криптограмы на отдельной ленте. Сопоставим машине Тьюринга Тт множество ее возможных состояний. Данное выше определение семантичности предполагает, что возможен переход из состояния когда известны / компонент ключа в состояние когда известны _/>/ + ! компонент ключа за один шаг работы вычислительного устройства, выполняющего криптоанализ (в данном случае машины Тт).

Таким образом, после того как становятся известны ¡3 компонент секретного ключа, процесс криптоанализа превращается в систему, которая может находиться в одном из не более, чем к — /3 +1 возможных состояний: — ¡3 компонент секретного ключа найдены верно, — /?+1 компонента секретного ключа найдена верно,..., - В— все компоненты секретного ключа

найдены верно.

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

1. Мощность множества шагов автомата А, требуемого на раскрытие произвольного Л +1 -го символа криптограммы длины к при Л известных символах, есть

g¿ где о(к-Л) = /(к) Т(монотонно возрас-

тающая с ростом к ), то есть не ограниченная сверху некоторой константой, не зависящей от к.

2. Если в некотором состоянии Е^ машины Тт становятся

к

известны — символов открытого текста, то

Еj+l = Ек_р = В

Данное допущение задает уровень семантичности криптограммы.

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

состояние Ег (г + 1, к — /3}) зависит только от текущего состояния Е]. Следовательно, в данной трактовке система с состоя-

1с—в

ниями {Е^} представляет собой цепь Маркова с к- (3+1

возможными состояниями. Переходные вероятности марковской цепи, как обычно, обозначаем р (вероятность перехода

Е^ —> Ег ). Из всего вышесказанного следует, что переходные вероятности Ру должны определяться, семантичностью криптограммы.

Основным моментом в дальнейших построениях является то, что переходные вероятности описанной марковской цепи однозначно определяют вероятности е {1,..,/^,} событий, описывающих исходы работы криптоаналитического автомата А, построенного в предыдущей главе.

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

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

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

Обозначим X—множество всех возможных паролей для данной системы защиты: | Х\ = п . Пусть количество входов данной

сети есть т. Обозначим через £)(-,/е{1 ,...,т} событие, заключающееся в том, что попытка проникновения в сеть оказалась удачной на г -том входе. Предположим, что события и Dj при г Ф ] статистически независимы, то есть имеет место Р{В1 = Р{Д } . Событие, заключающееся в том, что попытка проникновения оказалась удачной хотя бы на одном входе, обозначим 25.

Далее предложен алгоритм разбиения множества X на т классов Х\ ,...,Хт — Хо. При таком разбиении вероятность события, состоящего в том, что любые два пароля из указанного множества принадлежат различным классам Xмала и, следовательно, среди множества классов X,- почти наверное есть пустые, это есть следствие т.н. задачи "парадоксов дней рождения". С

другой стороны, при т = о{4ш) всем выбранным паролям с вероятностью близкой к 1 соответствуют различные натуральные номера.

Скажем, что класс Х{ находится на своем месте, если он

содержит пароль лтд (изначально заданный истинный пароль, соответствующий / -тому входу).

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

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

оценки вероятности Р представляет собой усложненный вариант задачи о совпадениях. При ее решении также используется еще одна классическая вероятностная задача — задача о случайном

размещении частиц по ячейкам. Окончательная оценка снизу веро-* *

ятности Р следующая: Р > 0,329.

С учетом V/ е 1,...,т => [п/тп\ <[Хг-|<]п / т[ получим, что вероятность проникновения в сеть при описанной стратегии есть:

Р> 0,329- — . п

В ТРЕТЬЕЙ ГЛАВЕ диссертации рассматривается проблема построения систем аутентификации, обладающих совершенной аутентичностью, при этом не рассматриваются рандомизированные шифры.

Совершенная аутентичность определяется равенством в границе Симмонса:

1о %Ра>-1{у,г), (7)

здесь Р1— вероятность успешной имитации, Р$—вероятность успешной подмены, Р^ =тж.{Р1 ,Р$}—вероятность обмана, 1{у\г) — Н{у) — Н{г\у), где Н{у)—энтропия Шеннона произвольной криптограммы у е У. Далее Ху, У2 означают, соответственно множество допустимых ключей при заданной криптограмме и множество допустимых криптограмм при заданном ключе.

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

Z = Zn <j....KjZym , Zy. n Zy. = 0,Vi,7 e {1 ,...,m =|11}:i * j

Доказана следующая теорема.

Теорема 3

Рассмотрим систему аутентификации, определяемую тройкой множеств X,Y,Z и преобразованием f. Если X образует линейный [и, к\ -код, множества допустимых секретных ключей пс всем криптограммам у е Y представляют собой смежные классь по коду X, а шифрующее преобразование f есть сложение соответствующих двоичных последовательностей по mod2, то наилучшая защита от попыток имитации достигается если X есть линейный (п, к, d) -код с минимальным кодовым расстоянием d, достигающий нижней границы Варшамова-Гилберта.

Следующим шагом является использование для построение систем аутентификации, не одного кода, а некоторого множеств* кодов с одинаковыми параметрами. Предположим, что в распоряжении отправителя и получателя имеется не один код, а некоторое семейство неизоморфных кодов Ф с одинаковыми параметрами (n,k,d). Затем отправитель наудачу выбирает некоторый ко; Xj б Ф и формирует криптограмму таким образом, что получатель, зная секретный ключ, однозначно восстанавливает принадлежность открытого текста коду Xi.

В результате предложен подход построения систем аутентификации на основе семейств непересекающихся кодов с одинаковыми параметрами, показано, что = 1 / | Ф |, где | Ф | означает мощность семейства кодов Ф.

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

Теорема 4

Предположим, что можно указать такие последовательности значений kj,tij, что при i — 1,2,... (для каждого rij) пространстве Vn. пред ставимо в виде объединения семейств непересекающихся

* *

кодов: Уп = (Ф)^...иФ/). Все коды семейств

*

Фу ,1 < у < / являются линейными (;?,• ,¿>у) -кодами, где для произвольного l<j<l=>Sj<d¡ и каждое семейство содержит т! кодов, а семейство Фп. образовано тп. непересекающимися , ) кодами, причем имеет место:

. — 1 уй,- ч

Тогда семейство Фп. образовано кодами достигающими границы

Варшамова—Гилберта.

Основным результатом третьей главы является приведенная ниже теорема. Теорема 5

Если при = //, = к, п > 2 • к и таком, что Х-(Ипк\12 существует семейство кодов Фп, с этими параметрами, описанное в теореме 4, то существует система аутентификации на основе множества кодов Ф = Ф/7., асимптотически

обладающая совершенной аутентичностью, то есть в границе Симмонса для такой системы достигается асимптотическое равенство (при п —> оо).

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

(8)

Соотношение (8) носит название границы Варшамова-Грайсмера (в других источниках—границы Грайсмера), а выражение, стоящее в правой части (8) обозначают g(k,d). Линейные коды, для которых в (8) достигается равенство называют кодами, достигающими границы Варшамова-Грайсмера.

Пусть Ск — порождающая матрица двоичного симплексного кода с параметрами

(2к -\,к,2к~х). Столбцы матрицы Ск образуют векторное пространство Ук размерности к над полем СЕ(2).

Отбросим из матрицы С/, блок столбцов = | ^ |... | , где — набор столбцов матрицы , образующий линейное векторное подпространство пространства Ук размерности г/,. Если матрица = \ является порождающей матрицей линейного кода, то этот код характеризуется параметрами

((2* -1) - 1Г=1 (2й' -1)Д2*"1 - ТР=12й'"1)

и достигает границы Грайсмера. Описанная процедура носит название процедуры Соломона-Штиффлера, матрица ^ называется порождающей матрицей антикода кода порожденого матрицей

Поскольку матрица оказывается разбитой на непересекающиеся множества, то пара , ) структурно представляет

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

Теорема 6

Если существует код Соломона-Штиффлера с параметрами к,с1),к,с1), такой, что для V/ е {1,...,/>-1} => = иу+1 и такой код единствен с точностью до автоморфизма, то для произвольного вектор-столбца V е и произвольного вектор-столбца хн. е £„.:/'е {1,...,/?-1} вектор V Ф хи. является вектор-столбцом матрицы .

Таким образом, для произвольного вектора V е некоторое подмножество столбцов порождающей матрицы Ск кода, описанного в условии теоремы 6, разбивается на непересекающиеся подмножества ,...,Ти, где Ти, -- V ф .

На базе структуры далее строится система аутен-

тификации с вероятностью обмана Р^ = 1 ¡(р -1).

В ПРИЛОЖЕНИИ приводится алгоритм семантического разу-порядочения сообщений над конечными алфавитами. В настоящее время общепринятым считается следующий стандарт секретной передачи данных. Ключ или управляющая последовательность передается при помощи некоторого несимметричного криптоалгоритма (например, RSA), а само сообщение при помощи симметричного алгоритма (типа DES). Такое положение вещей объясняется тем, что несимметричные алгоритмы отличаются крайне низкой скоростью работы и не могут использоваться для передачи больших сообщений. Между тем еще Шеннон говорил о том, что для сообщений с минимальной избыточностью статистический (семантический) анализ криптограммы невозможен (поскольку все исходы такого анализа равновероятны), согласно этому тезису всякое сообщение перед шифрованием предварительно сжимается некоторым алгоритмом сжатия (удаления избыточности). Но выход такого алгоритма не является той идеальной криптограммой, о которой говорил Шеннон, поскольку распадается на множество двоичных префиксов, соответствующих буквам исходного алфавита.

Предлагаемый алгоритм основан на разбиении множества

натуральных чисел {l,...,2s -1} на циклотомические классы по модулю 2S -1, и соответствии этому множеству векторного представления поля GF(2S). Алгоритм используется для семантического разупорядочения сообщения, то есть для преобразования сообщения в двоичный код по которому невозможно без знания малой управляющей информации на основании статистического анализа восстановить исходное сообщение. В качестве управляющей информации, передаваемой при помощи несимметричного криптоалгоритма может быть выбрана последовательность первых элементов циклотомических классов.

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

1. Предложен общий подход к получению оценок стойкости криптосистем с секретным ключом посредством описания вычислительного устройства, раскрывающего криптограмму (криптоанали-гического автомата) и, сопоставления процессу "раскрытие криптограммы".

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

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

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

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

По теме диссертации опубликованы следующие статьи:

1. Семенов А. А. О существовании некоторых линейных кодов размерности 3 над ОР(ф, q>4, достигающих границы Грайсмера // Компьютерная логика, алгебра, и интеллектное управление, сб. трудов Всероссийской школы т.4 С. 215-229, Иркутск 1995.

2. Семенов А. А. Справедливость гипотезы о кодах с максимально-достижимым расстоянием над СР(с|) для некоторых новых значений q // Методы оптимизации и их приложения, 10-я Байкальская школа-семинар, тез. докл. С. 120-121 Иркутск 1995.

3. Семенов А. А. О линейных кодах над СР(д), достигающих границы Грайсмера // Функционирование региональных рынков: поиски, проблемы, решения, тез. докл. Международного симпозиума, Иркутск 1995.

4. Семенов А. А. К вопросу нестойкости некоторых криптосистем // материалы городской конференции молодых ученых, тез. докл. С. 43-44. ИГЭА. Иркутск 1998.

5. Семенов А. А. О существовании нестатистических алгоритмов сжатия дискретных данных // Методы оптимизации и их приложения, труды 11 Международной Байкальской школы-семинара, т.З, С. 170-174, Иркутск, 1998.

6. Семенов А. А. Вычислительная сложность криптосистем с секретным ключом // препринт, изд. ИГЭА, Иркутск 1998, 33 с.

Р№ 020262 от 10.11.96

одписано в печать 30.10.98. Формат 60x90 1/16. Бумага офсетная, ечать офсетная. Усл. печ. л. 1. Тираж 100 экз. Заказ 22. УОП ИГЭА

здательство Иркутской государственной экономической академии 664015, Иркутск, ул. Ленина, 11

СЕМЕНОВ АЛЕКСАНДР АНАТОЛЬЕВИЧ

ОЦЕНКИ СТОЙКОСТИ СИСТЕМ ЗАЩИТЫ ДИСКРЕТНЫХ ДАННЫХ

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

научных исследованиях

Диссертация на соискание ученой степени кандидата технических наук

Научные руководители: д.-р. ф.м.н. МоскаленкоА.И. к.ф.м.н. Логачев В.Н.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................3

ГЛАВА I. Теоретико-вероятностное описание анализа криптограммы... ..14 1.1. Общая постановка задачи анализа криптоструктур................. 14

1.1.1. Индикаторы событий, описывающих анализ криптограммы............................................................16

1.1.2. Криптологические структуры.................................20

1.1.3. Криптоаналитические автоматы............... ...............21

1.2.4. Подход к определению стойкости криптосистем..........38

ILL Общий подход к оценке стойкости блочных шифров.............41

II.1 Л. О понятии семантичности криптограммы.................41

III.2. Постановка задачи криптоанализа для двоичной криптосистемы с коротким псевдослучайным ключом......... 44

11.1.3. Два подхода к анализу криптосистем

класса Ащ (2, к, Тт ib...................................................... .47

11.2. Анализ стойкости криптоструктур класса (X,S(D)) с

III. 1. Анализ возможности имитации..............................71

111. 2. Анализ возможности подмены...............................73

III. 3. Примеры построения систем аутентификации и возникающие в связи с этим комбинаторные задачи............77

111. 4. Оценки аутентичности систем, образованных семействами кодов...................................................... 85

III. 5. Системы аутентификации на основе других

Г

ПРИЛОЖЕНИЕ.........................................................................98

' ЗАКЛЮЧЕНИЕ........................................................................102

ЛИТЕРАТУРА.........................................................................ЛОЗ

ВВЕДЕНИЕ

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

Всю историю криптолоши принято делить (согласно замечанию Дж. Л. Месси) на два этапа. Первый, донаучный — с глубокой древности и до 1949г.. Второй, научный — с 1949г. и по сей день. Такой подход продиктован тем, что в 1949г. вышла работа К. Э. Шеннона "Теория связи в секретных системах" [1], которая остается наиболее значимой работой по теории криптосистем с секретным ключом. За, почти полвека, прошедших с момента ее публикации по данной тематике вышло (в открытой печати) незначительное количество статей (см., например, работы [14], [19], [20]), содержащих результаты, сопоставимые по своей значимости с результатами упомянутой работы Шеннона.

Остановимся подробнее на некоторых основных моментах этой работы.

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

Опишем теперь модель секретной системы Шеннона математически, следуя работе Дж. Л. Месси (см. [3]).

Базовыми объектами являются множества Х,У,2 соответственно открытых текстов, криптограмм и секретных ключей. Элементы этих множеств— следующие векторы:

* = (*Ь*2>->*#(х))> У= (УъУ2>->УМ(у))> 2 = •

Компоненты векторов могут выбираться из некоторых алфавитов, объемы которых есть соответственно Ь{х\Ь(у),Ь{£) (на практике чаще всего компоненты любого из векторов выбираются из {0,1}). Шифрующее и дешифрующее преобразования записываются в следующем виде:

у = Ех(х),х = В2(у),

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

Фиксированные элементы множеств Х,У,2 далее будем обозначать верхним нулевым индексом. Предполагается, что криптоаналитику доступны множества X, У,2, преобразования Е2,В2 и криптограмма у0. Не известны ему лишь истинныи открытый текст х и истинныи секретный ключ 2°. Таким образом, при известной криптограмме стойкость криптосистемы определяется только секретностью ключа (правило Керкхоффа).

Событие {х = х0} состоит в том, что выбранный криптоаналитиком элемент хеХ (оценка истинного открытого текста), при условии, что ему

у = у° совпадет с х°. Вероятность этого

— Р{х = х°|_у = j0} Шеннон и определяет как меру раскрываемости крип-

9 N

о том, что кри:

теоретической или практической криптостойкостью. Теоретически стойкие криптосистемы (по Шеннону) — это криптосистемы, для раскрытия

называемые совершенно-секретные системы. Согласно подходу Шеннона, совершенная секретность определяется следующим условием:

р{х = х° \у = у°} = Р{х = х0},

то есть вероятность раскрытия криптограммы 3;° равна вероятности нахождения истинного открытого текста криптоаналитиком при неизвест-

"выбор истинного открытого текста из X" равна его апостериорной вероятности. Далее Шенноном было показано, что такие криптосистемы ре=

стема Вернама. В этой криптосистеме элементы множеств Х,У,2 представляют собой двоичные векторы одинаковой длины и каждый бит от-

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

Для получения соотношений, связывающих длину секретного ключа с длиной открытого текста, Шеннон использует понятие информационн-ной энтропии, введенное им годом раньше в работе "Математическая теория связи" (1948 г.) (см. [2]). Энтропия системы 9? с п состояниями, в каждое из которых она переходит с вероятностями #, / е {!,...,»} есть

Н(Ш) = ^"Рг log—, '-1 Pi

здесь log—логарифм по основанию 2. В применении к криптологии, например, если для криптоаналитика все открытые тексты из некоторого

$ ^ 1

X с! равновероятны и Vz е{1,...,[Х |}=>рг- =—г-, то энтропия (неопре-

\Х I

из X есть

1 'log|X*|= log|X*|, если X* = X и X-

\x*\

можных двоичных последовательностей длины к, то Н(х) = к .

H(z) > Н(х),

В случае, когда L(x) = L(z), получаем:

N{z) > N(x).

Вывод, следующий из последнего неравенства: для совершенно-секретных систем при L(x) = L(z) необходимо чтобы длина секретного

Очевидно, что 1фиптоеиетемы, для которых выполняется (1) и, в ча= стности, криптосистемы Вернама (для которых в (1) достигается равенство) не являются практически выгодными, поскольку требуют передачи по

Осознавая, что на практике все равно придется использовать кришго-системы, в которых совершенно случайная "часть" ключа короче открытого текста, Шеннон вводит понятие ненадежности ключа.

/(и)— это неопределенность (энтропия) ключа при п известных знаках криптограммы. Число п такое, что /(л)«О Шеннон назвал расстоянием единственности и заметил, что имея в распоряжении и знаков шифртек-ста, криптоаналитик раскрывает криптограмму, однако, в общем случае, для этого он должен обладать неограниченными вычислительными ресурсами. Далее предпринято исследование на предмет ненадежности некото-

криптостойкости техникой, предложенной Шенноном, применительно к практически используемым криптосистемам представляется весьма непростым (это косвенно отмечено в работе [3] и в примечании редакторов жош перевода работы [1]).

Придя к таким выводам, Шеннон вводит понятие практической крип-

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

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

Особый интерес представляет значение W{ri), когда п неограниченно возрастает. По поводу получения оценок величины W{ri) можно процитировать Дж. Л. Месси (см. [3]): "На сегодняшний день не известно (по крайней мере специалистам, занятым открытыми работами) ни одной практической криптосистемы, для которой была бы определена сколько-нибудь содержательная нижняя граница W(°o) „"

Часть работы [1], посвященная изучению оценок величины W(ri) носит, в основном, эмпирический характер, хотя здесь впервые Шеннон неявно вводит понятие индикатора события "выбранная оценка совпала с наперед заданным открытым текстом'5. Об этом говорят следующие цитаты: "Хотя в принципе всегда можно найти эти решения (Например, испытывая все возможные ключи), но для различных систем нужно будет затратить весьма различный объем работы." и "Предположим далее, давая противнику все возможные преимущества, что он сконструировал электронное устройство для испытания ключей со скоростью один ключ в одну мксек (скажем, с помощью автоматического выбора и проверки с помощью критерия значимости %2). Можно ожидать, что он выберет правильный ключ примерно после половины всех возможных испытаний..."

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

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

но осознано и в соответствии с текущим моментом, поскольку Шеннон отмечает: "... в применении к физическим ситуациям, особенно когда дело касается "субъективных" вероятностей и неповторимых экспериментов, возникают многочисленные вопросы, связанные с логическим обоснованием. Например, при нашем подходе к проблеме секретности допускается, что априорные вероятности различных ключей и сообщений известны шифровальщику, но как он может определить их даже при использовании всех своих сведений о данной обстановке? " Еще одна цитата также объясняет, почему Шеннон не использовал строгого аксиоматического описания вероятностной картины эксперимента, а предпочел более технический подход: "...в других случаях, которые можно себе представить, например, при перехвате сообщений, передаваемых между собой марсианами, высадившимися на землю, априорные вероятности были бы настолько неопределенными, что не имели бы никакого значения. "

В последнее время, особенно с развитием информационных технологий, появились объекты, представляющие собой секретные системы (в несколько ином смысле, чем в определении Шеннона), в которых крип-тоаналитик (противник) может эффективно получать ответ на вопрос: "является ли найденная им оценка открытого текста собственно заданным наперед открытым текстом? " Допуская некоторую нестрогость, отметим, что примером таких секретных систем являются системы защиты, основанные на пароле: вводя некоторую оценку заданного наперед пароля, противник эффективно получает ответ "да" или "нет". Строгое описание подобных секретных систем дается в первой главе диссертации.

Г II 1 ^^ ^ _______!»_« ^

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

ределений Шеннона теоретической и практической стойкости, а также предлагается общая идея получения оценок стойкости криптосистем с секретным ключом, то есть оценок величины W(n).

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

66 99

задачи, как задача парадокса дней рождения и задача о размещении частиц по ячейкам).

Наиболее новым направлением в криптологии считается теория аутентификации. И хотя оригинальной статьей по этому вопросу правильнее считать работу [21], "творцом53 теории аутентификации признан Г. Дж. Симмонс, а основополагающей—его работа "Authentication theory/Coding theory55 (см. [15]). Не смотря на то, что теория аутентификации, по меньше мере, на 25 лет "моложе55 теории секретных систем Шеннона, количество публикаций по вопросам аутентификации сообщений намного превосходит число публикаций по теории секретных систем и продолжает расти, (см., например, [22]- [43])

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

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

шифратор криптоаналитик дешифратор получатель

-(Ы

1з

лирует секретный канал.

следует, что криптоаналитик он, как и в

в данном случае для него не проще, чем в случае схемы Шеннона. Одна-

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

тиком, за подлинную ет с истинной).

(даже если впоследствии окажется, что стратегия—стратегия подмены. В истинную криптограмму и

поддельную, которую ной, если получатель.

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

Р7, а

служит вероятность обмана Р4 = тах{/>7,/>5}.

по

сообщения из некоторого

тель ожидав/

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

обман (в �