47915 (Основи криптографії)

Міністерство освіти і науки України

Чернівецький національний університет

імені Юрія Федьковича

Факультет комп’ютерних наук

Кафедра комп’ютерних систем та мереж

Реферат

Основи криптографії

2007

Вступ

Під криптографією будемо розуміти область знань, що відноситься до методів і засобів перетворення повідомлень у незрозумілу для сторонніх осіб форму, а також перевірки істинності цих повідомлень. Під криптоаналітикою будемо розуміти засоби і методи, спрямовані на подолання криптографічного захисту. Сукупність криптографії та криптоаналітики називається криптологією. Розшифровуванням будемо називати відновлення вихідного повідомлення при відомому ключі шифрування. Дешифруванням будемо називати процес відновлення вихідного повідомлення при невідомому ключі шифрування. Таким чином, ті, кому призначено шифроване повідомлення його розшифровують, а ті, хто перехоплює його, намагаються дешифрувати.

Клод Шеннон у своїй роботі „Теорія связи в секретных системах” узагальнив накопичений до нього досвід розробки шифрів. Вияснилося, що навіть у дуже складних шифрувальних системах можна виділити в якості складових частин шифри заміни, шифри перестановки та їх комбінації. Деякі відомості про ці прості шифри можна знайти у художній літературі, зокрема „Золотий жук” Едгара По і „Пляшущие человечки” Артура Конан Дойла.

Розглянемо два приклади простих шифрів.

Шифр „Сцитала”. Цей шифр відомо з часів війни Спарти проти Афін у V ст. до н.е. Для його реалізації використовувалась т.зв. „сцитала” – циліндричний жезл певного діаметру. На сциталу намотували вузьку папірусну стрічку і на ній писали повідомлення вздовж осі сцитали. Коли стрічку знімали, на ній залишалися незрозумілі літери. Для розшифровки повідомлення адресат намотував стрічку на такий самий жезл і читав повідомлення. В цьому шифрі перетворення оригінального тексту у шифрований зводиться до перестановки літер оригінального тексту. Тому клас таких шифрів отримав назву шифру перестановки.

Шифр Цезаря. Цей шифр реалізує таке перетворення відкритого тексту: кожна літера замінюється третьою після неї літерою алфавіту, який вважається написаним по колу, тобто після „я” йде „а”. Відмітимо, що Цезарь замінював її третьою літерою, але можна міняти і будь-якою іншою. Головне, щоби адресат цього повідомлення знав величину і напрямок цього зсуву. Клас шифрів, до якого відноситься шифр Цезаря, називається шифрами заміни. З цього, напевне зрозуміло, що створення хорошого шифру є задачею непростою. Тому бажано збільшити час життя шифру, але тут зростає імовірність того, що криптоаналітики противника зможуть розкрити шифр і читати зашифровані повідомлення. Якщо у шифрі є змінний „ключ”, то його заміна призводить до того, що розроблені противником методи вже не дадуть ефекту. Під ключем будемо розуміти змінний елемент шифру, який застосовується для шифрування конкретного повідомлення. Наприклад, у шифрі сцитала ключем є діаметр жезлу, а у шифрі Цезаря – величина і напрямок зсуву літер шифротексту відносно літер відкритого. Описані міркування призвели до того, що безпека повідомлень, що шифруються, в першу чергу стала забезпечуватися ключем. Сам шифр, шифромашина або принцип шифрування прийнято вважати відомими суперникові і доступними для попереднього вивчення, але у шифрі з’явився невідомий елемент –ключ, від якого істотно залежать застосовувані перетворення інформації. Тепер користувачі, перш ніж обмінятися шифрованими повідомленнями, повинні обмінятися ключем, за допомогою якого можна прочитати зашифроване повідомлення. А для криптоаналітиків, які хочуть прочитати перехоплене повідомлення, основною задачею є знаходження ключа.

Принципи частотного крипто аналізу

Встановлено, що в будь-якій мові літери абетки зустрічаються нерівномірно. Якщо взяти достатньо великий текст (порядку мільйона символів) загального змісту та підрахувати частоту, з якою кожна літера абетки зустрічається в цьому тексті, ми побачимо, що найчастіше в українських текстах зустрічається літера „О” (0.082), а в російських та англійських – „Е” (0.071 та 0.12 відповідно). Звичайно, в залежності від тематики текстів, частотні характеристики його змінюються, але тенденція залишається незмінною. На цьому факті ґрунтується метод частотного криптоаналізу. Якщо метод шифрування „перехопленої шифровки” не приховує частотних особливостей мови (а саме таким і є шифр Цезаря), то криптоаналітики виконують наступні дії:

1. Підраховують відносні частоти, з якими кожна літера абетки зустрічається в „перехопленому” повідомленні. Робиться це за формулою: частота=кількість/довжина; де кількість – скільки разів літера зустрічається в повідомленні; довжина – кількість літер в повідомленні.

2. Літеру з найбільшою відносною частотою ототожнюють з літерою, яка має найбільшу частоту в таблиці.

3. Визначають величину зсуву.

4. Пробують дешифрувати повідомлення з визначеною в п.3 величиною зсуву. Якщо отримано логічний зв‘язний текст, повідомлення вважається дешифрованим. Якщо зв‘язного тексту не отримано, процедуру продовжують.

5. Літеру з найбільшою відносною частотою ототожнюють з літерою, яка має другу найбільшу частоту в таблиці.

6. Пробують дешифрувати повідомлення, перебираючи частотну таблицю, поки не отримують зв‘язного тексту.

Цим методом Вам необхідно користуватися для криптоаналізу в цій лабораторній роботі.

Криптографічна система RSA (Rivest, Shamir, Adleman), запропонована Рівестом, Шаміром і Едлеманом, належить до криптографічних систем з відкритим ключем. Її стійкість обумовлена великими проблемами при знаходженні розкладання великих простих чисел на множники.

Для того, щоби організувати передачу шифрованих повідомлень за допомогою криптосистеми RSA, необхідно зробити наступне:

1. За допомогою спеціальних алгоритмів згенерувати два великих простих числа p і q, які необхідно тримати у тайні.

2. Повідомити відправнику повідомлень (або розмістити у відкритому каталозі) число n=pq, а також випадкове ціле число Е, взаємно просте з добутком (p-1)(q-1).

3. Для розшифровки повідомлень, зашифрованих на відкритому ключі n, E, отримувачу необхідно мати число D, яке є мультиплікативним оберненим числа Е за модулем (p-1)(q-1), тобто DЕ=1 mod(p-1)(q-1). Знайти таке число дуже просто, оскільки найбільший спільний дільник Е і (p-1)(q-1) якраз і рівний одиниці за вибором Е.

Таким чином, відправник знає свій закритий ключ, n, E, а отримувач, крім того, знає ще свій секретний ключ D.

Довільне відкрите повідомлення можна уявити у вигляді послідовності цілих чисел з деякого інтервалу. Будемо вважати, що відправник передає секретне повідомлення у вигляді X₁,…,X_n 0<X_i<n-1, для всіх і від 1 до k.

Відправник для кожного блоку X_i вираховує

C_i=( X_i^E) mod n (1)

і передає C_i відкритим каналом зв’язку.

Маючи n, E і C_i, отримувач може розшифрувати повідомлення, використовуючи співвідношення

X_i=(C_i^D) mod n. (2)

Розглянемо в якості прикладу випадок p=3, q=11, n=3x11=33, E=7, D=3. Легко переконатися, що кожне з чисел E=7 і DE=21 взаємно прості з (p-1)(q-1)=20. Для передачі повідомлення М=”02” відправнику треба обчислити C=(2⁷) mod 33=29. Отримувач може розшифрувати повідомлення за допомогою такої операції: X=29³ mod 33=2. =2. Якщо ж ми маємо текстове повідомлення, алфавіт якого пронумеровано від 00 до 32 (з пробілом), тоді можна зашифрувати довільне повідомлення російською мовою. Наприклад, якщо ми маємо повідомлення „ПРОВЕРИМ ЗНАНИЕ АРИФМЕТИКИ”, то у зашифрованому вигляді на ключі n=33, E=7 воно буде мати вигляд:

27 25 20 29 14 25 02 12 32 28 07 00 07 02 14 32 00 25 02 26 12 14 06 02 10 02

Зрозуміло, що шифром в даному випадку є шифр простої заміни за табл. 1.

Таблиця 1. Таблиця заміни при шифруванні.

Одним з відомих алгоритмів дешифрування системи RSA є метод ітерацій. Згідно з ним вихідне повідомлення можна отримати з шифрованого повторним шифруванням доти поки не отримаємо відкритий текст.

Приклад 1. Нехай р=383, q= 563, n=215629, E=49. В цьому випадку відкритий текст повністю отримується уже через 10 ітерацій повторного шифрування. Щоби в цьому впевнитися, достатньо довести, що 49¹⁰=1 mod (p-1)(q-1). Виконання цієї рівності можна перевірити навіть на калькуляторі: (49⁴=5764801 -> 49⁴=183017 mod 214684 … 49⁹=56957 mod 214684 -> 49¹⁰= 1 mod 214684).

Інший метод атаки на шифр RSA – метод розкриття чисел p і q. Справа в тому, що n=pq (як і самі ці числа p і q) повинні бути досить великими, щоби розкласти його на множники було дуже складно (в цьому і полягає складність цього алгоритму шифрування). Бажано, щоби p і q вибиралися випадковим чином і не були „дуже близькими” одне до одного. Покажемо, яким чином можна використати близькість значень p і q. Будемо вважати, що p > q (що не накладає зайвих обмежень). Тоді для величин x=( p + q)/2, y=( p – q)/2 справедливе співвідношення: x²-y²=n. Перебираючи у порядку зростання варіанти x > , легко знайти розв’язок рівняння x²-y²=n, так як x=( p + q)/2 буде близьким до у випадку близькості p і q.

Приклад 2. Нехай n=pq=851. Використаємо описаний спосіб для знаходження p і q. Так як =29.17, беремо x=30 і обчислюємо 30²-851=49 і з першої спроби знаходимо розв’язок x=30 і y=7. Таким чином, p=30+7=37, q=30-7=23.

Крім вказаних обмежень на p, q, E, D накладаються й інші обмеження.

Система шифрування RSA може бути застосована для цифрового підпису. У випадку підпису повідомлення М відправник обчислює P=M^E mod n. Отримувач, який має М та Р, перевіряє справедливість співвідношення Р^D=М mod n і впевнюється у справжності повідомлення М.

Приклад 3. Нехай p=3, q=11, n=3x11=33, E=7, D=3. Тоді відправник повідомлення М=”02” обчислює цифровий підпис Р=2⁷ mod 33=29 і відправляє повідомлення „02, 29” отримувачу. Той, в свою чергу, перевіряє справжність повідомлення „02”, обчисливши М=(29³) mod 33=2.

Насправді підписують не саме повідомлення, а його т.зв. хеш-функцію. Спочатку оригінальне повідомлення обробляється деякою функцією, яка має таку властивість, що приймає на вході рядки різної довжини, а на виході видає деякий „дайджест”, як правило, однакової і меншої, ніж вхідна, довжини. Хеш-функція виконує математичні обчислення, у результаті яких обчислюється значення хеш-функції. Хеш-функція може бути дуже простою. Наприклад, вона може виконати підсумовування всіх одиниць двійкового коду, або додати значення кодів всіх літер рядка, що обробляється (т.зв. контрольна сума) і т.д. Головне полягає в тому, що значення хеш-функції повинно залежати від усього вхідного рядка, щоби не можна було (в крайньому разі було б дуже важко) підібрати два різних вхідних рядки з однаковим значенням хеш-функції. Якщо таке трапляється, то кажуть що виникла колізія. Ми будемо користуватися найпростішою хеш-функцією, яка дуже недосконала і може викликати значні колізії. Однак, вона дуже проста і не потребує витрат машинного часу, а також складного програмування. Ця функція просто сумує всі значення символів за табл. 1 за модулем 33:

H(M)= (3)

До отриманого таким чином числа застосовують алгоритм прикладу 3, отримуючи, таким чином, зашифрований цифровий підпис. Отримувач, маючи повідомлення і цифровий підпис, розшифровує текст повідомлення, знаходить хеш-функцію від нього за формулою (3), розшифровує цифровий підпис, і порівнює отримані значення. Якщо вони однакові, повідомлення і цифровий підпис є істинними.

Проблема адміністрування криптографічними ключами вважається основним недоліком симетричних криптоалгоритмів. Цю проблему можна вирішити за допомогою асиметричної криптографії, тобто взагалі не використовувати симетричні криптоалгоритми. Однак такий підхід вважають нераціональним, оскільки асиметричні алгоритми працюють значно повільніше за симетричні і не можуть використовуватися у ряді важливих криптографічних застосувань. Іншим способом розповсюдження ключів є специфічні алгоритми, розроблені спеціально для таких застосувань. Одним з таких алгоритмів відкритого розповсюдження ключів є алгоритм Діффі-Хеллмана. Нехай учасники інформаційного обміну, сторони А і В, домовилися використати цей алгоритм для обміну ключами. Для цього необхідно виконати наступні обчислення. Спочатку А і В обирають велике просте число р, модуль системи. Для цього числа р обирають первісний корінь а. Числа р і а відкрито передають по каналах зв‘язку, так щоб їх мали обидві сторони.

Далі виконується наступний протокол:

1. А генерує ціле велике випадкове число х і відправляє В число:

;