Держинский Р.И. Математические основы информационной безопасности

βi кроме β0 является по построению собственным префиксом некоторого кодового слова. βi имеет длину li, число собственных префиксов li – 1, а у всех кодовых слов по ɸ число различных собственных префиксов не превосходит ∑ =1( − 1) = L − 2. Так как среди β1β2 … βn нет одинаковых или равных β0, то n ≤ L – r, то есть в каждом из рассмотренных разбиений имеется не более L – r + 1 частей, которые распадаются не

более чем на (L−r+2) пар. Последняя пара при четном разбиении состоит из одной части.

2

Так как каждая пара частей дает не более W + 1 кодовых слов, то (W + 1)* (L−r+2) -

2

верхнее значение числа кодовых слов, что и требовалось доказать (В этом заключается суть теоремы Маркова).

Неравенство Макмиллана Теорема:

ɸ : a → B i = ̅̅̅̅̅

i i 1;

μ(Bi) = li, тогда, если алфавитное кодирование взаимно однозначно, то capB = q.

lmax = max(lj)

Ck

∑ =1 qk там где это возможно равно 0

Лемма: k :Ck ≤ qk

Доказательство: Ck – число наборов, Сk ≤ qk

Ck↔ (ij1 … ijn)

13

ll1 + ll2 + … + llk = k

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

Следствие:

Xn= ∑ Ckk ≤ ∑ =1 n lmax

=1

X ≤ (n * lmax)1/n

Лемма: ɸ :bi → A*

P1 ≥ P2 ≥ … ≥ Pk-1 ≥ PkPi = μ(Bi), тогда можно так представить слово в коде ɸ, что получится оптимальное кодирование ɸ’, такое, что кодовые слова B’k-1 и Bk’ будут различаться только в последнем разряде.

Лемма: ɸ - оптимальный код, ɸ: P1,P2 … Pk. Исходный алфавит не важен, указаны лишь частоты и соответствующие кодовые слова.

ɸ’: p1, p2 .. pk-1p’p’’

B1, B2, … ,Bk-1, Bk, 0, Bk+1, … 1

p’ + p’’ = pk

Одна из частей разбивается на два компонента. Если один из этих кодов префиксный, то второй при этом тоже префиксный и C(ɸ’) = C(ɸ) + Pk

Теорема редукции: пусть p’ + p’’ = pk (совпадение частот), тогда если ɸ’ оптимальный префиксный код, то и ɸ - оптимальный префиксный код. Если ɸ - оптимальный префиксный код и p1 ≥ p2 ≥ … ≥ p’ ≥ p’’, то ɸ’ тоже оптимальный префиксный код.

Коды с исправлением ошибок. Оценка функций исправления ошибок

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

После этого возникает задача однозначного декодирования.

14

Определение: Код называется исправляющим R ошибок, если при наличии в кодовом слове ≤ R ошибок существует возможность установить исходное слово.

Определение: Расстоянием Хэмминга ρ(α, β) между двумя наборами длины n (μ(α) = μ(β) = n) называется число разрядов, в которых эти разряды изменяются.

Определение: шаром разбиения с центром в наборе ̅ называется множество всех наборов длины n, расстояние от которых до ̅ не превосходит .

Определение: код с кодовым расстоянием ρmin определяется как расстояние по Хэммингу по требованию: ρmin = min(ρ(α, β)).

Теорема: Код К = { ̅1, ̅2, … , ̅n} исправляет R ошибок, если ρmin(K) ≥ 2*R +1.

Доказательство: заметим, что если в кодовом слове может произойти не более чем R

ошибок, то из него может получиться любое слово из шара с радиусом R с центром в этом кодовом слове, поэтому код исправляет R ошибок тогда и только тогда, когда шар радиуса

R с центром в кодовом слове не пересекается с другим шаром.

Определение: Код обнаруживает R ошибок, если при наличии в нем R ошибок путем замещения можно сказать о факте этих ошибок.

Теорема: Код К = { ̅1, ̅2, … , ̅m} обнаруживает R ошибок тогда, когда ρmin(K) ≥ R + 1.

Оптимальные коды и их свойства

Пусть в алфавите А существует К букв и для каждой из них известны частоты их появления p1, … , pn, ∑pi = 1 pj> 0. Рассмотрим алфавитное кодирование ɸ: А → {0, 1} ≡

B0 = A*.

p1 – a1 → B1 – l1

p2 – a2 → B2 – l2

………..

Исходной букве ai с частотой pi соответствует кодовое слово Bi. Если в тексте большой длины N примерно выдержаны частоты, то можно сказать, что каждый символ ai встречается Npi раз. Длина кодового текста ∑=0(Npi) i = N * ∑=0 i*li.

15

Строим код, который исправляет 2r ошибок. Кодовое слово имеет максимальную длину 2r

+ 1, и для него

m* S2r(n) ≥ 2n Mr(n) ≥ S2r(n)

Код Хэмминга. Численная оценка Mr(n)

Рассмотрим код, исправляющий одну ошибку – замещение в словах длины n.

Выберем K N

K ≤ lg2(n+1)

2K-1 ≤ n ≤ 2K – 1 K ≥ lg2(n+1) K = [lg2n+1] = [lg2(n+1)]

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

Разобьем все числа от 1 до n на K классов.

D = {m/m = (m , m , … , m ); m = 1 i = ̅̅̅̅̅}

i k k-2 0 i 1,

D0 = {1, 3, 5, 7, …}

D1 = {2, 3, 6, 7, 10, 11, …}

Кодом Хэмминга порядка n называется множество наборов ̅ = (α1, α2, … , αn),

удовлетворяющих системе

Теорема: код Хэмминга порядка n содержит 2n-k наборов, где K = log2n + 1

Теорема: справедлива оценка

17

Компоненты, образующие криптосистемы

Шифровальный блокнот

Одноразовый шифровальный блокнот – единственный в теоретическом смысле стойкий метод шифрования. В его основе лежит та же идея, что и в шифре Цезаря.

Пусть открытое сообщение записано с помощью символов расширенного алфавита, состоящего из 33 букв алфавита, 10 знаков препинания {..:;?!()-“} и знака пробела между словами. Число символов расширенного алфавита в русском варианте равно 44. Занумеруем их числами от 0 до 43. Тогда любой передаваемый текст можно рассматривать как последовательность {ап} чисел множества {0,1,2,…,43}.

В качестве секретного ключа берётся абсолютно случайная последовательность {сп} из того же множества чисел. Эта последовательность должна иметь ту же длину, что и передаваемый текст. Складывая по модулю 44 число ап с

соответствующим числом сп ключа (т. е, складывая числа ап и сп и беря остаток от целочисленного деления их суммы на 44), получаем новое число bn, лежащее в промежутке от 0 до 43:

ап + сп=bn, 0 ≤ bn≤ 43. Вычисления производятся по модулю 44.

Заменяя цифры последовательности {bn} символами расширенного алфавита, получим зашифрованный текст.

Чтобы восстановить открытый текст, надо воспользоваться тем же ключом:

ап = bn - сп, 0 ≤ bn ≤ 43. Вычисления производятся по модулю 44.

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

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

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

18

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

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

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

Другая проблема – в передаче копии блокнота получателю. Размер ключа

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

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

Алгоритмы генерации псевдослучайных последовательностей. Равномерно

распределенные случайные последовательности.

В случае с криптосистемами мы в основном имеем дело с равномерно распределенными случайными последовательностями (РРСП). Случайная последовательность вычетов , i= 1, …, t, … называется равномерно распределенной в случае выполнения следующих условий:

19

Для любого натурального t случайная величина распределена равномерно:

( = ) = 1

Для любого .

Псевдослучайной называется последовательность , i= 1, …, t, …,

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

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

Линейный конгруэнтный генератор

конгруэнтен , если =

Линейный конгруэнтный генератор подразумевает следующую последовательность:

+1 = + { }

0 ≠ a

a — мультипликатор.

BBS

Выбирается большое случайное простое число p.

Элемент q сравним с 3{4}

n = p*q

1)Выбирается случайное S, взаимно простое с n, такое, что 1 ≤S≤ − 1;

2)Вычисляется 0 = 2{ }

= −1{ }

Берется — минимальный бит

Извлекаем корни . . по модулю

20

XL-1

Одновременно с тактом осуществляется передача из состояния Si в Si-1.

C(D) = 1 + C1D + … + C2D Z2[D] – Шифрование при помощи связующего многочлена на

Z2. Вектор начальных состояний – [Si-1, Si-2 , … , S1 , S0]. Выполняющаяся последовательность – Si = C1*Sj-1 + C2*Sj-2 + … + C1*Sj-1{2}

Пример:

L = 4

[S3, S2, S1, S0] = [0101]

C(D) = 1 + D + D3 + D4 C = [1; 0; 1; 1]

S4 = S3 + S1 + S0 = 0 + 0 + 1 = 1

S5 = S4 + S2 + S1 = 1 + 1 + 0 + 0 = 2

(1, 0, 1, 0, 1, 0, 1, 0, …) – выполняющаяся последовательность имеет период 2.

Определение: Неприводимый многочлен называется примитивным, если D порождает группу f(D) (Fp*, D).

Если C(D) Z2[D] и многочлен C(D) неприводим, то для каждого из возможных вариантов начальных состояний порождается выполняющаяся последовательность максимально возможного периода, равного 2*l – 1.

Если выполняющаяся последовательность получена с использованием примитивного многочлена, то есть имеют место быть максимальные периоды и при этом длина подпоследовательности k удовлетворяет такому условию:

22