лаб 15. Лаб раб 15. Лабораторные работы
Скачать 0.6 Mb.
|
ЗаданиеВариант задания определяется последней цифрой номера зачетной книжки (0 соответствует 10 варианту). Сообщения создаются и шифруются на базе алфавита АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.К открытому тексту был применен шифр «Лесенка». Восстановите сообщение по шифрованному тексту из таблицы 1. Таблица 1 - Варианты условий к заданию
Содержание отчётаОтчёт должен содержать:
Контрольные вопросы
Лабораторная работа №5 Генерирование равномерно распределенных псевдослучайных последовательностей. Цель работы: Освоить основные алгоритмы программной генерации равномерно распределенных псевдослучайных последовательностей Конгруэнтные генераторыЛинейные и мультипликативные конгруэнтные генераторыЛинейнымконгруэнтнымгенератором(ЛКГ) с параметрами (x0, a, c, N) называется программный генератор РРСП, порождающий псевдослучайную последовательность x1, x2 ,... AA 0, 1, ... , N 1 с помощью рекуррентного соотношения: xt1 (axt c) mod N, t 0, 1, ... (1) Параметры этого генератора (1) имеют следующий смысл: x0 A – начальное, или стартовое, значение, a A \ {0} – ненулевой множитель, c A – приращение, N – модуль, равный мощности алфавита A. Если приращение c = 0, то генератор (1) называется мультипликативнымконгруэнтнымгенератором(МКГ), а если c ≠ 0, то смешаннымконгруэнтнымгенератором(СКГ). Перечислим свойства псевдослучайной последовательности, порождаемой ЛКГ.
t at1 xt ax0 cmod N, a1 t 1 .
x0 , xk, x2k, ... A, полученная из псевдослучайной последовательности (1) удалением всех членов, не кратных k, оказывается псевдослучайной последовательностью, порожденной ЛКГ (1) с k c(ak1) параметрами x0 , a, c, N, где a a mod N, c a1 mod N.
5 10q1 N max 20 тогда и только тогда, когда вычет a mod 200 принимает одно из следующих значений: 3, 11,13, 19, 21,27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91, 109, 117, 123, 131, 133, 139, 141, 147, 163, 171, 173, 179, 181, 187, 189, 197.
N 2q, q≥ 4, то максимально возможное значение периода Tmax 2q2 N 4 псевдослучайной последовательности достигается, если x0 ≥ 1 – нечетно и вычет a mod 8{3, 5}.
последовательные биграммы z(t) , z(t) : z(t) x, z(t) x , то точки 1 2 1 t 2 t1 zt z(t) , z(t) , t 1, 2, ... на плоскости R2 будут лежать на прямых из семейства 1 2 z2 az1 c kN, k 0, 1, ... Нелинейные конгруэнтные генераторыВосьмое свойство линейного и мультипликативного конгруэнтных генераторов псевдослучайных последовательностей представляет “слабость” этих генераторов и может активно использоваться для построения криптоатак в целях оценки параметров a, c, x0. Для устранения этого недостатка используют нелинейные конгруэнтные генераторы псевдослучайных последовательностей. Наибольшее распространение получили три подхода, описание которых приводится ниже. Квадратичные конгруэнтныегенераторы Этот алгоритм генерации псевдослучайной последовательности xt A 0, 1, ..., N1 определяется квадратичным рекуррентным соотношением: x dx2 ax
t 0, 1, ... (2) t1 t t где x0, a, c, d A– параметры генератора. Квадратичная конгруэнтная последовательность (2) имеет наибольший период Tmax = Nтогда и только тогда, когда выполнены следующие условия:
(a1) mod 2, d (a1) mod 4, еслиNкратно4, еслиNкратно2
ГенераторЭйхенауэра–Лена собращением Псевдослучайная нелинейная конгруэнтная последовательность Эйхенауэра–Лена с обращением определяется следующим нелинейным рекуррентным соотношением: ax1 cmod N, еслиx 1, xt1 t c, еслиxt 0 (3) где x1 – обратный к xtэлемент по модулю N, т.е. xx1 1 (mod N) ; x0, a, c A– параметры t t t генератора. Выбор параметров осуществляется на основании следующего свойства: если a, x0 – нечетны, c– четно, то генератор (3) имеет максимально возможный период T N 2q, 2q1 тогда и только тогда, когда a≡ 1 (mod 4), c≡ 2 (mod 4). Конгруэнтный генератор, использующий умножение спереносом max При этом нелинейная конгруэнтная псевдослучайная последовательность определяется рекуррентным соотношением: xt1 axt ct mod N (4) где в отличие от (2) «приращение» ct cxt1, xt2 ,..., x0 изменяется во времени и зависит от указанных аргументов нелинейно: c axt1 ct1 (5) t N Параметрами нелинейного конгруэнтного генератора (4), (5) являются x0, c0, a, N. |