Криптограммы, полученные при повторном использовании ключа.

Предполагаем, что алфавит А открытых текстов, гаммы и шифротекстов представляет собой множество чисел Z_n = {0,1,...,и- 1}. Пусть в распоряжении криптоаналитика оказались две криптограммы, полученные наложением одной и той же гаммы на два разных открытых текста:

где

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

Пусть S = {s_i}_i=1,2,… Тогда поставленная задача сводится к попытке подобрать пару открытых текстов, разность которых совпадает с известной последовательностью S. Будем в связи с этим говорить о разложении S на два составляющих открытых текста. В случае, когда данные тексты являются нормативными текстами, например, на русском, английском или другом языке, для решения последней задачи используется ряд подходов. Интуитивно понятно, что при достаточной длине текстов маловероятна возможность множественного представления данной после­довательности S в виде разности Т₁-Т₂. Как правило, такое разложение бывает единственным. Здесь имеет место приблизительно такая же ситуация, как и при рассмотрении вопроса о расстоянии единственности.

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

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

В таком случае можно вычислить начало второго сообщения:

Если l > 4, легко определить, является ли начало Т₂ "читаемым" или нет. В первом случае нужно попытаться продлить начало Т₂ по смыслу. Во втором случае нужно сдвинуть начало вероятного слова в Т₁ и проделать то же самое.

Если удалось развить Т₂ до т знаков (т>l): Т₂ = , то можно вычислить и соответствующие т-1 знаков и попытаться, в свою очередь, развить по смыслу Т₁.

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

Вопрос 15. Математическая модель шифра. Опорный шифр.

Под шифром понимается любой симметричный шифр, однозначной замены алфавитом которого служит множество шифр-величин. Это множество адаптировано к способу шифрования. Выбор той или иной простой замены осуществляется с помощью ключевого потока(распределителя), который представляет собой последовательность номеров простых замен. Ключевой поток может получаться случайным образом, на пример с помощью «рандолизатора» типа игровой рулетки. Такой шифр мы будем называть шифр с неограниченным ключом. Ключами шифра служат всевозможные ключевые потоки. Шифр с неограниченным ключом полностью определяется своим действием на множестве шифр-велечин и рандомезаторе, ключевой поток может также функционально зависеть от ключа шифра и вычисляться детерминировано(по некоторому алгоритму или программе). Число возможных ключевых потоков фиксированной длины, не превосходит числа ключей шифра. Такой шифр будет называться шифром с ограниченным ключом. На практике чаще всего используются шифры с ограниченным ключом. Ключевым потоком для таких ключей служит последовательность некоторого автономного автомата, множество состояния которого совпадает с множеством ключей шифра.

Пусть Х и Y кончное множество шифровелечин и шифрообозначений, с которыми оперирует некоторый шифр замены. |X|>1 |Y|>1 |Y|>=|X| это означает что открытые и шифрованный тексты представ в алфавите X и Y, процесс шифрования открытого текста Заключается в замене каждой шифровелечины на некоторой шифрообозначение. В соответствии и с одним из n>1 иньективных отображений . Индексированных числами j принадлежит К.

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

-> X ()=x, все x

Известно что Y=

Определение №1. Опорным шифром шифрозамены назовем совокупность ∑=(X,Y,K,E,D) в которой X и Y- множество шифровелечин, K-множество ключей, Е-множество иньективных отображений и D- множество правил расшифрования.

K=(0,1,…,(n-1)) E=() D={di,j ϵ k}

Определение 2. l-ой степенью назовем совокупность объектов =(, , , , ), l ϵ N, в которой , , декартовы степени множеств X,Y,K соответственно.

- множество правил шифрования.

: , Таких что для = , …, ϵ и = ϵ

Правило зашифрования ()= () … () ϵ , ϵ E, i=1,l

-множество состоящее из отображений : , , таких что для

= , …, ϵ () и = , …, ϵ

()= … ϵ , ϵ D,, i=1,l

При l=1 l-опорный шифр будет равен ∑ ( ∑)

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

Ключевой поток строится следующим образом: последовательность ,…, ϵ K номеров простых замен , используемых для зашифрования открытого текста = , …, ϵ X, i=1, l.

Имеются два принципиальных способа построения такой ключевой последовательности. Если нужно выбрать один из двух вариантов, достаточно подбросить монету. Аналогично можно поступить для случайного выбора одного из 2^m вариантов, достаточно подбросить монету m раз подряд. Заметим что исходы бросания образуют последовательность испытаний случайной велечины кси,которая будет принимать значения 0 и 1 с вероятностями p и q. 0 будет орел, 1 решка.

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

Этот выбор производится в соответствии с частотными характеристиками открытых текстов. Характеристики для обычных открытых текстов далеко не равномерное. Пусть p()={ } (3)

p()={ } (4)

Это априорно выбранные распределения вероятностей. Обозначим через… случайные велечины которые принадлежат значениям из , в соответствии с распределениями в законах (3)и(4). По определению эти случайные величины полагаем независимыми. Используем понятие l-опорного шифра, в данном случае под ним будем понимать пятёрку (, , , где , -случайные величины, -случайная величина с множеством исходов

P()={ }

-правила шифрования и расшифрования соответственно.

Распределение индуцируется распределением она зависит от . И её можно оценить

В ряде случаев не всякое слово длины l в алфавите x может появится в открытом тексте. Например для l=2 слово из «ъъ» вероятность появления равна 0. А с точки зрения шифрования совершенно безразлично, встретится такая биграмма в тексте или нет. По этому исключим из открытых текстов исключим l-грамм и будем рассматривать >0. Это условие мы используем при изучении совершенных шифров. Запрещенных l-грамм не слишком много, точнее что для всех выполняется следующее неравенство | |>| |, любой открытый текст можно удлинить некоторой шифровелечиной до открытого текста большей величины. При этом полагаем что .

Определение 3. Пусть (, , , где совокупность случайных чисел , , , множество правил шифрования и расшифрования для которых выполняется следующее условие P{ }>0, P{ }>0, все . Тогда шифром замены с неограниченным ключом назовем семейство =(,l ) сумма всех шифров длинны l. При этом совокупность будем называть l-опорным шифром.

Вопрос 16. Шифр с неограниченным ключом

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

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

Шифр с НЕ ограниченным ключом – ключами шифра служат всевозможные ключевые потоки. Шифр с неограниченным ключом полностью определяется своим действием на мн-вешифровеличин и рандомизаторов.

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

Пусть - совокупность случайных величин , множеств правил зашифрования и расшифрования для которой выполняются условия P{ = } > 0, P{ = } > 0. l -й опорный шифр шифра

Тогда шифром замены с неограниченным ключом назовем семейство l N). Шифр с неограниченным ключом представляет собой семейство шифров действующих на множествах открытых текстов, l ∈ Ν, и объединенных общим способом преобразования множества шифрвеличин. Для зашифрования открытого текста длины l (так же как и для расшифрования криптограммы длины l) шифр с неограниченным ключом использует l -й опорный шифр. При этом из множества с помощью некоторого рандомизатора случайно выбирается ключ в соответствии с априорным распределением P().

Вопрос 17. Модель шифра с ограниченным ключом.

Исходными предпосылками построения такого шифра служит опорный шифр сигма, конечное множество ключей-К, и множество правил зашифрования { K, N }, в определении действия . Также как и для шифра с неограниченным ключом используется ,

, i=1,l, где по прежнему К={0,1,…,n-1} множество номеров простых замен входящих в опорный шифр.

Отличие шифра с неограниченным ключом состоит в следующем: для шифра с ограниченным ключом, ключевой поток вычисляется по выбранному ключу k K.

Определение 4. Пусть C:K N--> – произвольное отображение, такое что для любы k K и n N, i=1,l

Такое что ψ (k,l)= причем множество отображений { ψ (k,l), k K}=K, назовем последовательность ….., а само отображение кси- генератором ключевого потока. Причем в этом определении ключевой поток однозначно определяется ключом k K и числом l.

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

Определение 5. Пусть имеется математическая модель , где совокупность случайных величин правила зашифрования и расшифрования , распределение P(), определяется нашей формулой и выполняется следующее условие P{ }>0. Для всех тогда шифром ….

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

Криптографические свойства шифра с ограниченным ключом определяется в первую очередь свойствами генератора ключевого потока.

Например если: где все k K, то получаем слабый шифр простой замены. Если генератор выдаёт нам следующую последовательность ,то мы получаем переодическую последовательность. То получаем более стойкий шифр, например Виженера.

18. Шифры совершенные по Шенону.

Первая Условная вероятность и вторая условная вероятность где .

Имеет смысл рассматривать x и y одинаковой длины. пусть , , для шифра с ограниченным ключом условная вероятность появления шифротекста (1). выполняется следующее условие

при . , при этом распределение вероятностей определяется через оприорное распределение на множестве ключей шифра Pk. Условную вероятность можно вычислить по стандартной формуле .(2)

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

Шифр с ограниченным ключом .

Шифр с неограниченным ключом .

Если шифр является совершенным то для любых , и любого натурального числа e выполняется следующее неравенство

Доказательство: 1.от противного: пусть тогда мы бы имели согласно первому следующее равенство . А согласно второму

А из третьего следует .

Шифр с ограниченным ключом не является совершеннм.

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

Совершенными могут быть лишь только шифры с неограниченным ключом.

Шифр с неограниченным ключом является совершенным, тогда и только тогда, когда его l- опорный шифр является совершенным при любом l принадлежащим N. Такой подход позволяет нам при изучении свойств шифром, рассматривать лишь их опорные шифры. Под шифром будем понимать совокупность (, , , , состоящей из случайных величин, заданных на конечных множествах x-открытых текстов и y-шифрованных текстов. В соответствии с априорным распределением вероятностей

. При этом |x|>1, |1|>1, |k|>1, а также правил зашифрования таких что . Полагаем что случайные величины и независимы.

Вероятность появления вычисляется обычно по формуле . Из общих соображение следует следующее равенство .

Если шифр совершенен то справедливы следующие неравенства |X|≤|Y|≤|K|, первое неравенство очевидно, если шифр совершенен то согласно доказательству утверждения 2, | |≥1 по этому для любого x X. { }=Y и по этому в большинстве случаев применяемые на практике шифр обладают следующим…

Шенону удалось описать эндоморфные шифры с минимально возможным числом ключей. Это число не меньше чем |Y|.

Дата добавления: 2015-12-01