Найпоширеніші методи шифрування

Шифр Цезаря:
симетричний алгоритм шифрування підстановками. Використовувався римським імператором Юлієм Цезарем для приватного листування.
Принцип дії полягає в тому, щоб циклічно зсунути алфавіт, а ключ — це кількість літер, на які робиться зсув.
Якщо зіставити кожному символу алфавіту його порядковий номер (нумеруючи з 0), то шифрування і дешифрування можна виразити формулами:

де

— символ відкритого тексту,

— символ шифрованого тексту,

— потужність алфавіту, а

— ключ.
Можна помітити, що суперпозиція двох шифрувань на ключах

є просто шифруванням на ключі

. Більш загально, множина шифруючих перетворень шифру Цезаря утворює групу

Шифр Цезаря має замало ключів — на одиницю менше, ніж літер в абетці. Тому перебрати усі ключі не складає особливої роботи. Дешифрування з одним з ключів дасть нам вірний відкритий текст.
Також зламати шифр Цезаря також можна, як і звичайний підстановочний шифр, у зв’язку з тим, що частота появи кожної літери в шифртексті збігається з частотою появи у відкритому тексті. Якщо припустити, що частота появи літер у відкритому тексті приблизно відповідає середньостатистичній відносній частоті появи літер в текстах мови, на якій написано повідомлення, тоді ключ знаходиться зіставленням перших декількох літер, що трапляються найчастіше у відкритому та зашифрованому текстах. Тобто за допомогою методу частотного криптоаналізу. [5]
Шифр Віженера:
поліалфавітний шифр, який у якості ключа використовує слово. Ключове слово повторюється, поки не отримано гаму, рівну довжині повідомлення.
Отримав назву на честь Блеза де Виженера. C_i = (P_i + K_j) mod 33 (Pі, Kj, Ci – місце в алфавіті виражене через цифри). Сі – буква, яку потрібно зашифрувати, Рі – буква по верхньому ряду, Кі – буква по нижньому ряду таблиці.

По вертикалі вибираємо літери відкритого тексту, а по горизонталі — ключа, на перетині цих значень отримуємо знаки шифротексту. Наприклад:
Відкритий текст: «полі/алфа/вітн/ий ши/фр»
Ключ: «ключ/ключ/ключ/кл юч/кл»
Шифротекст: «аайд/кьтч/мцрі/фш цґ/дв». [6]

Шифр Вермана:
у криптографії ця система шифрування винайдена в 1917 році співробітниками AT&T Джозефом Моборном і Гільбертом Вернамом.
Для відтворення шифртексту відкритий текст об'єднується операцією «виключне АБО» з ключем (названим одноразовим блокнотом або шифроблокнотом). При цьому ключ повинен володіти трьома критично важливими властивостями:
1. Бути справді випадковим;
2. Збігатися з розміром з заданим відкритим текстом;
3. Застосовуватися тільки один раз.
Шифр названий на честь телеграфіста AT&T Гільберта Вернама, що в 1917 році побудував телеграфний апарат, який виконував цю операцію автоматично - треба було тільки подати на нього стрічку з ключем. Не будучи шифрувальником, тим не менше, Вернам вірно помітив важливу властивість свого шифру - кожна стрічка повинна використовуватися тільки один раз і після цього знищуватися.
В 1949 році Клод Шеннон опублікував роботу, в якій довів абсолютну стійкість шифру Вернама. Інших шифрів з цією властивістю не існує. Це по суті означає, що шифр Вернама є найбезпечнішою криптосистемою з усіх можливих. При цьому умови, яким повинен задовольняти ключ, настільки сильні, що практичне використання шифру Вернама є важко здійсненним. Тому він використовується тільки для передачі повідомлень найвищої секретності.
На початку 20 ст. для передачі повідомлень все ширше і ширше використовувалися телетайпи. Тому потрібні були методи, що дозволяють шифрувати текст не до того, як він потрапляє до телеграфіста, а безпосередньо в момент передачі, і, відповідно, розшифровувати в момент прийому.
Подальше вдосконалення методу, запропонованого Вернамом, належить майбутньому начальнику зв'язку військ США Джозеф Моборну, що об'єднав хаотичність «гами», на яку спирався Вернам у своїй системі «автоматичного шифрування», з використовуваним у той час у військах правилом «одноразового шифрблокнота». Ідея Моборна полягала в тому, що кожна випадкова «гама» повинна використовуватися один, і тільки один раз. При цьому для шифрування кожного знака всіх текстів, які вже передані або будуть передані в найближчому майбутньому, повинен застосовуватися абсолютно новий і такий, що не піддається передбаченню знак «гами».
На практиці можна один раз фізично передати носій інформації з довгим дійсно випадковим ключем, а потім по мірі необхідності пересилати повідомлення. На цьому заснована ідея шифроблокнотів: шифрувальник при особистій зустрічі забезпечується блокнотом, кожна сторінка якого містить ключ. Такий же блокнот є і у приймаючої сторони. Використані сторінки знищуються. Крім того, якщо є два незалежних канали, в кожному з яких ймовірність перехоплення низька, але відрізняється від нуля, шифр Вернама також можна застосувати: по одному каналу можна передати зашифроване повідомлення, по другому - ключ. Для того, щоб розшифрувати повідомлення, перехоплювач повинен прослуховувати обидва канали.
Шифр Вернама може застосовуватися, якщо є односторонній захищений канал: ключ передається в одну сторону під захистом каналу, повідомлення в іншу сторону захищаються ключем.
У період між двома світовими війнами в більшості країн з'являються електромеханічні шифратори. Вони були двох типів. Перший - пристрій, що складається з комутаційних дисків та механізму зміни їх кутових положень. За обома сторонами комутаційного диска розміщені контакти, відповідні алфавіту відкритого та шифрованого тексту. Контакти ці з'єднуються між собою відповідно до деякого правила підстановки, що зветься комутацією диска. Ця комутація визначає заміну літер в початковому кутовому положенні. При зміні кутового положення диска змінюється і правило підстановки. Таким чином, ключ шифрування містить кілька невідомих: схему з'єднання контактів і початкове кутове положення. Якщо після шифрування кожної літери міняти кутове положення диска - отримаємо багато алфавітне шифрування. Ще більш складний пристрій отримаємо, з'єднавши послідовно кілька дисків, кутові положення яких змінюються з різною швидкістю.
Широко відома шифрмашина «Енігма», якою були оснащені німецькі війська часів Другої світової війни, є типовим прикладом пристрою на комутаційних дисках. Конструктивно «Енігма» походила на звичайну друкарську машинку, тільки натискання клавіші призводило не до удару молоточка по паперу, а створювало електричний імпульс, що надходив у схему криптоперетворення. Американська шифрмашина М-209 - типовий приклад другого типу шифратора.
Таким чином, перед Другою світовою війною всі провідні країни мали на озброєнні електромеханічні шифрсистеми, що володіють високою швидкістю обробки інформації і високою стійкістю. Вважалося, що застосовувані системи неможливо розшифрувати і криптоаналізу більше робити абсолютно нічого. Як часто буває, ця думка була згодом спростована, і дешифровщики були безпосередніми учасниками бойових дій.
Завдяки накладеним обмеженням на ключ, в 1949 році Клод Шенон довів, що шифр Вернама є абсолютно криптостійким. Але:
1. Для роботи шифру Вернама необхідна дійсно випадкова послідовність нулів та одиниць (ключ). За визначенням, послідовність, отримана з використанням будь-якого алгоритму, є не зовсім випадковою, а псевдовипадковою. Тобто, потрібно отримати випадкову послідовність неалгорітмічно (наприклад, використовуючи радіоактивний розпад ядер, створений електронним генератором білий шум або інші досить випадкові події).
2. Проблемою є таємна передача послідовності та збереження її в таємниці. Якщо існує надійно захищений від перехоплення канал передачі повідомлень, шифри взагалі не потрібні: секретні повідомлення можна передавати з цього каналу. При цьому, оскільки довжина ключа така ж, як і довжина повідомлення, передати його не простіше, ніж повідомлення. Шифроблокнот на фізичному носії можна вкрасти або скопіювати.
3. Можливі проблеми з надійним знищенням використаної сторінки. Цьому схильні як паперові сторінки блокнота, так і сучасні електронні реалізації з використанням компакт-дисків або флеш-пам'яті.
4. Якщо третя сторона якимось чином дізнається повідомлення, вона легко відновить ключ і зможе підмінити повідомлення на інше такої ж довжини.
5. Шифр Вернама чутливий до будь-якого порушення процедури шифрування. Наприклад, контррозвідка США часто розшифровувала радянські та німецькі послання через неточності генератора випадкових чисел. Бували випадки, коли одна і та ж сторінка блокнота застосовувалася двічі - США також розшифровували такі послання. [7]

Наприклад:
Слово "Москаленко" ключ 57065
1 листок: 38902...
2 листок: 57065 23252 82110 22152 42125
3 листок: 23056...
Текст "привет мир" ключ 57065
1 листок: 28763...
2 листок: 73521...
3 листок: 57065 26271 91215 29432 31927
Кодування алфавіту виконуватиметься в такій послідовності: 0 – 00…, 9 – 09…, а – 10…, я – 43.

RSA— криптографічна система з відкритим ключем.
RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису. Алгоритм використовується у великій кількості криптографічних застосунків.
Опис алгоритму:
Безпека алгоритму RSA побудована на принципі складності факторизації цілих чисел. Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.
Для того, щоб згенерувати пари ключів виконуються такі дії:
вибираються два великі прості числа

приблизно 512 біт завдовжки кожне;
обчислюється їх добуток

;
обчислюється функція Ейлера

;

вибирається ціле

таке, що

та

взаємно просте з

;

за допомогою розширеного алгоритму Евкліда знаходиться число

таке, що

;

Число

називається модулем, а числа

— відкритою й секретною експонентами відповідно. Пари чисел

є відкритою частиною ключа, а

— секретною. Числа

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

обчислюється

.
Число

використовується в якості шифротексту. Для розшифрування потрібно обчислити

.
Неважко переконатися, що при розшифруванні ми відновимо вихідне повідомлення:

З умови

випливає, що

для деякого цілого

, отже

Згідно з теоремою Ейлера:

, тому

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

вибирається невеликим, звичайно 3, 17 або 65537 (2 обрати не можна, бо

повинно бути взаємно простим із

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

до степеня 17 потрібно виконати тільки 5 операцій множення:

Вибір малого значення відкритого показника може призвести до розкриття повідомлення, якщо воно відправляється відразу декільком одержувачам, але ця проблема вирішується за рахунок доповнення повідомлень.
Значення секретного показника

повинне бути досить великим. У 1990 році Міхаель Вінер показав, що якщо

, то є ефективний спосіб обчислити

по

. Однак, якщо значення

вибирається невеликим, то

виявляється досить великим і проблеми не виникає.
Система RSA використовується для захисту програмного забезпечення й у схемах цифрового підпису. Також вона використовується у відкритій системі шифрування PGP.
Через низьку швидкість шифрування (близько 30 кбіт/сек при 512 бітному ключі на процесорі 2 ГГц), повідомлення звичайно шифрують за допомогою продуктивніших симетричних алгоритмів з випадковим ключем (сеансовий ключ), а за допомогою RSA шифрують лише цей ключ.
Алгоритм електронного цифрового підпису Ель Гамаля (EGSA):
Надійний та зручний для реалізації на персональних комп’ютерах алгоритм цифрового підпису був розроблений у 1984 році американцем арабського походження Тахером Ель Гамалем. У 1991 році Національний інститут стандартів (НІСТ) США обґрунтував перед комісією Конгресу США вибір цього алгоритму як бази для відповідного національного стандарту. Найменування EGSA має походження від слів El Gamal Signature Algorithm (алгоритм цифрового підпису Ель Гамаля). Ідея EGSA базується на тому, що для практичної неможливості фальсифікації ЕЦП може бути використана практично нерозв’язувана задача дискретного логарифмування.
Алгоритм:
1. Перший користувач вибирає випадкове секретне число k, взаємно просте з Р-1, і обчислює число A^k mod P
2. Потім застосовуємо алгоритм Евкліда для значення b рівнянні:
m = (X1 * а +k * b) mod (P-1)
Пара чисел (а, b) буде цифровим підписом повідомлення m.
3. Повідомлення m разом з підписом (а, b) відправляється користувачеві 2.
4. Користувач 2 отримує повідомлення m і з використанням відкритого
ключа першого абонента Y1 обчислює два числа за наступними формулами
с1=Y1^a * a^b mod P, c2= A^m mod P
Якщо с1 = с2, то цифровий підпис першого користувача вірний.
Приклад обчислення і перевірки цифрового підпису:
Маємо наступні загальні параметри: Р = 43, А = 23.
Один з користувачівпідписує своє повідомлення m=15 цифровим підписом, сформованим по алгоритму Ель Гамаля. Спочатку він обирає собі закритий ключ Х1=7 і формує відкритий ключ: Y1 = 23^27 mod 41 = 4. Відкритий ключ передаємо іншим партнерам. Потім обираємо випадкове секретне число до, взаємно просте з Р-1. Нехай k=12. Далі обчислюємо число a = A^k mod P = 23^13 mod 41 = 31.
Потім за допомоою алгоритму Евкліда знаходиться b в рівнянні:
m = (X1 * а +k * b) mod (P-1) = 15=7 * 31+13 * 6 mod 40
Рішенням буде значення b=6.
Таким чином, пара чисел (31, 6) буде цифровим підписом повідомлення m=15.
Потім інший партнер перевіряє цифровий підпис в повідомленні(за бажанням): він отримує отримує відкритий ключ першого користувача та обчислює с1 і с2 і порівнює їх.
с1=Y1^a * a^b mod P=23^7 * 31^6 mod 41=40,

c2= A^m mod P= 23^15 mod 41= 40
Якщо с1 = с2, то цифровий підпис в повідомленні m=15 вірний. [8]
Алгоритм Диффі-Хеллмана:
Припустимо, що обом абонентам відомі деякі два числа g і p (наприклад, вони можуть бути «зашиті» в програмне забезпечення), які не є секретними і можуть бути відомі також іншим зацікавленим особам. Для того, щоб створити невідомий більш нікому секретний ключ, обидва абонента генерують великі випадкові числа: перший абонент — число a, другий абонент — число b. Потім перший абонент обчислює значення A = gamod p і пересилає його друга, а другий обчислює B = gbmod p і передає першому.
Передбачається, що зловмисник може отримати обидва цих значення, але не модифікувати їх (тобто у нього немає можливості втрутитися в процес передачі). На другому етапі першого абонент на основі наявної в нього a і отриманого по мережі B обчислює значення Bamod p = gabmod p, а другий абонент на основі наявної в нього b і отриманого по мережі A обчислює значення Abmod p = gabmod p. Як неважко бачити, у обох абонентів вийшло одне і те ж число: K = gabmod p. Його вони і можуть використовувати в якості секретного ключа, оскільки тут зловмисник зустрінеться з практично нерозв’язною (за розумний час) проблемою обчислення gabmod p по перехоплених gamod p і gbmod p, якщо числа p, a, b обрані досить великими.

Під час роботи алгоритму, кожна сторона:
генерує випадкове натуральне число a — закритий ключ;
спільно з віддаленої стороною встановлює відкриті параметри p і g (зазвичай значення p і g генеруються на одній стороні і передаються іншій), де
p є випадковим простим числом;
g є первісним коренем за модулем p;
обчислює відкритий ключ A, використовуючи перетворення над закритим ключем A = ga mod p;
обмінюється відкритими ключами з віддаленої стороною;
обчислює загальний секретний ключ K, використовуючи відкритий ключ віддаленої сторони B і свій закритий ключ a;
K = Ba mod p
Ключ виходить рівним з обох сторін, тому що:
Ba mod p = (gb mod p) a mod p = gab mod p = (ga mod p) b mod p = Ab mod p. [9]