Разрушение частот букв на основе регулярных комбинаторных структур
Збережено в:
| Опубліковано в: : | Труды Института прикладной математики и механики НАН Украины |
|---|---|
| Дата: | 2008 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2008
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/20024 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Разрушение частот букв на основе регулярных комбинаторных структур / В.В. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 185-193. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-20024 |
|---|---|
| record_format |
dspace |
| spelling |
Скобелев, В.В. 2011-05-20T08:03:57Z 2011-05-20T08:03:57Z 2008 Разрушение частот букв на основе регулярных комбинаторных структур / В.В. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 185-193. — Бібліогр.: 3 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/20024 518.6+681.3 ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики НАН Украины Разрушение частот букв на основе регулярных комбинаторных структур Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Разрушение частот букв на основе регулярных комбинаторных структур |
| spellingShingle |
Разрушение частот букв на основе регулярных комбинаторных структур Скобелев, В.В. |
| title_short |
Разрушение частот букв на основе регулярных комбинаторных структур |
| title_full |
Разрушение частот букв на основе регулярных комбинаторных структур |
| title_fullStr |
Разрушение частот букв на основе регулярных комбинаторных структур |
| title_full_unstemmed |
Разрушение частот букв на основе регулярных комбинаторных структур |
| title_sort |
разрушение частот букв на основе регулярных комбинаторных структур |
| author |
Скобелев, В.В. |
| author_facet |
Скобелев, В.В. |
| publishDate |
2008 |
| language |
Russian |
| container_title |
Труды Института прикладной математики и механики НАН Украины |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| issn |
1683-4720 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/20024 |
| citation_txt |
Разрушение частот букв на основе регулярных комбинаторных структур / В.В. Скобелев // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 185-193. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT skobelevvv razrušeniečastotbukvnaosnoveregulârnyhkombinatornyhstruktur |
| first_indexed |
2025-11-25T20:39:00Z |
| last_indexed |
2025-11-25T20:39:00Z |
| _version_ |
1850527404916736000 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2008. Том 17
УДК 518.6+681.3
c©2008. В.В. Скобелев
РАЗРУШЕНИЕ ЧАСТОТ БУКВ НА ОСНОВЕ
РЕГУЛЯРНЫХ КОМБИНАТОРНЫХ СТРУКТУР
Разработан аксиоматический подход, предназначенный для решения задачи разрушения частот
букв в словах исходного языка, основанный на использовании регулярных комбинаторных струк-
тур. Доказана корректность предложенного подхода. Оценена асимптотическая временная и ем-
костная сложность дискретного преобразователя, предназначенного для решения задачи разру-
шения частот букв в словах исходного языка, и построенного в соответствии с предложенным
подходом.
Введение. Одной из типичных атак на шифры является частотный анализ, т.е.
использование статистических свойств применяемого естественного языка и поиск
слов с характерной структурой [1]. Этот тип атак является основным при наличии у
криптоаналитика только шифртекста, т.е. в наихудшей для криптоаналитика ситу-
ации. Шифры неустойчивые к таким атакам принято считать абсолютно неустойчи-
выми шифрами [2]. Поэтому разработка моделей и методов, обеспечивающих стой-
кость шифра к частотному анализу, является актуальной задачей при построении
любых вычислительно стойких коммерческих шифров. В [3] сформулированы тре-
бования, предъявляемые к комбинаторным структурам, предназначенным для ре-
шения рассматриваемой задачи и показано, что этим требованиям удовлетворяют
шары и грани единичного куба.
Основной целью настоящей работы является построение и анализ дискретного
преобразователя, построенного на основе регулярных комбинаторных структур, и
предназначенного для решения задачи разрушения частот букв в словах исходного
языка.
1. Основные понятия и определения. Снабдив схему шифрования дискрет-
ным преобразователем, осуществляющим разрушение частот букв на этапе предвы-
числений, мы естественно приходим к схеме, представленной на рис.1.
Рис. 1. Положение дискретного преобразователя, разрушающего частоты в схеме шифрования.
Побуквенное кодирование исходного текста двоичной последовательностью осу-
185
В.В. Скобелев
ществляется обычным образом и укладывается в рамки следующей модели.
Пусть исходные сообщения образуют бесконечный язык L ⊆ Σ+. Длину слова u
обозначим через d(u). Предположим, что каждая буква алфавита Σ встречается, по
крайней мере, в одном слове u ∈ L. Положим
l1 = dlog |Σ|e.
Зафиксируем инъекцию cdng : Σ → El1 (где E = {0, 1}) и расширим ее на
множество Σ+ в соответствии с равенством
cdng(σ1 . . . σn) = cdng(σ1) . . . cdng(σ1).
Ясно, что язык cdng(L) = {cdng(u)|u ∈ L} представляет собой такой язык в
алфавите cdng(Σ) = {cdng(σ)|σ ∈ Σ}, что:
1) d(cdng(u) = l1 · d(u) (u ∈ L);
2) dcdng(Σ)(cdng(u)) = d(u) для любого слова u ∈ L, где dcdng(Σ)(cdng(u)) – это
длина слова cdng(u) в алфавите cdng(Σ).
Под алгоритмом побуквенного кодирования исходного текста двоичными после-
довательностями принято понимать любой алгоритм, осуществляющий вычисление
значений cdng(σ) (σ ∈ Σ) с временной и емкостной сложностью, соответственно,
равной T = O(dlog |Σ|e) (|Σ| → ∞) и V = O(d|Σ| · log |Σ|e) (|Σ| → ∞).
Эффективность представленной на рис. 1 схемы шифрования для легальных
пользователей и ее стойкость к криптоанализу существенно зависят от комбинатор-
ных структур, применяемых в процессе разрушения частот букв. Поэтому важными
характеристиками являются возможность компактного представления используе-
мой комбинаторной структуры в неявном виде и существование быстрого алгорит-
ма порождения элементов этой структуры одного за другим в явном виде. Комби-
наторные структуры, обладающие этими двумя свойствами, назовем регулярными
комбинаторными структурами.
2. Регулярные комбинаторные структуры. Пусть n(u, σ) (u ∈ Σ+, σ ∈ Σ) –
число вхождений буквы σ в слово u. Ясно, что
∑
σ∈Σ
n(u, σ) = d(u)
и
n(cdng(u), cdng(σ)) = n(u, σ)
для всех u ∈ Σ+ и σ ∈ Σ.
Положим
L(k) = {u ∈ L|d(u) ≤ k} (k ∈ N)
и
ν(L(k), σ) =
∑
u∈L(k)
n(u, σ)
∑
u∈L(k)
d(u)
(k ∈ N, σ ∈ Σ).
186
Регулярные комбинаторные структуры
Тогда ∑
σ∈Σ
ν(L(k), σ) = 1
и
ν(cdng(L(k)), cdng(σ)) = ν(L(k), σ) (k ∈ N, σ ∈ Σ).
Предположим, что для каждого σ ∈ Σ существует предел
lim
k→∞
ν(L(k), σ) = a(σ) > 0.
Тогда для любого фиксированного числа ε > 0 для каждого σ ∈ Σ существует такое
число k0(σ, ε) ∈ N, что
|ν(L(k), σ)− a(σ)| < ε
для всех k ≥ k0(σ, ε) (k ∈ N).
Зафиксируем такое достаточно малое число ε > 0 , что a(σ) − ε > 0 (σ ∈ Σ).
Пусть
k0(ε) = max{k0(σ, ε)|σ ∈ Σ}.
Назовем относительной частотой появления буквы σ ∈ Σ в словах языка L число
frqnc(L, σ) = ν(L(k0(ε)), σ).
Отметим, что frqnc(L, σ) > 0 для всех σ ∈ Σ.
В дальнейшем предполагается, что числа frqnc(L, σ) (σ ∈ Σ) представлены дво-
ичными дробями и вычислены с точностью до 2−r (r ∈ N), причем
∑
σ∈Σ
frqnc(L, σ) = 1.
Так как
frqnc(cdng(L), cdng(σ)) = frqnc(L, σ) (σ ∈ Σ),
то построение комбинаторных структур в терминах языка cdng(L) и относитель-
ных частот frqnc(L, σ) корректно. Для краткости записи относительную частоту
frqnc(L, σ) (σ ∈ Σ) будем обозначать frqnc(σ).
Зафиксируем число h ∈ N (h ≥ r) и такое число l2 ∈ N, что l2 ≥ l1 + h.
Регулярной комбинаторной структурой для языка L назовем бинарное отноше-
ние ∆ ⊆ El1 ×El2 , удовлетворяющее следующим пяти условиям.
Условие 1. pr1∆ = cdng(Σ).
Условие 2. |∆(cdng(σ))| = 2r · frqnc(σ) (σ ∈ Σ).
Условие 3. ∆(cdng(σ1))
⋂
∆(cdng(σ2)) = ∅ для всех σ1, σ2 ∈ Σ (σ1 6= σ2).
Условие 4. Емкостная сложность представления в неявном виде каждого множе-
ства ∆(cdng(σ)) (σ ∈ Σ) равна O(l2) (|Σ| → ∞).
Условие 5. Существует алгоритм A, который при фиксированной начинающейся
с нуля нумерации элементов любого множества ∆(cdng(σ)) (σ ∈ Σ) с временной и
емкостной сложностью, равной O(l2) (l2 →∞), порождает: а) 0-й элемент множества
187
В.В. Скобелев
Рис. 2. Схематическое представление регулярной комбинаторной структуры.
∆(cdng(σ)); б)по j-му элементу (j = 0, 1, . . . , |∆(cdng(σ))|−1) множества ∆(cdng(σ))
порождает (j + 1) ( mod |∆(cdng(σ))|)-й элемент множества ∆(cdng(σ)).
Регулярная комбинаторная структура ∆ схематически изображена на рис. 2.
Теорема 1. Множество регулярных комбинаторных структур для языка L –
непустое множество.
Доказательство. Достаточно показать, что существует регулярная комбинатор-
ная структура в случае, когда l2 = l1 + h.
Пусть Sσ,h (σ ∈ Σ) – множество всех таких слов ασ ↑↑ 0h−r ∈ Eh (ασ ∈ Er),
что ασ – двоичное представление числа, принадлежащего множеству Z2r·frqnc(σ)−1.
Определим бинарное отношение ∆h ⊆ El1 ×El2 равенством
∆h =
⋃
σ∈Σ
{(cdng(σ), cdng(σ) ↑↑ ασ ↑↑ 0h−r) | ασ ↑↑ 0h−r ∈ Sσ,h}.
Так как
pr1∆h = cdng(Σ)
и
|∆h(cdng(σ))| = 2r · frqnc(σ) (σ ∈ Σ),
то для бинарного отношения ∆h выполнены условия 1 и 2.
А так как cdng – инъекция, то для всех σ1, σ2 ∈ Σ (σ1 6= σ2)
(cdng(σ1), cdng(σ1) ↑↑ ασ1 ↑↑ 0h−r) 6= (cdng(σ2), cdng(σ2) ↑↑ ασ2 ↑↑ 0h−r),
т.е.
∆h(cdng(σ1))
⋂
∆h(cdng(σ2)) = ∅ (σ1, σ2 ∈ Σ, σ1 6= σ2)
188
Регулярные комбинаторные структуры
и, следовательно, для бинарного отношения ∆h выполнено условие 3.
Представлением каждого множества ∆h(cdng(σ)) (σ ∈ Σ) в неявном виде яв-
ляется упорядоченная тройка (cdng(σ), 2r · frqnc(σ), h − r), т.е. емкостная слож-
ность представления каждого множества ∆h(cdng(σ)) в неявном виде равна O(l2)
(|Σ| → ∞). Это означает, что для бинарного отношения ∆h выполнено условие 4.
Зафиксируем такую нумерацию элементов множества ∆h(cdng(σ)) (σ ∈ Σ), что
номер каждого элемента cdng(σ) ↑↑ ασ ↑↑ 0h−r ∈ ∆h(cdng(σ)) (ασ ↑↑ 0h−r ∈ Sσ,h)
совпадает с тем двоичным числом, которое представляет α. Отсюда вытекает, что
для бинарного отношения ∆h выполнено условие 5. ¤
Отметим, что для любой регулярной комбинаторной структуры ∆ ⊆ El1 × El2
истинно равенство
pr2∆ = 2r.
3. Анализ математической модели дискретного преобразователя. По-
строим математическую модель дискретного преобразователя, осуществляющего
разрушение частот букв в словах языка cdng(L), и основанного на использовании
регулярной комбинаторной структуры ∆ ⊆ El1 ×El2 .
Пусть A(σ, j) (σ ∈ Σ, j ∈ Z|∆(cdng(σ))|) – j-й элемент множества ∆(cdng(σ)), по-
рождаемый алгоритмом A, а CNTR – одномерный массив длины |Σ|, элементы
которого занумерованы элементами множества cdng(Σ). Положим
Q = {CNTR | 0 ≤ CNTR(cdng(σ)) ≤ |∆(cdng(σ))| (σ ∈ Σ)}.
Массив CNTR ∈ Q предназначен для подсчета (по mod |∆(cdng(σ))|) числа вхож-
дений каждой буквы cdng(σ) ∈ cdng(Σ) в слово cdng(u) ∈ cdng(L).
Обозначим через GNRT (Q) псевдослучайный выбор элемента CNTR ∈ Q.
Рассмотрим следующий алгоритм преобразования слова
cdng(u) = cdng(σ1) . . . cdng(σn) ∈ cdng(L)
в слово в алфавите pr2∆.
Шаг 1. result := Λ, CNTR := GNRT (Q), i := 1.
Шаг 2. CNTR(cdng(σi)) := (CNTR(cdng(σi)) + 1) ( mod |∆(cdng(σi))|).
Шаг 3. bi := A(σi, CNTR(cdng(σi))).
Шаг 4. result := result ↑↑ bi, i := i + 1.
Шаг 5. Если i ≤ n, то переход к шагу 2, иначе конец.
Обозначим через B(cdng(u)) слово в алфавите pr2∆, в которое предложенный
алгоритм переводит слово cdng(u) ∈ cdng(L). Положим
L = {B(cdng(u)) | u ∈ L}.
Отметим, что предложенный алгоритм осуществляет инъекцию языка cdng(L)
в язык L. При этом, для любого слова cdng(u) ∈ cdng(L)
dpr2∆(B(cdng(u))) = d(u),
189
В.В. Скобелев
где dpr2∆(B(cdng(u))) – длина слова B(cdng(u)) в алфавите pr2∆.
Теорема 2. Относительная частота появления каждой буквы x ∈ pr2∆ в
словах языка L равна 2−r.
Доказательство. Так как
ν(L(k), x) =
∑
u∈L(k)
n(B(cdng(u)), x)
∑
u∈L(k)
d(u)
(k ∈ N, x ∈ pr2∆)
и ∑
x∈pr2∆
ν(L(k), x) = 1 (k ∈ N),
то
lim
k→∞
∑
x∈pr2∆
ν(L(k), x) = 1,
т.е. ∑
x∈pr2∆
frqnc(L, x) = 1.
Из шагов 2–4 предложенного алгоритма вытекает, что
n(B(cdng(u)), x) ≤ n(u, σ)
|∆(cdng(σ))| + 1 (x ∈ ∆(cdng(σ)))
для любого слова cdng(u) ∈ cdng(L).
Следовательно, для всех x ∈ ∆(cdng(σ))
ν(L(k), x) ≤
∑
u∈L(k)
(
n(u,σ)
|∆(cdng(σ))|
)
+ 1
∑
u∈L(k)
d(u)
=
=
1
|∆(cdng(σ))| ·
∑
u∈L(k)
n(u, σ)
∑
u∈L(k)
d(u)
+
∑
u∈L(k)
1
∑
u∈L(k)
d(u)
=
=
1
|∆(cdng(σ))| ·
∑
u∈L(k)
n(u, σ)
∑
u∈L(k)
d(u)
+
|L(k)|∑
u∈L(k)
d(u)
.
Отсюда вытекает, что для всех x ∈ ∆(cdng(σ))
frqnc(L, x) = lim
k→∞
frqnc(L, x) ≤
190
Регулярные комбинаторные структуры
≤ lim
k→∞
1
|∆(cdng(σ))| ·
∑
u∈L(k)
n(u, σ)
∑
u∈L(k)
d(u)
+
|L(k)|∑
u∈L(k)
d(u)
=
=
1
|∆(cdng(σ))| · frqnc(L, σ) + lim
k→∞
|L(k)|∑
u∈L(k)
d(u)
.
Так как L – бесконечный язык, то
lim
k→∞
|L(k)|∑
u∈L(k)
d(u)
= 0.
Следовательно,
frqnc(L, x) ≤ 1
|∆(cdng(σ))| · frqnc(L, σ) =
1
2r · frqnc(L, σ)
= 2−r.
Предположим, что существует такое x ∈ ∆(cdng(σ)), что frqnc(L, x) < 2−r. Тогда
1 =
∑
x∈pr2∆
frqnc(L, x) <
∑
x∈pr2∆
2−r = 2r · 2−r = 1.
Получено противоречие. Следовательно, предположение – ложное. Отсюда вы-
текает, что frqnc(L, x) = 1 для всех x ∈ ∆(cdng(σ)). ¤
Теорема 3. Временная и емкостная сложность преобразования слова
cdng(u) = cdng(σ1) . . . cdng(σn) ∈ cdng(L)
в слово в алфавите pr2∆ равна, соответственно,
T (n) = O(TGNRT (|Σ|) + n · l2 · 2r) (|Σ| → ∞) (1)
и
V (n) = O(VGNRT (|Σ|) + l2 · |Σ|+ n · l2) (|Σ| → ∞), (2)
где TGNRT (|Σ|) и VGNRT (|Σ|) – соответственно, временная и емкостная слож-
ность заполнения массива CNTR при помощи псевдослучайного генератора таки-
ми числами, что 0 ≤ CNTR(cdng(σ)) ≤ |∆(cdng(σ))| (σ ∈ Σ).
Доказательство. Временная сложность шага 1 предложенного алгоритма равна
T1 = O(TGNRT (|Σ|) (|Σ| → ∞). (3)
Оценим временную сложность цикла, определяемого шагами 2–5.
Временная сложность выполнения как шага 2, так и шага 4, равна
T2 = O(l2) (|Σ| → ∞). (4)
191
В.В. Скобелев
Временная сложность 1-го исполнения шага 3 равна
T
(1)
3 = O(l2 · 2r) (|Σ| → ∞), (5)
а для каждого последующего исполнения шага 2
T
(2)
3 = O(l2) (|Σ| → ∞). (6)
Временная сложность выполнения шага 5 равна
T4 = O(1) (|Σ| → ∞). (7)
Из (3)–(7) вытекает (1).
Емкостная сложность шага 1 предложенного алгоритма равна
V1 = O(VGNRT (|Σ|) (|Σ| → ∞). (8)
Оценим объем памяти, необходимой для реализации цикла, определяемого ша-
гами 2–5.
Для хранения текущего значения A(σ,CNTR(cdng(σ))) (σ ∈ Σ) необходим объем
памяти, равный
V2 = O(l2 · |Σ|) (|Σ| → ∞). (9)
Объем памяти, необходимой для реализации как шага 2, так и шага 3, равен
V3 = O(l2) (|Σ| → ∞). (10)
Объем памяти, необходимой для реализации шага 4, равен
V4 = O(n · l2) (|Σ| → ∞). (11)
Объем памяти, необходимой для реализации шага 5, равен
V5 = O(n) (|Σ| → ∞). (12)
Из (8)–(12) вытекает (2). ¤
Секретным сеансовым ключом для предложенного алгоритма является настрой-
ка псевдослучайного генератора GNRT . Из (1),(3),(5) и (6) вытекает, что временная
сложность во многом определяется именно исполнением шага 1 и первым исполне-
нием шага 3.
Ни массив GNRT (Q), ни исходные значения A(σ,CNTR(cdng(σ))) (σ ∈ Σ) не
зависят от слова cdng(u) ∈ cdng(L), преобразуемого алгоритмом. Следовательно,
если процесс разворачивания ключа, т.е. вычисление массива GNRT (Q) и массива
A(σ,CNTR(cdng(σ))) (σ ∈ Σ) вынести за рамки предложенного алгоритма (т.е.
на этап предвычислений), то асимптотическая временная сложность станет равной
O(n · l2) (|Σ| → ∞), т.е. полное разрушение частот букв исходного сообщения будет
осуществляться с линейным замедлением.
192
Регулярные комбинаторные структуры
Несложно показать, что предложенный алгоритм, рассматриваемый как поточ-
ный шифр, является неустойчивым шифром по отношению к атаке, осуществляемой
на основе заранее выбранного исходного текста и является вычислительно устойчи-
вым шифром по отношению к атаке, осуществляемой на основе только шифртекста.
Заключение. В настоящей работе построена и исследована математическая мо-
дель дискретного преобразователя, построенного на основе регулярной комбинатор-
ной структуры и предназначенного для решения задачи разрушения частот букв в
словах исходного языка.
Рассмотренный в работе подход допускает следующее обобщение. Пусть в неяв-
ном виде задано семейство регулярных комбинаторных структур
S = {∆i | i = 1, . . . , n},
а в процессе реализации предложенного алгоритма выбор бинарного отношения
∆i ∈ S в очередном фрагменте преобразуемого слова осуществляется с помощью
псевдослучайного генератора Γ чисел, принадлежащих множеству Nn. Будем счи-
тать, что инициализация генератора Γ является частью секретного сеансового клю-
ча. В результате мы приходим к нестационарному поточному шифру, который явля-
ется устойчивым шифром по отношению к атаке, осуществляемой на основе заранее
выбранного исходного текста.
Отметим, что неявно заданное семейство регулярных комбинаторных структур S
представляет собой естественное обобщение парадигмы управляемой подстановоч-
ной операции, применяемой при построении высокоскоростных блочных шифров.
Такое обобщение получается за счет перехода от отображений к бинарным отноше-
ниям.
1. Алферов А.П. и др. Основы криптографии. – М.: Гелиос АРВ, 2002. – 480c.
2. Диффи У., Хеллмен М.Е. Защищенность и имитостойкость: Введение в криптографию // ТИ-
ИЭР. – 1979. – Т.67. – №3. – С.71-109.
3. Скобелев В.В. Построение стойких к частотному анализу криптосистем на основе регулярных
комбинаторных структур // Искусственный интеллект. – 2004. – №1. – С.88-96.
Ин-т прикл. математики и механики НАН Украины, Донецк
vv_skobelev@iamm.ac.donetsk.ua
Получено 19.05.08
193
содержание
Том 17
Донецк, 2008
Основан в 1997г.
|