Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

271

На первом этапе случайно выбирается начальный вектор у0 и вычисляе­ тсязначение р(Г(у°) ® а), равное числу несовпадений значений вектора Г(у°) с правой частью системы уравнений и называемое уровнем вершины. Далее рас­ сматриваются все вектора у°(1), у°(2),...,у°(п), отличающиеся от у0 одной коор­ динатой, вычисляются их уровни и в качестве у1выбирается вершина минима­ льного уровня. Далее повторяется первый этап с заменой у0 на у1.

Процедура продолжается до возникновения ситуации, когда у -у н1. В этом случае, как говорят, мы пришли в локальный минимум поверхности уров­ ней вершин.

При попадании в локальный минимум производится анализ полученно­ го значения у*. Если по принятым критериям найденный вариант признается решением, то на этом процедура поиска заканчивается. В противном случае случайно выбирается новая начальная точка у0 и алгоритм повторяется.

Таким образом, метод координатного спуска заключается в выборе на­ чального значения переменных, переборе всех соседних с ним элементов и движении по направлению снижения уровня. Отсюда следует и название «ме­ тод координатного спуска».

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

Удачно подобранные примеры применения статистических методов криптоанализа и расчета их трудоемкости содержатся в книге Грушо А.А., Тимонйной Е.Е., Применко Э.А. «Анализ и синтез криптоалгоритмов», 2000, 108 стр. Для изучения методов криптоанализа, созданных на основе теории ста­ тистических решений, рекомендуем книгу /25/.

Параграф 5.5 Введение в теорию случайных систем уравнений

Материалы данного параграфа базируются на статье Г.В. Балакина «Введение в теорию случайных систем уравнений» Труды по дискретной математике. Том 1, стр. 1-18 (Под ред. В. Н. Сачкова и др.) Научное издательство «ТВП», 1997 г.

1.Примеры случайных систем уравнений.

Впараграфе рассматриваются системы уравнений

/ 1(х1,...,хя) = а„ 1 = 1,...,1.,

(1)

272

в которых

X,. еА /\ |АГ| = д, а,. е М , 1 = 1,...,/,

N ,М - некоторые множества, например, N = {0,1,...,</ - 1},М = {0 ,1 ,...,т -1}. Каждая функция, задает отображение Ы" ъ М .

Если система (1) рассматривается над конечным полем СГ(д), то т = <7 и

элементы поля для удобства будем отождествлять с наименьшими неотрицательными вычетами по модулю <7. При т = ц = 2 система (1)

называется булевой. Особое промежуточное положение занимают так

называемые псевдобулевы системы, для которых неизвестные		,...,хп булевы,
т. е. принимают только два значения 0 и 1 , а функции /	,	задают

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

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

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

Конечные автоматы, «черный ящик». В этом случае системой (!) задается функционирование автомата. Входом являются неизвестные л:, ,...,хп>

выходом - правая часть а 1,...,а1 (Как правило, все функции / , одинаковы и отличаются друг от друга только выбором аргументов. Например, если функция ? = (1 = 1,...,1) принадлежит некоторому множеству

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

273

возникает сложная задача определения закона функционирования автомата (проблема «черного ящика»)

Передача сигналов по каналу связи. Пусть сигнал х, ,...,хп кодируется

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

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

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

Классификация ираспознавание образов. Очевидно, что задача решения системы уравнений (1) сводится к задаче классификации (распознавания)

неизвестных х, , т. е. к определению множеств неизвестных,

принимающих заданное значение $ еМ ,$ = О,...,# —1. Если решение исходной системы единственное, то и решение задачи классификации тоже единственное. На систему уравнений (1) можно посмотреть и с другой

стороны. Каждая функция из / , характеризует некоторые свойства

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

(неизвестных х, ).

Для простейшего случая, когда / к( х ) = /{х ^ ,х^ ), системе (1) * ставится в соответствие ориентированный граф по следующему правилу: вершина х^ соединяется с вершиной х^ дугой ик веса

\{ик ) = ак = / ( х 1 >*/ ) • Функция /( х , ,х] ) может характеризовать близость

по какому-то свойству между объектами х(. и х ., например, расстояние между

ними. Здесь возникает много интересных задач по изучению различных характеристик графов.

Линейный случайный код. Рассмотрим случайный код, реализации которого представляют собой линейный код над СР(^). В этом случае кодирующая матрица А кода есть случайная матрица, х = ( х 1,...,хп) есть

274

входное слово, а = ( а 1,...,а1) есть кодовое слово, л:п а. еСГ(д),

/ = 1 , . у = 1 >

п . Входное слово преобразуется в кодовое слово с

помощью матрицы А :

хА = а

Эта система является (в силу случайности матрицы А ) случайной системой линейных уравнений над СГ(д).

2. Классификация систем уравнений.

Вначале выделим важный класс случайных систем уравнений. В общем случае случайная система уравнений

<Р,(хп...,хп) = С,.

* = 1

,

.

(2)

по некоторому вероятностному закону выбирается из некоторой совокупности

систем уравнений П. Здесь под элементарным событием й> = (/д ),< оеП м ы

подразумеваем конкретную реализацию системы уравнений (2)

{р = (<РХ, - , 9 , ) = / = ( 7 1 ) . с = (с,

):= а = ( а , а , )}.

Каждому элементарному событию со приписывается вероятность

р(<у)>0, ^ р ( й ) ) = 1 .

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

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

I
М = П а ( ® / )>	= ( 7 а ),<о = Ц	),
/=1

275

где р { — вероятностная мера на множестве возможных реализации /-го уравнения системы.

Классификацию систем уравнений можно проводить по трем параметрам:

1)характер зависимости правых и левых частей в системе;

2)алгебраический вид левых частей;

3)способ задания правых частей.

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

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

Определение 2.2. Система (2) называется случайной системой уравнений

с независимыми частями, если ее левая часть (р —{<рх		) не зависит от
правой части с = {сх	)

По сути дела, введенные в определениях 2.1 и 2.2 понятия относятся не столько к вероятностной структуре случайной системы, сколько к форме ее записи. Например, в любой системе можно перенести правые части в левые,4 сделав ее полуслучайной.

Для случайной системы уравнений с независимыми частями выполняется равенство

р{со) = }>(/)р(а), со = ( /,а ) е П

где 7 и р - вероятностные меры на множествах значений левой и правой частей случайной системы уравнений, соответственно. Заметим, что случайная система может оказаться полуслучайной, если р{со) = / ( / ) или

р{а)) = р (а ).

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

276

уравнений, лишь иногда оговаривая особенности рассматриваемых систем. Обозначим В,( число решений случайной системы из ( уравнений.

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

уравнений следующего вида:
	/,(х ) = а„ а,. = /.(х ° ) 1 = 1,...,1,	(3)
где х° = (х®	) есть некоторый вектор, называемый обычно истинным

решением. Эта система отличается от системы (2) тем, что правые части системы (3) всегда (при любом числе уравнений) удовлетворяют условиям

а 1 = (х° ),/ > 1. Вероятность того, что случайная система с независимыми

частями (2) несовместна, как правило, стремится к 1 при ^ >со.

Определение 2.3. Система уравнений (2) называется заведомо совместной случайной системой уравнений, если

(4)

Таким образом, истинное решение х° удовлетворяет системе (3) при любом ее расширении (добавление уравнений). Ложное решение может не удовлетворить некоторому уравнению при расширении системы. Как правило, будем считать, что система допускает только одно истинное решение, другие случаи будут особо оговариваться. Обозначим через г\( число решений

заведомо совместной случайной системы из I уравнений. Очевидно, что Г]1> 1.

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

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

277
При случайном выборе функций /	, и истинного решения х°

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

а,=- //(*°) 1 = I

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

у;.(х°)=а,, 1 = 1,...,*.

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

В заключение кратко скажем о наиболее типичных способах задания правых частей в системах уравнений. Системы могут иметь точно известную правую часть, правую часть, известную в вариантах, и искаженную правую часть. Заметим, что для заведомо совместной системы уравнений ее истинная правая часть обязательно содержится среди возможных вариантов правых частей, а при наличии искажений система может оказаться несовместной. В последнем случае иногда в правую часть вводят так называемые мешающие параметры (см. Балакин Г. В. Системы уравнений с мешающими параметрами. -В сб.: Всероссийская школа-коллоквиум по стохастическим методам геометрии и анализа. Тезисы докладов. М.: ТВП, 1994, с. 11-12), характеризующие искажения, и система уравнений остается заведомо совместной, т. е. имеет истинное решение х° при некоторых истинных значениях мешающих параметров (искажений).

/

278

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

3. Задачи анализа систем уравнений.

Основная задача для случайных систем - определить или оценить величину Р{^, > О} - вероятность совместности системы. Представляют интерес также среднее число решений и структура множества решений. Более сложная задача - найти распределение числа решений ^ . Ясно, что последняя задача содержит в себе нахождение вероятности совместности и среднего числа решений.

Зная функциональную зависимость среднего числа решений случайной системы от числа уравнений, нетрудно оценить так называемый «порог единственности» - минимальное число уравнений 10, при котором среднее число решений случайной системы не превосходит 1:

• Е ^ ,о <1, Е ^ _ , > 1 .

Очень важно для случайной системы оценить момент I* - «порог несовместности», когда система становится несовместной:

$■=<>.

Найти распределение этого момента /*, как правило, очень трудно. Для линейных систем над полем СР(#) он связан с появлением линейных зависимостей между строками матрицы системы.

При изучении заведомо совместных систем основная задача - найти распределение числа решений и структуру множества решений. Более простыми задачами могут оказаться оценка среднего числа решений и вероятностных характеристик числа уравнений, при котором заведомо совместная система с заданной вероятностью имеет только одно решение. Для линейных заведомо совместных систем над полем СР(#) с матрицей А(

распределение числа решений определяется рангом г(Лг) случайной матрицы

А

Р к = « " г,<))=1. Р { < 7 , = 1 } = Р И 4 ) = и }

279

По аналогии со случайными системами определим «порог единственности» для заведомо совместной системы равенством

(0 = тш{* :Е(т7, - 1 )< 1,Е(/7м -1 ) > 1},

т. е. /0 - минимальное число уравнений, при котором среднее число ложных решений заведомо совместной системы не превосходит 1 ;

'Г = т т { ^ 7 ,_ , >2,7, =1},

т.е. I* - минимальное число уравнений, при котором заведомо совместная система имеет единственное решение. Ложные решения при

I> I*отсутствуют.

Предположим, что во всех I уравнениях заведомо совместной системы

левые части не зависят от V, неизвестных. Тогда очевидно, что в заведомо

совместной системе 7, > . Здесь возникает, как правило, комбинаторная

задача нахождения распределения случайной величины V,. Например, оценка такого момента I, что у,_, > 0 , а V, = 0 .

Очень существенным моментом для заведомо совместной системы является изучение структуры множества возможных решений, связи ложных решений с истинным решением. Например, если с вероятностью, стремящейся к 1 при I, п —» оо, ложные решения отличаются от истинного решения х не

более чем к(п) координатами, к{п) = о(п), то первое же найденное решение

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

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

4. Сравнение случайных систем с независимыми частями и заведомо совместных случайных систем уравнений.

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

г

280

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

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

Рассмотрим связь между распределениями числа решений Е, случайной системы уравнений с независимыми частями и числа решений 1} заведомо совместной случайной системы.

Согласованные системы уравнений.

Пусть в системе уравнений

<р1(х) = с„ 1 = 1,...,*,

(5)

функции срх,...,ср1 задающие отображение ТУ" в М , по каким-то вероятностным законам выбираются из некоторых множеств функций Ф Ф , , соответственно, неизвестный вектор х может принимать <7"

возможных значений Зс(1),...,х(^"), а значения с,,...,с, правой части в одном

случае по некоторому вероятностному закону независимо от левой части

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

х = х(]). Распределения левых частей в обоих случаях одинаковы.

Обозначим множество возможных реализаций случайных систем уравнений с независимыми частями символом О, подразумевая под элементарным событием со = ( / , я ), соеО конкретную систему уравнений (5) с

9 = 7 - (/х	\ с = а = ( а х	).
Пусть, далее, О, - множество реализаций случайной системы (5),
которым удовлетворяет значение х = х(/), / =			; Г20 - множество

несовместных систем уравнений; р{со) = ]}(/)р (а ) есть вероятность