2.8 Методи та засоби генерування та розподілу ключів. Приклади розв’язку задач та задачі для самостійного розв’язання
2.8.1 Приклади розв’язку задач
Задача 1.
Визначте допустимі параметри окремих рядків заміни (2.31) для ГОСТ 28147-89.
Розв'язок задачі.
В ГОСТ 28147-89 використовуються підстановки чотири біта в чотири біта, тобто здійснюється підстановка шістнадцяткових символів, тому n=24=16.
Вибравши параметр а=1 із співвідношень (2.32) – (2.34), маємо:
(2.59)
Таким чином рядок кожної із таблиць заміни має відповідати таким умовам:
число інверсій має змінюватися на відрізку від 50 до 70;
число циклів – від 1 до 5;
число зростань – від 7 до 9.
Задача 2.
Визначте параметри ключів підстановки (окремих рядків), що наведені в таблиці 2.12.
Таблиця 2.12 – Ключі підстановки
.
Розв’язок задачі.
Розглянемо перший рядок. Під інверсією розуміється загальне число символів в рядку, які менше символу, що розглядається. Далі знаходиться сума цих величин для кожного із символів рядка. Для першого символу – 14 визначаємо, що меншими від нього є числа 3, 7, 10, 1,0, 11, 12, 8, 4, 6, 9, 5, 13, 2 - всього 14 символів; для символу 3 є числа 1, 0, 2 - всього три числа. Далі для 7 - 6, 0 – 8, 1 - 1, 0 – 0, 11 - 6, 12 - 6, 15 - 7, 8 – 6, 4-1,6- 2, 9 – 2, 5 - 1,13- 1. Всього інверсій 14+3+6+8+1+0+6+6+7+6+1+2+2+1+1=62. Під циклом розуміється кількість переходів між нульовим рядком та відповідним рядком підстановки. Пояснимо на прикладі. Нехай є перестановка, що наведена у таблиці 2.13.
Таблиця 2.13 – Перестановка
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
14 |
3 |
7 |
10 |
1 |
0 |
11 |
12 |
15 |
8 |
4 |
6 |
9 |
5 |
13 |
2 |
Здійснюємо за таблицею 2.13 переходи:
0-14135-0 – це перший цикл, ми розпочали з 0 і прийшли знову в 0 – цикл замкнувся. Пояснимо цикл: нуль першого рядка замінюється на 14 рядка підстановки (другого рядка), далі 14 першого рядка на 13 другого рядка, 13 першого рядка на 5 другого рядка i 5 першого рядка на 0 другого.
Другий цикл будуємо аналогічно:
1 - 3 → 10 → 4 -1
Третій цикл:
2 - 7 → 12 → 9 → 8 →15 - 2
Четвертий цикл:
6 -11 - 6.
Таким чином, рядок ключа має 4 цикли.
Число циклів визначаємо прямо по рядку.
Збільшення такі: 37; 710; 1011; 1112; 1215; 46;6 9;
5 13.
Всього вісім збільшень.
Таким чином у розглянутої таблиці підстановки 62 - інверсії, 4 - цикли по 8 збільшень. Порівнюючи отримані значення з пороговими, що наведені в задачі 1, робимо висновок, що розглянута підстановка є випадковою.
2.8.2 Задачі для самостійного розв’язання
Задача 1. Визначте основні параметри ключа заміни (число інверсій, число циклів та число збільшень), рядки якого наведені у таблиці 2.14.
Таблиця 2.14 – Ключ заміни
j\ki |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
1 |
4 |
10 |
9 |
2 |
13 |
8 |
0 |
14 |
6 |
11 |
1 |
12 |
7 |
15 |
5 |
3 |
2 |
14 |
11 |
4 |
12 |
6 |
13 |
15 |
10 |
2 |
3 |
8 |
1 |
0 |
7 |
5 |
9 |
3 |
5 |
6 |
1 |
13 |
10 |
3 |
4 |
2 |
14 |
15 |
12 |
7 |
6 |
0 |
9 |
11 |
4 |
7 |
13 |
10 |
1 |
0 |
8 |
9 |
15 |
14 |
4 |
6 |
12 |
11 |
2 |
5 |
3 |
5 |
6 |
12 |
7 |
1 |
5 |
15 |
13 |
8 |
4 |
10 |
9 |
14 |
0 |
3 |
11 |
2 |
6 |
4 |
11 |
10 |
0 |
7 |
2 |
1 |
13 |
3 |
6 |
8 |
5 |
9 |
12 |
15 |
14 |
7 |
13 |
11 |
4 |
1 |
3 |
15 |
5 |
9 |
0 |
10 |
14 |
7 |
6 |
8 |
2 |
12 |
8 |
1 |
15 |
13 |
0 |
5 |
7 |
10 |
4 |
9 |
2 |
3 |
14 |
6 |
11 |
8 |
12 |
Прийміть рішення, які рядки ключа відповідають вимогам випадковості згідно з (2.59).
Задача 2. Визначте параметри ключа (блока) заміни, що наведений в таблиці 2.15. Прийміть рішення відносно того, який із рядків задовольняє вимоги (2.59), а яка не задовольняє.
Таблиця 2.15 – Ключ заміни
Ki |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
1 |
11 |
4 |
2 |
13 |
1 |
8 |
5 |
7 |
3 |
14 |
12 |
0 |
6 |
9 |
15 |
10 |
2 |
15 |
13 |
12 |
14 |
10 |
11 |
1 |
9 |
3 |
2 |
5 |
4 |
7 |
8 |
6 |
0 |
3 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
0 |
2 |
4 |
6 |
8 |
10 |
12 |
14 |
4 |
8 |
12 |
4 |
3 |
7 |
5 |
10 |
1 |
15 |
2 |
14 |
9 |
0 |
13 |
11 |
6 |
5 |
6 |
3 |
0 |
13 |
4 |
10 |
11 |
2 |
14 |
1 |
7 |
8 |
9 |
5 |
12 |
15 |
6 |
0 |
15 |
2 |
14 |
3 |
13 |
4 |
12 |
5 |
11 |
6 |
10 |
7 |
9 |
8 |
1 |
7 |
5 |
8 |
1 |
3 |
6 |
9 |
15 |
14 |
7 |
12 |
10 |
13 |
11 |
2 |
4 |
0 |
8 |
0 |
2 |
4 |
6 |
8 |
10 |
12 |
14 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
Задача 3. Розробити алгоритм та програму формування рядків ключа заміни (4 біти в 4 біти), використовуючи випадкові або псевдовипадкові послідовності. Перевірте, що рядки відповідають вимогам (2.59).
Задача 4. Розробити алгоритм та програму визначення основних параметрів ключів заміни, приклади яких наведено в табл.2.14 та 2.15. Визначте за допомогою цих програм властивості ключів, взявши їх із таблиць 2.14 та 2.15 або сформувавши довільно.
Задача 5. Розробити алгоритм та програму формування ключа підстановки типу байт в байт, використовуючи випадкові або псевдовипадкові послідовності. Дослідіть властивості рядків ключа за такими параметрами як число інверсій, циклів та збільшень. Прийміть рішення про придатність вашого ключа для застосування.
Задача 6. Побудуйте схему генератора двійкових випадкових послідовностей, у якого використовувалось би 4 канали незалежного формування випадкових чисел.
Задача 7. Побудуйте схему генератора двійкових випадкових послідовностей, у якого використовувалось би 4 канали незалежного формування випадкових чисел та було б два незалежних виходи зняття двійкових послідовностей.
Задача 8. Розробіть алгоритм та програму підстановки типу байт в байт, якщо вона задається порівнянням:
,
де
–
значення вхідного байта, записаного у
вигляді поліному, а
– зворотний елемент (поліном). Перевірте
правильність формування
таблиці
для
,
де
– номер із класного журнала. Перевірте
властивості підстановки, використовуючи
вирази (2.32) – (2.34).
2.8.3 Контрольні запитання та завдання
1. Поясніть схему генератора випадкових послідовностей з одним або двома каналами формування випадкових бітів.
Яка послідовність вважається випадковою?
Чим відрізняється випадкова послідовність від псевдовипадкової?
Яким чином можна оцінити властивості послідовності за n-им алфавітом?
Які вимоги висуваються до ключа заміни (рядка), що забезпечує одноразову підстановку 4 біти в 4 біти?
Яким чином можна визначити число інверсій
підстановки ступеню n?Яким чином можна визначити число циклів
підстановки ступеню n?Яким чином можна визначити число збільшень
підстановки ступеню n?Сформулюйте вимоги до ключа (блоку) заміни, що використовується в ГОСТ-28147-89.
Сформулюйте вимоги до ключа (блоку) заміни, що використовується в ГОСТ-34.311-95.
Сформулюйте вимоги до таблиць перетворень, що застосовуються в FIPS-197.
Як можна побудувати таблицю підстановки для випадку, коли вхідним елементом є значення байта, а виходом має бути зворотний елемент в полі GF(28).
Визначте значення параметрів збільшень та циклів для першого та другого рядків ключа заміни таблиці 2.15, прийміть рішення про їх сприйнятність.
Визначте значення параметрів інверсій та циклів для сьомого та восьмого рядків ключа заміни таблиці 2.15, прийміть рішення про їх сприйнятність.
Визначте значення числа інверсій, циклів та збільшень для шостого рядка таблиці 2.15, сформулюйте пропозиції про можливість її використання як рядка ключа заміни.
Яким чином можна задати заміну на зворотний елемент та афінне перетворення в FIPS-197 у вигляді однієї розширеної таблиці підстановки? Які недоліки та переваги такого рішення?