Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 138-149

1. ВВЕДЕНИЕ

1.1. Введение в проблему

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

Подобные нарушения могут привести к случаям [1–3, 20, 21]:

$ \bullet $ уменьшения мощности алфавита ключа или неравновероятного распределения символов ключа (при применении шифра гаммирования);

$ \bullet $ утечкам информации о символах исходного сообщения;

$ \bullet $ повторного использования ключа шифрования.

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

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

Такой подход может привести к потере истинного варианта восстановления, вероятность которой оценивается исходя из введенной теоретико-вероятностной модели исследуемого процесса [6–8]. С увеличением количества значений на выходе канала связи восстановление исходного текста становится затруднительным из-за высокой степени неопределенности выбора осмысленного текста, возникающей в процессе поиска подходящих вариантов. То есть трудность состоит в выборе истинного исходного текста среди большого количества восстановленных осмысленных текстов.

Степень неоднозначности восстановления $r$ – это математическое ожидание числа возможных осмысленных текстов, которые могут быть получены путем применения алгоритма восстановления [2]. Значение $r$ зависит от длины текста $s$ и позволяет оценить эффективность восстановления исходного текста. Цель процедуры восстановления – получить подлинный осмысленный текст.

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

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

1.2. Постановка задачи

Пусть при передаче знаков входного сообщения ${{x}_{1}},...,{{x}_{N}}$, выбираемых из алфавита A мощностью m, на выходе канала связи наблюдаются множества символов различной длины ${{\{ {{x}_{i}}\} }_{{{{l}_{i}}}}}$ = = $(x_{i}^{{(1)}},...,x_{i}^{{({{l}_{i}})}})$, $x_{i}^{{(j)}} \in A$ $\forall i = 1,...,N$, j = $1,...,{{l}_{i}}$. Значения величин ${{l}_{i}}$ предполагаются таковыми, что полное восстановление сообщения невозможно. При этом задача состоит в поиске участков сообщения длиной $s$ символов с относительно небольшими значениями ${{l}_{i}}$ и попытках восстановить на них отдельные части передаваемого сообщения. В рамках определенной теоретико-вероятностной модели появления наборов ${{\{ {{x}_{i}}\} }_{{{{l}_{i}}}}}$ и моделей словарей требуется оценить среднюю долю восстановленного текста исходного сообщения.

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ КАНАЛА СВЯЗИ

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

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

Рассмотрим соответствующий дискретный канал связи без памяти [9, 10]. Пусть в качестве входного и выходного конечных алфавитов выступает множество символов A (${\text{|}}A{\text{|}} = m < \infty $). Каждому i‑му входному символу сообщения ${{x}_{i}}$ соответствует множество ${{\{ {{x}_{i}}\} }_{{{{l}_{i}}}}}$ значений мощностью ${{l}_{i}}$.

Зададим вероятности $p_{k}^{{(i)}} = P({{l}_{i}} = k)$ появления на выходе множества ${{\{ {{x}_{i}}\} }_{k}}$, состоящего из k значений; $k = 1,...,m$; $\sum\limits_{k = 1}^m {p_{k}^{{(i)}} = 1} $.

Далее определим, что состав множества значений ${{\{ {{x}_{i}}\} }_{k}}$ для каждого входного символа образуется случайным и равновероятным выбором из всех упорядоченных последовательностей длины k, построенных без повторения знаков в исходном алфавите.

Таким образом, модель канала определяется:

$ \bullet $ алфавитом $A$ кодовых символов на входе и выходе мощностью m;

$ \bullet $ множеством входных сообщений $X$ длиной $N$ символов, где $x = ({{x}_{1}},{{x}_{2}},...,{{x}_{N}}) \in X$ является входным сообщением, ${{x}_{i}} \in A$, $\forall i = 1,...,N$;

$ \bullet $ множеством значений выходных символов $(\{ {{x}_{1}}{{\} }_{{{{l}_{1}}}}},\{ {{x}_{2}}{{\} }_{{{{l}_{2}}}}},...,{{\{ {{x}_{N}}\} }_{{{{l}_{N}}}}})$, где ${{l}_{i}}$ – мощность множества ${{\{ {{x}_{i}}\} }_{{{{l}_{i}}}}}$, $\forall i = 1,...,N$;

$ \bullet $ вероятностями $p_{k}^{{(i)}}$ появления выходных множеств ${{\{ {{x}_{i}}\} }_{k}}$ для $k = 1,...,m$, при этом состав множества ${{\{ {{x}_{i}}\} }_{k}}$ образуется путем выбора каждого знака из алфавита A по урновой схеме без возвращения, $\forall i = 1,...,N$.

Далее предлагается алгоритм восстановления отдельных частей неизвестного сообщения, передаваемого в данном канале связи, и рассматривается случай фиксированного произвольного вероятностного распределения $p_{k}^{{(i)}} = {{p}_{k}}$ в канале связи для всех $i = 1,...,N.$

3. ОПИСАНИЕ АЛГОРИТМА

3.1. Об s-граммах сообщения

Для реализации алгоритма восстановления сообщение разделяется на отдельные $s$-граммы. Под $s$-граммой понимается последовательность из $s$ символов текста, которые выбираются “с зацеплением”, т.е. для каждой следующей $s$-граммы осуществляется сдвиг вправо на один символ.

Номер $s$-граммы в сообщении определяется по порядковому номеру ее первого символа. То есть $i$-я $s$-грамма обозначается как $({{x}_{i}},{{x}_{{i + 1}}},...,{{x}_{{i + s - 1}}})$. При рассмотрении отдельной $s$-граммы вводится внутренняя нумерация ее символов. Например, для i-й $s$-граммы: $({{x}_{{{{i}_{1}}}}},{{x}_{{{{i}_{2}}}}},...,{{x}_{{{{i}_{s}}}}})$. Соответствующее число значений для $j$-го символа i-й $s$-граммы обозначается как ${{l}_{{{{i}_{j}}}}}$. Общее количество $s$-грамм в сообщении длиной N символов равно $N - s + 1$.

3.2. Алгоритм восстановления s-грамм

Вход алгоритма: общая длина неизвестного сообщения (N), длина восстанавливаемых участков ($s$), информация о возможных значениях каждого $i$-го знака сообщения (${{\{ {{x}_{i}}\} }_{{{{l}_{i}}}}}$) и их количестве (${{l}_{i}}$), критическая граница отбора участков ($L$), параметр ($\beta $), предварительно созданный словарь $s$-грамм и его мощность (${{D}_{s}}$).

Алгоритм включает следующие этапы:

1. Выбор подходящих отрезков сообщения. Для восстановления необходимо выбрать те $s$-граммы сообщения, для которых известно небольшое среднее количество значений.

Критерий выбора s-грамм: среднее геометрическое значение ${{L}_{i}}$ числа возможных символов для соответствующей i-й $s$-граммы не должно превышать заданной критической границы $L$ для любого i:

где $s$ – длина сегмента текста ($s$-граммы), ${{l}_{{{{i}_{j}}}}}$ – число вариантов для $j$-го символа в $i$-й $s$-грамме, ${{L}_{i}}$ – среднее число вариантов для i-й $s$-граммы, $L$ – критическая граница отбора сегментов.

2. Построение вариантов восстановления $s$-граммы. Поиск всех возможных комбинаций, которые могут быть построены с использованием известной информации о значениях знаков $s$-граммы.

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

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

Критерий восстановления s-граммы: степень неопределенности восстановления (число вариантов восстановления для одного отрезка) не должна превышать $r\;\leqslant \;{{r}_{{{\text{max}}}}} = \left\lfloor {{{2}^{{\beta s}}}} \right\rfloor $, где s – длина сегмента сообщения, $\beta $ – численный параметр меньше 1. На практике часто используется значение $\beta = 0.1$ (табл. 1).

Выход алгоритма: варианты восстановления отдельных s-грамм сообщения, число восстановленных s-грамм.

Этап создания словарей коротких s-грамм заданного покрытия не входит в данный алгоритм. Словари создаются предварительно на основе соответствующего текстового корпуса [12, 13] (подробнее в разделе 4).

При численных оценках рассматриваются следующие параметры алгоритма:

1. Длина отрезка текста $s$: 10–25 символов.

2. Критическая граница $L$: 8–16 символов.

3. Параметр $\beta = 0.1$.

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

4. СЛОВАРИ S-ГРАММ

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

Поскольку словари составляются на основе языкового корпуса ограниченного объема, их покрытие является неполным. Это означает, что не все существующие $s$-граммы языка оказываются включены в данный словарь. То есть возможно появление ошибок, когда существующая $s$-грамма отсутствует в словаре и отбрасывается как недопустимая в данном языке.

Таким образом, степень покрытия ${{\tau }_{s}}$ словаря $s$-грамм – это отношение объема построенного словаря к общему количеству существующих $s$‑грамм в языке [14]:

где ${{D}_{s}}$ – объем словаря s-грамм, $M(s)$ – число осмысленных s-грамм в языке.

Проблема определения степени покрытия заключается в том, что точное количество всех осмысленных s-грамм в языке неизвестно, особенно для больших порядков, хотя асимптотическую оценку можно получить, используя теоретико-вероятностную модель Шеннона [22]. Для приблизительной оценки степени покрытия словарей s-грамм могут использоваться и другие методы: эмпирическая проверка [11, 14], оценка на основе количества однократно встречаемых s-грамм [13] и др.

Словари s-грамм представляют собой модель открытого текста, в которой сообщение рассматривается как последовательность $s$-грамм из словаря. В предлагаемом алгоритме данные словари рассматриваются как критерий распознавания открытого текста.

Неполнота покрытия может привести к потере истинного варианта восстановления s-граммы, если ее не окажется в используемом словаре. Поэтому ${{\tau }_{s}}$ является параметром, влияющим на общую вероятность успешного восстановления отрезка сообщения в канале связи на 4 шаге алгоритма.

На основе объема словаря может быть вычислена энтропия s-граммы в расчете на один символ [12, 13]:

Значения энтропии $s$-грамм используются для оценки количества осмысленных текстов заданной длины в языке [15, 16].

Предельное значение ${{H}_{s}}$ принимается за энтропию языка:

5. МАТЕМАТИЧЕСКИЕ СВОЙСТВА АЛГОРИТМА

5.1. Вероятность появления L-ограниченных отрезков

Количество возможных значений ${{l}_{{{{i}_{j}}}}}$ для неизвестного ${{i}_{j}}$-го символа является дискретной случайной величиной, принимающей целые значения от $1$ до $m$ с вероятностями ${{p}_{k}} = P({{l}_{{{{i}_{j}}}}} = k)$ для любого ${{i}_{j}}$. При этом случайные величины ${{l}_{{{{i}_{j}}}}}$ для всех отрезков распределены одинаково и независимо. Значение критической границы $L$ фиксировано; значение $m$ – конечное.

Отрезок сообщения ($s$-грамма) с номером i называется $L$-ограниченным, если:

Cредней характеристикой $i$-го отрезка сообщения называется случайная величина:

Вероятность появления отрезка сообщения, отбираемого для восстановления, определяется вероятностью его $L$-ограниченности и может быть выражена через величину ${{S}_{i}}$:

Поскольку для любого ${{l}_{{{{i}_{j}}}}}$ верно, что μ = = ${\text{E}}({{\log }_{2}}{{l}_{{{{i}_{j}}}}}) = \sum\limits_{k = 1}^m {{{p}_{k}}\mathop {\log }\nolimits_2 k} $, ${{\sigma }^{2}} = {\text{D}}(\mathop {\log }\nolimits_2 {{l}_{{{{i}_{j}}}}})$ = = $\sum\limits_{k = 1}^m {{{p}_{k}}\mathop {\log }\nolimits_2^2 k} - {{\left( {\sum\limits_{k = 1}^m {{{p}_{k}}\mathop {\log }\nolimits_2 k} } \right)}^{2}}$, математическое ожидание и дисперсия величины ${{S}_{i}}$ равны ${\text{E}}{{S}_{i}} = \mu $ и ${\text{D}}{{S}_{i}} = \frac{{{{\sigma }^{2}}}}{s}$ для любого i.

Пусть длина отрезка сообщения $s \to \infty $. Тогда согласно центральной предельной теореме [17]:

для любого i, где $R = \sqrt s \cdot \frac{{\mathop {\log }\nolimits_2 L - \mu }}{\sigma }$, $\Phi $ – функция стандартного нормального распределения.

Предельное распределение из утверждения 1 может быть использовано для приближенной оценки вероятности появления $L$-ограниченных отрезков в сообщении в случае конечного значения величины s:

Так как сообщение имеет длину $N$ символов, количество последовательных отрезков длины s равно $N - s + 1$. Ожидаемое количество $L$-ограниченных отрезков в сообщении равно:

Величины ${{S}_{{i - 1}}}$ и ${{S}_{i}}$ соседних отрезков являются зависимыми (имеют непустое пересечение), так как имеют $s - 1$ общих компонент. Определим степень их корреляционной зависимости, показывающую долю совпадающих элементов в соседних отрезках.

а) Коэффициент корреляции двух соседних отрезков длиной $s$ символов равен:

б) Коэффициент корреляции $k$-го и $m$-го ($k < m$) произвольных отрезков длиной $s$ символов равен:

а) Заметим, что ${{l}_{{i - {{1}_{j}}}}} = {{l}_{{{{i}_{{j - 1}}}}}}$. Поскольку величины ${{S}_{{i - 1}}}$ и ${{S}_{i}}$ имеют непустое пересечение, коэффициент корреляции их средних величин равен:

б) Заметим, что ${{S}_{k}}$ является линейной комбинацией случайных величин. Обобщение этой формулы для двух произвольных отрезков производится аналогично с учетом свойства ковариации: если $m - k < s$, то ${{S}_{k}}$ и ${{S}_{m}}$ имеют непустое пересечение, при этом у каждой из двух компонент есть $m - k$ различных независимых слагаемых, а остальные $s - m + k$ слагаемых совпадают. Ковариации независимых величин равны 0, а ковариация случайной величины, являющейся общей частью для обеих компонент, с собой равна дисперсии: $\frac{1}{{{{s}^{2}}}}(s - m + k){{\sigma }^{2}}$. Если $m - k\; \geqslant \;s$, величины ${{S}_{k}}$ и ${{S}_{m}}$ являются независимыми (их пересечение пусто), поэтому их ковариация равна 0.

Условная вероятность появления $L$-ограниченного отрезка также может быть оценена с помощью нормального распределения в случае $s \to \infty $:

где $f(x,y)$ = $\frac{s}{{2\pi {{\sigma }^{2}}\sqrt {1 - {{\rho }^{2}}} }}{{e}^{{ - \frac{1}{{2(1 - {{\rho }^{2}})}}\left( {\frac{{s{{{(x - \mu )}}^{2}}}}{{{{\sigma }^{2}}}} - \rho \frac{{2s(x - \mu )(y - \mu )}}{{{{\sigma }^{2}}}} + \frac{{s{{{(y - \mu )}}^{2}}}}{{{{\sigma }^{2}}}}} \right)}}}$, $\rho = \frac{{s - 1}}{s}$ – коэффициент корреляции $i$-го и $(i - 1)$-го отрезков, $R = \sqrt s \cdot \frac{{\mathop {\log }\nolimits_2 L - \mu }}{\sigma }$.

При этом ожидаемая средняя величина следующего отрезка при условии $L$-ограниченности предыдущего [17]:

где $\phi $ – плотность стандартного нормального распределения, $\Phi $ – функция стандартного нормального распределения, $R = \sqrt s \cdot \frac{{\mathop {\log }\nolimits_2 L - \mu }}{\sigma }$.

Определим случайный вектор $\vec {S}$ = (S₁, S₂, ..., ${{S}_{{N - s + 1}}}{{)}^{T}}$, характеризующий сообщение длиной $N$ символов. Вероятность, что все отрезки сообщения одновременно являются $L$-ограниченными, стремится к многомерному нормальному распределению при $s \to \infty $:

где $\vec {\theta } = \left( {\begin{array}{*{20}{c}} \mu \\ \mu \\ \vdots \\ \mu \end{array}} \right)$ – вектор средних значений, Σ = = $\left( {\begin{array}{*{20}{c}} {{{\sigma }^{2}}}&{}&{{{\sigma }_{{{{S}_{1}},{{S}_{{N - s + 1}}}}}}} \\ \vdots & \ddots & \vdots \\ {{{\sigma }_{{{{S}_{{N - s + 1}}},{{S}_{1}}}}}}&{}&{{{\sigma }^{2}}} \end{array}} \right)$ – ковариационная матрица, на пересечении $k$-й строчки и $m$-го столбца которой стоят значения ковариации отрезков: $\vec {S}$ – многомерный нормальный вектор размерности $N - s + 1$, компонентами которого являются величины ${{S}_{i}}$, имеющие нормальное распределение при $s \to \infty $.

Вероятность одновременной $L$-ограниченности всех отрезков сообщения в пределе подчиняется многомерному нормальному распределению с соответствующими ковариационной матрицей и вектором средних значений.

При этом ненулевую ковариацию имеют компоненты вектора ${{S}_{k}}$ и ${{S}_{m}}$, такие что $m - k < s$.

Для ряда вероятностных распределений (например, равномерного) сумма независимых величин быстро сходится к нормальному распределению. Традиционные оценки погрешности, порождаемые центральной предельной теоремой в конечном случае, такие как неравенство Берри-Эссена, при среднем значении $s$ (десятки) показывают лишь грубые оценки и завышенные верхние границы. Это связано с тем, что, во-первых, разные классы распределений сходятся к нормальному с разной скоростью, а оценка погрешности дается общая для любой структуры распределения. Во-вторых, неравенство Берри-Эссена использует оценку погрешности в виде отношения третьего момента к корню из числа слагаемых. Такая форма ошибки будет давать довольно точную оценку только на больших s. Из численных расчетов известно, что равномерное распределение быстро сходится к нормальному, намного быстрее общих теоретических оценок [18]. Поэтому при суммировании равномерно распределенных случайных величин уже при 6–10 слагаемых удается добиться достаточной близости к нормальному закону [23].

С помощью нормального распределения можно приближенно оценить вероятность появления $L$-ограниченных отрезков в случае конечного значения величины s. Далее в расчетных примерах для равномерного распределения утверждения 1–4 применяются, начиная со значения $s \geqslant 10$.

5.2. Случай повторного использования ключа

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

Шифрованные тексты $M$ сообщений одинаковой длины сопоставляются друг с другом. В местах совпадения шифрованных символов у данных сообщений совпадают и исходные символы, так как ключевая последовательность при шифровании не менялась. Таким образом, во всех местах совпадения шифрованных символов последнего сообщения с символами любого из предыдущих сообщений открытые символы неизвестного сообщения восстанавливаются однозначно. Для остальных знаков остается $m - M + 1$ возможных значений (m – мощность алфавита открытого текста).

В случае повторного использования ключа для описания распределения числа возможных значений можно воспользоваться моделью случайных индикаторов. Либо на месте i-го символа сообщения найдено совпадение с вероятностью p, либо совпадений не найдено с вероятностью $1 - p$. По данным экспериментальных исследований при двукратном использовании ключа $p = 0.06$.

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

Введем случайную величину:

В местах совпадений неизвестный символ последнего сообщения определяется по информации об открытых символах предыдущих сообщений. Тогда количество ${{l}_{{{{i}_{j}}}}}$ вариантов знаков для всех отрезков неизвестного сообщения:

где $m$ – мощность алфавита, $M$ – число сообщений на одинаковом ключе.

Пусть вероятность $P\{ {{\xi }_{{{{i}_{j}}}}} = 1\} = p$, $P\{ {{\xi }_{{{{i}_{j}}}}} = 0\} $ = = 1 – p соответственно для любых i и j.

Средней характеристикой $i$-го отрезка сообщения в случае повторного шифрования называется случайная величина:

Очевидно, что ${{\hat {S}}_{i}}$ – это количество символов на i-м отрезке, для которых удалось восстановить исходный знак.

Математическое ожидание и дисперсия величины ${{\hat {S}}_{i}}$:

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

Вероятность того, что среднее геометрическое любого $i$-го отрезка неизвестного сообщения не превосходит заданной границы L, имеет биномиальное распределение с параметрами $s$ и $p$:

для любого $i$, где $C_{s}^{k}$ – биномиальный коэффициент, где $v = \left[ {s - s\frac{{\mathop {\log }\nolimits_2 L}}{{\mathop {\log }\nolimits_2 (m - M + 1)}}} \right]$.

Ковариация k-го и m-го произвольных отрезков сообщения длиной $s$ символов равна:

Для сообщения длиной $N$ символов рассмотрим биномиальный вектор:

где $M(s)$ – средняя характеристика i-й s-граммы сообщения, имеющая биномиальное распределение с параметрами s и p.

Вероятность того, что все отрезки сообщения длины s одновременно являются $L$-ограниченными, имеет мультиномиальное распределение с вектором средних значений $\theta $ и ковариационной матрицей $\Sigma $:

5.3. Математическая модель распределения числа осмысленных текстов

Пусть ${{N}_{s}} = {{m}^{s}}$ – общее количество всех s-грамм в алфавите мощностью $m$, среди которых присутствует ровно $M(s)$ осмысленных s-грамм. Величина $M(s)$ оценивается как ${{2}^{{{{H}_{s}} \cdot s}}}$, где ${{H}_{s}}$ – энтропия s-грамм в расчете на один символ [12, 13].

Далее определим ${{n}_{i}}$ как число возможных вариантов восстановления для i-го отрезка, среди которых присутствует один истинный. Поскольку состав выходных множеств для каждого неизвестного знака сообщения образуется случайным равновероятным выбором символов из исходного алфавита, мы рассматриваем множество ${{n}_{i}} - 1$ (ложных вариантов восстановления) как выборку на множестве ${{N}_{s}} - 1$, в котором $M(s) - 1$ осмысленных текстов.

Тогда вероятность, что в выборке из ${{n}_{i}} - 1$ различных вариантов восстановления ровно ${{r}_{i}}$ окажутся осмысленными, описывается гипергеометрическим распределением [17], т.е.

Если восстанавливается i-й отрезок сообщения (мощность алфавита – $m$ символов) длиной s символов со средним числом значений ${{L}_{i}}$, то вероятность появления ${{r}_{i}}$ осмысленных вариантов восстановления для данного отрезка:

Данное утверждение следует из формулы (18). При этом вероятность найти ровно 1 осмысленный текст (истинный) оценивается при значении параметра ${{r}_{i}} = 0$.

Таким образом, вероятность успеха восстановления $i$-й $s$-граммы со средним числом значений ${{L}_{i}}$ с учетом допустимой многозначности определяется как:

где ${{r}_{{{\text{max}}}}} = \left\lfloor {{{2}^{{\beta s}}}} \right\rfloor $ – максимально допустимая степень неоднозначности восстановления s-граммы, $\beta $ – параметр алгоритма.

Предельное распределение числа осмысленных текстов возникает, когда $s \to \infty $. Тогда параметры ${{N}_{s}} = {{m}^{s}} \to \infty $, $M(s{{) = 2}^{{Hs}}} \to \infty $, $H$ – предельное значение энтропии ${{H}_{s}}$ при $s \to \infty $. При этом полагаем ${{L}_{i}}\;\leqslant \;\frac{m}{2}$. Вид предельного распределения зависит от количества осмысленных текстов в выборке.

Поскольку нижеприведенные утверждения 9–10 описывают случаи предельного распределения при $s \to \infty $, в них учитывается не энтропия коротких s-грамм, а соответствующее предельное значение энтропии (т.е. энтропия языка).

Вероятность найти ровно 1 осмысленный текст (истинный) при $s \to \infty $:

Используя формулу Стирлинга и второй замечательный предел:

Вероятность получить ${{r}_{i}} = \left\lfloor {{{2}^{{\beta s}}}} \right\rfloor $ осмысленных текстов, среди которых один истинный, при восстановлении i-го отрезка длиной $s \to \infty $ имеет вид:

где $w = \left( {\left( {H - \beta + \mathop {\log }\nolimits_2 \frac{{{{L}_{i}}}}{m}} \right)s + \mathop {\log }\nolimits_2 e} \right) \cdot {{2}^{{\beta s}}} - \frac{\beta }{2}s - \frac{1}{2}$.

При использовании утверждений 8-9 для численных расчетов значение параметра s должно удовлетворять условию ${{H}_{s}} \approx H$. Для русского языка $s\; \geqslant \;50$, $H \approx 0.78$.

Если допустимое количество осмысленных текстов зависит от s, то ${{r}_{i}} = \left\lfloor {{{2}^{{\beta s}}}} \right\rfloor \to \infty $. Предполагая параметры $\beta < 1$; ${{L}_{i}}\;\leqslant \;\frac{m}{2}$:

где $w = \left( {\left( {H - \beta + \mathop {\log }\nolimits_2 \frac{{{{L}_{i}}}}{m}} \right)s + \mathop {\log }\nolimits_2 e} \right) \cdot {{2}^{{\beta s}}} - \frac{\beta }{2}s - \frac{1}{2}$.

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

6. ЭФФЕКТИВНОСТЬ АЛГОРИТМА

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

Тогда общая вероятность восстановления отрезков сообщения, среднее значение вариантов которых не превышает заданную критическую границу L, без учета степени покрытия словаря оценивается как:

где ${{P}_{{появл}}}(s,L)$ – вероятность появления i-го отрезка длины s со среднем числом вариантов, не превышающим $L$; ${{P}_{{однозн}}}(s,{{L}_{i}},\beta )$ – вероятность, что восстановление i-го отрезка со среднем числом вариантов ${{L}_{i}}$ не превысит допустимую многозначность.

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

где ${{\tau }_{s}}$ – степень покрытия словаря $s$-грамм.

Если общая доля восстановленной информации на выходе канала связи превышает установленное критическое значение $\pi > {{\pi }_{0}}$, то данный канал связи оценивается как незащищенный.

7. ТРУДОЕМКОСТЬ АЛГОРИТМА

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

Пусть $L$ – критическая граница отбора отрезков сообщения, s – длина восстанавливаемого отрезка сообщения, ${{D}_{s}}$ – объем словаря s-грамм. Тогда количество вариантов восстановления $L$‑ограниченного отрезка, проверяемых на присутствие в словаре, не превышает ${{L}^{s}}$.

Асимптотическая сложность восстановления L-ограниченного отрезка при реализации бинарного алгоритма поиска по словарю имеет вид:

Общее количество $L$-ограниченных отрезков в сообщении длиной N символов приведено в утверждении 5.

8. ЧИСЛЕННЫЕ ОЦЕНКИ ПАРАМЕТРОВ АЛГОРИТМА ДЛЯ РУССКОГО ЯЗЫКА

Рассмотрим алгоритм восстановления сообщения на русском языке с фиксированным алфавитом открытого текста – 35 символов (32 буквы кириллического алфавита, пробел, точка и запятая).

При расчетах использованы оценки энтропии s-грамм русского языка [12].

Поскольку для отрезков длиной более 50 символов значение энтропии стабилизируется, за уровень предельной энтропии принято значение 0.78 бит на символ.

Исследуемые параметры алгоритма приведены в табл. 4.

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

Следовательно, для русского языка восстановление 10-грамм при среднем числе значений больше 8–9 символов практически бессмысленно. Для 15-грамм максимальная эффективность восстановления будет для значения $L$ не больше 12–13 символов.

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

Очевидно, такой параметр – минимальная длина $s$-граммы, при которой вероятность восстановления отрезка приближается к единице для любого среднего числа вариантов знака. На основе вероятностей гипергеометрического распределения определяется длина такой минимальной $s$-граммы для русского языка (с алфавитом в 35 символов) – 16 символов.

Для ряда случаев конкретного вида распределения вероятностей ${{p}_{k}} = P({{l}_{{{{i}_{j}}}}} = k)$ (числа значений ${{i}_{j}}$-го входного символа) несложно получить численные оценки эффективности алгоритма.

Пусть, например, количество значений для всех отрезков распределено независимо и случайно равновероятно от 1 до m, т.е. принимает значения с одинаковыми вероятностями для любого $k = 1,2,...,m$. Значение критической границы $L$ фиксировано.

Теоретическая оценка эффективности алгоритма для русского языка (доля восстановленных отрезков в сообщении без учета степени покрытия словарей) при разных значениях параметров s и $L$, когда количество ${{l}_{{{{i}_{j}}}}}$ значений для всех отрезков распределено равномерно от 1 до 35, приведена в табл. 5.

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

9. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА

В рамках подтверждения построенной модели проводится сравнение теоретических оценок эффективности алгоритма с экспериментальными результатами. Для осуществления эксперимента используются программная реализация²² предлагаемого алгоритма и созданный корпус публицистических текстов русского языка объемом 1 миллион символов³³, подробно описанный в [12, 13].

На основе текстового корпуса программно⁴⁴ создаются словари s-грамм, используемые при восстановлении сообщения (табл. 6).

Последовательно рассматривается восстановление отрезков сообщения длиной 10, 15, 20 и 25 символов. Общая длина сообщения N = 1000 символов. Для разных значений критической границы L определяется относительная доля успешно восстановленных отрезков.

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

10. ЗАКЛЮЧЕНИЕ

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

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

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

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

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