Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации icon

Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации




Скачати 72.32 Kb.
НазваЛекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации
Дата конвертації24.11.2012
Розмір72.32 Kb.
ТипЛекция
1. /Лекции 1_5/Вопросы к лекции 4.doc
2. /Лекции 1_5/Вопросы к лекции 5.doc
3. /Лекции 1_5/Лекция 1.doc
4. /Лекции 1_5/Лекция 2.doc
5. /Лекции 1_5/Лекция 3.doc
6. /Лекции 1_5/Лекция 4.doc
7. /Лекции 1_5/Лекция 5.doc
Лекции 4 в чем заключается свойство непредсказуемости равномерно распределенной случайной последовательности?
Лекции 5 Как устроен линейный конгруэнтный генератор ррсп?
Лекция основные понятия и задачи криптологии > Предмет криптологии, криптография и криптоанализ История криптографии ровесница истории письменности
Лекция элементарные шифры и их свойства
Лекция модели угроз безопасности криптосистем одним из важнейших направлений исследований в теоретической криптографии является создание стойких криптосистем
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации
Лекция псевдослучайные последовательности и методы их генерации > Генераторы случайных и псевдослучайных последовательностей

Лекция 4. ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ И ИХ ТЕСТИРОВАНИЕ




4.1. Свойства данных для формирования ключевой информации


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

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

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

В связи с этим, возникают три тесно связанных между собой вопроса.

1. Что такое случайная равномерно распределенная последовательность, предназначенная для формирования ключевых данных?

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

3. Как определить, что некоторая фиксированная последовательность удовлетворяет требованиям случайности и равномерности?

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

Испытание (наблюдение) случайной величины.

Определение: Дискретной равномерно распределенной случайной последовательностью (РРСП) называется последовательность результатов независимых в совокупности испытаний случайной величины .

Свойства РРСП:

1) Для любого любая - мерная упорядоченная выборка (вектор с компонентами ), имеет равномерное распределение с вероятностью ;

2) Любая подпоследовательность последовательности также РРСП;

3) Сумма по модулю РРCП и любой независимой от нее последовательности также является РРСП;

4) РРСП не может быть предсказуема, т.е. для любого натурального и условная вероятность .

Устройство, реализующее РРСП, называется генератором РРСП.

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

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

Для решения этой задачи, прежде всего, необходимо дать практически применимое определение РРСП.

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

1) Последовательность называется случайной по Шеннону, если энтропия ее максимальна (в последовательности отсутствует избыточность).

По этому определению ГПСЧ, построенные на основе любого алгебраического закона преобразования некоторого начального случайного числа, являются некачественными (ПСЧ получены из относительно короткого вектора – начального заполнения, то они обязательно избыточны, а энтропия всей последовательности равна энтропии начального вектора).

2) Последовательность длины бит называется случайной по Колмогорову, если ее нельзя получить в результате работы какого-либо алгоритма, двоичная запись кратчайшей программы для реализации которого содержит менее бит.

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

3) Последовательность называется случайной (по Блюм, Голдвассер, Микалли и Яо), если не существует полиномиального (вероятностного) алгоритма, который сможет отличить ее от истинно случайной.

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

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

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

Генераторы таких последовательностей называют криптографически стойкими (cryptographically strong). Стойкость, в данном случае, есть не только свойство последовательности (или генератора), но и свойство наблюдателя, а точнее, его вычислительных возможностей.

Для ПСП доказано важное утверждение.

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

4.2. Статистическое тестирование ПСП


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

Алгоритмы этого набора будем называть тестами (критериями) на случайность, а процесс проверки последовательности – тестированием.

Если тест не смог отличить последовательность от случайной, то будем говорить, что последовательность проходит или выдерживает, данный тест. В противном случае, будем говорить, что тест отклоняет последовательность.

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

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

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

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

С каждым тестом связаны два параметра:

1. вероятность ошибки 1-го рода – вероятность напрасно отклонить истинно случайную последовательность, т.е. принять гипотезу , в то время как верна гипотеза (можно сказать, напрасно принять ). Величина α также называется уровнем значимости теста.

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

2. вероятность ошибки 2-го рода – вероятность напрасно принять неслучайную последовательность за случайную, т.е. принять гипотезу при условии, что верна гипотеза .

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

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

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

  2. если , где называется пороговым значением статистики, то принимается гипотеза .

  3. Если , то принимается гипотеза .

Тест называется двусторонним, если при его проверке используется неравенство вида .

Значение определяется из соотношения

,

где – функция распределения вероятностей статистики при условии истинности гипотезы ,

– уровень значимости теста.

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

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

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

Например, для проверки вида распределения тестируемой последовательности можно воспользоваться статистикой :

.

здесь – частота встречаемости символа в последовательности знаков шифрованного текста,

– длина тестируемой последовательности,

– вектор распределения вероятностей символов, соответствующий гипотезе .

Статистика при имеет т.н. распределение с степенями свободы, где . Это распределение табулировано.

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

В случае РРСП имеет место . Пусть величина – квантиль уровня распределения с степенью свободы, соответствующая уровню значимости , т.е. аналог : .

Если для выборки выполняется неравенство: , то принимается гипотеза о случайном характере последовательности, в противном случае – гипотеза отвергается.

Обычно для тестирования используется некий набор тестов.

Количество тестов в наборе определяется исходя из так называемой общей ошибки 1-го рода, т.е. той части случайных последовательностей, которые не пройдут хотя бы один из тестов.

,

Для выбранной величины количество тестов определяется как из соотношения .

Важным фактором «объективного» тестирования, является независимость тестов. Если – события, соответствующие фактам прохождения случайной последовательностью совокупности тестов , то эти тесты являются независимыми, когда

.



Схожі:

Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconВопросы к зачету по дисциплине «основы информатики и вычислительной техники» Для студентов 1-го курса дневной формы обучения
Информация, ее виды и свойства. Способы представления информации в компьютере. Единицы измерения информации
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconДокументи
1. /ПО СЗИ/Учбов_ матер_али/Модуль 1/ЛЗ1-Механизмы обеспечения информационной безопасности операционной...
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconУчебник «Информатика и икт» для 8 класса
Представление информации. Информация, информационные объекты различных видов. Язык как способ представления информации: естественные...
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconДокументи
1. /Аннотация 2.doc
2. /Аннотация.doc
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconЛекция 3 Информационные технологии для организационного управления
...
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconИнформация Свойства и единицы измерения
Информатика это техническая наука, определяющая сферу деятельности, связанную с процессами хранения, преобразования и передачи информации...
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconАлгоритм и его свойства Алгоритм
Каждый алгоритм предполагает наличие некоторых входных данных и приводит за ограниченное время к определённым
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconМетоды формирования информационной компетенции
Задания на поиск информации в справочной литературе, сети Интернет, путем опросов, интервьюирования, работы с литературными первоисточниками,...
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconЛабораторная работа №1 знакомство с microsoft access
Информационной моделью (или структурой данных) называют совокупность взаимосвязанных данных. Базы данных, соответственно типам информационных...
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconЛекция Локальная организация ландшафтов с позиций относительной однородности потоков вещества, энергии и информации Понятие контрастности сред
Территориальные сопряжения геосистем: парадинамические, парагенетические геосистемы
Лекция псевдослучайные последовательности и их тестирование > Свойства данных для формирования ключевой информации iconДокументи
1. /1/Билеты по курсу.doc
2. /1/Вступительная...

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи