Сучасна криптографія

Ларс Кнудсен [6] розрізняє розкриття  алгоритмів шифрування за такими категоріями, наведеними в порядку зменшення  їхньої важливості.

1. Повне розкриття. Криптоаналітик отримав такий ключ K, що D_K(C) = P.
2. Глобальна дедукція. Криптоаналітик отримав альтернативний алгоритм, що дає змогу відтворити D_K(C), не знаючи ключа K.
3. Часткова (локальна) дедукція. Криптоаналітик отримав відкритий текст для певного перехопленого криптотексту.
4. Інформаційна дедукція. Криптоаналітик отримав деяку інформацію про ключ або відкритий текст. Такою інформацією можуть бути декілька бітів ключа, відомості про форму відкритого тексту тощо.

Алгоритм є безумовно безпечним, якщо інформації для отримання відкритого тексту недостатньо, незалежно від обсягу шифротекстів у криптоаналітика. По суті, лише шифрограми, утворені за допомогою методу одноразового блокнота (див. параграф 2.1), неможливо розкрити навіть з необмеженими ресурсами. Усі інші криптосистеми піддаються розкриттю з використанням лише шифротексту простим  перебиранням можливих ключів (брутальною атакою) і перевіренням осмисленості отриманих відкритих текстів.

У криптографії більше цікавляться  криптосистемами, які важко зламати обчислювальним способом. Алгоритм уважають обчислювально безпечним (або, як іноді називають сильним), коли його не можна зламати з використанням доступних ресурсів нині або в майбутньому. Термін “доступні ресурси” є досить розмитий, бо складність зламування шифру можна виміряти різними способами, зокрема:

1. складністю даних -  обсягом даних, які використовують на вході операції розкриття;
2. складністю опрацювання -  часом, потрібним для зламування;
3. вимогами до пам’яті -  обсягом пам’яті, необхідної для зламування.

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

Тоді як складність зламування шифру  є сталою (до часу, доки якийсь криптоаналітик не придумає кращого способу розкриття), потужність комп’ютерів постійно зростає. За останні півстоліття їхні обчислювальні потужності феноменально зросли, й немає ніяких причин вважати, що ця тенденція не буде збережена. Багато криптографічних методів зламувань ґрунтується на використанні паралельних обчислень: задачу розбивають на мільярди маленьких фрагментів, розв’язування яких не потребує міжпроцесорної взаємодії. Оголошення алгоритму шифрування надійним лише тому, що його важко зламати, використовуючи сучасну техніку, в кращому випадку ненадійне. Добрі криптосистеми проектують стійкими до зламування з урахуванням розвитку обчислювальних засобів на багато років уперед.

1.2. Застосування шифрувань

1.2.1. Захист даних від несанкціонованого доступу

Забезпечити захист даних від доступу  до них невтаємничених осіб можна  за допомогою як симетричних, так  і асиметричних алгоритмів. Вибір алгоритму зумовлений передусім вимогами до швидкості роботи криптографічної системи. Можливі такі застосування.

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

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

1.2.2. Підписування документів

Документи можна підписувати за допомогою асиметричних алгоритмів. Абонент В публікує (наприклад, на своєму боці електронної мережі) один з пари ключів, саме той, який слугує для дешифрування (саме тому цей ключ називають публічним, або явним, ключем). Інший із пари ключів зберігається в таємниці. Цей ключ називають приватним ключем. Абонент В підписує документи, шифруючи їх за допомогою свого приватного ключа. Це можливе, оскільки:

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

1.2.3. Захист таємниці електронної пошти

Пересилання електронної пошти  пов’язано з багатьма небезпеками. Хтось, хто має контроль над вузлом Інтернету, може видозмінити лист або переслати його комусь іншому. Щоб запобігти подібного роду видозмінам можна використати наступний сценарій.

Припустимо, що абонент В має пару ключів для асиметричного шифруючого алгоритму. Коли абонент А хоче послати лист до абонента В, то реалізується наступний протокол.

• Абонент А бере публічний ключ абонента В.
• Абонент А шифрує текст свого листа до абонента В за допомогою його публічного ключа й посилає зашифрований лист електронною поштою.
• Абонент В дешифрує отриманий лист за допомогою свого приватного ключа й отримує в такий спосіб оригінальний текст.

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

1.2.4. Електронний нотаріус

До нотаріуса звертаємось у  двох важливих ситуаціях:

• коли хочемо офіційно підтвердити існування документа без розголошення його змісту;
• коли хочемо гарантувати, щоб у певному документі, наприклад у торговій угоді, недобросовісний партнер не зробив змін.

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

Для отримання „відбитків пальців” використовуємо так звані однонапрямлені хешувальні (вкорочувальні) функції. Кажемо, що H є однонапрямленою хешувальною функцією, якщо виконуються такі умови:

1. для кожного тексту X легко обчислити H(X);
2. H(X) має однакову довжину для всіх текстів X (тому довжина H(X) не дає жодної інформації про текст X);
3. практично неможливо для заданого Y знайти таке X, що H(X) = Y.

З наведених умов випливає, що послідовність H(X) повинна бути досить довгою для того, щоб унеможливити систематичний пошук. Коли значення хешувальної функції складається з 128 біт, то маємо 2¹²⁸ можливих варіантів.

З метою „нотаріального” підтвердження  власності на документ X необхідно обчислити значення функції H(X) i опублікувати або розмістити його в нотаріуса. У цьому разі роль нотаріуса може відігравати спеціальна мережева програма. Пізніше, коли треба довести власність на документ X, достатньо подати X i зазначити місце, де раніше помістили значення H(X). Підтвердження полягає в обчисленні значення H(X) для поданого тексту X i порівнянні його із попередньо опублікованим або депонованим у нотаріуса.

Зазначимо, що описаний метод міг  би, наприклад, забезпечити просте засвідчення  автентичності комп’ютерних програм.

1.3. Історія криптографії

Історія криптографії пов’язана з  великою кількістю дипломатичних  та військових таємниць і тому оповита  туманом легенд. Свій слід в історії  криптографії залишило багато відомих  історичних осіб. Найповніша книга  з історії криптографії містить понад тисячу сторінок. Вона опублікована 1967 р. і українською мовою не перекладена (Kahn David. The Story of Secret Writing. New York: Macmillan, 1967).

Перші відомості про використання шифрів у військовій справі пов’язані  з іменем спартанського полководця Лісандра (шифр скитала). Такий шифр використовували спартанці для військових повідомлень під час війни Спарти проти Афін у V ст. до н. е. Скиталою називали дерев’яний валик, на який щільно намотували стрічку пергаменту або шкіри. Повідомлення писали рядками вздовж поверхні валика так, щоб у рядку на один виток стрічки припадала тільки одна буква. Стрічка, знята з валика, містила незрозумілу послідовність літер. Її можна було прочитати, лише намотавши стрічку на валик такого самого діаметра. Тобто в цьому випадку ключем до прочитання повідомлення був діаметр валика.

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

Криптоаналіз уперше застосували  арабські дослідники. Опис частотного аналізу є в їхніх писемних джерелах початку XV ст.

На початку XVI ст. був запропонований шифр Play-fair (чесна гра; або в іншій модифікації - шифр чотирьох квадратів). Відомий математик Кардано, автор формули для розв’язування кубічного рівняння, запропонував один із варіантів шифру перестановки. Гомоморфний шифр заміни запропоновано видатним німецьким математиком Карлом Фрідріхом Гауссом.

Французький криптограф XVI ст. Блез де Віженер запропонував шифр заміни, який кілька століть уважали надійним. Як одиниці явного тексту він вибрав блоки, складені з k літер. Потім пересував кожний блок на певне „кодове слово” довжини k. Лише в 60-х роках XIX ст. офіцер пруського війська Касискі виявив, що цей шифр можна частотно аналізувати.

У роки першої світової війни з’явились  подрібнювальні шифри, чи не найвідомішим з яких є шифр ADGVX, що його використовувала німецька армія. Шифр ADGVX є шифром перестановки в поєднанні з шифром підстановки. Цей, для того часу дуже складний алгоритм, розкрив французький криптоаналітик Жорж Пенвен.

У 1917 р. інженери Г. Вернам та М.Моборн із фірми AT&T винайшли шифр одноразового блокнота для застосування в телетайпному зв’язку. Цей шифр можна вважати узагальненням шифру Віженера на випадок, коли довжина ключа збігається з довжиною тексту. Шифр одноразового блокнота абсолютно надійний, і лише деякі обставини звужують сферу його застосування. Зокрема, застосування цього шифру передбачає використання безпечного каналу зв’язку для обміну довгими ключами шифрування. Назва шифру походить від того, що агент, який виконував шифрування вручну, отримував копії своїх ключів, записані на окремих сторінках блокнота. Як тільки ключ використано, сторінку з ним відразу ж знищували. Саме шифр одноразового блокнота застосовували для захисту від підслуховування гарячої лінії зв’язку, встановленої під час холодної війни між Вашингтоном і Москвою.

Попередником сучасних шифрувальних пристроїв була роторна машина, винайдена 1917 р. Едвардом Хепберном з Окленда, Каліфорнія. На цих машинах ґрунтувалась уся військова криптографія упродовж майже 50 років. Базовими елементами роторної машини є сам ротор та механічне колесо, що слугує для виконання операції підстановки.

У початковому варіанті роторна  машина мала клавіатуру та чотири колеса, що оберталися на одній осі. На кожному  колесі з лівого й правого боку було по 25 електричних контактних майданчиків, що відповідали 25 символам латинської абетки (літери I та J ототожнені). Контактні майданчики лівого й правого боку були в певному порядку попарно з’єднані всередині колеса 25 комутаційними провідниками. Наприклад, ротор могли використовувати для заміни А на L, B на U, С на Z і так далі. У процесі руху колеса складалися разом, і їхні контакти, доторкаючись один до одного, забезпечували проходження електричних імпульсів через усі чотири колеса. Наприклад, у чотирироторній машині перший ротор міг замінювати А на L, другий - L на V, третій - V на D і четвертий - D на S. Літера S була остаточним символом шифротексту (рис.1.4).

 

 

 

Рис. 1.4. Структура роторної шифрувальної машини.

 

 

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

Отже, для дешифрування повідомлення треба було знати внутрішні з’єднання  в кожному колесі (статична ключова інформація) і ключ шифрування (динамічна ключова інформація). Конструкція роторної машини виявилась дуже вдалою в сенсі стійкості до криптоаналізу вручну. Знаючи внутрішні з’єднання в колесах, для зламування шифру необхідно перебрати 25⁴ = 390 625 можливих варіантів з метою відтворення ключа шифрування, а коли ще й внутрішні з’єднання невідомі, то 25⁸ ≈ 1,5∙10¹¹ варіантів.

Надалі шифрувальні роторні  машини розвивалися в напрямі  збільшення кількості коліс та розширення використовуваного алфавіту. Шифрування на базі роторних машин реалізувало багаторазову композицію шифрів Віженера.

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

Незважаючи на складність Енігми, алгоритм, який вона реалізовувала, був розкритий під час війни. Група польських криптографів зламала шифр німецької Енігми й пояснила розкритий алгоритм англійцям. У ході війни німці модифікували Енігму, а англійці продовжували криптоаналіз нових версій. Перша електронно-обчислювальна машина сконструйована за участю видатного англійського математика Алана Тюрінга саме з метою зламування шифру машини Енігма.