Произведите вычисление псевдослучайной последовательности по алгоритму RC4 (n=3) и найдите z1

Произведите вычисление псевдослучайной последовательности по алгоритму RC4 (n=3) и найдите z1, z2, z3, z4 и z5. В качестве секретного ключа используйте последовательность: “3, 2, 1”.
Решение.
Характеристики алгоритма RC4 в приложении к нашей задаче:
а) параметр n = 3;
б) внутреннее состояние RC4 включает массив размером 2n = 23 = 8 слов;
в) внутреннее состояние RC4 включает два счетчика, каждый размером в одно слово;
г) оба счетчика при n = 3 трехбитовые, обозначаемые i и j;
д) вычисления проводятся по модулю 2n = 23 = 8;
е) массив используется как таблица замен, называемая S-бокс, обозначается S; в каждый момент таблица S содержит все возможные 3-битовые числа в перемешанном виде;
ж) конкретная перестановка значений в таблице определяется ключом; так как каждый элемент таблицы принимает значения в промежутке от 0 до 7, то его можно рассматривать либо как число, либо как номер другого элемента в таблице;
з) алгоритм RC4 состоит из двух этапов; на первом подготовительном этапе производится инициализация таблицы замен S; на втором основном этапе вычисляются псевдослучайные числа.
Алгоритм первого этапа (алгоритм 1) – инициализации таблицы S – состоит в следующем. Вначале она заполняется последовательно числами от 0 до 7. Ключ представляется в виде последовательности 3-битовых слов, которыми заполняется другой массив K, такого же размера, как S. Если ключ оказался короче, чем надо, он повторяется нужное число раз. Затем выполняются следующие действия:
п.1) j = 0; i = 0;
п.2) j = (j + Si + Ki) mod 8;
п.3) поменять местами Si и Sj;
п.4) i = i + 1;
п.5) если i < 8, то перейти на п.2
В результате выполнения алгоритма 1 производится начальное заполнение таблицы замен S, причем начальное перемешивание значений производится в зависимости от секретного ключа.
После того, как таблица S подготовлена, начинается генерация случайных 3-битовых слов. Для этого счетчикам i и j присваивается начальное значение 0. Затем для получения каждого нового случайного значения zi выполняются действия в соответствии с алгоритмом 2:
п.1) j = 0; i = 0;
п.2) i = (i + 1) mod 8;
п.3) j = (j + Si) mod 8;
п.4) поменять местами Si и Sj;
п.5) a = (Si + Sj) mod 8;
п.6) zi = Sa
Полученное 3-битовое значение zi может использоваться в качестве ключа для шифрования очередного 3-битового блока входного потока данных.
Приступаем к реализации алгоритма RC4.
Заполняем таблицу S последовательно числами от 0 до 7:
Номер элемента 0 1 2 3 4 5 6 7
Значение элемента 0 1 2 3 4 5 6 7
Подготавливаем таблицу K, записав в неё ключ необходимое число раз:
Номер элемента 0 1 2 3 4 5 6 7
Значение элемента 3 2 1 3 2 1 3 2
Для перемешивания содержимого таблицы S используем алгоритм 1 (все операции выполняются по модулю 8):
Пункт алгоритма Действия Новое i Новое j Таблица S
1 j=0; i=0; 0 0

2 j=j+Si+Ki=0+0+3=3;
3

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 1 2 0 4 5 6 7
4 i=i+1 1

5 i<8, переход на п.2

2 j=j+Si+Ki=3+1+2=6;
6

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 6 2 0 4 5 1 7
4 i=i+1 2

5 i<8, переход на п.2

2 j=j+Si+Ki=6+2+1=1;
1

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 2 6 0 4 5 1 7
4 i=i+1 3

5 i<8, переход на п.2

2 j=j+Si+Ki=1+0+3=4;
4

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 2 6 4 0 5 1 7
4 i=i+1 4

5 i<8, переход на п.2

2 j=j+Si+Ki=4+0+2=6;
6

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 2 6 4 1 5 0 7
4 i=i+1 5

5 i<8, переход на п.2

2 j=j+Si+Ki=6+5+1=4;
4

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 2 6 4 5 1 0 7
4 i=i+1 6

5 i<8, переход на п.2

2 j=j+Si+Ki=4+0+3=7;
7

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 2 6 4 5 1 7 0
4 i=i+1 7

5 i<8, переход на п.2

2 j=j+Si+Ki=7+0+2=1;
1

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 3 0 6 4 5 1 7 2
4 i=i+1 8

5 i<8, конец алгоритма

После выполнения алгоритма 1 получена готовая таблица S:
Номер элемента 0 1 2 3 4 5 6 7
Значение элемента 3 0 6 4 5 1 7 2
Генерируем первые пять 3-битовых чисел псевдослучайной последовательности, применяя алгоритм 2:
Вычисление Пункт алгоритма Действия Новое i Новое j Новое a Таблица S
z1 1 j=0; i=0 0 0

2 i=i+1 1

3 j=j+Si=0+0=0
0

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 3 6 4 5 1 7 2

5 a= Si+Sj=3+0=3

3

6 z1=S3=4

z2 2 i=i+1 2

3 j=j+Si=0+6=6
6

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 3 7 4 5 1 6 2

5 a= Si+Sj=7+6=5

5

6 z2=S5=1

z3 2 i=i+1 3

3 j=j+Si=6+4=2
2

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 3 4 7 5 1 6 2

5 a= Si+Sj=7+4=3

3

6 z3=S3=7

z4 2 i=i+1 4

3 j=j+Si=2+5=7
7

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 3 4 7 2 1 6 5

5 a= Si+Sj=2+5=7

7

6 z4=S5=1

z5 2 i=i+1 5

3 j=j+Si=7+1=0
0

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 1 3 4 7 2 0 6 5

5 a= Si+Sj=0+1=7

6

6 z5=S6=6

Вычисление псевдослучайной последовательности по алгоритму RC4 дало следующие результаты: z1=4, z2=1, z3=7, z4=1 и z5=6. Числа имеют размер n=3 бита, то есть имеют значения от 0 до 7.
Практическое занятие №3.
Поточные шифры и генераторы псевдослучайных чисел.
Упражнение 1.
Определите первые 20 бит псевдослучайной последовательности, получаемой с помощью генератора ПСЧ на основе линейного сдвигового регистра, изображенного на рисунке, если начальное значение регистра следующее:
а) b4=0, b3=0, b2=0, b1=1;
б) b4=1, b3=1, b2=0, b1=1.

Решение.
а).
Номер состояния Внутреннее состояние регистра Результат вычисления функции обратной связи
f = b1 b4 Извлекаемый бит b1

b4 b3 b2 b1

0 0 0 0 1 1 1
1 1 0 0 0 1 0
2 1 1 0 0 1 0
3 1 1 1 0 1 0
4 1 1 1 1 0 1
5 0 1 1 1 1 1
6 1 0 1 1 0 1
7 0 1 0 1 1 1
8 1 0 1 0 1 0
9 1 1 0 1 0 1
10 0 1 1 0 0 0
11 0 0 1 1 1 1
12 1 0 0 1 0 1
13 0 1 0 0 0 0
14 0 0 1 0 0 0
15 0 0 0 1 1 1
16 1 0 0 0 1 0
17 1 1 0 0 1 0
18 1 1 1 0 1 0
19 1 1 1 1 0 1
б).
Номер состояния Внутреннее состояние регистра Результат вычисления функции обратной связи
f = b1 b4 Извлекаемый бит b1

b4 b3 b2 b1

0 1 1 0 1 0 1
1 0 1 1 0 0 0
2 0 0 1 1 1 1
3 1 0 0 1 0 1
4 0 1 0 0 0 0
5 0 0 1 0 0 0
6 0 0 0 1 1 1
7 1 0 0 0 1 0
8 1 1 0 0 1 0
9 1 1 1 0 1 0
10 1 1 1 1 0 1
11 0 1 1 1 1 1
12 1 0 1 1 0 1
13 0 1 0 1 1 1
14 1 0 1 0 1 0
15 1 1 0 1 0 1
16 0 1 1 0 0 0
17 0 0 1 1 1 1
18 1 0 0 1 0 1
19 0 1 0 0 0 0

Упражнение 2.
Определите период псевдослучайных последовательностей, получаемых с помощью генератора ПСЧ на основе сдвигового регистра с обратной связью из упражнения 1.
Решение.
Поскольку генератор ПСЧ на основе сдвигового регистра с обратной связью из упражнения 1 состоит из четырёх разрядов, то максимально возможный период псевдослучайной последовательности равен 24 – 1 = 15 (исключается нулевое состояние регистра).
В случаях а) и b) упражнения 1 совпадают состояния регистров 0 и 15, что дает длину последовательности бит, равную 15.
В целом эта последовательность имеет циклический характер и одна последовательность от другой отличается только началом отсчета.

Упражнение 3.
Произведите вычисление псевдослучайной последовательности по алгоритму RC4 (n=3) и найдите z1, z2, z3, z4 и z5. В качестве секретного ключа используйте последовательность: 1, 2, 3.
Решение.
Приступаем к реализации алгоритма RC4.
Заполняем таблицу S последовательно числами от 0 до 7:
Номер элемента 0 1 2 3 4 5 6 7
Значение элемента 0 1 2 3 4 5 6 7
Подготавливаем таблицу K, записав в неё ключ необходимое число раз:
Номер элемента 0 1 2 3 4 5 6 7
Значение элемента 1 2 3 1 2 3 1 2
Для перемешивания содержимого таблицы S используем алгоритм 1 (все операции выполняются по модулю 8):
Пункт алгоритма Действия Новое i Новое j Таблица S
1 j=0; i=0; 0 0

2 j=j+Si+Ki=0+0+1=1;
1

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 1 0 2 3 4 5 6 7
4 i=i+1 1

5 i<8, переход на п.2

2 j=j+Si+Ki=1+0+2=3;
3

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 1 3 2 0 4 5 6 7
4 i=i+1 2

5 i<8, переход на п.2

2 j=j+Si+Ki=3+2+3=0;
0

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 2 3 1 0 4 5 6 7
4 i=i+1 3

5 i<8, переход на п.2

2 j=j+Si+Ki=0+0+1=1;
1

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 2 0 1 3 4 5 6 7
4 i=i+1 4

5 i<8, переход на п.2

2 j=j+Si+Ki=1+4+2=7;
7

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 2 0 1 3 7 5 6 4
4 i=i+1 5

5 i<8, переход на п.2

2 j=j+Si+Ki=7+5+3=7;
7

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 2 0 1 3 7 4 6 5
4 i=i+1 6

5 i<8, переход на п.2

2 j=j+Si+Ki=7+6+1=6;
6

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 2 0 1 3 7 4 6 5
4 i=i+1 7

5 i<8, переход на п.2

2 j=j+Si+Ki=6+5+2=5;
5

3 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 2 0 1 3 7 5 6 4
4 i=i+1 8

5 i<8, конец алгоритма

После выполнения алгоритма 1 получена готовая таблица S:
Номер элемента 0 1 2 3 4 5 6 7
Значение элемента 2 0 1 3 7 5 6 4
Генерируем первые пять 3-битовых чисел псевдослучайной последовательности, применяя алгоритм 2:
Вычисление Пункт алгоритма Действия Новое i Новое j Новое a Таблица S
z1 1 j=0; i=0 0 0

2 i=i+1 1

3 j=j+Si=0+0=0
0

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 2 1 3 7 5 6 4

5 a= Si+Sj=2+0=2

2

6 z1=S2=1

z2 2 i=i+1 2

3 j=j+Si=0+1=1
1

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 1 2 3 7 5 6 4

5 a= Si+Sj=2+1=3

3

6 z2=S3=3

z3 2 i=i+1 3

3 j=j+Si=1+3=4
4

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 1 2 7 3 5 6 4

5 a= Si+Sj=7+3=2

2

6 z3=S2=2

z4 2 i=i+1 4

3 j=j+Si=4+3=7
7

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 1 2 7 4 5 6 3

5 a= Si+Sj=4+3=7

7

6 z4=S7=3

z5 2 i=i+1 5

3 j=j+Si=7+5=4
4

4 поменять Si и Sj

Номер 0 1 2 3 4 5 6 7

Значение 0 1 2 7 5 4 6 3

5 a= Si+Sj=4+5=1

1

6 z5=S1=1

Вычисление псевдослучайной последовательности по алгоритму RC4 дало следующие результаты: z1=1, z2=3, z3=2, z4=3 и z5=1. Числа имеют размер n=3 бита, то есть имеют значения от 0 до 7.

Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!:

четырнадцать + 7 =

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.

Adblock detector