Если приращение , то генератор () называется мультипликативным конгруэнтным генератором (МКГ), а если , то смешанным конгруэнтным генератором (СКГ).

«Слабость» ЛКГ и МКГ заключается в том, что если рассматривать последовательные биграммы , то точки , на плоскости будут лежать на прямых из семейства . Для устранения этого недостатка нелинейные конгруэнтные генераторы, среди которых известны: квадратичный конгруэнтный генератор; Генератор Эйхенауэра-Лена с обращением; конгруэнтный генератор, использующий умножение с переносом.

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

, ()

где - параметры генератора. Выбор этих параметров осуществляется на основе следующих двух свойств последовательности ().

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

1). - взаимно простые числа;

2). - кратны , где - любой нечётный простой делитель ;

3). - чётное число, причем

4). Если кратно 9, то либо , либо и .

Свойство . Если , то наибольший период тогда и только тогда, когда - нечётно, - чётно, - нечётное число, удовлетворяющее соотношению

.

Генератор Эйхенауэра-Лена с обращением. Псевдослучайная нелинейная конгруэнтная последовательность Эйхенауэра-Лена с обращением определяется следующим нелинейным рекуррентным соотношением :

(

где - обратный к элемент по модулю , т.е. - параметры генератора.

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

(

Где в отличие от (), «приращение» изменяется во времени и зависит от указанных аргументов нелинейно:

()

Параметрами нелинейного конгруэнтного генератора (), () является .

Рекуррентны в конечном поле. Обращение мультикапликативной конгруэнтной последовательности является линейная рекуррентная последовательность порядка над конечным полем ( - простое число):

 ()

где - коэффициенты рекуррентны, а - начальные значения рекуррентны.

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

()

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

Генераторы Фибоначчи. Общий вид рекуррентного соотношения, определяющего генератор Фибоначчи задаётся уравнением

, ()

где - параметры генератора, . В случае или - целые числа .

4. Первый этап развития криптографии

Защита информации может быть двух видов: шифрование и передача по закрытому каналу.

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

Будем считать, что A (Алиса) - отправитель сообщения, а В (Боб) - корреспондент (получатель) сообщения, Е (Елена) - некий враг.

Классическая система секретной связи показана на рис. 1.

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

Шифрование осуществляется в соответствии с этой подстановкой. Величина не является единственно возможной.

Криптоанализ этого шифра очень прост. Для любого современно языка вычислены частотные характеристики букв, т.е. относительные частоты их появления в “нормальных” текстах.

Модулярный шифр.

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

Гомофоническое шифрование.

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

Полиграммное шифрование.

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

Замена биграмм производится по правилам:

1) если и находятся на одной строке, то биграмма шифруется диаграммой , где буквы и являются правыми соседями букв и соответственно, если правого соседа нет, то берется буква строки.

2) если и находятся на одном столбце, то берутся нижние соседи с аналогичной оговоркой.

3) если , то в незашифрованном тексте между ними вставляется незначащая буква (например, ).

4) при нечетном количестве букв в незашифрованном тексте к нему дописывается незначащая буква.

5) в наиболее вероятном количестве, когда и расположены в разных столбцах и строках, и выбираются, как показано на схеме:

Код Энигма.

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

Код Энигма в своем первоначальном виде потерял свою привлекательность при появлении ЭВМ, т.к. пять барабанов могли обеспечить лишь около ста миллионов ключей, что возможно перебрать за один день.

5. Второй этап развития криптографии

5.1 Шенноновское понятие секретных систем

По Шеннону существует три общих типа секретных систем:

1. Системы маскировки, которые включают в себя применение таких методов, как невидимые чернила, представление сообщения в форме безобидного текста или маскировки криптограммы, и другие методы, с помощью которых факт наличия сообщения скрывается от противника;

2. Тайные системы (например, инвертирование речи), в которых для раскрытия сообщения требуется специальное оборудование;

3. «Собственно» секретные системы, где смысл сообщения скрывается при помощи шифра, кода и т.д., но само существование сообщения не скрывается и предполагается. Что противник обладает любым специальным оборудованием, необходимым для перехвата и записи переданных сигналов.

Математически криптограмма выглядит следующим образом: , где - сообщение, - ключ, т.е. является функцией от и .

Оценка секретных систем.

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

1) Количество секретности.

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

2) Объем ключа.

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

3) Сложность операции шифрования и дешифрования.

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

4) Разрастание числа ошибок.

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

5) Увеличение объема сообщения.

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

Совершенная секретность.

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

Страницы: 1, 2, 3, 4, 5, 6