Быстрый поиск

Дипломная работа: Розробка імовірнісної моделі криптографічних протоколів

Блок S6

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

Таблиця 1.10

Блок S7

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

Таблиця 1.11

Блок S8

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

4. Вихід С = С1 С2 … С8 перемішується фіксованою підстановкою Р2.

Таблиця 1.12

Підстановка Р2.

16	7	20	21	29	12	28	17	1	15	23	26	5	18	31	10
2	8	24	14	32	27	3	9	19	13	30	6	22	11	4	25

Розклад ключів.

1. У 64-бітовому ключі К усуваються біти 8, 16..., 64. Біти, що залишилися, перемішуються підстановкою Р3.

Таблиця 1.13

Підстановка Р3

57	49	41	33	25	17	9	1	58	50	42	34	26	18
10	2	59	51	43	35	27	19	11	3	60	52	44	36
53	55	47	39	31	23	15	7	62	54	46	38	30	22
14	6	61	53	45	37	29	21	13	5	28	20	12	4

Вихід Р3(К) представляється у вигляді Р3(К) = С0D0, де С0 ліва половина D0 права.

2. Чергове значення СіD обчислюється по схемі

Сi = Li(Сi-1), Di = Li(Di-1),

де Li циклічне зрушення вліво на одну позицію, якщо i = 1, 2, 9, 16. У решт випадків Li зрушення вліво на дві позиції.

3. На цьому етап вихід перемішується підстановкою Р4.

Таблиця 1.14

Підстановка Р4

14	17	11	24	1	5	3	28	15	6	21	10
23	19	12	4	26	8	16	7	27	20	13	2
41	52	31	37	47	55	30	40	51	45	33	48
44	49	39	56	34	53	46	42	50	36	29	32

Дешифрування DES.

Після всіх підстановок, перестановок, операцій XOR і циклічних зрушень можна подумати, що алгоритм дешифрування, різко відрізняючись від алгоритму шифрування, точно також заплутаний. Навпаки, різні компоненти DES були підібрані так, щоб виконувалася дуже корисна властивість: для шифрування і дешифрування використовується один той же алгоритм.

DES дозволя використовувати для шифрування або дешифрування блоку одну і ту ж функцію. Єдина відмінність полягає в тому, що ключі повинні використовуватися в зворотному порядку. Тобто, якщо на етапах шифрування використовувалися ключі К1, К2, К3, ..., K16, то ключами дешифрування будуть K16, K15, K14, ..., К1. Алгоритм, який створює ключ для кожного етапу, також циклічний. Ключ зрушується направо, а число позицій зрушення рівне 0, 1,2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

Опис алгоритму RSA.

Система RSA використовується як для шифрування, так і для підпису.

Вона базується на односторонній функції з «лазівкою» (trapdoor function).

Ця система базується на наступних двох фактах з теорії чисел:

1) задача перевірки числа на простоту порівняно легким;

2) задача розкладання чисел виду п = pq (р і q – прості числа) на множники є дуже важкою, якщо ми знаємо тільки п, а р і q – великі числа (це так зване завдання факторизації).

Виберемо p і q – великі прості числа. Хай модуль n = p×q, функція j(n) = (p-1)×(q-1) – функція Ейлера. Візьмемо довільне 1£ е<j(n) таке, що
НОД(е, j(n)) = 1. Тоді існує єдине 1£ d <j(n) таке, що

ed(modj(n)) = 1. (1.1)

Система шифрування RSA – це система з відкритим ключем, де
е – відкритий, а d – секретний ключі, п – відоме. Якщо 0£ x<n це відкрите повідомлення, то криптограма отримується таким чином:

С = х(mod n).

Сторона, що отримала зашифроване повідомлення обчислює

х’ = Сd (mod n), причому х’ = х.

Доказ:

х = Сd (mod n) = хed (mod n)

Рівність (1.2.1) означає, що для деякого k

ed = kj(n) + 1.

Звідси і iз теореми Ейлера слідує

x’ = xkφ(n) + 1 (mod n) = x.

Те, що і потрібно було довести.

Розглянемо властивості системи RSA

1) Система шифру дешифрує інформацію коректно;

2) Зловмисник, що перехоплює всі повідомлення і що знає всю відкриту інформацію, не зможе знайти початкове повідомлення при великих р і q. Це пояснюється тим, що зловмисник знає тільки відкриті параметри n і e. Для того, щоб знайти d, він повинен знати значення j(n) = (p - l)(q - 1), а для цього, у свою чергу, йому потрібно знати p і q. Взагал кажучи, він може знайти p і q, розклавши n на множники, проте це важке завдання.

Одностороння функція у = xе (mod n), що використовується в системі RSA, володіє так званою «лазівкою», що дозволяє легко обчислити зворотну функцію х = (mod n), якщо відоме розкладання n на прості множники. (Дійсно, легко обчислити j(n) = (p - 1)(q - 1), а потім d = e-1 (mod j(n))) Якщо р і q невідомі, то обчислення значення зворотної функції практично неможливе, а знайти p і q по n дуже важко, тобто знання p і q це «лазівка» або «потайний хід»). Такі односторонні функції з лазівкою знаходять застосування і в інших розділах криптографії.

Відзначимо, що для схеми RSA важливо, щоб кожен абонент вибирав власну пару простих чисел p q, тобто всі модулі n для кожного учасника повинні бути різні (інакше один абонент міг би читати зашифровані повідомлення, призначен для іншого абонента). Проте цього не вимагається від другого відкритого параметра е. Параметр е може бути однаковим у всіх абонентів. Часто рекомендується вибирати е = 3 . Тоді шифрування виконується максимально швидко, всього за два множення.

Підпис RSA.

Хай М повідомлення, яке треба підписати. Підпис отримується за наступним алгоритмом:

С = М(mod n),