Методы и средства защиты компьютерной информации

РАБОТА 1. ИССЛЕДОВАНИЕ ХАРАКТЕРИСТИК ТЕКСТОВ

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

омощью методов, приведенных ниже.

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

Критерий "хи-квадрат", вероятно, самый распространенный из всех статистических критериев. Он используется не только сам по себе, но и как составная часть многих других тестов. Прежде чем приступить к общему описанию критерия "хи", рассмотрим сначала в качестве примера, как можно было бы применить этот критерий для анализа игры в кости. Пусть каждый раз бросаются независимо две "правильные" кости, причем бросание каждой из них приводит с равной вероятностью к выпадению одного из чисел 1, 2, 3, 4, 5 и 6 вероятности выпадения любой суммы s при одном бросании представлены в таблице:

Например, сумма S=4 может быть получена тремя способами:

1+3, 2+2, 3+1; при 36 возможных исходах это составляет 3/36=1/12=P4

Если бросать кости N раз, можно ожидать, что сумма S появится в среднем nps раз. Например, при 144 бросаниях значение 4 должно появиться около 12~раз. Следующая таблица показывает, какие результаты были в действительности, получены при 144 бросаниях.

Отметим, что фактическое число выпадений отличается от среднего во всех случаях. В этом нет ничего удивительного. Дело в том, что всего имеется 36144 возможных последовательностей исходов для 144 бросаний, и все они равновероятны. Одна из таких последовательностей состоит, например, только из двоек ("змеиные глаза"), и каждый, у кого "змеиные глаза" выпадут подряд 144~раза, будет уверен, что кости поддельные. Между тем эта последовательность так же вероятна, как и любая другая. Каким же образом в таком случае мы можем проверить, правильно ли изготовлена данная пара костей? Ответ заключается в том, что сказать определенно "да" или "нет" мы не можем, но можем дать \EMPH{вероятностный} ответ, т.е. указать, насколько вероятно или невероятно данное событие.

Естественный путь решения нашей задачи состоит в следующем. Вычислим (прибегнув к помощи ЭВМ) сумму квадратов разностей фактического числа выпадений Ys и среднего числа выпадений nps:

Для плохого комплекта костей должны получаться относительно высокие значения V. Возникает вопрос, насколько вероятны такие высокие значения? Если вероятность их появления очень мала, скажем равна 1/100, т.е. отклонение результата от среднего значения на такую большую величину возможно только в одном случае из 100, то у нас есть определенные основания для подозрений. (Не следует забывать, однако, что даже хорошие кости будут давать такое высокое значение V один раз из 100, так что для большей уверенности следовало бы повторить эксперимент и посмотреть, получится ли повторно высокое значение V).

В статистику V все квадраты разностей входят с равным весом, хотя (Y7 - np7) 2, например, вероятно, будет намного больше, чем (Y2 - np2) 2, так как s=7 встречается в шесть раз чаще, чем s=2. Оказывается, что в "правильную" статистику, или по крайней мере такую, для которой доказано, что она наиболее значима, член (Y7 - np7) 2 входит с множителем, который в шесть раз меньше множителя при (Y2 - np2) 2 Таким образом, следует заменить~ (3) на следующую формулу:

Определенную таким образом величину V называют статистикой “хи-квадрат", соответствующей значениям Y2, …, Y12 полученным в эксперименте.

Подставляя в эту формулу значения из (2), получаем

Теперь, естественно, возникает вопрос, является ли значение 7 7/48 настолько большим, что его случайное появление можно считать маловероятным. Прежде чем отвечать на этот вопрос, сформулируем критерий “хи-квадрат" в более общем виде. Предположим, что все возможные результаты испытаний разделены на k категорий. Проводится n независимых испытаний это означает, что исход каждого испытания абсолютно не влияет на исход остальных. Пусть ps вероятность того, что результат испытания попадет в категорию s, и пусть Ys число испытаний, которые действительно попали в категорию s.

Сформируем статистику

В предыдущем примере имелось 11 возможных исходов при каждом бросании костей, так что k=11. [Формулы (4) и (6) различаются только нумерацией: в одном случае она производится от 2 до 12, а в другом от 1 до k.]

Используя тождество

и равенства

можно преобразовать формулу (6) к виду

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

Большим преимуществом рассматриваемого метода является то, что одни и те же табличные значения используются при любых n и любых вероятностях ps. Единственной переменной является v =k - 1. На самом деле приведенные в таблице значение не являются абсолютно точными во всех случаях: это приближенные значения, справедливые лишь при достаточно больших значениях n Как велико должно быть n? Достаточно большими можно считать такие значения n, при которых любое из nps не меньше 5; однако лучше брать n значительно большими, чтобы повысить надежность критерия. Заметим, что в рассмотренных примерах мы брали n=144, и np равнялось всего 4, что противоречит только что сформулированному правилу. Единственная причина этого нарушения кроется в том, что автору надоело бросать кости; в результате числа из таблицы оказались не очень подходящими для нашего случая. Было бы горазда лучше провести эти эксперименты на машине при n=1000 или 10000

Датчики a, b, d прошли испытания удовлетворительно, датчик c находится на грани и должен быть, по-видимому, забракован, а датчики e и f определенно не прошли испытаний. Датчик~f, безусловно, маломощен; датчики c и d обсуждались в литературе, но у них слишком мало значение a. В датчике d реализован метод вычетов в том виде, в каком он был впервые предложен Лемером в 1948г., а в датчике c-линейный конгруэнтный метод с≠0 также в его первоначальном виде (Ротенберг, 1960).

Брюс Шнайер, Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си 816 стр., 2002 г. Издательство: Триумф Дональд Кнут Искусство программирования Том 2.

 Скачать реферат