Razbor_kriptov_-_chast_2

В предыдущем пункте мы доказали, что s ≥ kr-1+1. Получаем s = kr-1+1.

Теорема доказана.

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

Следствие.

Любая НРП(k,n) компенсирована, причем kn-1+1 ≤ Л(НРП(k,n)) ≤ kn-1

Пояснение: на периоде НРП(k,n) встречаются все kn элементов из Xn. Сумма элементов на периоде равна на 0, а поэтому, как мы уже заметили ранее, для определения следующего элемента требуется kn-1 предыдущих.

А теперь подумаем, почему сумма элементов на периоде равна 0? Оказывается, этому есть объяснение. На периоде находятся все kn элементов из Xn. Тогда для каждого элемента а из Х найдется и обратный элемент a-1 относительно операции сложения. Сумма таких элементов дает 0: a+a-1=0. Отсюда и получается xi + … + xn = 0.

Замечание. Для последовательности Х над полем из 2 элементов GF(2), являющейся НРП(2,n), выполнено: Л(Х_) ≥ 2n-1+n.

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

Статистические требования к последовательностям сформулированы в постулатах Голомба. Говорят, они подобны трем слонам, на которых стоит современная криптография. Но начать нужно не со слонов, а с огромной черепахи, которая является основой всей конструкции… Так, все, давайте к делу.

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

Примечание: на самом деле не обязательно «чисто»: даже если у нее есть предпериод, с некоторого элемента она будет чисто периодической (когда попадем на период).

Для такой последовательности обозначим: n0 – количество нулей на периоде

n1 – количество единиц на периоде

n1S – количество всех s-грамм «1…1» на периоде n0S – количество всех s-грамм «0…0» на периоде

n0(d) – количество нулей на периоде (отрезке (0, t-1)) последовательности X_d = {xi xi d

n1(d) – количество единиц на периоде (отрезке (0, t-1)) последовательности X_d = {xi

xi d

Последняя последовательность построена по принципу: берем сумму элементов на расстоянии d.

Вспомним, что такое функция автокорреляции.

Опр. Функцией автокорреляции (автокорреляцией) последовательности Х_ называется функция вида:

CX_Х_(d) =		∑	1

xi xi d – чувствуете? Сейчас будет какое-то преобразование.

Идействительно, заметим 2 вещи. Они будут часто использоваться в будущем

1.Если элементы на расстоянии d совпали, то сумма xi xi d равна 0 (XOR одинаковых элементов равен нулю).

2.Если элементы на расстоянии d не совпали, то сумма xi xi d равна 1 (XOR разных элементов равен единице).

Итак, приходим к пониманию того, что xi xi d можно заменить на «0» или «1», в зависимости от того, совпадают ли элементы xi и xi d

Едем дальше. Допустим, эту сумму можно заменить на 0. В таком случае получаем ∑ 1 . Сколько таких элементов будет под знаком суммы? Ровно столько,сколько совпадающих

элементов	xi	и	xi d на периоде последовательности. Посмотрите внимательно: под знаком
суммы стоит		1 в степени		xi	xi d	, которая равна 0, если эти элементы совпадают, и «1»
						0	1

в противном случае. Суммирование идет от i=0 до t. Другими словами: берем x0 и x0+d, сравниваем. Если равны – в сумму пойдет (-1) , если не равны – (-1) . Затем берем x1 и x1+d, сравниваем, и так далее. В результате получим некоторый набор:

∑

1

= (-1)0 + (-1)1 + …

Осталось посчитать, сколько будет элементов (-1)0 и сколько (-1)1. Как уже заметили чуть выше: слагаемых вида (-1)0 будет ровно столько, сколько совпадающих элементов xi и xi d на периоде последовательности. А слагаемыхвида (-1)0 окажется столько, сколько несовпадающих элементов xi и xi d на периоде последовательности.

Вспомним обозначения, которое мы ввели чуть раньше:

n0(d) – количество нулей на периоде (отрезке (0, t-1)) последовательности X_d = {xi

xi d

n1(d) – количество единиц на периоде (отрезке (0, t-1)) последовательности X_d = {xi xi d

Другими словами, можно сказать, что n0(d) – количество совпадающих элементов на периоде, а n1(d) – количество несовпадающих.

То есть элементов (-1)0 будет n0(d). А элементов (-1)1 будет n1(d).

Не забываем про знак суммы. Если сложить единицу саму с собой n0(d) раз, получится n0(d).

Если сложить (-1) саму с собой n1(d) раз, получится -n1(d).

Таким образом, формулу автокорреляции можно переписать в виде: CX_(d) = 1/t (n0(d) – n1(d))

Это не самая очевидная формула (на то она и черепаха). Постарался объяснить ее максимально подробно, при необходимости лучше перечитать ее вывод.

Теперь перейдем к слонам постулатам. Они служат для оценки статистических свойств последовательности.

Постулаты Галомба (для двоичной последовательности Х_ с длиной периода t).

1.|n1 – n0| ≤ 1

2.n1* 21-S = n1S = n0S = n0*21-S, где

s = 1..<log2t>. Здесь <log2t> - целая часть снизу от указанного логарифма.

Примечание: равенство рассматривается как приблизительное 3. CX_(d) = const, если d не делится на t.

Примечание: если d делится на t (то есть d=kt), то имеем вырожденный случай: элементы всегда будут совпадать (ибо период): xi = xi+d = xi+kt.

И тогда CX_(d)=1/t ∑ единиц = 1/t * t = 1. Рассмотрим подробнее эти постулаты: что же они значат.

Постулат №3 задает количество совпадений в исходной последовательности и ее версии, сдвинутой на d. Оно должно быть равным. То есть если были последовательности (x0, …, xt) и (x2, …, x0), то независимо от d количество совпадений элементов в них будет равным. Конечно, с оговоркой, что d не делится на t.

Постулат №1 оценивает только количество нулей и единиц на периоде (сбалансированность «0» и «1»). Если t четный, то количество нулей и единиц должно совпадать Если нечетный – различаться не более, чем на 1.

Постулат №2 проверяет сбалансированность s-грамм «0..0» и «1..1». То есть, например, последовательности из трех нулей и трех единиц должны встретиться одинаковое количество раз.

А теперь подумаем: почему 1 постулат не применяется в чистом виде и был забракован самыми жесткими криптографами? Дело в том, что он слишком сильный. Представьте, что есть последовательность с длиной периода t=2128. Допустим, что над созданием этой последовательности много лет трудилась команда лучших криптоаналитиков и она получилась с лучшими криптографическими свойствами. Но количество нулей и единиц совсем чуть-чуть не совпадает: например, нулей 2127-5, а единиц – 2127+5. Такая последовательность будет забракована по первому постулату, что плохо. Поэтому в реальных задачах применяют нормирующие коэффициенты, зависящие от длины периода последовательности.

Опр. Последовательность Х_, удовлетворяющая постулатам Галомба, называется псевдошумовой.

Утв. Пусть Х_ - двоичная последовательность, удовлетворяющая постулатам Галомба (псевдошумовая) с длиной периода t. Тогда:

t – нечетно

CX_(d) = -1/t для любого t не делящего d.

Другими словами: уточняем постулат. В том смысле, что если последовательность постулатам удовлетворяет, то Cx_(d) не просто константа, а равна -1/t.

Доказательство.

Докажем от противного. Предположим, что t – четное.

Рассмотрим таблицу последовательностей, где в самой верхней строчке – исходная последовательность, в следующей – она же, сдвинутая на 1, а в последней – она же, сдвинутая на t-1.

Введем переменную α = ∑

совпадений в 1и строках

несовпадений в них же .

Перед тем, как вычислять ее значение, заметим вот что. Сколько совпадающих элементов в 1 и 2 строках? Ровно столько, сколько нулей в последовательности {xi xi 1 .

Это мы чуть выше разбирали, здесь тот самый d равен 1. Аналогично, количество несовпадений равно количеству единиц в последовательности {xi xi 1 .

Для 1 и 3 строк аналогично:

Сколько совпадающих элементов в 1 и 3 строках? Ровно столько, сколько нулей в последовательности {xi xi 2 . Количество несовпадений равно количеству единиц в последовательности {xi xi 2 .

Тогда для первой и последней строк совпадений будет n0 t 1 , несовпадений – n1 t 1 . Теперь мы готовы к вычислению альфы.

α =		∑	совпадений в 1		и	строках		несовпадений в них же		=
	∑
=			1	1	) =	∑	_	1	= t * Cx_(t-1).

Поясним подробнее.

Что такое Cx(d)? Это, как мы показали выше: CX_(d) = 1/t (n0(d) – n1(d))

Домножив на t, получим то, что получили: t * CX_(d) = (n0(d) – n1(d)).

Обратите внимание: по 3 постулату Галомба Сх всегда принимает одно и то же значение. Поэтому здесь написано просто Cx, а не Cx(d) – от d ничего не зависит!

Проще говоря: Cx_(t-1) – это Cx умножить на (t-1).

Итак, получили: α = t * Cx_(t-1).

Теперь посчитаем другим способом: по столбцам. Все с тем же предположением, что t – четное.

Раз t – четное, то по первому постулату количество нулей и единиц будет равным: n0 n1 t/2.

Рассмотрим теперь первый элемент первого столбца. Сколько раз х1 совпадет с элементами ниже него? Правильный ответ: t/2 1 раз. Смотрите пример для x1 0:

Вспомним, что такое альфа и что мы считаем. Альфа – это количество совпадений минус количество несовпадений. Здесь совпадений окажется t/2 1, а несовпадений – t/2 . Так и запишем, добавив сумму по столбцам:

α ∑		1		∑	1 t

В прошлом шаге было получено:α = t * Cx_(t-1).

Приравняем альфы: t * Cx_(t-1) = -t

Разделим на (t-1): t * Cx_ = -

Справа получилась несократимая дробь: . Но что такое t*Сх? Вспоминаем определение:

CX_ = 1/t (n0(d) – n1(d))

Домножаем на t:

t * Cx_ = n0(d) – n1(d)

Таким образом, t*Сх – это количество целое число . В нашем случае это число оказалось несократимой дробью – противоречие.

Полученное противоречие доказывает, что предположение «t – четное» неверно.

Пусть теперь t – нечетное. Посчитаем Cx.

Если t – нечетное, то количество нулей и единиц на периоде попервому постулату будет различаться ровно на 1. Пусть нулей и единиц. То есть единиц наодну больше, чем нулей.

Снова смотрим на таблицу матрицу:

Посчитаем количество нулей и единиц в первом столбце в зависимости от того, чему равен х1:

В случае x1 1 количество совпадений будет равно количеству несовпадений:

В случае х1 0:

Тогда α 0 – t 1	t 1 .	α = t * Cx_(t-1).
На прошлыхшагах получили:
Приравняем: α = t * Cx_(t-1) =		умножить на (t-1).
x
//Напомним,C _(t-1) здесь – Схt 1 .
Разделим на t 1	и получим то, что требовалось доказать: Cx 1/t.
Утверждение доказано.

Бонус: тестовый вопрос вопрос и ответ предоставлены криптографом .

Что общего у ЛРП и ЛРС?

А.этопочтиодноитоже Б. это понятия, не имеющие между собой ничего общего В. это схожие понятия, различающиеся по 7 й производной

Г. то же, что В, но «по 5 й производной» Д. это слова из трех букв Е. нет верного ответа

Утв. ЛРП max n является псевдошумовой последовательностью удовлетворяет постулатам Галомба .

Доказательство.

Сколько единиц на периоде ЛРП? Было утверждение, что на периоде ЛРП max n сбалансированы все s граммы. При этом всякая ненулевая s-грамма (всякий ненулевой вектор длины s) встречается 2n-s раз, а нулевая s-грамма – 2n-s-1 раз (так как нулевого вектора на цикле нет – в нем петля).

Воспользуемся этой формулой напрямую. Сколько раз встретится s-грамма из одного элемента – единицы? Правильно: n1 = 2n-1. Аналогично n0 = 2n-1-1.

Для s-граммы длины s:

n1S = 2n-s

n0S = 2n-s-1.

Итак, постулаты 1 и 2 выполнены: «0» и «1», а также наборы из несколькихнулей и единиц встречаются одинаковое число раз или одно из них – на 1 раз больше .

Покажем, что выполнен и постулат №3.

xi – ЛРП max n по условию

xi d – тоже ЛРП max n просто отбросили первые d 1 элементов

А что можно сказать про их сумму? Вот смотрите, были последовательности xi и yi – обе ЛРП max n. Тогда xi yi – тоже ЛРП max n.Ведь элементы с номером n 1 и далее выражаются через предыдущие:

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

Для элементов xi и xi d он точно одинаковый, а поэтому xi xi d – тоже ЛРП max n.

А раз так, то нулевая s грамма встретится здесь 2n 1 1 раз, а единичная – 2n 1 раз.

Nед xi xi d	2n 1
Nнулей xi xi d	2n 1 1	1/t * 2n 1 – 1 2n 1 1/t
Отсюда Cx_ d	1/t * n0 d – n1 d

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

Получили, что ЛРП max n, несмотря на слабые криптографические свойства перехватывая 2n бит, злоумышленник сможет восстановить последовательность , удовлетворяет трем постулатам Галлона.

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

Вероятностныемоделикриптографии.

Введем следующие распределения вероятностей.

1.рисх – распределение вероятности на множестве открытых текстов. Другими словами: вероятность появления каждого открытого текста

2.ркл – распределение вероятности на множестве ключей

Другими словами: с какой вероятностью будет выбран именно этот ключ.

3.рш – распределение вероятности на множестве шифротекстов

4.рисх.к. – совместное распределение вероятности на множестве открытых текстов и ключей

5.рисх.ш. – совместное распределение вероятности открытых текстов и шифротектов.

Другими словами:с какой вероятностью данный открытый текст перейдет в этот шифротекст

6.рисх/ш – условное распределение вероятности на множестве открытых текстов при фиксированном шифротексте .

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

Введем следующие обозначения. a – открытый текст

z – ключ

у – шифротекст

E a,z – шифротекст, полученный в результате зашифрования текста а на ключеz.

Определим несколько соотношений для вероятностей.

1. рисх,к a,z рисх a *ркл z

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

2. рш y ∑ исх а Ркл , где a и z такие, что E a,z y

Другими словами: вероятность того, что при заданных a и z шифротекст окажется равным y, равна произведениювероятностей использования данного текста и данного ключа.

3.рисх/ш a|y исх.ш. ,

шу

4.Другими словами: вероятность того, что при заданном шифротекстеисходным сообщением было а. Вычислили по формуле из теории вероятности «А при условии В»: Р A|B

Опр. Шифротекст называется совершенно стойким по Шеннону, если открытый текст

и шифротекст статистически независимы: рисх a рисх/ш a|y .

Пояснение: при заданном шифротексте все открытые тексты равновероятны. То есть по известному шифротексту нельзя ничего сказать об открытом тексте.

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

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

Обратите внимание: это означает, что какой бы большой кусочек шифротекста не был перехвачен, нельзя однозначно восстановить исходный текст. Ключевое слово – однозначно. Это означает, что некоторые предположения сделать все же можно в отличие от стойкости по Шеннону . То есть условие Шеннона, где по известному шифротекста нельзя вообще ничего предположить об исходном тексте, гораздо более сильное. Отсюда – замечание.

Замечание. Совершенно стойкий шифр является идеально стойким.

ШифрВернама.

Опр. Шифр Вернама по модулю m – шифр, в котором значения открытого текста, шифротекста и ключа принимают значения в Z n , гдеn – длина сообщения. А длина ключа и длина криптограммs шифротекста совпадает с длиной открытого текста. То есть:

a a1, …, an – открытый текст

zz1, …, zn – ключ

y y1, …, yn – шифротекст, где yi ai zi mod m , i 1..n

Теорема.

Шифр Вернама по модулю m является совершенно стойким при случайном равновероятном выборе ключа из множества Zmn n символов из Zm .

Замечание свойство шифра Вернама : при известном или неизвестном открытом тексте все криптограммы равновероятны.

Поточныешифры Предисловие.

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

Опр. Потомный шифр переводит t й символ открытого текста xt из Х в t й символ шифротекста yt из У с использованием изменяющихся от такта к такту отображений:

φt :X Y.

Здесь Х и У – алфавиты открытого и шифрованного текстов, соответственно.

Поточные шифры бывают:

1.Синхронные СПШ

2.Самосинхронизирующиеся ССПШ

Рассмотрим эти 2 типа поточных шифров.

Синхронныепотомныешифры. Устройство СПШ.

СПШ состоит из управляющего и шифрующего блоков. Управляющий блок генерирует управляющую гамму γt , используемую для формирования изменяющихся от такта к такту отображений: φγt .

Ход работы: на вход поступает символ открытого текста xt, для него формируется символ гаммы γt. Затем шифрующий блок зашифровывает символ открытого текста xt в символ шифротекста yt с использованием отображения φγt.

Функционирование СПШ определено соотношением:

yt φγt xt

fш γt, xt .

Другими словами: символ шифротекста получается применением функции φγt к символу открытого текста xt. Или что тоже самое, но более подробно – применение функции зашифрования, зависящей от символагаммы и символаоткрытого текста.

Общая схема СПШ.