6.1. Метод средних квадратов

а) Выбирается произвольное целое 2k-значное числоx₀, которое возводится в квадрат, в результате получается 4k-значное число, из него выбираются средние 2kзнака, которые образуют следующее случайное число. Процедура повторяется нужное число раз.

б) Берутся два произвольных 2k-значных числа, которые перемножаются и дополняются до 4k-значности. Из середины берутся 2kзнака, следующее число получается из произведения полученного числа и предыдущего.

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

6.2. Мультипликативный метод

Задаются константы Cиm. Берется произвольное число, следующим псевдослучайным числом будет текущее, умноженное наCи разделенное по модулюm.

6.3. Аддитивный метод (генератор Фибоначчи)

Определяется цело число m. Берутся два целых числа. Следующее число равно сумме двух предыдущих, взятой по модулюm.

6.4. Линейный метод

Определяется набором целых чисел a[j],j[1,k] и целымm. Первоначально берутсяkцелых чисел. Следующее псевдослучайное число равно сумме поjот 1 доkпроизведенийa[j]x_i+1-jделенной по модулюm.

6.5. Комбинированный метод

Берется целое 2^k-значное числоx₀. Число

x₀’ представляет собой последние 2kразряда квадратаx₀,

x₀’’ – первые 2kразряда произведенияCx₀’ (С – целое число),

x₀’’’ – первые 2kразряда квадратаx₀’’,

x₀’’’’ – последние 2kразряда квадратаx₀’’’,

x₀’’’’’ – суммаx₀’’ иx₀’’’’.

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

Вопросы по теме

1. Случайные и псевдослучайные величины

2. Основные алгоритмы генерации псевдослучайной последовательности

7. Кодирование информации

7.1. Кодирование как средство криптографической защиты информации

Шифр простой подстановки

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

Шифр Вижинера

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

Шифрование гаммированием.

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

DES

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