лаб 15. Лаб раб 15. Лабораторные работы

• Название: Лабораторные работы
• Анкор: лаб 15
• Дата: 22.09.2022
• Размер: 0.6 Mb.
• Имя файла: Лаб раб 15.docx
• Тип: Документы; #690117
• страница: 7 из 26

Задание

Вариант задания определяется последней цифрой номера зачетной книжки (0 соответствует 10 варианту).

Сообщения создаются и шифруются на базе алфавита

АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

К открытому тексту был применен шифр «Лесенка». Восстановите сообщение по шифрованному тексту из таблицы 1.
Таблица 1 - Варианты условий к заданию

№ вариан та	Задание
1.	ВЩИТЗЬВЬЛОНЕНИУШИЗЕГАЕТСЮЕНОЙОСВЕПТПЫВЗШТРРОБОПАЕАО МНЛОЛОТМРЯЯЕЬЛОЛЕНА
2.	ЛЕСЕПЕУЕОНЬНЯПЗННМИЬУИЩЮДТКРТЮБПОХЕИООИФАЕНШЕИБЕВО ОИЩЕАСРНИЛВЯОЦСАЕЗТОЙИММРЕЗСТАИСЬАИРИТРНАЫ
3.	МЕЕЕСНЬМТПЦСНРЧЯТЫЗДОЕЕТОЫЕТИСООВЧЛИГЧСЕСИВКИЕОИЕКЛВ САУОНСЕЛОЬЯПНМБИТСОЙНЗОИЕЕЕНФВДОАЛЕНСМО
4.	ВРОСМЕННАЗАРТМНММММИМНИАКНФЦЯСОВУЕАДЕНАНСХТАОИЛЕЛ О ЮЕЖОНФЦЫТЭРЯРЯАБЬДРБНКТОИХЕЛОИМВНЯОИАУЫУА
5.	СААИАЕЬДЛЬЩКТСЕМИБСДОЧКЕЬХЕОЕИИАСЕНОБИОННРЙМРСНЦТЗОЛ ЕВНЦОАСПНТФИЕОСЖСАФИСНЯЬОЕОИМПТНПТИАТЯВЮЙМР
6.	ОЗСЗСЕСЕОИИИЩДАТОТТПНЙФИКЕНДЕПИСЕАИИСАНОАМАЯЯЧДДКТС ИЙЧЫСВОЕЕЕАООЯИСБНЛБНЖНЦЧОЗИЕОЯЕИНТИНБ
7.	СЕЕАСБЕАЕМООЧЯРТОКЕАОЕИМЗСТЕЧЕВОСТЕОАЕТТРЧОНСАОНИСИТО ЖТРНТВЛФАЕИБИТБПООПВНЗНЬЕИПИЯАПДСЩЯ
8.	ОИЯИОРИОМТБЕДННСТРЕВЕКОФНАЬОШАСОСОЫМОНАПНТРМИТНТЕТ УМРЗПЕЕЧРПАЕБОГЛЕОАЦСАСОЬНЛКИУВТВС
9.	ПВАНЩОАЕИНРИЫЯТЗТЫАНРИИСРРТГЕДХВСРЕМСЫУЯТЯАМОАДАИЛЯ У ЛИСЕШЗЫТКОРПАННЯРШЬИНЕАНХТНИЕЧНЕЮАИН
10.	КЕЬИАНЗПДООИАЕИООНННЦААОАТЖЕЛССВНЦОФИЧЩТНВНГИКСАФИ С ОИАИОНОООТОЛНИАТРОЕТКЫЗСАИГЕИДЛЬМЗТУАХМТНЧОДЯ

Содержание отчёта

Отчёт должен содержать:

1. 
   задание к работе;
   
2. 
   программу.
   
3. 
   результаты работы программы.
   

Контрольные вопросы

1. 
   На чем основывается метод перестановок?
   
2. 
   Оцените надежность шифра «Лесенка».
   
3. 
   Дайте определение абсолютной защищенности.
   

Лабораторная работа №5 Генерирование равномерно распределенных псевдослучайных последовательностей.

Цель работы: Освоить основные алгоритмы программной генерации равномерно распределенных псевдослучайных последовательностей

Конгруэнтные генераторы

Линейные и мультипликативные конгруэнтные генераторы

^{Линейнымконгруэнтнымгенератором(ЛКГ) с параметрами (x}0^{, a, c, N) называется} программный генератор РРСП, порождающий псевдослучайную последовательность

x₁, x₂ ,... AA 0, 1, ... , N 1 ^{с помощью рекуррентного соотношения:}

x_t1  (ax_t c) mod N,

t 0, 1, ...

(1)

Параметры этого генератора (1) имеют следующий смысл:

x₀  A

– начальное, или

стартовое, значение, a  A \ {0} – ненулевой множитель, c  A – приращение, N – модуль, равный мощности алфавита A.

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

Перечислим свойства псевдослучайной последовательности, порождаемой ЛКГ.

1. 
   Для общего члена последовательности (1) справедлива формула:
   

^{ t} a^t1 ^

x_t ^ ax₀ 



c^mod N,

a1 _

t 1 .

2. 
   Найдется номер   A, начиная с которого последовательность (1) “зацикливается” с периодом T N– .
   

3. 
   Для любого k≥ 2 подпоследовательность
   

x₀ , x_k, x_2k, ... A, полученная из

псевдослучайной последовательности (1) удалением всех членов, не кратных k, оказывается псевдослучайной последовательностью, порожденной ЛКГ (1) с

^k

c(a^k1)

^{параметрами} x₀ , a, c, N^{, где} a a

mod N^{, c}

a1

mod N.

4. 
   Псевдослучайная последовательность (1), порождаемая ЛКГ, достигает ^{максимального значения периода T}max ^{= N тогда и только тогда, когда выполнены} следующие три условия:
   
   1. 
      c, N– взаимно простые, т.е. НОД(c, N) = 1;
      
   2. 
      число b = a– 1 кратно pдля любого простого числа p< N, являющегося делителем N;
      
   3. 
      число bкратно 4, если Nкратно 4.
      
5. 
   ^{Для МКГ, если x}0^{, N– взаимно простые, a– первообразный элемент по модулю N,} а φ(N) – максимально возможный порядок по модулю N, то псевдослучайная ^{последовательность имеет максимальный период T}max^.
   

6. 
   ^{Для МКГ, если N = 10q, q ≥ 5 и x}0 ^{не кратно 2 или 5, то T}
   

 5 10^q1  ^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.

7. 
   Для МКГ, если
   

N 2^q, q≥ 4, то максимально возможное значение периода

^Tmax

_{ 2}q2 _ ^N

4

^{псевдослучайной последовательности достигается, если x}0 ^{≥ 1 –}

нечетно и вычет a mod 8{3, 5}.

8. 
   “Слабость” ЛКГ и МКГ заключается в том, что если рассматривать
   

последовательные биграммы z^(t) , z^(t) : z^(t)  x, z^(t)  x , то точки

1 2 1

t 2 t1

z^t z^(t) , z^(t) ,

t 1, 2, ...

на плоскости R²

будут лежать на прямых из семейства

1 2

z₂  az₁  c kN,

k 0, 1, ...

Нелинейные конгруэнтные генераторы

Восьмое свойство линейного и мультипликативного конгруэнтных генераторов псевдослучайных последовательностей представляет “слабость” этих генераторов и может ^{активно использоваться для построения криптоатак в целях оценки параметров a, c, x}0^{. Для} устранения этого недостатка используют нелинейные конгруэнтные генераторы псевдослучайных последовательностей. Наибольшее распространение получили три подхода, описание которых приводится ниже.
Квадратичные конгруэнтныегенераторы

Этот алгоритм генерации псевдослучайной последовательности

x_t A 0, 1, ..., N1 определяется квадратичным рекуррентным соотношением:

x  dx²  ax

• 
  cmod N,
  

t 0, 1, ...

(2)

t1 t t

^{где x}0^{, a, c, d A– параметры генератора.}

Квадратичная конгруэнтная последовательность (2) имеет наибольший период

^Tmax ^{= Nтогда и только тогда, когда выполнены следующие условия:}

• 
  c, N– взаимно простые числа;
  
• 
  d, a–1 – кратны p, где p– любой нечетный простой делитель N;
  
• 
  d – четное число, причем:
  

^(a1) mod 2,
_d ^{(a1) mod 4,}



еслиNкратно4,

еслиNкратно2

• 
  если Nкратно 9, то либо dmod 9 = 0, либо dmod 9 = 1 и c∙d mod 9 = 6;
  
• 
  ^{если N = 2q , q ≥ 2, то наибольший период T}max ^{= 2q тогда и только тогда, когда c –} нечетно, d – четно, a – нечетное число, удовлетворяющее соотношению: a= (d+1) mod 4.
  

ГенераторЭйхенауэра–Лена собращением

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

^ax^1  cmod N,



еслиx

 1,

^xt1 ^{ }



t

c, еслиx_t 0

(3)

^{где x1 – обратный к x}t^{элемент по модулю N, т.е. xx1  1 (mod N) ; x}0^{, a, c A– параметры}

t ^{t t}

генератора.

Выбор параметров осуществляется на основании следующего свойства: если

^{a, x}0 ^{– нечетны, c– четно, то генератор (3) имеет максимально возможный период T}

N 2^q,

_{ 2}q1

тогда и только тогда, когда a≡ 1 (mod 4), c≡ 2 (mod 4).
Конгруэнтный генератор, использующий умножение спереносом

max

При этом нелинейная конгруэнтная псевдослучайная последовательность определяется рекуррентным соотношением:

x_t1  ax_t c_t mod N

(4)

где в отличие от (2) «приращение» c_t cx_t1, x_t2 ,..., x₀  изменяется во времени и зависит от указанных аргументов нелинейно:

_c ^{ ax}t1 ^{ c}t1 ^

(5)

^t _{ N} _

^{Параметрами нелинейного конгруэнтного генератора (4), (5) являются x}0^{, c}0^{, a, N.}