Неверно что к достоинствам поточных систем относится

Информационные технологии

Математические методы защиты информации

Ниже представлен список вопросов по предмету Математические методы защиты информации МФПУ/МФПА «Синергия»

В асимметричной системе шифрования для независимой работы N абоне.

В поточных шифрах в один момент времени процедура шифрования прои.

В симметричной системе получатель и отправитель используют для ши.

В симметричной системе шифрования для независимой работы N абонен.

В системе открытого распределения ключей Диффи-Хеллмана используе.

В совершенном (идеальном) шифре апостериорные вероятности открыты.

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

Достоинством асимметричных систем шифрования (по сравнению с симм.

Защита информации в системе Диффи-Хеллмана основана на сложности.

Использование симметричного криптоалгоритма использование различн.

Максимальное количество раундов шифрования по стандарту ГОСТ 2814.

Мерой имитостойкости шифра является вероятность успешного …

Метод разделения секрета используется, в первую очередь для сниже.

Моделирование процедуры расшифрования предусматривает …

Неверно, что активная атака, проводимая противником, предусматрив.

Неверно, что к достоинствам симметричных систем шифрования относя.

Неверно, что к недостаткам симметричных систем шифрования относят.

Неверно, что при искусственном формировании речевого сигнала испо.

Одноразовый блокнот проверку целостности сообщения …

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

Основой для формирования алгоритмов симметричного шифрования явля.

Параметр q отечественного стандарта цифровой подписи ГОСТ Р 34.10.

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

Подмена шифрованного сообщения предусматривает.

При зашифровании по стандарту шифрования ГОСТ 28147-89 полное рас.

При моделировании активных действий противника, его обычно ставят.

При рассмотрении практической стойкости шифров предполагается, чт.

Противник, производя подмену или имитацию сообщения исходит из пр.

Протокол Диффи-Хеллмана является протоколом.

Рабочая характеристика шифра – это Средний объем работы W(N), нео.

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

С увеличением полосы пропускания канала возможность голосовой иде.

Спектром сигнала называется эквивалентный сигналу.

Число операций, необходимых для определения использованного ключа.

Электронная цифровая подпись – это …

Источник

Поточный шифр

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

Содержание

История

Потоковые шифры на базе сдвиговых регистров активно использовались в годы войны, ещё задолго до появления электроники. Они были просты в проектировании и реализации.

В 1965 году Эрнст Селмер, главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров. Позже Соломон Голомб, математик Агентства Национальной Безопасности США, написал книгу под названием «Shift Register Sequences» («Последовательности сдвиговых регистров»), в которой изложил свои основные достижения в этой области, а также достижения Селмера.

Режим гаммирования для поточных шифров

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

Расшифрование производится операцией XOR между той же самой гаммой и зашифрованным текстом: .

Очевидно, что если последовательность битов гаммы не имеет периода и выбирается случайно, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательные особенности. Так ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике. Поэтому обычно применяют ключ меньшей длины (например, 128 бит). С помощью него генерируется псевдослучайная гаммирующая последовательность ( она должна удовлетворять постулатам Голомба). Естественно, псевдослучайность гаммы может быть использована при атаке на поточный шифр.

Классификация поточных шифров

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

Синхронные поточные шифры

Синхронные поточные шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от открытого текста и шифротекста.

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

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

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

Самосинхронизирующиеся поточные шифры

Основная идея построения была запатентована в 1946 г. в США.
Определение:
Самосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в которых поток ключей создаётся функцией ключа и фиксированного числа знаков шифротекста.

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

Поточные шифры на регистрах сдвига с линейной обратной связью (РСЛОС)

Теоретическая основа

Есть несколько причин использования линейных регистров сдвига в криптографии:

Определение: Регистр сдвига с линейной обратной связью длины L состоит из L ячеек пронумерованных ,каждая из которых способна хранить 1 бит и имеет один вход и один выход; и синхросигнала (clock), который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции:

На первом шаге:

На втором шаге:

Следующее соотношение описывает в общем виде работу РСЛОС:

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

Обозначим: . Тогда:

Пример: Возьмём неприводимый примитивный многочлен Этот многочлен можно записать, как – выписаны степени, при которых стоят ненулевые коэффициенты.
Запишем в исходном состоянии в ячейки и определим длину периода генератора:

Таблица. Определение периода генератора

Обратная связь	Ячейка0	Ячейка1	Ячейка2
1	0	0	1
0	1	0	0
1	0	1	0
1	1	0	1
1	1	1	0
0	1	1	1
0	0	1	1
1	0	0	1

Период генератора равен На выходе генератора буде последовательность:
Приведём примеры некоторых примитивных многочленов по модулю 2:

Линейная сложность

Линейная сложность бинарной последовательности – одна из самых важных характеристик работы РСЛОС. Поэтому остановимся на этой теме поподробнее.
Прежде чем дать определение линейной сложности введём некоторые обозначения.
— бесконечная последовательность с членами
– конечная последовательность длины , членами которой являются
Говорят, что РСЛОС генерирует последовательность , если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает с . Аналогично, говорят, что РСЛОС генерирует конечную последовательность , если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых членов члены последовательности .
Наконец дадим определение линейной сложности бесконечной двоичной последовательности.
Определение: Линейной сложностью бесконечной двоичной последовательности называется число , которое определяется следующим образом:

Определение:
Линейной сложностью конечной двоичной последовательности называется число , которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых членов .
Свойства линейной сложности: Пусть и – двоичные последовательности. Тогда:
1. Для любого 0″ border=»0″ /> линейная сложность подпоследовательности удовлетворяет неравенствам
2. тогда и только тогда, когда – нулевая последовательность длины .
3. тогда и только тогда, когда .
4. Если – периодическая с периодом , тогда
5.
Эффективным алгоритмом определения линейной сложности конечной двоичной последовательности является алгоритм Берлекемпа-Месси.

Потоковые шифры основанные на РСЛОС. Усложнение

К сожалению, выходная последовательность РСЛОС легко предсказуема. Так, зная 2L знаков выходной последовательности, легко найти исходное заполнение регистра, решив систему линейных уравнений (см. пункт “Поточные шифры на регистрах сдвига с линейной обратной связью”).
Считается, что для криптографического использования выходная последовательность РСЛОС должна иметь следующие свойства:

Существует несколько методов проектирования генераторов ключевого потока, которые разрушают линейные свойства РСЛОС и тем самым делают такие системы криптографически более стойкими:
1. использование нелинейной функции, объединяющей выходы нескольких РСЛОС
2. использование нелинейной фильтрующей функции для содержимого каждой ячейки единственного РСЛОС
3. использование выхода одного РСЛОС для управления синхросигналом одного (или нескольких) РСЛОС.

Нелинейная комбинация генераторов

Известно, что каждая Булева функция может быть записана как сумма по модулю 2 произведений порядков независимых переменных, . Это выражение называется алгебраической нормальной формой функции . Нелинейным порядком функции называется максимальный порядок членов в записи её алгебраической нормальной формы.
Например, Булева функция имеет нелинейный порядок 3. Максимально возможный нелинейный порядок Булевой функции равен количеству переменных
Предположим теперь, что у нас регистров сдвига с линейной обратной связью, их длины попарно различны и больше двух. Все регистры объединены нелинейной функцией , как показано на рисунке. Функция представлена в алгебраической нормальной форме. Тогда линейная сложность потока ключей равна .
Если – попарно взаимно-простые числа, то длина периода ключевого потока равна: . Например, если , то . И длина периода ключевого потока равна .

Пример (генератор Геффа):
В этом генераторе используются три РСЛОС, объединённые нелинейным образом. Длины этих регистров попарно простые числа.
Нелинейную функцию для данного генератора можно записать следующим образом:

Длина периода:

Линейная сложность:

Генератор Геффа криптографически слаб, потому что информация о состояниях генераторов РСЛОС 1 и РСЛОС 3 содержится в его выходной последовательности. Для того чтобы понять это, обозначим -ые выходные биты РСЛОС 1,2,3 и потока ключей, соответственно. Тогда корреляционная вероятность последовательности по отношению к последовательности :

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

Генераторы на нелинейных фильтрах

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

Генераторы основанные на управлении синхросигналом

В нелинейных комбинациях генераторов и генераторах на нелинейных фильтрах перемещение данных во всех РСЛОС контролируется одним синхросигналом.
Основная идея функционирования рассматриваемого типа генераторов – внести нелинейность в работу генераторов потока ключей, основанных на РСЛОС, путём управления синхросигналом одного регистра выходной последовательностью другого.
Есть 2 типа генераторов основанных на управлении синхросигналом:
1. генератор переменного шага
2. сжимающий генератор.

Генератор переменного шага

Основная идея:
РСЛОС 1 используется для управления передвижением битов двух других РСЛОС 2 и 3.

Алгоритм работы:
1. Регистр РСЛОС 1 синхронизован внешним синхросигналом
2. Если на выходе регистра РСЛОС 1 единица, то на регистр РСЛОС 2 подаётся синхросигнал, а РСЛОС 3 повторяет свой предыдущий выходной бит (для начального момента времени предыдущий выходной бит РСЛОС 3 принимается равным 0)
3. Если на выходе регистра РСЛОС 1 ноль, то на регистр РСЛОС 3 подаётся синхросигнал, а РСЛОС 2 повторяет свой предыдущий выходной бит (для начального момента времени предыдущий выходной бит РСЛОС 2 также принимается равным 0)
4. Выходная последовательность битов генератора с переменным шагом является результатом применения операции побитового исключающего ИЛИ к выходным последовательностям регистров РСЛОС 2 и РСЛОС 3.

Увеличение безопасности генераторов с переменным шагом:

Сжимающий генератор

Контролирующий регистр РСЛОС 1 используется для управления выходом РСЛОС 2. Алгоритм:

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

Для увеличения безопасности сжимающего генератора:

Основные отличия поточных шифров от блочных

Большинство существующих шифров с секретным ключом однозначно могут быть отнесены либо к поточным, либо к блочным шифрам. Но теоретическая граница между ними является довольно размытой. Например, используются алгоритмы блочного шифрования в режиме поточного шифрования (пример: для алгоритма DES режимы CFB и OFB).
Рассмотрим основные различия между поточными и блочными шифрами не только в аспектах их безопасности и удобства, но и с точки зрения их изучения в мире:

Теперь о положении в мире:

Проектирование поточных шифров

Согласно Райнеру Рюппелю можно выделить четыре основных подхода к проектированию поточных шифров:

Теоретические критерии Райнера Рюппеля для проектирования поточных систем:

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

Криптоанализ. Атаки на поточные шифры

Все методы криптоанализа поточных шифров обычно подразделяют на силовые (атака «грубой силой»), статистические и аналитические.

Силовые атаки

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

Статистические атаки

Статистические атаки делятся на два подкласса:

Оба метода используют принцип линейной сложности.

Аналитические атаки

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

Корреляционные атаки

Являются наиболее распространёнными атаками для взлома поточных шифров.

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

Существуют следующие подклассы корреляционных атак:

Рассмотрим на примере базовой корреляционной атаки Зигенталера («разделяй и вскрывай»), которая основана на понятии расстояния Хэмминга между двумя двоичными последовательностями одинаковой длины. Применима к комбинирующим генераторам.

Для выявления влияния j-го линейного регистра сдвига (с выходной последовательностью на гамму шифра моделируется часть генератора как двоичный симметричный канал (ДСК). Алгоритм атаки состоит из двух этапов (иногда называемые фазами):

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

Теперь немного о подборе порогового значения и необходимого для успешного криптоанализа количество бит гаммы : Задаём нужные нам вероятности «ложной тревоги» и пропуска истинного начального заполнения .

Например, выбрали , где — длина регистра. А затем из этих условий находим и .

Атаки, основанные на низко-весовых проверках четности

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

Быстрые корреляционные атаки

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

Компромисс «время-память»

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

Состоит из двух этапов:

Примерами этого класса атак являются атака Стива Беббиджа и атака Бирюкова-Шамира.

«Предполагай и определяй»

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

Сложность алгоритма зависит от устройства генератора и от количества предположений.

Источник