Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Основи криптографії. Тема 2. Симетричні криптосистеми. Носов В.В.
Лекція 4. Безпека симетричних криптосистем
Навчальні питання
1. Ентропія, надлишковість і відстань одиничності 1
2. Взаємна інформація 6
3. Безумовно безпечні системи 9
4. Псевдовипадкові послідовності 10
Час – 2 год.
Література.
Вступ
В лекции 1 было указано, что криптоанализ криптосистемы часто зависит от имеющейся в тексте структуры. Например, в табл. 2.1 был определен ключ 22 (или -4) из-за того, что открытый текст оказался единственным осмысленным из возможных.
Структура открытого текста сохраняется и в шифртексте, хотя и в скрытой форме. Если информация, содержащаяся в структуре открытого текста, превышает неопределенность (энтропию) ключа, то может появиться возможность найти открытый текст по криптограмме!
Для оценки безопасности криптосистем напомним основные определения и понятия, связанные с количеством информации.
Энтропия, избыточность и расстояние единственности
Пусть — случайная величина, распределение которой на множестве задается вероятностями
Разумеется, и для всех . Покажем, что величина
хорошо подходит для измерения количества информации, содержащейся в сообщении о том, что произойдет событие . В основании логарифма число 2 можно заменить на любое другое, но, как будет видно ниже, двойка лучше всего отражает наше интуитивное понимание информации. В случае, когда в основании логарифма стоит 2, единица информации называется бит.
Пусть , т.е. ; тогда . Теперь событие достоверно, и сообщение о том, что оно произойдет, не несет никакой информации (как, например, фраза "Солнце завтра снова взойдет"). Это прекрасно соответствует формуле (5.1), поскольку .
Теперь рассмотрим событие, происходящее с вероятностью , типа рождения ребенка определенного пола. Тогда . В предположении, что дети обоих полов рождаются с одинаковой вероятностью, ясно, что сообщение о поле новорожденного дает ровно один бит информации.
Например, 1 означает рождение мальчика, а 0 — рождение девочки. Это вновь согласуется с формулой (5.1), поскольку .
Если некоторое событие происходит с вероятностью , то сообщение о том, что оно происходит, дает два бита информации. Это очевидно в ситуации с четырьмя равновозможными исходами. Каждому из этих исходов можно сопоставить свою двоичную последовательность длины два. С другой стороны, количество информации, которую несет сообщение о событии, происходящем с вероятностью , не должно зависеть от вероятностей других возможных событий. Таким образом, значение , вычисленное по формуле (5.1), вновь согласуется с нашей интуицией. Продолжая подобным образом, получаем, что
Математическое ожидание случайной величины , определенной на множестве , называется энтропией и обозначается либо через , либо через , где . Следовательно,
При принято обозначать , и писать вместо .
Поскольку стремится к при , не возникает проблем с определением функции энтропии при равенстве нулю (или 1) некоторых из вероятностей .
График функции изображен ниже при помощи функции Plot пакета "Matnematica".
p =.;
Entrop[p_] = -p*Log[2, p] - (1 - p)*Log[2, 1 - p];
Plot[Entrop[x], {x, 0, 1}]
Функцию энтропии можно вычислить следующим образом.
MultiEntropy[p_List] :=
p = {1/4, 1/4, 1/4, 1/4};
MultiEntropy[p]
|| 2
Можно дать следующие интерпретации энтропии случайной величины .
Помня эти интерпретации, можно ожидать, что функция энтропии обладает следующими свойствами.
, т.е. добавление к множеству невозможного события не влияет на неопределенность величины .
для любой перестановки множества , т.е. перенумерование различных событий множества оставляет энтропию неизменной.
, т.е. неопределенность величины максимальна, если все события равновероятны.
, т.е. среднее количество двоичных разрядов, необходимое для описания результата из множества равно числу битов, необходимых при объединении событий и в одно событие, обозначаемое как , плюс число битов, необходимых для того, чтобы различить события и при условии, что событие произошло. Например, если , то и
Можно показать (см. [3]), что функция, определяемая формулой (5.1), — единственная непрерывная функция, удовлетворяющая условию (5.2) и порождающая функцию энтропии , обладающую приведенными выше свойствами .
Пример 5.1
Рассмотрим подбрасывание монеты. Пусть и , . Энтропия задается формулой (5.4).
Очевидно, что значение подтверждается тем фактом, что для представления результата такого эксперимента с правильной (обычной) монетой необходим один бит. Например, , a .
Рассмотрим неправильную монету, у которой , а . Тогда энтропия эксперимента по подбрасыванию неправильной монеты . Можно ожидать, что в среднем для представления результата эксперимента с неправильной монетой, для которой , окажется достаточно . Это утверждение верно в том смысле, что можно сколь угодно приблизиться к числу . Трюк состоит в том, что результат большого числа бросаний представляется единственной двоичной строкой. Например, результат двух бросаний можно закодировать, используя неравномерный (чем больше вероятность, тем меньше кодовое слово) префиксный код (ни одна кодовая комбинация не является началом другой, более длинной), следующим образом:
|
выпало |
вероятность |
представление |
Математическое ожидание длины такого представления равно
Но при этом описаны результаты сразу двух бросаний, т.е. при такой схеме на одно бросание приходится по . Объединяя в одну группу по три, четыре и более бросаний, будем получать все более и более точное приближение для величины .
Существует, однако, проблема однозначного декодирования, состоящая в том, как получатель по длинной строке из нулей и единиц может определить, сколько экспериментов проводилось (сколько букв в символе) и какой был результат у каждого из них. Нетрудно проверить, что любая последовательность, состоящая из подпоследовательностей 111, 110, 10 и 0, однозначно разбивается на такие блоки, поскольку использовался префиксный код ни одна кодовая комбинация не является началом другой, более длинной.
Пример 5.2 (часть 1)
При кодировании достаточно длинных последовательностей из 26 букв английского алфавита двоичными последовательностями можно добиться того, что на каждую букву будет приходиться по . Действительно, для кодирования -буквенных последовательностей потребуется битов, т.е. на каждую букву будет приходиться по битов, а эта последовательность сходится к при .
С другой стороны, энтропию 1-грамм легко вычислить по вероятностям, приведенным в табл. 1.1. Получится 4,15 бита на букву.
Таблица 1.1. Распределение вероятностей 1-грамм в английском языке.
Подобные вычисления были проведены для биграмм и триграмм (см. [4] приложение F). Получены следующие величины:
По некоторым тестам асимптотическое значение величины при . меньше, чем 1.5 бита па букву!
Определение 5.1
Обозначим через , открытый текст, порожденный источником открытых текстов над алфавитом . Тогда избыточность текста определяется равенством
Число является мерой избыточности, приходящейся на одну букву текста.
Если алфавит состоит из букв, то каждый символ представляется с помощью битов, а избыточность текста из букв задается равенством . Если допустить использование представлений разной длины для разных символов алфавита со средней длиной представления битов на символ, то получим
.
Избыточность является мерой того, насколько длина данного текста превосходит длину текста, минимально необходимого для хранения содержащейся в данном тексте информации (все измеряется в битах).
Теперь обратимся к криптосистеме , состоящей из криптографических преобразований , проиндексированных ключами из ключевого пространства . Предположим, что неизвестный открытый текст представляет собой правильный текст на английском языке. Тогда, имея на руках шифртекст, криптоаналитик может попытаться, перебирая все возможные ключи, получить все варианты открытых текстов.
Поскольку шифртекст состоит из нескольких букв, некоторые ключи придется признать недопустимыми из-за того, что они приводят к невозможным или маловероятным комбинациям букв в открытом тексте. При этом, чем длиннее будет шифртекст, тем больше ключей окажутся отвергнутыми из-за того, что они разрушают структуру или смысл английского текста.
Говоря более формально, они разрушают избыточность открытого текста. Рано или поздно останется единственный возможный кандидат на роль ключа шифрования.
Вернемся к обобщенной постановке. Пусть длина открытого текста равна битов. Имеется двоичных последовательностей, но лишь из них представляют собой осмысленные сообщения. Вероятность того, что дешифрование при помощи ошибочного ключа приведет к допустимому сообщению, равна. Если перепробовать все возможные ключи, то можно ожидать, что получится осмысленных сообщений. Причем если все ключи равновероятны, а — случайная величина, задающая распределение ключей в пространстве , то . Тогда число осмысленных сообщений равно
.
Если это число не превосходит 1, то весьма вероятно, что лишь один ключ приводит к осмысленному дешифрованию данного шифртекста. Это происходит при
т.е. в ситуации, когда избыточность открытого текста из букв () удовлетворяет условию
то лишь один ключ приводит к осмысленному дешифрованию шифртекста.
Если величина не является равномерно распределенной, то при обосновании полученной выше оценки мы все равно будем считать величину мерой неопределенности ключа.
Определение 5.2
Пусть в криптосистеме используются ключи из ключевого пространства , а открытые тексты порождаются источником . Рассмотрим атаку против криптосистемы на основе известного шифртекста. Расстояние единственности этой криптосистемы определяется как
где — энтропия ключа, a — избыточность открытого текста.
Смысл такого названия в том, что если избыточность открытого текста превосходит неопределенность ключа, то криптоаналитик, обладающий достаточными вычислительными ресурсами, может восстановить открытый текст по криптограмме. Таким образом, расстояние единственности показывает пользователю криптосистемы, когда необходимо сменить ключ для того, чтобы обеспечить безопасность системы.
Пример 5.2 (часть 2)
Продолжим обсуждение примера 5.2. Предположим, что к английскому тексту применяется простая подстановка. Предположив, что все ключей равновероятны, находим
Оценив приблизительно избыточность английского текста из букв числом , получим, что расстояние единственности равно .
Процитируем Фридмана [5]: "практически каждый пример из 25 или более букв, представляющий собой результат действия одноалфавитной подстановки на осмысленный английский текст, может быть легко расшифрован". Отметим, что числа 25 и 28 прекрасно согласуются.
Часто одна случайная величина содержит информацию о другой. В криптосистемах открытый текст и шифртекст связаны посредством ключа. Дадим формальное определение (в теоретико-информационном смысле этого слова) абсолютно безопасной криптосистемы.
Пусть и — случайные величины, определенные на множествах и соответственно. Вероятность или сокращенно
задаёт совместное распределение величин и . Вероятность того, что при условиии, что , называется условной вероятностью и обозначается или
Выполняется соотношение
(5.5)
Неопределенность величины при условии называется условной частной энтропией и определяется аналогично функции энтропии равенством
(5.6)
Эту величину можно интерпретировать как среднее количество информации, содержащейся в сообщении о значении случайной величины , если уже известно, что .
Условной энтропией величины по величине называется усредненное значение неопределенности по всем . Т.е.
Пусть совместная энтропия определяется аналогично функции энтропии от одной переменной.
Теорема 5.1 (цепное правило)
Доказательство. Используя соотношения (5.5) и (5.7), получим
Второе равенство следует из перестановочности аргументов в .
Иначе говоря, приведенная выше теорема утверждает, что неопределенность совместного распределения величин и равна неопределенности плюс неопределенность по .
Следствие 5.2
Пусть и — независимые случайные величины. Тогда
Доказательство. Для того, чтобы доказать утверждение i), повторим доказательство теоремы 5.1, используя равенство .
Утверждения ii) и iii) непосредственно следуют из i) и цепного правила.
Рассмотрим разность между количеством информации (см. 5.1), содержащейся в сообщении , и количеством информации, содержащейся в том же сообщении при заранее известном условии . Эту разность естественно считать количеством информации о том, что , содержащейся в сообщении . Обозначим это через . Тогда выполняется равенство
Заметим, что имеет место симметрия .
Взаимная информация случайных величин определяется как математическое ожидание величины , т.е.
Теорема 5.3
Доказательство. Из равенства (5.8) следует, что
Остальные равенства следуют из теоремы 5.1.
Величину можно интерпретировать как среднее количество информации, которое дает об (или, наоборот, об ).
Продублируем понятия собственной энтропии, условной энтропии, совместной энтропии и средней взаимной информации.
На рис. 2 условно показана собственная энтропия H(X) и H(Y), условные энтропии H(Y/X) и H(X/Y) и совместная энтропия H(X,Y).
H(X/Y)
H(Y)
H(X,Y)
H(X)
H(Y/X)
I(X,Y)
Рис. 2
Часть рисунка, отмеченная штриховкой, называется средней взаимной информацией I(X,Y), содержащейся в ансамблях Х и Y. Она показывает, какое (в среднем) количество информации содержит сообщение X о сообщении Y (или наоборот, сообщение Y о сообщении X).
Как следует из рис. 2,
Если сообщения X и Y полностью независимы (рис. 3), то взаимная информация отсутствует и ,
H(Y)
H(X,Y)
H(X)
Рис. 3
Если сообщения X и Y частично зависимы (рис. 2), то взаимная информация ,
Если X и Y полностью зависимы (X и Y содержат одну и ту же информацию) и , то ,
Если X является подмножеством Y (рис. 4), то .
H(Y)
H(X,Y)
H(X)
H(Y/X)
I(X,Y)
Рис. 4
Пример 5.3
Двоичный симметричный канал передачи информации может быть описан следующим образом. Источник посылает значение величины с вероятностью или тоже с вероятностью . Приемник получает значение величины с вероятностью или же с вероятностью ( интерпретируется как вероятность ошибки, которую вносит источник шума). Это означает, что , и что вероятность того, что источник посылал при получении равно
Аналогично, . Кроме того, и Таким образом, для двоичного симметричного канала по формуле
𝐼(𝑋;𝑌)=− (5.8) получаем,
Можно заключить, что приемник получает битов информации о случайной величине по полученному значению величины .
Практическое достижение "границы" является фундаментальной проблемой алгебраической теории кодирования.
При , как и следовало ожидать, приемник не получает никакой информации о переданных символах, поскольку .
Вернемся к традиционной криптосистеме, описанной ранее. Пусть выбор ключа из ключевого пространства происходит с вероятностью , открытый текст представляет собой последовательность случайных величин
а шифртекст — последовательность случайных величин
Таким образом, . В большинстве приложений будет равно . Поскольку является взаимно-однозначным отображением, открытый текст должен однозначно определяться по ключу и шифртексту, следовательно, выполняется равенство
(5.9)
Пользователя криптосистемы, конечно, интересует, как много информации об дает .
Теорема 5.4
Сформулируем это на словах. Неопределенность ключа в сумме с информацией об открытом тексте, которую дает шифртекст, не меньше, чем неопределенность открытого текста. Это вновь хорошо согласуется с нашей интуицией.
Доказательство теоремы 5.4. Из равенства (5.9) и цепного правила (теорему 5.1
можно применять и к условной энтропии) следует, что
Т.е. неопределенность ключа по шифртексту не меньше, чем неопределенность открытого текста по шифртексту. И действительно, зная шифртекст, можно восстановить открытый текст при наличии ключа, но не всегда можно восстановить ключ при наличии открытого текста.
Из этого следует, что
и по теореме 5.3 получаем
Определение 5.3
Криптосистема называется безусловно безопасной или обладает совершенной секретностью, если
Следствие 5.5
Если система абсолютно безопасна, то
Следствие 5.5 говорит, что в безусловно безопасной криптосистеме, в которой все ключи и все открытые тексты равновероятны, ключей должно быть не меньше, чем открытых текстов.
Пример 5.4
Допустим, что у нас ключей, и каждый из них может быть выбран с вероятностью . Тогда
Если сообщение представляет собой результат бросаний правильной монеты, то, очевидно, , и для совершенной секретности необходимо выбрать .
Это можно реализовать при шифровании , где через обозначены первые битов ключа, а через — покоординатное сложение по модулю 2. При таком шифровании каждый шифртекст может быть получен из каждого открытого текста с равной вероятностью.
Помимо теоретической стойкости криптосистемы рассматривают ее практическую стойкость. Для этого вводят рабочую характеристику
- среднее количество работы (измеренное в удобных единицах), требуемое для нахождения ключа на основе знания знаков шифротекста с помощью наилучшего криптоаналитического алгоритма.
Обычно криптосистемы оценивают с помощью достигнутой оценки рабочей характеристики при использовании наилучшего из известных методов дешифрования. Криптосистемы называются практически стойкими если они не могут быть вскрыты в течение реального времени () всеми общедоступными методами.
На практике используют именно это понятие стойкости криптосистем. По сути дела из этого определения можно сделать вывод о том, что проблема создания практически стойких криптосистем или шифров может быть сведена к проблеме нахождения наиболее сложных задач, удовлетворяющих определенным условиям.
Можно составить шифр таким образом, чтобы раскрытие его было эквивалентно (или включало в себя, решение некоторой задачи, про которую известно, что для ее решения требуется определенный (желательно большой объем) работы). Поэтому стойкость криптосистемы можно определить вычислительной сложностью алгоритмов, применяемых криптоаналитиками для шифрования. Такой подход к определению стойкости криптосистем, основанный на понятии вычислительной сложности криптоаналитических алгоритмов (в отличие от информационно-теоретического, рассмотренного выше) основан не на вопросе о том возможно ли извлечь информацию об открытом тексте из анализа шифротекста, а на вопросе о том, осуществимо ли это в приемлемое время. Этот подход позволяет достичь свойства совершенной секретности криптосистемы даже для случаев, когда используется секретные ключи значительно меньше по размерам чем длина открытого шифруемого текста.
Вычислительная сложность алгоритма в свою очередь измеряется его временной и емкостной сложностями в зависимости от размера входных данных.
Временная сложность это время, затрачиваемое алгоритмом для решения задачи, рассматриваемое как функция размера задачи или количества входных данных.
Емкостная сложность это емкость необходимой машинной памяти. Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями. Эти сложности алгоритма определяют в итоге размер задачи, которую можно решить этим алгоритмом.
Если при данном размере задачи в качестве меры сложности берётся наибольшая из сложностей по всем входам этого размера, то она называется сложностью в худшем случае. Если в качестве меры сложности берется «средняя» сложность по всем входам данного размера, то она называется средней сложностью. Обычно среднюю сложность найти труднее чем сложность в худшем случае.
Внедрение логических схем во время и после Второй мировой войны способствовало созданию полностью электронных криптосистем. Они оказались весьма практичными в том смысле, что были легки в реализации и очень быстры. Но анализ их безопасности отнюдь не легок! Работа с логическими схемами часто приводит к алфавиту . Имеются лишь две возможные перестановки (подстановки) на множестве . Одна из них меняет местами оба символа. Это можно описать как прибавление 1 (по модулю 2) к обоим элементам. Другая перестановка оставляет символы неизменными, что означает прибавление 0 (по модулю 2) к этим элементам.
Так как шифр Вернама безусловно безопасен (абсолютно стоек), но не очень практичен, естественно возникает схема, изображенная на рис. 3.1.
Рис. 3.1. Двоичная криптосистема с псевдослучайной последовательностью
Разумеется, желательно, чтобы последовательность была случайной, но машина с конечным числом состояний и детерминированным алгоритмом работы не может генерировать случайную последовательность. В этой ситуации всегда порождается итоговая периодическая (ultimately periodic) последовательность. Это наблюдение показывает, что (исключая начальный сегмент) данная схема есть специальный случай криптосистемы Виженера.
С другой стороны, можно попытаться генерировать последовательности, которые кажутся случайными, имеют длинные периоды и хорошие криптографические свойства.
Golomb S.W. [6] сформулировал три постулата, которым должна удовлетворять двоичная периодическая последовательность, чтобы называться псевдослучайной. Прежде чем привести их, введем необходимую терминологию.
Определение 3.1
Последовательность называется периодической с периодом , если — наименьшее натуральное число, для которого
при всех .
Отрезок длины есть подпоследовательность из , состоящая из идентичных символов, ограниченная иными символами. Если отрезок начинается в момент , то справедливы условия
Мы различаем следующие отрезки:
блок длины ,
лакуна длины .
Автокорреляция периодической последовательности с периодом определяется формулой:
(3.1)
где (соответственно, ) обозначает число совпадений (соответственно, несовпадений) на полном периоде между и ; вторая последовательность есть последовательность , сдвинутая влево на позиций. Таким образом,
Заметим, что можно также написать .
Пример 3.1
Рассмотрим периодическую последовательность с периодом , заданную ее первыми элементами.
С помощью функций Count, Length, Mod, RotateLeft и Table пакета "Mathematica" легко вычисляются все значения автокорреляционной функции , .
segment = {1, 1, 0, 1, 0, 0, 0, 0};
p = Length[segment];
Table[2*Count[Mod[
segment - RotateLeft[segment,k],2],0] - p) / p, {k, 0, p – 1}]
|| {1, 0, 0, 0, -1/2, 0, 0, 0}
Если кратно , получаем , , так что . В этом случае говорят о внутрифазовой автокорреляции. Если не делит , то говорят о внефазовой автокорреляции. В этом случае значение лежит между и .
Определение 3.2 (Golombs Randomness Postulates)
G1: Количество нулей и единиц в одном периоде приблизительно совпадает, т.е. вероятности их появления , если четно, и , если нечетно.
G2: Половина отрезков в цикле имеют длину 1, четверть отрезков имеют длину 2, восьмая часть отрезков имеют длину 3 и т.д.; кроме того, половина отрезков данной длины — лакуны, другая половина — блоки.
G3: Внефазовая автокорреляция имеет одно и то же значение для всех .
G1 утверждает, что нули и единицы встречаются приблизительно с одной и той же вероятностью. Их появления легко подсчитать с помощью функции Count пакета "Mathematica".
segment = {1, 1, 0, 1, 0, 0, 0, 0};
Count[segment,0]
Count[segment,1]
|| 5
|| 3
G2 утверждает, что после комбинации 011 символ 0 (приводящий к блоку длины 2) имеет ту же вероятность, что и символ 1 (приводящий к блоку длины ), и т.п. Таким образом, G2 говорит, что конкретные -граммы встречаются с правильными частотами. Эти частоты можно вычислить с помощью функций Count, Length, RotateLeft, Table и Take пакета "Mathematica":
segment={0,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1};
p = Length[segment];
ngram = {1, 0, 1}; k = Length[ngram];
Count[Table[Take [
RotateLeft[segment, i], k] == ngram, {i, p}], True]
|| 3
Интерпретация постулата G3 более трудна. Это условие говорит, что число совпадений в данной последовательности и в ее сдвинутой версии не дает никакой информации о периоде последовательности, если сдвиг не кратен периоду. Похожая ситуация описывается в лемме 3.1, где такое сравнение позволяет определить длину ключа, использованного в шифре Виженера. В криптографических приложениях слишком велико для такого подхода.
Лемма 3.1
Пусть — двоичная последовательность с периодом , удовлетворяющая постулатам случайности Голомба. Тогда нечетно и принимает значение , когда не делится на .
Доказательство. Рассмотрим циклическую -матрицу с верхней строкой . Подсчитаем двумя способами число всех совпадений за вычетом числа несовпадений между верхней строкой и всеми прочими строками. В силу постулата G3 построчный подсчет дает вклад для каждой строки с номером . В целом получается значение . Теперь мы подсчитаем ту же сумму по столбцам, рассматривая число совпадений за вычетом числа несовпадений между всеми нижними клетками и верхней.
Случай четного
В силу G1 вклад каждого столбца равен , так как каждый столбец содержит в точности совпадений нижних клеток с верхней и в точности несовпадений. Сумма этих значений по всем столбцам равна . Приравнивая два значения суммы, получаем . Однако из равенства (3.1) следует, что число целое. Это невозможно, когда , так как .
Случай нечетного
Для столбцов получаем вклад , равный 0, а для столбцов — вклад , равный . Следовательно, значение суммы есть . Приравнивание этой суммы к дает .
Хорошо известный критерий и спектральный критерий дают способы проверки свойств псевдослучайности данной последовательности.
Имеются также свойства криптографической природы, которым должна удовлетворять последовательность на рис. 3.1.
С1: период последовательности должен быть очень большим (величиной порядка 1050);
С2: последовательность должна легко генерироваться;
С3: знание части открытого текста и соответствующего шифртекста (атака с известным открытым текстом) не должно позволить криптоаналитику сгенерировать всю последовательность .
Линейные регистры сдвига с обратной связью
Регистры сдвига с обратной связью реализуют очень быстрый способ порождения бинарных (или двоичных) последовательностей. Их общий вид показан на рис. 3.2.
Рис. 3.2. Общий вид регистра сдвига с обратной связью.
Регистр сдвига с обратной связью (FSR — от feedback shift register) длины имеет ячеек памяти, значения которых совместно образуют (начальное) состояние регистра сдвига. Функция отображает в и называется функцией обратной связи регистра. Так как является булевой функцией, она может быть легко построена из элементарных логических функций.
После первого такта работы регистр сдвига выдаст и перейдет в состояние где . Продолжая таким образом, регистр сдвига генерирует бесконечную последовательность .
Пример 3.2
Рассмотрим случай , когда задается равенством Исходя из начального состояния , можно легко определить последующие состояния с помощью функций Mod, Do и Print пакета "Mathematica"
Clear[f];
f[x_,y_,z_]:= Mod[x*y + z, 2];
{s0,s1,s2} = {0, 1 ,1};
Do[{s0,s1,s2}= {s1, s2, f[s0,s1,s2]};
Print [{s0,s1,s2}],{i, 1, 6}]
{1,1,1}
{1,1,0}
{1,0,1}
{0,1,1}
{1,1,1}
{1,1,0}
Частный случай линейной функции :
где все — двоичные цифры, а сложение выполняется по модулю 2.
Общий вид линейного регистра сдвига с обратной связью (кратко LFSR) показан на рис. 3.3.
Рис. 3.3. Общий вид линейного регистра сдвига.
Выходная последовательность такого LFSR может быть описана посредством начального состояния и линейного рекуррентного соотношения
(3.2)
или, эквивалентно,
(3.3)
где по определению. Пусть обозначает состояние в момент , т.е. . Имеется следующее, аналогичное (3.2), рекуррентное соотношение для последовательных состояний регистра:
(3.4)
Коэффициенты в (3.2) и на рис. 3.3 называются коэффициентами обратной связи регистра. Если , то соответствующий переключатель на рис. 3.3 разомкнут, а если , то замкнут. Предположим, что всегда . Следствием данного предположения является то, что любое состояние LFSR имеет не только единственное следующее состояние, что естественно, но и единственного предшественника. В самом деле, для любого значение однозначно определяется по посредством (3.2).
Пример 3.3
При , , получаем LFSR на рис. 3.4.
Рис. 3.4. Пример LFSR при .
Начальное состояние (1,0,0,0) дает следующий список последовательных состояний:
{s0, s1, s2, s3} = {1, 0, 0, 0}
Do[{s0, s1, s2, s3} = {s1, s2, s3, Mod[s0 + s1, 2]};
Print [i, " ", {s0, s1, s2, s3}], {i, 15}]
|| {1, 0, 0, 0}
|
1 {0,0,0,1} 2 {0,0,1,0} 3 {0,1,0,0} 4 {1,0,0,1} 5 {0,0,1,1} |
6 {0,1,1,0} 7 {1,1,0,1} 8 {1,0,1,0} 9 {0,1,0,1} 10 {1,0,1,1} |
11 {0,1,1,1} 12 {1,1,1,1} 13 {1,1,1,0} 14 {1,1,0,0} 15 {1,0,0,0} |
Заметим, что состояние в момент идентично состоянию в момент , так что выходная последовательность имеет период 15.
Выходную последовательность регистра можно легко определить с помощью функций Table, Mod и Do пакета "Mathematica"
Clear[s]; {s[0], s[1], s[2], s[3]} = {1, 0, 0, 0};
s[j_] := Mod[s[j-4] + s[j-3], 2];
Table[s[j], {j, 0, 15}]
|| {1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1}
Состояние называется нулевым, если все его компоненты равны 0.
Так как для LFSR длины существуют в точности ненулевых состояний, а нулевое состояние всегда переходит само в себя, можно заключить, что период выходной последовательности никогда не превосходит .
Висновки
Контрольні питання
Задачі
Задача 5.1. Покажите, что функция i удовлетворяет условиям Р1-Р4.
Задача 5.3. Предположим, что на одну букву английского текста приходится по полтора бита информации. Каково расстояние единственности для шифра Цезаря, примененного к английскому тексту? Ответьте на тот же вопрос для криптосистемы Виженера с ключом длины .
Задача 5.4. Рассмотрим источник открытого текста без памяти, выдающий случайную величину , равномерно распределенную на множестве . На выходе канала приемник получает переменную , которая равна с вероятностью , и принимает любое из двух оставшихся значений с вероятностью . Вычислите взаимную информацию величин и .
Задача 5.5. Пусть источник открытых текстов выдает независимые друг от друга буквы , одинаково распределенные на множестве . Распределение вероятностей задается равенствами , и . Рассмотрим две схемы кодирования:
Получившийся открытый текст сначала преобразуется в последовательность из 0 и 1 по одной из приведенных выше схем, а затем шифруется с помощью алгоритма DES. Каково расстояние единственности для каждой из этих схем?
Задача 5.6. Докажите, что одноразовый блокнот является безусловно безопасной системой.