Розробка імовірнісної моделі криптографічних протоколів (стр. 5 из 19)
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),тоді (М, С) – повідомлення з підписом. Перевірка підпису здійснюється таким чином
С
( mod n) = М (mod n) = М’.Якщо М = М’, то підпис вірний.
1.3. Методика визначення стійкості криптосистем
Є декілька різних критеріїв, які можна було б використовувати для оцінки якості пропонованої секретної системи. Розглянемо найбільш важливі з цих критеріїв.
1. Кількість секретності.
Деякі секретні системи є досконалими в тому сенсі, що положення супротивника не полегшується в результаті перехоплення будь-якої кількості повідомлень. Інші системи, хоч і дають супротивнику деяку інформацію при перехопленні чергової криптограми, але не допускають єдиного «рішення». Системи, що допускають єдине рішення, дуже різноманітні як по витраті часу і сил, необхідних для отримання цього рішення, так і по кількості матеріалу, який необхідно перехопити для отримання єдиного рішення.
2. Об'єм ключа.
Ключ повинен бути переданий з передавального пункту в приймальний пункт у такий спосіб, щоб його не можна було перехопити. Іноді його потрібно запам'ятати. Тому бажано мати ключ настільки малий, наскільки це можливо.
3. Складність операції шифрування і дешифрування. Операції шифрування і дешифрування повинні бути по можливості простими. Якщо ці операції проводяться уручну, то їх складність приводить до втрати часу, появі помилок і т.д. Якщо вони проводяться механічно, то складність призводить до використання великих і дорогих пристроїв.
4. Розростання числа помилок.
У деяких типах шифрів помилка в одній букві, допущена при шифруванні або передачі, приводить до великого числа помилок у розшифрованому тексті. Такі помилки розростаються в результаті операції дешифрування, викликаючи значну втрату інформації і часто вимагаючи повторної передачі криптограми. Природно, бажано мінімізувати це зростання числа помилок.
5. Збільшення об'єму повідомлення.
У деяких типах секретних систем об'єм повідомлення збільшується в результаті операції шифрування. Цей небажаний ефект можна спостерігати в системах, в яких робиться спроба потопити статистику повідомлення в масі нульових символів, що додаються, або де використовуються багатократні заміни.
Основний принцип – принцип Кіркхофа – , який має бути покладений у критосистему, полягає в тому, що стійкість системи має визначатися лише стійкістю ключа. Тобто криптоаналітику відомий весь алгоритм шифрування, крім ключа.
Питання про теоретичну стійкість шифрів вперше було сформульоване Клодом Шенноном: «Наскільки надійна криптосистема, якщо криптоаналітик супротивника має в своєму розпорядженні необмежений час і всі необхідні засоби для аналізу криптограм?». З цим питанням тісно зв'язане наступне питання: «Чи існують шифри, які не міг би розкрити криптоаналітик, що має в своєму розпорядженні скільки завгодно велику криптограму і необмежені обчислювальні ресурси?».
Ідеальний шифр за Шенноном – це шифр, в якому кожен біт шифртекста залежить від кожного біта відкритого тексту і від кожного біта ключа. При виконанні цієї умови відкритий і шифрований тексти будуть статистично незалежні, тобто для будь-якого відкритого тексту а і будь-якої криптограми у