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

В лекції викладені питання і завдання, пов'язані з захистом інформації, шифруванням і дешифруванням, цифровим підписом, комп'ютерною безпекою тощо.

У загальнодоступній формі роз'ясняються основні поняття криптографії. Наводяться необхідні відомості з математичного апарату криптографії. Крім того, викладаються й останні ідеї сучасної криптографії.

Як приклади розбираються шифри, добре відомі з історії й детективної літератури.

ЗМІСТ

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

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

Криптографія — наука про методи перетворення (шифрування) інформації з метою її захисту від незаконних користувачів.

Стеганографія — набір засобів і методів приховання факту передачі повідомлення.

Шифр — спосіб, метод перетворення інформації з метою її захисту від незаконних користувачів.

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

1.2. Чим криптографія відрізняється від стеганографії

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

Перші сліди стеганографічних методів губляться в далекій давнині. Наприклад, відомий такий спосіб приховання письмового повідомлення: голову раба голили, на шкірі голови писали повідомлення, і після відростання волосся раба відправляли до адресата.

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

Також з детективів відомий сучасний метод «мікрокрапки»: повідомлення записується за допомогою сучасної техніки на дуже маленький носій — «мікрокрапку», що пересилається зі звичайним листом, наприклад, під маркою або де-небудь в іншому заздалегідь обумовленому місці.

Один типічний стеганографічний прийом тайнопису — акровірш — добре відомий знавцям поезії. Акровірш – це така організація віршованого тексту, при якому, наприклад, початкові букви кожного рядка утворять приховуване повідомлення.

У наш час у зв'язку із широким поширенням комп'ютерів відомо багато тонких методів «приховування» захищеної інформації, усередині великих обсягів інформації, що зберігається в комп'ютері.

Навіть із наведеної невеликої кількості прикладів видно, що при використанні стеганографії на відміну від криптографії таємна інформація не перетвориться, а ховається сам факт її передачі.

1.3. Як можна представити основний об'єкт криптографії

Можна представити так:

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

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

Відзначимо, що історично в криптографії закріпилися деякі чисто військові слова (супротивник, противник, атака на шифр тощо). Вони найточніше відображають зміст відповідних криптографічних понять. Разом з тим широко відома військова термінологія, заснована на понятті коду (військово-морські коди, коди Генерального штабу, кодові книги, кодопозначення тощо) уже йдуть з теоретичної криптографії. Справа в тому, що за останні три десятиліття сформувалася теорія кодування — новий великий науковий напрямок, що розробляє й вивчає методи захисту інформації від випадкових перекручувань у каналах зв'язку. І якщо раніше терміни кодування й шифрування вживалися в деякому смислі як синоніми, то тепер це неприпустимо. Так, наприклад, дуже поширений вираз «кодування – різновид шифрування» стає просто неправильним.

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

Розкриття (зламування) шифру — процес одержання захищеної інформації (відкритого тексту) із шифрованого повідомлення (шифротексту) без знання застосованого шифру. Шифрування (зашифрування) — процес застосування шифру до захищуваної інформації, тобто перетворення захищуваної інформації, у шифроване повідомлення за допомогою певних правил, що містяться у шифрі.

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

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

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

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

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

1.4. Криптографія як мистецтво. Трохи історії

Довгий час заняття криптографією було долею диваків-одинаків. Серед них були обдаровані вчені, дипломати, священнослужителі. Відомі випадки, коли криптографія вважалася навіть чорною магією. Цей період розвитку криптографії як мистецтва тривав з незапам'ятних часів до початку XX століття, коли з'явилися перші шифрувальні машини. Розуміння математичного характеру розв'язуваних криптографією завдань прийшло тільки в середині XX століття – після робіт видатного американського вченого К. Шеннона.

Історія криптографії пов'язана з великою кількістю дипломатичних і військових таємниць і тому обкутано туманом легенд. Найповніша книга з історії криптографії містить більше тисячі сторінок. Вона опублікована в 1967 році в Нью-Йорку й українською мовою ще не перекладена¹. Російською мовою недавно вийшла у світ фундаментальна праця по історії криптографії в Росії².

Свій слід в історії криптографії залишили багато добре відомих історичних особистостей. Наведемо декілька найяскравіших прикладів.

Перші відомості про використання шифрів у військовій справі пов'язані з ім'ям спартанського полководця Лисандра (шифр «Сциталь», V століття до нашої ери). Цезар використав у листуванні шифр, що ввійшов в історію як «шифр Цезаря». У древній Греції був винайдений вид шифру, що надалі став називатися «квадрат Полиття». Братерство франкмасонів з моменту свого виникнення (VIII століття) розробило й використало цілу систему особливих шифрів. Одну з перших книг по криптографії написав абат І. Три-телій (1462 - 1516), що жив у Німеччині. У 1566 році відомий механік і математик Д. Кардано опублікував роботу з описом винайденої ним системи шифрування («ґрати Кардана»). Франція XVI століття залишила в історії криптографії шифри короля Генріха IV і Ришельє. У згаданій книзі Т. А. Соболєвої докладно описано багато російських шифрів, у тому числі й «цифрова азбука» 1700 року, автором якої був Петро Великий.

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

Багато цікавої інформації із криптографії публікується у науково-популярному журналі «Cryptology», що видається в США. Великий бібліографічний список (111 назв) закордонної літератури з криптографії міститься в дуже корисній і важливій статті Диффі й Хеллмена³, що перекладена російською мовою й загальнодоступна (про революційний внесок авторів цієї статті в криптографію розкажемо нижче).

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

Шифр «Сциталь». Цей шифр відомий із часів війни Спарти й Персії проти Афін. Спартанський полководець Лисандр підозрював персів у можливій зраді, але не знав їхніх таємних планів. Його агент у стані персів надіслав шифроване повідомлення, що дозволило Лисандру випередити персів і розгромити їх. Шифроване повідомлення було написано на поясі офіційного гінця від персів у такий спосіб: агент намотав пояс на сциталь (дерев'яний циліндр певного діаметра) і написав на поясі повідомлення уздовж сциталя; потім він розмотав пояс, і вийшло, що поперек пояса безладно написані букви. Гонець не догадувався, що візерунок на його гарному поясі насправді містить зашифровану інформацію. Лисандр взяв сциталь такого ж діаметра, акуратно намотав на нього пояс й уздовж сциталя прочитав повідомлення від свого агента.

Наприклад, якщо роль сциталя виконує олівець із шістьома гранями, то відкритий текст КРИПТОГРАФИЯ може бути перетворений у зашифрований текст

Шифротекст може бути й іншим, тому що він залежить не тільки від діаметра олівця. Проекспериментуйте!

Відзначимо, що в цьому шифрі перетворення відкритого тексту в шифрований полягає в певній перестановці букв відкритого тексту. Тому клас шифрів, до яких ставиться й шифр «Сциталь», називається шифрами перестановки. Математичному опису таких шифрів присвятимо розділ 2.4.

Шифр Цезаря. Цей шифр реалізує подальше перетворення відкритого тексту: кожна буква відкритого тексту ставиться третьої після її буквою в алфавіті, що вважається написаним по колу, тобто після букви «я» йде буква «а». Тому клас шифрів, до яких відноситься й шифр Цезаря, називається шифрами заміни. Математичному опису таких шифрів присвячений розділ 2.4.

Наприклад, відкритий текст КРИПТОГРАФИЯ при такому способі шифрування перетвориться в шифротекст

НУЛТХСЕУГЧЛВ.

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

Шифр Виженера. Цей шифр зручніше за все уявляти собі як шифр Цезаря зі змінною величиною зсуву. Щоб знати, на скільки зсувати чергову букву відкритого тексту, заздалегідь домовляються про спосіб запам'ятовування зсувів. Сам Виженер пропонував запам'ятовувати ключове слово, кожна буква якого своїм номером в алфавіті вказує величину зсуву. Ключове слово повторюється стільки разів, скільки потрібно для заміни всіх букв відкритого тексту. Наприклад, ключове слово ВАЗА означає наступну послідовність зсувів букв відкритого тексту

3191319131913191...

Наприклад, відкритий текст КРИПТОГРАФИЯ при такому способі шифрування перетвориться у шифротекст

НССРХПЛСГХСА.

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

Подумайте самі:

1. Проекспериментуйте із шифрами Цезаря й Виженера.

2. Спробуйте знайти спосіб розкриття шифру «Сциталь» (не знаючи діаметра сциталя).

1.5. Що таке ключ

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

У найдавнішому шифрі «Сциталь», описаному в розділі 1.4, ключем є діаметр сциталя. При цьому не міняючи принцип побудови шифру, можна для шифрування різних повідомлень користуватися сциталями різних діаметрів.

У шифрах типу шифру Цезаря ключем є величина зрушення букв шифротексту щодо букв відкритого тексту.

Навіщо ж потрібний ключ? З попереднього викладу зрозуміло, що придумування гарного шифру — справа трудомістка. Тому бажано збільшити «час життя» гарного шифру й використовувати його для шифрування як можна більшої кількості повідомлень. Але при цьому виникає небезпека, що супротивник уже розгадав (розкрив) шифр і читає захищену інформацію. Якщо ж у шифрі є змінний ключ, то, замінивши ключ, можна зробити так, щоб розроблені супротивником методи вже не дадуть ефекту. Цей принцип особливо корисний і важливий у тих випадках, коли застосовуються дорогі шифрувальні машини (шифромашини) у великих мережах зв'язку.

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

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

Повернемося до формального опису основного об'єкта криптографії (розділ 1.3). Тепер у нього необхідно внести істотну зміну - додати недоступний для супротивника секретний канал зв'язку для обміну ключами:

Практична побудова таких мереж зв'язку для великого обміну шифрованими повідомленнями стало ще дорожчим заходом.

Подумайте самі:

1. Що є ключем у шифрі Виженера?

1.6. Атака на шифр. Стійкість шифру

Під атакою на шифр розуміють спробу розкриття цього шифру.

Під стійкістю шифру розуміють здатність шифру

протистояти всіляким атакам на нього.

Поняття стійкості шифру є центральним для криптографії. Хоча якісно зрозуміти його досить легко, але одержання строгих доказових оцінок стійкості для кожного конкретного шифру — проблема невирішена! Це пояснюється тим, що дотепер немає необхідних для вирішення такої проблеми математичних результатів. (Ми повернемося до обговорення цього питання в розділі 2.6.) Тому стійкість конкретного шифру оцінюється тільки шляхом усіляких спроб його розкриття й залежить від кваліфікації криптоаналітиків, що атакують шифр. Останню процедуру іноді називають перевіркою стійкості.

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

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

З більш-менш специфічних наведемо ще три приклади можливостей супротивника:

• супротивник може перехоплювати всі шифровані повідомлення, але не має відповідних їм відкритих текстів;

• супротивник може перехоплювати всі шифровані повідомлення й добувати відповідні їм відкриті тексти;

• супротивник має доступ до шифру (але не до ключів!) і тому може зашифровувати й дешифрувати будь-яку інформацію.

Рекомендуємо самостійно придумати ще кілька можливостей супротивника. Підкажемо, наприклад, використання так називаного «імовірного слова» у відкритому тексті: супротивникові з яких-небудь міркувань відомо, що у відкритому тексті зустрічається конкретне слово. Іноді така інформація полегшує процес розкриття шифру.

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

Англійський математик Чарльз Беббідж (XIX в): «Усяка людина, навіть якщо віна не знайомою з технікою розкриття шифрів, твердо вважає, що зможе винайти абсолютно стійкий шифр, і чим розумніша й освіченіша ця людина, тим більш тверде її переконання. Я сам розділяв цю впевненість у плині багатьох років.»

«Батько кібернетики» Норберт Вінер (XX в): «Будь-який шифр може бути розкритий, якщо тільки в цьому є нагальна потреба й інформація, яку передбачається одержати, коштує витрачених засобів, зусиль і часу...»

Ми повернемося до цього питання в розділі 2.5 після розповіді про роботи Клода Шеннона.

1.7. Криптографія й криптологія

Криптологія — наука, що складається із двох галузей: криптографії й криптоаналізу.

Криптографія— наука про способи перетворення (шифрування) інформації з метою її захисту від незаконних користувачів.

Криптоаналіз — наука (і практика її застосування) про методи й способи розкриття шифрів.

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

Співвідношення криптографії й криптоаналізу очевидно: криптографія – захист, тобто розробка шифрів, а криптоаналіз – напад, тобто атака на шифри. Однак ці дві дисципліни зв'язані одна з одною, і не буває гарних криптографів, що не володіють методами криптоаналізу. Справа в тому, що стійкість розробленого шифру можна довести тільки за допомогою проведення різних атак на шифр, стаючи подумки в положення супротивника (див. розділи 1.6, 2.6).

1.8. Чому потрібно багато різних шифрмашин

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

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

Деякі таємниці (наприклад, державні, військові й ін.) повинні зберігатися десятиліттями, а деякі (наприклад, біржові) — уже через кілька годин можна розголосити. Необхідно враховувати також і можливості того супротивника, від якого захищається задана інформація. Одна справа – протистояти одинаку або навіть банді кримінальників, а інша справа – потужній державній структурі. Через таку розмаїтість вимог доводиться розробляти різні шифри, які реалізуються в сотнях типів шифруючих машин і пристроїв. Разом з тим у найрозвиненіших у криптографічному відношенні країнах існують стандартні шифри: наприклад, DES – у США й СКЗД – у Росії.

1.9. Залежність криптографії від рівня технології

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

Умовно можна виділити три принципово різних етапи в розвитку математичного апарату криптографії.

До 40-х років XX століття були тільки електромеханічні шифрмашини, тому й спектр математичних перетворень був обмежений: застосовувалися в основному методи комбінаторного аналізу й теорії ймовірностей.

Після появи електронної техніки, а тим більше комп'ютерів, сильно змінився й математичний апарат криптографії.

Одержали розвиток прикладні ідеї й методи теорії інформації, алгебри, теорії кінцевих автоматів.

Роботи Диффі й Хеллмена (70-і роки) послужили поштовхом для бурхливого розвитку нових напрямків математики: теорії однобічних функцій, доказів з нульовим розголошенням. Зараз прогрес саме в цих напрямках визначає практичні можливості криптографії.

Розділ 2 МАТЕМАТИЧНІ ОСНОВИ

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

2.1. Приведення будь-якої інформації до двійкового вигляду

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

У теоретичній криптографії прийнято працювати з універсальним алфавітом, який складається із усіх двійкових слів деякої довжини. Двійкове слово довжини п — це набір з n нулів й одиниць. Відповідний алфавіт складається з 2 символів. Вибір такого алфавіту пояснюється багатьма міркуваннями.

При використанні комп'ютерів зручно представляти інформацію у вигляді послідовностей нулів й одиниць. Це, зокрема, обумовлено застосовуваними технічними засобами: у комп'ютері використовуються елементи, які можуть перебувати в одному із двох станів. Одне з них позначається «0» а інше – «1».

З іншого боку, слова в будь-якому алфавіті можна легко перевести у двійкові слова. Нехай ми маємо справу з текстами російською мовою й нехай букви «е» і «ё» , а також «и» та «й» не розрізняються, а пробіл між словами вважається окремою буквою (позначення: _). Тоді наш алфавіт складається із тридцяти двох символів. Розглянемо тепер телеграфний код старе технічне застосування двійкової системи числення. Він складається теж з 32 символів — двійкових слів довжини 0. Зіставимо кожній букві двійкове слово довжини 5 у такий спосіб:

– → 00000, А – → 00001, Б – → 00010, В – → 00011, Г – →

– → 00100, Д – → 00101, ... , Ю – → 11110, Я – → 11111.

Замінивши в тексті кожну букву на відповідне двійкове слово, одержимо двійковий вид нашої інформації — деяку послідовність нулів й одиниць (або, як прийнято говорити, бітів). Подібним чином можна оперувати й із будь-яким іншим алфавітом.

На практиці створюються спеціальні пристрої, які дозволяють автоматично переводити текстову інформацію, що вводиться людиною, у двійкову.

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

Таким чином, двійкові слова й двійкові послідовності – типові об'єкти в криптографічних дослідженнях.

Подумайте самі:

1. Доведіть, що кожне натуральне число n єдиним чином представляється у вигляді

п = 2k + ak-1 2k-1 +... + а12 + а0,

де k — деяке ціле ненегативне число, а кожне із чисел ak-l, … a0 – або 0, або 1.

2.2. Випадковість і закономірність у двійкових послідовностях

Поняття послідовності відомо ще зі шкільних років. Однак послідовності, які там вивчалися, були детермінованими — вони однозначно відновлювалися по їхніх декількох елементах. Так, арифметична й геометрична прогресії відновлюються по будь-яким двом своїм підряд стоячим членам. Значення многоточлена в цілих крапках також утворять детерміновану послідовність: вона визначається будь-якими п + 1 своїми членами, де n — ступінь даного багаточлена (доведіть це!).

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

Нехай ми підкидаємо «правильну» монету. Залежно від того, як вона падає, думаємо черговий член послідовності рівним 0 (орел) або 1 (решка). Як показує досвід, звичайно не можна вгадати, як монета впаде в черговий раз. Однак, якщо підкидати монету досить довго, приблизно в половині випадків випаде орел, а в половині — решка. Говорять, що монета падає випадковим чином, причому в кожному підкиданні з однаковою ймовірністю 1/2 випадає орел (0) або решка (1).

Однак бувають ситуації («крива монета»), коли орел і решка випадають із різною ймовірністю р и q відповідно р ≠ q . Відзначимо, що р + q = 1 ! У випадковій двійковій послідовності, отриманої на основі підкидання «кривої монети», р можна вважати частотою появи нуля, a q — частотою появи одиниці.

Для тих, хто вивчав границі, уточнимо: якщо позначити через S0(k) число нулів, а S1(k) – число одиниць серед k перших членів нашої послідовності, то тоді

Контрольне питання. Нехай ми випадковим чином підкидаємо монету, причому р = q = 1/2 і перші сто членів відповідної послідовності рівні 1 (100 разів підряд випала решка). Чому дорівнює ймовірність того, що 101-им членом цієї послідовності знову буде 1?

Правильна відповідь на це питання: 1/2. Тому що q = 1/2, а випадковість нашої послідовності саме й означає, що кожен черговий її член дорівнює 1 з імовірністю q незалежно від того, якими були попередні її члени.

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

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

Близьким за духом, але простішим і добре відомим, особливо для програмістів, є такий об'єкт, як датчик випадкових чисел. Це — деякий пристрій або програма, що виробляє псевдовипадкові послідовності. Псевдовипадкові послідовності в деяких ситуаціях вважають невідрізненними від випадкових, причому для різних ситуацій і завдань підбирають підходящі датчики. Чим сильніші вимоги накладаються на випадковість вироблюваних послідовностей, тим складнішим є відповідний датчик випадкових чисел. Багато із шифромашин можна вважати датчиками випадкових чисел, що задовольняють дуже високим вимогам на якість вироблюваних послідовностей.

Опишемо, наприклад, один найпростіший датчик, запропонований в 1949 році Д. Х. Лемером і надалі одержав назву лінійного конгруентного методу. Для заданого початкового числа а0 він виробляє нескінченну послідовність натуральних чисел { dk } за таким рекуррентним законом:

Тут параметри датчика d ,l, N — деякі цілі числа. Запис а = b (mod N), взагалі кажучи, означає, що а = b ділиться на число N; у цьому випадку в ролі ak береться залишок від ділення d + ak-1 ∙l на N.

Оскільки всі члени послідовності { ak } – ненегативні цілі числа, що не перевершують N–1, то серед них найдуться два однакових, скажемо ai й ai+t. Тоді, як легко бачити, ai= ai+t для k>I, тобто послідовність періодична з довжиною періоду t. Звичайно, періодичність не зовсім узгоджується з нашими уявленнями про випадковості, але, виявляється, можна підбирати такі параметри датчика, щоб період був досить великим й у послідовності були багато ознак випадковості.

Слід зазначити, що «гарної для всіх варіантів випадкової послідовності» практично не існує: наскільки «гарної» є випадкова послідовність, залежить від її призначення.

Подумайте самі:

1. Доведіть наступне твердження: імовірність того, що при k підкиданнях кривої монети 1 раз випаде орел, рівний

1. Придумайте такі числа d, l й N, щоб N було не занадто малим і довжина періоду послідовності, отриманої лінійним конгруентним методом, була близька до N.

2. Придумайте який-небудь свій датчик випадкових чисел.

2.3. Що таке алгоритм і його складність

Під алгоритмом, якщо говорити неформально, можна розуміти чітко описану послідовність дій, що приводить до певного результату.

Поняття алгоритму дуже довго залишалося інтуїтивним поняттям. Тільки в 30-і роки XX століття в роботах видатних математиків Д. Гільберта, А. Черча, С. Кліні, Е. Поста й А. Тьюринга були запропоновані формальні визначення алгоритму на основі поняття рекурсивної функції й на основі опису алгоритмічного процесу. Тим самим сформувалася теорія алгоритмів — новий напрямок у математиці, що стало згодом теоретичною основою розвитку обчислювальної техніки. У наш час теорія алгоритмів бурхливо розвивається, багато її понять проясняються й уточнюються {доведеність, можливість розв'язання, ефективність й ін.).

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

Дуже важливим поняттям у математиці (інтуїтивно зрозумілим, але не дуже просто формалізується) є складність алгоритму. Наведемо простий приклад. Нехай потрібно вгадати задумане число, про яке відомо, що воно натуральне й не перевершує 1000. Дозволяється задавати питання, на які можна відповісти «так» або «ні». Одним із способів (алгоритмів) угадування може бути такий: послідовно перебираються всі числа від 1 до 1000 доти, поки потрібне число не буде знайдено. У найгіршому разі для цього буде потрібно 999 питань. Однак можна запропонувати й інший алгоритм, що дозволяє вгадати число за 10 питань: спочатку з'ясовується, чи більше вгадане число 500 чи ні, якщо так, те більше 750 чи ні й т.д. З кожним кроком число можливих кандидатів зменшується у два рази. Тут складністю алгоритму можна вважати число питань. Тоді перший алгоритм в 100 разів «складніший» другого.

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

У математичній теорії складності обчислень розглядаються алгоритми рішення не конкретних задач, а так званих масових задач. Масові задачі зручно уявляти собі у вигляді нескінченної серії індивідуальних завдань. Індивідуальне завдання характеризується деяким розміром, тобто обсягом вхідних даних, необхідних для опису цієї задачі. Якщо розмір індивідуальної задачі — деяке натуральне число п, тоді складність алгоритму рішення масової задачі стає функцією від п. Наведемо два приклади.

Розглянемо алгоритм простого перебору всіх двійкових ключів довжини n. Ясно, що таких ключів — , і тому в даному алгоритмі кроків, тобто його складність дорівнює . Це — найпростіший приклад експонентного алгоритму (його складність виражається через п експонентою). Більшість експонентних алгоритмів – це просто варіанти повного перебору.

Розглянемо тепер алгоритм множення стовпчиком двох n-значних чисел. Він складається з множень однозначних чисел, тобто його складність, вимірювана кількістю таких множень, дорівнює . Це – найпростіший приклад поліноміального алгоритму (його складність виражається через п поліномом).

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

У математиці є багато задач, для вирішення яких поки не вдалося побудувати поліноміальний алгоритм. До них відноситься, наприклад, задача комівояжера: є п міст, з'єднаних мережею доріг, і для кожної дороги зазначена вартість проїзду по ній; потрібно вказати такий маршрут, що проходить через всі міста, щоб вартість проїзду цим маршрутом була мінімальною.

Подумайте самі:

1.Чи можете ви запропонувати алгоритм множення двох n-значних чисел, що вимагає меншого числа множень однозначних чисел, ніж при множенні стовпчиком?

2.4. Шифри заміни й перестановки

У своїй роботі «Математична теорія секретного зв'язку» Клод Шеннон узагальнив накопичений до нього досвід розробки шифрів. Виявилося, що навіть у складних шифрах в ролі типових компонентів можна виділити шифри заміни, шифри перестановки або їхнього поєднання. Ці шифри можна вважати як би базовими.

Шифр заміни є найпростішим, найбільш популярним шифром. Типовими прикладами є шифр Цезаря, «цифирная азбука» Петра Великого й «танцюючі чоловічки А. Конан-Дойля. Як видно із самої назви, шифр заміни здійснює перетворення заміни букв або інших «частин» відкритого тексту на аналогічні «частини» шифрованого тексту. Зрозуміло, що, збільшивши алфавіти, тобто оголосивши «частини» буквами, можна будь-який шифр заміни звести до заміни букв. Тепер уже легко дати математичний опис шифру заміни.

Нехай X та Y — два алфавіти відкритого й відповідно шифрованого текстів, що складаються з однакового числа символів. Нехай також g : X→ Y – взаємно однозначне відображення X в Y. Це означає, що кожній букві х алфавіту X зіставляється однозначно певна буква у алфавіту Y, що ми позначаємо символом g(x) причому різним буквам зіставляються різні букви. Тоді шифр заміни діє так: відкритий текст х1 х2 ,. . . хп перетвориться в шифрований текст g(х1 ) g(х2 ) … g(хn ) – питанню про розкриттів шифру заміни ми повернемося в розділі 2.8.

Шифр перестановки, як видно з назви, здійснює перетворення перестановки букв у відкритому тексті. Типовим і найдавнішим прикладом шифру перестановки є шифр «Сциталь». Звичайно відкритий текст розбивається на відрізки рівної довжини й кожен відрізок шифрується (тобто в ньому переставляються букви) незалежно. Нехай, наприклад, довжина відрізків дорівнює п і σ – взаємно однозначне відображення {l,2,...,n} у себе. Тоді шифр перестановки діє так: відрізок відкритого тексту х1 х2 ,. . . хп перетвориться у відрізок шифрованого тексту хσ(1) . . . хσ(n).

Важливою проблемою при практичному використанні шифрів заміни й перестановки є проблема зручного запам'ятовування відображень g та σ. Ясно, що легко запам'ятовувати деякі відображення: наприклад, відображення «невеликих» розмірів, відображення, реалізовані яким-небудь предметом (сциталь у шифрі «Сциталь» і т.п.). Якщо ж відображення «великого» розміру, то процес запам'ятовування значно ускладнюється. Наприклад, широко відомі біграмні шифри. У них перетворювали біграми (пари букв). Оскільки кількість біграм перевищує 1000, то на практиці біграмні шифри виглядають як спеціальні книжки.

Для полегшення запам'ятовування відображень g та σ винаходилися різні хитромудрі способи. Правда, «розплатою» за це було спрощення використовуваних відображень і тим самим зменшення стійкості шифрів.

Популярним способом запам'ятовування відображення σ, тобто шифру перестановки, є такий. Нехай, наприклад, п = 20. Беремо прямокутну таблицю розміру 4x5, уписуємо в неї відкритий текст «по рядках», а шифрований текст зчитуємо «по стовпцях». Можливі й хитріші способи вписування й зчитування.

Подумайте самі:

1. Випишіть відображення g для шифру Цезаря.

2. Випишіть відображення <7 для описаного шифру перестановки — прямокутника 4x5.

2.5. Чи можливий абсолютно стійкий шифр

Так, і єдиним таким шифром є яка-небудь форма так званої стрічки однократного використання, у якій відкритий текст «поєднується» з повністю випадковим ключем такої ж довжини.

Цей результат був доведений К. Шенноном за допомогою розробленого їм теоретико-інформаційного методу дослідження шифрів. Ми не будемо зупинятися на цьому докладно, але зацікавленому студенту рекомендую вивчити відповідну роботу К. Шеннона.

Обговоримо особливості будови абсолютно стійкого шифру й можливості його практичного використання. Типовим і найпростішим прикладом реалізації абсолютно стійкого шифру є шифр Вєрнама, що здійснює побітове додавання n-бітового відкритого тексту й n-бітового ключа:

Тут х1 . . . хп – відкритий текст, k1 ... kn – ключ, у1 .... уn – шифрований текст; символи складаються за такими правилами: 0  0 = 0 , 0  1 = 1  0 = 1, 1  1 = 0 . Рекомендую студенту самостійно продумати, чому шифр Вернама є абсолютно стійким. (Підказка. Якщо відомі тільки у1 .... уn a k1 ... kn – невідомі й зовсім випадкові (більш строго — рівноймовірні), то х1 . . . хп можуть бути будь-якими. У цьому випадку говорять також, що рівняння шифрування не дають ніякої інформації про відкритий текст.)

Підкреслимо тепер, що для абсолютної стійкості істотним є кожне з наступних вимог до ключа однократного використання:

3. повна випадковість (рівноймовірність) ключа (це, зокрема, означає, що ключ не можна виробляти за допомогою якого-небудь детермінованого пристрою);

4. рівність довжини ключа й довжини відкритого тексту;

5. однократність використання ключа.

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

Але, виявляються, саме ці умови й роблять абсолютно стійкий шифр дуже дорогим і непрактичним. Перш ніж користуватися таким шифром, ми повинні забезпечити всіх абонентів достатнім запасом випадкових ключів і виключити можливість їхнього повторного застосування. А це зробити надзвичайно важко й дорого. Як відзначала Д. Кан: «Проблема створення, реєстрації, поширення й скасування ключів може здатися не занадто складною тому, хто не має досвіду передачі повідомлень по каналах військового зв'язку, але у воєнний час обсяг переданих повідомлень ставить у тупик навіть професійних зв'язківців. За добу можуть бути зашифровані сотні тисяч слів. Створення мільйонів ключових знаків зажадало б величезних фінансових витрат і було б пов’язане з великими затратами часу. Тому що кожен текст повинен мати свій власний, єдиний і неповторний ключ, застосування ідеальної системи зажадало б передачі принаймні такої кількості знаків, що еквівалентно всьому обсягу переданої військової інформації.»

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

2.6. Стійкість теоретична й практична

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

Звичайно цю думку виражають так: супротивник з необмеженими ресурсами може розкрити будь-який неабсолютно стійкий шифр.

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

Тому у користувача залишається єдиний шлях – одержання практичних оцінок стійкості. Цей шлях складається з таких етапів:

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

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

• при цьому необхідно в максимально забезпечити моделювання сил, засобів і можливостей супротивника;

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

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

2.7. Чи завжди потрібна атака на ключ

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

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

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

6. в усвідомлених текстах будь-якої природної мови різні букви зустрічаються з різною частотою, а дія підстановки g «переносить» цю закономірність на шифрований текст;

7. будь-яка природна мова має так звану надмірність, що дозволяє з великою ймовірністю «угадувати» зміст повідомлення, навіть якщо частина букв у повідомленні невідома.

Наведемо для прикладу відносні частоти букв алфавіту російської мови.

N	Буква	Відносна частота	N	Буква	Відносна частота	N	Буква	Відносна частота
1	а	0,062	12	л	0,035	23	ц	0,004
2	б	0,014	13	м	0,026	24	ч	0,012
3	в	0,038	14	н	0,053	25	ш	0,006
4	г	0,013	15	о	0,090	26	щ	0,003
5	д	0,025	16	п	0,023	27	ы	0,016
6	е, ё	0,072	17	р	0,040	28	ъ, ь	0,014
7	ж	0,007	18	с	0,045	29	э	0,003
8	з	0,016	19	т	0,053	30	ю	0,006
9	и	0,062	20	у	0,021	31	я	0,018
10	й	0,010	21	ф	0,002	32	–	0,175
11	к	0,028	22	х	0,009

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

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

• у оповіданні Е. По «Золотий жук»;

• у оповіданні А. Конан-Дойля «Танцюючі чоловічки»;

• у книзі М.Н. Аршинова й Л.Е. Садовского «Коди и математика».

2.8. Криптографія, комбінаторні алгоритми й обчислювальна техніка

Давайте задамо питанням: від прогресу в яких галузях науки залежать оцінки практичної стійкості шифрів? Уважний студент сам з попереднього викладу відповість на це питання: у першу чергу це – теорія складності алгоритмів й обчислень, а також складність реалізації алгоритмів на обчислювальній техніці. В останні роки ці області бурхливо розвиваються, у них отримані цікаві результати, які, зокрема, впливають на оцінки практичної стійкості шифрів. Багато корисних результатів носять характер «хитрувань» для прискорення алгоритмів і тому швидко входять у масову практику програмістів. Особливо це відноситься до області комбінаторних алгоритмів, що виросла з добре відомих типових задач швидкого пошуку й сортування даних. Систематичний докладний виклад цих питань міститься в популярному тритомнику Д. Кнута «Мистецтво програмування для ЕОМ».

Зауважимо, що до області комбінаторних алгоритмів відносяться також алгоритми для добре відомих ігор-головоломок типу «кубика Рубика».

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

Подумайте самі:

8. Доведіть, що найменший елемент серед чисел { х1 , ..., хn} не можна знайти менше, ніж за п–1 порівняння.

9. Запропонуйте алгоритм розташування чисел { х1 , ..., хn} у зростаючому порядку і використовує менше, ніж

порівнянь (тобто ефективніший, чим тривіальний алгоритм послідовного порівняння кожного числа з кожним).

10. На полиці безладно стоять n томів зібрання творів. Хазяїн, побачивши два томи, що стоять у неправильному порядку, міняє їх місцями. Доведіть, що не пізніше, ніж через n2 таких перестановок, томи будуть розставлені один за одним.

11. На сортувальній станції є декілька потягів. Дозволяється або розчепити потяг, що складається з декількох вагонів, на два потяги, або видалити потяг, якщо в ньому всього один вагон. Доведіть, що, виконуючи ці дії в довільному порядку, ми рано чи пізно видалимо всі вагони.

12. Задумано й уведено в комп'ютер n натуральних чисел b1, ..., bn. За один крок дозволяється ввести в комп'ютер будь-які n інших натуральних чисел b1, ..., bn. Після цього комп'ютер обчислює суму пекло а1 b1+ ... + аn bn і виводить результат на екран. Ясно, що цей результат містить деяку інформацію про задумані числа. За яке мінімальне число кроків завжди можна вгадати задумані числа?

Розділ 3. НОВІ НАПРЯМКИ

В 1983 році в книжці «Коды и математика» М.Н. Аршинова й Л.Е. Садовского (бібліотечка «Квант») було написано: «Прийомів тайнопису – безліч, і, швидше за все, це та область, де вже немає потреби придумувати що-небудь істотно нове.» Однак це була чергова велика омана щодо криптографії. Ще в 1976 році була опублікована робота молодих американських математиків У. Диффі й М. Е. Хеллмена «Нові напрямки в криптографії», що не тільки істотно змінила криптографію, але й привела до появи й бурхливого розвитку нових напрямків у математиці. У цьому розділі ми опишемо основні поняття «нової криптографії.»

3.1. Що таке однобічна функція

Однобічною називається функція F: X→ Y ,

Яка володіє двома властивостями:

а) існує поліноміальний алгоритм обчислення значень F(х);

б) не існує поліноміального алгоритму інвертування

функції F(х), тобто розв'язок рівняння F(х)=у відносно х .

Зауважимо, що однобічна функція істотно відрізняється від функцій, звичних зі шкільної лави, через обмеження на складність її обчислення й інвертування. Це нове поняття в математиці уведено в 1975 році Диффі й Хеллменом. Але за минулі роки так і не вдалося побудувати жодного приклада однобічної функції. Проте активне вивчення властивостей цього, поки гіпотетичного, математичного об'єкта дозволило встановити його зв'язок з іншими більше вивченими об'єктами. При цьому вдалося довести, що проблема існування однобічної функції еквівалентна одній з добре відомих невирішених проблем – «чи збігаються класи складностей Р та NP»? Строге визначення класів Р та NP виходить далеко за межі нашого курсу. Підготовленим студентам рекомендую фундаментальну монографію М. Гері й Д. Джонсона «Обчислювальні машини й труднорозв'язувані задачі».

Говорячи неформально, клас Р складається із задач із поліноміальною складністю. Більш строго, клас Р – це клас мови в, розпізнаваних за поліноміальний час на детермінованій машині Тьюринга. Якщо таку машину Тьюринга доповнити гіпотетичною здатністю «угадування», виходить більше сильна модель – недетермінована машина Тьюринга. Клас NP – це клас мов, розпізнаваних за поліноміальний час на недетермінованій машині Тьюринга. Проблема збігу класів Р та NP – це проблема співвідношення можливостей двох моделей обчислень: детермінована й недетермінована машина Тьюринга.

Іншим поняттям, більш близьким до традиційної криптографії, у якій є секретний ключ, є поняття однобічної функції із секретом. Іноді ще вживаються терміни функція з пасткою, функція опускних дверей (англійська назва: one-way trap-door function).

Однобічною функцією із секретом К називається функція FК : X→Y, що залежить від параметра К і володіє трьома властивостями:

а) при кожному К. існує поліноміальний алгоритм обчислення значень FК(X);

б) при невідомому К. не існує поліноміального алгоритму інвертування FК;

в) при відомому К існує поліноміальний алгоритм інвертування FК.

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

Приклади таких функцій приводяться в розділах 3.5, 3.6, 3.7. Варто відзначити, що для деяких кандидатів на звання однобічної функції були знайдені поліноміальні алгоритми інвертування й тим самим доведено, що ці функції не є однобічними.

3.2. Що дає однобічна функція для криптографії

Застосування однобічної функції в криптографії дозволяє:

1) організувати обмін шифрованими повідомленнями з використанням тільки відкритих каналів зв'язку, тобто відмовитися від секретних каналів зв'язку для попереднього обміну ключами;

2) залучити в завдання розкриття шифру важку математичну задачу й тим самим підвищити обґрунтованість стійкості шифру;

3) вирішувати нові криптографічні задачі, відмінні від шифрування (цифровий підпис тощо).

Перш ніж розглядати конкретні приклади, опишемо ідею Диффі й Хеллмена в загальному вигляді.

Користувач А, що хоче одержувати шифровані повідомлення, повинен спочатку вибрати яку-небудь однобічну функцію FK c секретом К. Він повідомляє всім зацікавленим (наприклад, публікує) опис функції FK як свій алгоритм шифрування. Але при цьому значення секрету К він нікому не повідомляє й тримає в секреті. Якщо тепер користувач В хоче послати А захищену інформацію х X, то він обчислює FK (x) та посилає по відкритому каналу до А. Оскільки А для свого секрету уміє інвертувати FK , те він обчислює X по отриманому FK (х). Ніхто інший не знає К і тому в силу властивості б) однобічної функції із секретом не зможе за поліноміальний час по відомому шифрованому повідомленню FK (х) обчислити захищену інформацію х.

Таким чином, побудована система передачі захищеної інформації, причому виконані дві нових властивості:

• для передачі повідомлень не потрібен попередній обмін ключами по секретному каналу зв'язку;

• стійкість шифру залежить від складності рішення важкого математичного завдання інвертування однобічної функції із секретом.

Описану систему називають криптосистемою з відкритим ключем, оскільки алгоритм шифрування FK є загальнодоступним або відкритим.

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

Описану вище ідею Диффі й Хеллмен запропонували використовувати також для цифрового підпису повідомлень, що неможливо підробити за поліноміальний час. Нехай користувачеві А необхідно підписати повідомлення х. Він, знаючи секрет К, знаходить таке у, що FK ( ) y = х, і посилає у користувачеві В у ролі свого цифрового підпису. Користувач В зберігає у як доказ того, що А підписав повідомлення х. Цей доказ незаперечний, оскільки ніхто інший в силу властивості б) однобічної функції із секретом не зможе за поліноміальний час по відомому повідомленню х = FK (у) підробити цифровий підпис у.

В подальшому на основі аналогічних міркувань був запропонований ще цілий ряд так званих криптографічних протоколів. Ці протоколи дозволили вирішити багато нових задач взаємодії віддалених користувачів по технічних каналах зв'язку в умовах різних загроз (докладніше про це див. у 3.8).

3.3. Числа, і поля в сучасній криптографії

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

Приведемо основні властивості операцій додавання на множині дійсних чисел F .

13. Для кожних трьох елементів а, b, c  F а + (b +c) = (а + b) + с.

14. У множині F є елемент 0 такий, що для кожного а  F а+0=0+а=а.

15. Для кожного елемента а  F існує такий елемент х  F, що а + х = х + а (такий елемент називається протилежним до даного).

16. Для кожних двох елементів a ,b a + b = b + а.

17. Для кожних трьох елементів a , b, с  F. а  ( b  с) = (а  b )  с.

18. У множині F є елемент 1 (не рівний 0) такий, що для кожного a  F a ⋅1 = 1⋅ a = a

19. Для кожного елемента а  F а  0 існує такий елемент х  F, що а  х = х  а = 1 (такий елемент називається оберненим до заданого).

20. Для кожних двох елементів а, b  F а  b = b  а.

21. Для кожних трьох елементів а, b, c  F а  (b +c) = аb + а  с.

Властивості 1)  4) –– це властивості операції додавання, властивості 5)  8) ––властивості операції множення, а властивість 9) встановлює зв'язок між цими двома операціями.

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

Полем, називається множина F із двома відображеннями («операціями»), кожна з яких зіставляє будь-якій парі елементів з F однозначно визначений третій елемент із F і ці відображення (умовно позначувані «+» та «• ») задовольняють дев'яти аксіомам (властивостям), наведеним вище.

Особливо важливими для криптографії є скінченні поля. Сконструюємо одне з таких полів.

Нехай р – просте число. Розглянемо безліч чисел {0, 1, 2, ..., р – 1} з операціями додавання й множення по модулі р (сумою двох чисел уважаємо залишок від розподілу на р звичайної суми, добутком – залишок від ділення на р звичайного добутку). Легко перевірити, що властивості 1)  4) виконані: для властивостей 1) і 4) це очевидно, елемент 0 у властивості 2) — це звичайний нуль, протилежний до елемента а у властивості 3) — це елемент р – а. Так само легко перевіряються властивості 5), б), 8) і 9). Властивість 7) треба доводити. Пропонуємо вам довести це самостійно, пояснимо тільки ідею: для кожного а{0, 1, 2, ..., р – 1} потрібно знайти такі х та у, що ах = 1 + ру, тобто ах — ру = 1, а такі х та у завжди можна знайти за допомогою алгоритму Евкліда.

Скінченне поле — дуже цікавий математичний об'єкт. Виявляється, наприклад, що число елементів у кінцевому полі може бути тільки ступенем простого числа, і навпаки, для будь-якого простого числа р і для будь-якого натурального числа n існує й у деякому смислі єдине поле з рn елементів. Для нього уведене навіть спеціальне позначення GF(рn).

Пояснимо більш докладно, у якому розумінні поле з рn елементів єдине. У математиці прийнято не розрізняти багато об'єктів, досліджувані властивості яких збігаються. Наприклад, для того, щоб складати й множити, зовсім не обов'язково вчити окремо таблиці додавання й множення для яблук, і окремо – для стільців. Досить уміти складати числа. Число в даній ситуації можна представляти як кількість одиниць деякого узагальненого продукту, неважливо якого. У теорії полів два поля G та F вважаються «однаковими» або ізоморфними, якщо можна побудувати таке взаємно однозначне відображення s : F → F щоб для будь-яких х1, х2  F виконувалися умови

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

Яскравий приклад використання полів у криптографії ви знайдете в розділі 3.5, що описує криптосистему RSA. Для її повного розуміння рекомендуємо вирішити (або прочитати в будь-якій книзі по теорії чисел, наприклад, у книзі И.М. Виноградова «Основи теорії чисел» або в книзі О. Оре,. Запрошення в теорію чисел») наведені нижче задачі.

Подумайте самі:

22. Функцією Ейлера (позначення φ(n)) називається кількість ненегативних цілих чисел, менших п і взаємно простих з п . Нехай

де pl, ..., pk – різні прості числа, a 1, ..., k – натуральні. Довести, що

23. (Мала теорема Ферма). Нехай р — просте число, a — число, взаємно просте з р. Доведіть, що тоді

24. (Теорема Ейлера). Нехай а й п — взаємно прості числа. Доведіть, що тоді

3.4. Проблеми факторизації чисел і дискретного логарифмування

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

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

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

Серед останніх досягнень у цій області можна згадати про успіх Ленстри й Монассі, що розклали в червні 1990 року 155-розрядне число на три простих. Для цього вони використали 1000 об'єднаних ЕОМ і використали шість тижнів їхнього машинного часу. Обчислення проводилися за допомогою алгоритму англійського математика Дж. Полларда. Ленстра й Монассі вважають, що в той час (1991 р.) можна протягом року розкласти нові класи цілих чисел довжиною до 155 розрядів, затративши на це 200 млн. доларів. Ще одна більша проблема –– дискретне логарифмування в скінченних полях. Нехай, наприклад, нам дані елементи а і b з кінцевого поля F , причому відомо, що а= bx при деякому натуральному x. Задача дискретного логарифмування полягає в тому, щоб визначити це x. Зрозуміло, можна просто перебирати послідовно всі натуральні числа, перевіряючи, чи виконана зазначена рівність, але це буде експонентний алгоритм. Поки найкращий з розроблених математиками алгоритмів дискретного логарифмування є субекспоненційним.

В наш час ці описані важкі математичні проблеми мають численні криптографічні додатки (див. розділи 3.5, 3.6, 3.7).

3.5. Криптосистема RSA

В розділі 3.2 описано, як Диффі й Хеллмен за допомогою однобічної функції із секретом побудували криптосистему з відкритим ключем. Правда, вони не запропонували функцій, зручних для реалізації.

Однак уже на початку 1977 р. американські фахівці з комп'ютерних наук Р. Ривест, А. Шамир і Л. Адлеман придумали одну таку функцію. Система на основі цієї функції виявилася дуже практичною й одержала широке поширення за назвою «система RSA» по перших англійських буквах прізвищ авторів. Опишемо систему RSA. При цьому ми будемо використати без докладних пояснень позначення й результати розділів 3.2 й 3.3. Нехай п=pq , де р та q – великі прості числа, а е — деяке число, взаємно просте з φ(n) . Знайдемо число d з рівняння

Числа р , q та d будемо вважати секретними й позначимо секрет К = { p, q, d } . Числа n та е будемо вважати загальнодоступними. Множини відкритих повідомлень X і шифрованих повідомлень Y будемо вважати рівними

X = Y = {1, 2, ..., n–1}.

Функцію FK : X→ Y визначимо рівністю

Властивість а) однобічної функції із секретом виконана для FK очевидним чином. Перевіримо властивість в). Для цього просто вкажемо, як при відомому F інвертувати функцію FK : розв'язанням рівняння FK (х) = у буде х = у d (mod n). Детальне доведення цього факту залишаємо студентові, наведемо лише необхідні викладення без коментарів:

Властивість б) для функції FK строго не доведена. Поки загальновизнано, що для інвертування FK необхідно розкласти п на множники, а, як указувалося в розділі 3.4, задача факторизації цілих чисел відноситься до важких математичних задач.

Таким чином, описану функцію FK можна вважати кандидатом на звання однобічної функції із секретом. Система RSA будується за допомогою цієї функції так, як викладено в розділі 3.2.

У газеті «Известия» за 29 квітня 1994 р. під заголовком «Надсекретний шифр розгаданий за 17 років» з'явилося наступне повідомлення: «Коли в 1977 році математики Рональд Ривест, Ади Шамир і Леонард Адлеман зашифрували фразу з декількох слів, використовуючи комбінацію з 129 цифр, вони стверджували, що на розгадку знадобляться трильйони років. Однак ключ до найскладнішого у світі шифру «PCА-129 » (мається на увазі система RSA) був знайдений за 17 років... Розгадка шифру за такий відносно короткий строк має величезне значення для державних організацій і підприємців, які користуються аналогічними довгими цифровими кодами для захисту секретних відомостей у своїх комп'ютерних базах даних...». Поки це повідомлення не підтверджене науковими публікаціями, ясно лише, що мова йде про те, що вдалося розкласти на множники те 129-значне число, що було використано в 1977 році. Але вже давно в реальних системах RSA використовуються довші числа.

Подумайте самі:

1. Розберіть приклади роботи системи RSA, наведені на стор. 241 243 книги М. Гарднера «От мозаик Пенроуэа к надежным шифрам».

3.6. Відкритий розподіл ключів

Крім принципу побудови криптосистеми з відкритим ключем, Диффі й Хеллмен у тій же роботі запропонували ще одну нову ідею — відкритий розподіл ключів. Вони задалися питанням, чи можна організувати таку процедуру взаємодії абонентів А та В по відкритих каналах зв'язку, щоб вирішити наступні задачі:

25. спочатку в А та В немає ніякої загальної секретної інформації, але наприкінці процедури така загальна секретна інформація (загальний ключ) в А та В з'являється, тобто видається;

26. супротивник, що перехоплює всі передачі інформації й знає, що хочуть одержати А і В, проте не може відновити виготовлений загальний ключ А і В.

Диффі й Хеллмен запропонували вирішувати ці задачі за допомогою функції

де р — велике просте число, х – довільне натуральне число,  — деякий примітивний елемент поля GF(p). Примітивним називається такий елемент , із GF(p) , що кожен елемент поля, за винятком нуля, може бути представлений у вигляді ступеня . Можна довести, хоча це й не просто, що примітивний елемент завжди існує. Загальновизнано, що інвертування функції тобто дискретне логарифмування, є важкою математичною задачею (див. розділ 3.4).

Власне процедура або, як прийнято говорити, протокол виготовлення загального ключа описується в такий спосіб. Числа р та  вважаються загальнодоступними. Абоненти А та В незалежно один від одного випадково вибирають по одному натуральному числу – скажемо хА й хВ. Ці елементи вони тримають як таємницю. Далі кожний з них обчислює новий елемент:

Потім вони обмінюються цими елементами по каналі зв'язку. Тепер абонент А, одержавши ув і знаючи свій секретний елемент хА, обчислює новий елемент

Аналогічно робить абонент В:

Із властивостей поля випливає, що тим самим у А та В з'явився загальний елемент поля, рівний Цей елемент і оголошується загальним ключем А і В.

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

3.7. Цифровий підпис

Ідея цифрового підпису (іноді її ще називають електронним підписом) була запропонована Диффі й Хеллменом. Суть ідеї – використання однобічної функції із секретом FK (див. розділ 3.2). У наш час ця ідея реалізована у великій кількості систем передачі даних, особливо банківських. Повідомлення, підписане цифровим підписом, можна уявляти собі як пару (х ,у), де х – повідомлення (платіжне доручення в прикладі з банком і т.п.), FK : X→ Y – однобічна функція, відома всім взаємодіючим абонентам, у – рішення рівняння FK ( y ) = х. З визначення функції FK (див. розділ 3.2) очевидні наступні достоїнства цифрового підпису:

27. підписати повідомлення х, тобто вирішити рівняння FK ( y ) = x, може тільки абонент – власник даного секрету К; інакше кажучи, підробити підпис неможливо;

28. перевірити дійсність підпису може будь-який абонент, що знає відкритий ключ, тобто саму функцію FK;

29. при виникненні спорів відмовитися від підпису неможливо в силу її непідробності;

30. підписані повідомлення (х, у) можна, не побоюючись збитку, пересилати по будь-яких каналах зв'язку.

Саме перераховані достоїнства й обумовили широке поширення систем цифрового підпису. Опишемо, як практично виглядає використання цифрового підпису, на найпростішому прикладі: робота банку із платіжними дорученнями своїх клієнтів. Всі абоненти цієї мережі знають однобічну функцію FK і кожен клієнт має свій власний, нікому не відомий секрет К. Клієнт підписує платіжне доручення х за допомогою функції FK зі своїм секретом К і посилає підписане платіжне доручення в банк. Банк, одержавши повідомлення від клієнта й знаючи відкритий ключ, перевіряє дійсність підпису клієнта й тільки після цього виконує його платіжне доручення. У силу відзначених вище достоїнств цифрового підпису й банк, і клієнт упевнені, що їхні інтереси не постраждають.

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

Подумайте самі:

1. Користуючись загальною схемою з розділу 3.2, опишіть схему цифрового підпису RSA.

3.8. Що таке криптографічний протокол

Під криптографічним протоколом розуміють таку процедуру взаємодії абонентів, у результаті якої абоненти (не супротивники!) досягають своєї мети, а супротивник — не досягає.

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

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

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

Наведемо ще кілька прикладів задач, розв'язуваних віддаленими абонентами. (Студентеві рекомендую за своїм смаком самостійно придумати ще які-небудь приклади).

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

Протокол вирішення цієї задачі прийнято називати протоколом підписання контракту.

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

Протокол рішення цього завдання прийнято називати протоколом підкидання монети.

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

1) X — скінченна множина цілих чисел, що містить однакова кількість парних і непарних чисел;

2. будь-які числа що мають один образ мають одну парність;

3. по заданому образі «важко» обчислити парність невідомого аргументу х.

Підкидання монети грає роль випадковості і рівноймовірний вибір елементу а роль орла й решки — парність і непарність х відповідно. Нехай А абонент, що підкидає монету, а В – абонент, що вгадує результат. Протокол складається з таких кроків:

1. А вибирає х («підкидає монету»), зашифровує х, тобто обчислює і відправляє у абонентові В;

2. В одержує у , намагається вгадати парність х і відправляє свою здогадку абонентові А;

3. А одержує здогадку від В і повідомляє В, чи вгадав він, відправляючи йому обране число х;

4) В перевіряє, чи не обманює А, обчислюючи значення і порівнюючи його з отриманим на другому кроці значенням у .

Рекомендуємо студентові самостійно перевірити, що необхідні вимоги до протоколу підкидання монети виконані через властивості функції

3. Взаємодіють два абоненти А і В (типовий приклад: А — клієнт банку, В — банк). Абонент А хоче довести абонентові В, що він саме А, а не супротивник.

Протокол вирішення цієї задачі прийнято називати протоколом ідентифікації абонента.

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

Цю задачу прийнято називати задачею про візантійських генералів, а протокол її рішення — протоколом візантійської угоди.

Опишемо приклад, якому ця задача зобов'язана своєю назвою. Візантія. Ніч перед великою битвою. Візантійська армія складається з n легіонів, кожний з яких підкоряється своєму генералу. Крім того, в армії є головнокомандуючий, що керує генералами. Однак імперія перебуває в занепаді й до однієї третини генералів, включаючи головнокомандуючого, можуть бути зрадниками. Протягом ночі кожний з генералів одержує від головнокомандуючого наказ про дії на ранок, причому можливі два варіанти наказу: «атакувати» або «відступати». Якщо всі чесні генерали атакують, то вони перемагають. Якщо всі вони відступають, то їм вдається зберегти армію. Але якщо частина з них атакує, а частина відступає, то вони зазнають поразки. Якщо головнокомандуючий виявиться зрадником, то він може дати різним генералам різні накази, тому накази головнокомандуючого не варто виконувати беззаперечно. Якщо кожен генерал буде діяти незалежно від інших, результати можуть виявитися жалюгідними. Очевидно, що генерали мають потребу в обміні інформацією один з одним (щодо отриманих наказів) для того, щоб дійти згоди.

Осмислення різних протоколів і методів їхньої побудови привело в 1985  1986 рр. до появи двох плідних математичних моделей — інтерактивної системи доказу й докази з нульовим розголошенням.

Математичні дослідження цих нових об'єктів дозволили довести кілька тверджень, досить корисних при розробці криптографічних протоколів.

Під інтерактивною системою доказу (Р, V, S) розуміють протокол взаємодії двох абонентів: Р (доказуючий) і V (перевіряючий). Абонент Р хоче довести V, що твердження S істинно. При цьому абонент V самостійно, без допомоги Р, не може довести твердження S (тому V і називається що перевіряючим). Абонент Р може бути й супротивником, що хоче довести V , що твердження S істинно, хоча воно хибне. Протокол може складатися з багатьох раундів обміну повідомленнями між Р і V і повинен задовольняти двом умовам:

31. повнота — якщо S дійсно істинно, то абонент Р майже напевно переконає абонента V визнати це;

32. коректність — якщо S хибно, то абонент Р навряд чи переконає абонента V, що S істинно.

Тут словами «майже напевно» й «навряд чи» я замінив точні математичні формулювання, що використовують поняття ймовірності.

Підкреслимо, що у визначенні системи (P, V, S) не допускалося, що V може бути супротивником. А якщо V виявився супротивником, який хоче «вивідати» у Р яку-небудь нову корисну для себе інформацію про твердження S? У цьому випадку Р, природно, може не хотіти, щоб це трапилося в результаті роботи протоколу (Р, V, S). Протокол (Р, V, S), що вирішує таку задачу, називається доказом з нульовим розголошенням і повинен задовольняти, крім умов 1 і 2, ще й наступній умові:

3) нульове розголошення (або стійкість) — у результаті роботи протоколу (P,V, S) абонент V не збільшить свої знання про твердження S або, інакше кажучи, не зможе витягти ніякої інформації про те, чому S істинно.

В 1991 році для широкого класу математичних проблем (що включає так звані NP-повні задачі) удалося довести існування доказів з нульовим розголошенням. Втім, це доведено тільки в припущенні, що існує однобічна функція.

Наведемо одне практичне застосування теорії доказів з нульовим розголошенням — «інтелектуальні картки» (непідробні посвідчення особи, кредитні картки й т.п.). У них вмонтований мікропроцесор, що реалізує дії абонента Р у протоколі, що претендує бути протоколом доказу з нульовим розголошенням (P, V, S).

Тут абонент Р — власник картки, а абонент V — наприклад, комп'ютер у банку або в прохідний секретної установи. Подумайте, чому в такому випадку можна забезпечити непідробність посвідчень особи й кредитних карток.

Висновок

Ви прослухали основи по криптографії. Якщо вам хочеться детальніше довідатися історію криптографії, події й легенди, пов'язані з нею, то рекомендую спробувати знайти й прочитати згадані в розділі 1.4 книги Д. Кана й Т.А. Соболєвої, а також будь-які номери журналу «Cryptology.»

Якщо ви захоплюєтеся програмуванням і вам захотілося самому реалізувати які-небудь криптографічні алгоритми, то насамперед корисно опанувати згадану в розділі 2.8 книгу Д. Батога. Потім можна звернутися до однієї із численних книг для програмістів з питань захисту інформації в ЕОМ.

Якщо вас цікавлять математичні питання криптографії, то в першу чергу необхідно поглибитися в ті розділи математики, які згадані в розділах 2.1, 2.2, 2.3, 3.3, 3.4 й 3.8. Систематичну освіту в цій області можна одержати в ДУІКТ, КПІ, КНАУ тощо.

Що ще можна почитати про криптографію

3. Т. Л. Соболєва. Тайнопис в історії Росії. (Історія криптографічної служби Росії ХУШ - початку XX в.). М., 1994.

4. К. Шеннон. Роботи з теорії інформації й кібернетику. М., МУЛ, 1963.

5. У. Диффи, М.Э. Хеллмэн. Захищеність й имитостойкость. Введення в криптографію. ТИИЭР, тім 67, N 3, 1979.

6. М. Фролов. Таємниці тайнопису. М., 1992.

7. М. Гарднер. Від мозаїк Пенроуза до надійних шифрів. М., Мир, 1993.

8. А.Н. Лебедєв. Криптографія з «відкритим ключем» і можливості її практичного застосування. «Захист інформації», випуск 2, 1992.

ДОДАТОК Обрані завдання олімпіад по криптографії

Для школярів при ИКСИ діє вечірня фізико-математична школа. З 1991 року інститут проводить олімпіади по криптографії й математиці, обрані завдання яких публікуються в даному додатку.

Завдання

33. Ключем шифру, називаного «ґрати», є трафарет, зроблений із квадратного аркуша картатого паперу розміром ПУ.П (П — четно). Деякі із кліток вирізують для того, щоб в отвори, що вийшли, на чистий аркуш паперу того ж розміру можна було вписувати букви тексту, що підлягає зашифруванню. Одна зі сторін трафарету є позначеною. Крім того, трафарет повинен володіти однією важливою властивістю: при накладенні його на чистий аркуш паперу чотирма можливими способами (позначеною стороною нагору, вправо, униз, уліво) його вирізи повністю покривають всю площу квадрата, причому кожна клітка виявляється під вирізом рівно один раз.

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

Знайдіть число різних ключів для довільного парного числа П.

34. 2. На адресу олімпіади прийшла шифртелеграмма

ЦДОЗИФКДЦЮ.

Прочитайте зашифроване повідомлення, якщо відомо, що використався шифр, по якому до двозначного порядкового номера букви в алфавіті (від 01 до 33) додавалося значення багаточлена

f(x) = xe + 3x5+x4 + x3+4x2+4x + 5,

обчислене або при X = Х^, або при X = Х2 (у випадковому порядку), де Х^,Х2 — корінь тричлена X + Зх +1, а потім отримане число замінялося відповідної йому буквою.

35. Одна фірма запропонувала пристрій для автоматичної перевірки пароля. Паролем може бути будь-який непустий упорядкований набір букв в алфавіті {d,b,c} . Будемо позначати такі набори більшими латинськими буквами. Пристрій переробляє уведений у нього набір Р у набір Q = ф (-Р) . Відображення ф тримається в секреті, однак про нього відомо, що воно визначено не для кожного набору букв Р и має наступні властивості. Для будь-якого набору букв Р

1) ф (ар) ; 2) ф (ЬР) = ф (Р)вф (Р) ;

3) набір ф (сР) виходить із набору ф (/?) виписуванням букв у зворотному

порядку.

Пристрій визнає пред'явлений пароль вірним, еслиф(-Р) = Р. Наприклад, трибуквений набір ЪиЪ є паролем, тому що ф (ЪиЬ) = ф (яб)яф (flb) = ЪиЪ . Підберіть пароль, що складається більш, ніж із трьох букв.

36. 4. Комерсант для передачі цифрової інформації з метою контролю передачі розбиває рядок переданих цифр на п'ятірки й після кожних двох п'ятірок приписує дві останні цифри від суми чисел, зображених цими п'ятірками. Потім процес шифрування здійснюється шляхом додатка до шифруемым цифр членів арифметичної прогресії з наступною заміною сум цифр залишками від розподілу на 10. Прочитайте зашифроване повідомлення:

423461405313.

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

38. на число 10, де U, Ъ фіксовані натуральні числа. З'ясувати, при яких значеннях CL й Ъ можливо однозначне расшифрование.

Фірма запропонувала на ринок кодовий замок. При установці власник замка зіставляє кожної з 26 латинських букв, розташованих на клавіатурі, довільне натуральне число (відоме лише власникові замка). Після вибору довільної комбінації попарно різних букв, відбувається підсумовування числових значень набраних букв і замок відкривається, якщо сума ділиться на 26. Доведіть, що для будь-яких числових значень букв існує комбінація, що відкриває замок.

39. Розглядається шифр, у якому букви російського 30-буквеного алфавіту ?1. занумеровані по наступній таблиці:

АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЬЫЭЮЯ 1234 56789 10 11121314 1516171819202122232425 26272829 30

Для зашифрування повідомлення т = t^,^...tn вибирається деяка послідовність ДО = y{Y2З « (ключ), що складається з букв алфавіту Q. Зашифрування складається в позначном додаванні відповідних букв із Т и К наступною заміною суми буквою алфавіту Q, номер якої дорівнює залишку від розподілу цієї суми на число 30.

Відомо, що два повідомлення т 1 і т 2 зашифровані за допомогою одного ключа (к), і що кожне з них містить слово «кораблі». Відновити Tj Т 2 по текстах даних криптограм: CTj =ЮПТЦАРГШАЛЖЖЕВЦЩЫРВУУ а 2 =ЮПЯТБНЩМСДТЛЖГПСГХСЦЦ

40. 8. Перехоплена «шифровка»

РБЬНПТСИТСРРЕЗОХ

Щодо шифру відомо наступне:

• використається шифр попереднього завдання;

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

41. 9. Шифр простої заміни в алфавіті А = {ala2,...,an} , щоскладається з П різних букв, полягає в заміні кожної букви шифруемого тексту буквою того ж алфавіту, причому різні букви заміняються різними. Ключем шифру простої заміни називається таблиця, у якій зазначене, якою буквою треба замінити кожну букву алфавіту А. Якщо слово ТЕРМІНОВО зашифрувати простою заміною за допомогою ключа: АБВГДЕЖЗШСЛМНОПРСТУФХЦЧШЩЬЫЭЮЯ

ЧЯЮЭЫЫЦШЦХФУБДТЗВРПМШСАИОЖЕСГН,

те вийде слово ВЗДАБД. Зашифрувавши отримане слово за допомогою того ж ключа ще раз, одержимо нове слово ЮШЫЧЯЫ. Скільки всього різних слів можна одержати, якщо зазначений процес шифрування продовжити необмежено?

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

43. У пункті Б отримане шифроване повідомлення додатково шифрується за допомогою некотооого лоугого iimdroa поостой заміни в тім же алфавіті, а відновите вихідне повідомлення

З_ГЖТПНБЛЖ ПРО РСТКД КСПХЕУ Б _Е_ПФ ПУБ_ЮО Б СП_ЕОКЖУУЛЖЛ СМЦХБЭКГОЩПЫ УЛ КЛ_ИКНТЛЖГ,

знаючи, що в одному з переданих відрізків зашифроване слово КРИПТОГРАФІЯ.

44. 11. Дано послідовність ІЗ1,З2,З3,...,Сп,..., у якій Слесть остання цифра числа п». Довести, що ця послідовність періодична і її період дорівнює 20.

45. 12. Знаки алфавіту, що складає з букв російської мови й символу боялася між словами (_), замінимо парами цифр відповідно до таблиці:

АБ У ГДЕЖЗ І КЛМНОПРС Т УФХЦЧШЩЬЫЭЮЯ_ 0102030405060708091011 1213 1415 161718 19202122232425262728293031

Для зашифрування повідомлення довжини т , записаного в цьому алфавіті, спочатку перетворимо буквений текст у цифровий Т = tlt2,...,t2m , а потім, вибравши відрізок ДО = Сп+1,Сп+2,...,Сп+2тпоследовательности із завдання 11, здійснимо послідовне поразрядное додавання цифр тексту Тс цифрами відрізка ДО, причому як черговий знак шифрованого тексту береться цифра одиниць відповідної суми (молодший розряд). Прочитайте зашифроване повідомлення:

2339867216458160670617315588.

Шифрування

Розглянуті основні концепції шифрування, різні види шифрування (із закритим і відкритим ключем), питання управління ключами. Дано поняття цифрового підпису. Приділена увага питанням довіри в інформаційних системах.

"Все, що необхідно для забезпечення безпеки – це якісне шифрування". Це твердження можна чути повсюди. Якщо інформація захищена шифруванням, ніхто не в силах її прочитати або змінити. Якщо ми використовуємо шифрування, то знаємо, з ким маємо справу, тому шифрування можна інтерпретувати і як аутентифікацію.

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

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

У цій лекції розглянемо основні поняття, пов'язані з шифруванням, і про те, як використовувати шифрування в цілях забезпечення безпеки інформації. Ми детально не розглядатимемо математичну основу шифрування. Проте, ми розглянемо декілька прикладів, аби розібратися в тому, як різні алгоритми шифрування використовуються в хорошій програмі безпеки.

Основні концепції шифрування

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

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

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

• Конфіденційність. Шифрування використовується для приховування інформації від неавторизованих користувачів при передачі або при зберіганні.

• Цілісність. Шифрування використовується для запобігання зміні інформації при передачі або зберіганні.

• Ідентифікованість. Шифрування використовується для аутентифікації джерела інформації і запобігання відмови відправника інформації від того факту, що дані були відправлені саме ним.

Терміни, пов'язані з шифруванням

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

• Звичайний текст. Інформація у вихідному вигляді. Також називається відкритим текстом.

• Шифрований (Зашифрований) текст. Інформація, піддана дії алгоритму шифрування.

Мал. Ш.1.  Загальний принцип шифрування

• Алгоритм. Метод, використовуваний для перетворення відкритого тексту в шифрований текст.

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

• Шифрування. Процес перетворення відкритого тексту в шифр.

• Дешифрування. Процес перетворення шифру у відкритий текст.

Існують також чотири терміни, які необхідно знати:

• Криптографія. Наука про приховування інформації за допомогою шифрування.

• Криптограф. Особа, що займається криптографією.

• Криптоаналіз. Мистецтво аналізу криптографічних алгоритмів на предмет наявності вразливостей.

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

Атаки на систему шифрування

Системи шифрування можуть піддатися атакам трьома наступними способами:

• Через слабкі місця в алгоритмі.

• За допомогою атаки "грубої сили" по відношенню до ключа.

• Через вразливості в довколишній системі.

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

Атаки "грубої сили" є спробами підбору будь-якого можливого ключа для перетворення шифру у відкритий текст. В середньому аналітик з використанням цього методу повинен перевірити дію 50 відсотків всіх ключів, перш ніж доб'ється успіху. Таким чином, потужність алгоритму визначається лише кількістю ключів, які необхідно перепробувати аналітикові. Отже, чим довший ключ, тим більше загальна кількість ключів, і тим більше ключів повинен перепробувати зловмисник до того, щоб знайти коректний ключ. Атаки з використанням грубої сили теоретично завжди повинні закінчуватися успішно за наявності необхідної кількості часу і ресурсів. Отже, алгоритми потрібно оцінювати за періодом часу, протягом якого інформація залишається захищеною при проведенні атаки з використанням "грубої сили". Алгоритм розцінюється як безпечний, якщо витрати на отримання ключа за допомогою атаки "грубої сили" перевищують вартість захищуваної інформації.

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

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

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

Шифрування з секретним ключем

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

У чому суть шифрування на секретним ключем?

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

Мал. Ш.2.  Шифрування з секретним ключем

Шифрування з секретним ключем забезпечує конфіденційність інформації в зашифрованому стані. Розшифрувати повідомлення можуть лише ті особи, яким відомий ключ. Будь-яка зміна в повідомленні, внесена під час передачі, буде виявлена, оскільки після цього не удасться правильно розшифрувати повідомлення. Шифрування з секретним ключем не забезпечує аутентифікацію, оскільки будь-який користувач може створювати, шифрувати і відправляти реальне повідомлення.

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

Підстановлювальні шифри

Підстановлювальні шифри існують вже близько 2500 років. Найранішим прикладом є шифр Атбаш. Він виник приблизно в 600 році до н.е. і полягав у використанні єврейського алфавіту в зворотному порядку.

Юлій Цезарь використовував підстановлювальний шифр, який так і називався, – шифр Цезаря. Цей шифр полягав в заміщенні кожної букви іншою буквою, розташованою в алфавіті на три букви далі від шифрованої. Таким чином, буква A перетворювалася в D, B перетворювалася в E, а Z перетворювалася в C.

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

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

Одноразові блокноти

Одноразові блокноти (One-time Pad, OTP) є єдиною теоретично незламуваною системою шифрування. Одноразовий блокнот є списком чисел у випадковому порядку, використовуваним для кодування повідомлення (див. таблиці. Ш.1). Як видно з назви системи, OTP може використовуватися лише один раз. Якщо числа в OTP є дійсно випадковими, OTP має більшу довжину, чим повідомлення, і використовується лише один раз, то шифрований текст не надає якого-небудь механізму для відновлення вихідного ключа (тобто самого OTP) і, отже, повідомлень.

Одноразові блокноти використовуються в інформаційних середовищах з дуже високим рівнем безпеки (але лише для коротких повідомлень). Наприклад, в Радянському Союзі OTP використовувався для зв'язку розвідників з Москвою. Двома основними недоліками OTP є генерація дійсно випадкових блокнотів і проблема поширення блокнотів. Вочевидь, що якщо блокнот стає відомим, то розкривається і та інформація, яку він захищає. Якщо блокноти не є дійсно випадковими, можуть бути виявлені схеми, які можна використовувати для проведення аналізу частоти символів, що зустрічаються.

Таблиця Ш.1. Функціонування одноразового блокноту

Повідомлення	S	E	N	D	H	E	L	P
Букви, замінені відповідними числами	19	5	14	4	8	5	12	16
Одноразовий блокнот	7	9	5	2	12	1	0	6
Додавання відкритого тексту в ОТР	26	14	19	6	20	6	12	22
Шифрований текст	Z	N	S	F	T	F	L	V

Ще одним важливим моментом, пов'язаним з OTP, є те, що одноразові блокноти можуть використовуватися лише один раз. Якщо OTP використовується кілька разів, то його можна проаналізувати і зламати. Це відбувалося з деякими радянськими OTP в період холодної війни. Тоді для прочитування зашифрованої інформації в Національному Агентстві безпеки був створений проект "Верона". Інформація про перехоплення даних цим проектом знаходиться на сайті NSA (http://www.nsa.gov ).

Увага!

Деякі сучасні системи шифрування також використовують щось подібне до OTP. Цей тип систем шифрування забезпечує досить високий рівень захисту, проте він точно також є легко зламуваною системою. Як правило, OTP непридатні для використання в середовищах з великим об'ємом трафіку.

Data Encryption Standard (DES)

Алгоритм Data Encryption Standard (DES) був розроблений компанією IBM на початку 1970-х рр. Національний інститут стандартів і технологій США (NIST) прийняв на озброєння алгоритм (публікація FIPS 46) для DES в 1977 р. після вивчення, модифікації і затвердження алгоритму в NSA. Алгоритм піддавався подальшій модифікації в 1983, 1988, 1993 і 1999 рр.

DES використовує ключ завдовжки 56 біт. Використовуються 7 біт з байта, восьмий біт кожного байту використовується для контролю парності. DES є блоковим алгоритмом шифрування, оброблювальним одноразово один 64-бітовий блок відкритого тексту (див. мал. Ш.3). У алгоритмі DES виконуються 16 циклів шифрування з різним підключем в кожному з циклів. Ключ піддається дії свого власного алгоритму для створення 16 підключів (див. мал. Ш.4).

Рис. Ш.3.  Блок-схема алгоритму DES

Рис. Ш.4.  Алгоритм генерації підключа DES

На блок-схемі алгоритму DES зображено декілька блоків, в яких відбувається перестановка. Даний стандарт шифрування передбачає спеціальне переупорядковування бітів для кожної перестановки. Те ж саме відноситься до алгоритму генерації підключа. Для перестановочної вибірки 1 і 2 передбачено певне переупорядковування бітів. На малюнку Ш.3 також зображена функція виклику f. У цій функції знаходяться S-блоки. S-блоки є блоками табличного пошуку (також визначені у стандарті), що змінюють 6-бітові вихідні дані на 4-бітові.

Алгоритм DES може функціонувати в чотирьох режимах.

• Електронний шифрблокнот. Це базовий алгоритм блокового шифрування, в якому текст і ключ об'єднуються і утворюють шифрований текст. У цьому режимі ідентичний вхід утворює ідентичний вихід.

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

• Зворотний зв'язок по шифрованому тексту. У даному режимі як вхідні дані в DES використовується раніше згенерований шифрований текст. Після цього вихідні дані комбінуються з відкритим текстом і утворюють новий шифртекст.

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

Було розкрито декілька атак, обчислювальних потужностей, що вимагають менше, ніж вичерпний пошук (диференціальний і лінійний криптоаналіз; для отримання детальніших відомостей по ці атаки відвідайте сайт (http://www.rsasecurity.com/rsalabs/faq/ ). Проте ці атаки вимагають великого об'єму вибіркового відкритого тексту і, отже, практично не здійсненні в реальному світі. Сьогодні особливо помітним слабким місцем шифрів став 56-бітний ключ. 56 біт ключа забезпечують потенційну кількість ключів, рівною 255. У сьогоднішніх комп'ютерних системах весь простір ключів може бути вивчений за невеликий проміжок часу. У 1997 р. організація Electronic Frontier Foundation (EFF) анонсувала комп'ютерну систему, яка зможе знайти ключ DES за чотири дні. Створення цієї системи коштувало 250 000 доларів. За допомогою сучасного устаткування можна визначити ключ DES за допомогою атаки "грубої сили" за 35 хвилин. Цього часу дуже мало, аби захистити інформацію, яка повинна зберігатися в секреті. У переробленій публікації FIPS (46-2 і поточна 46-3) в NIST визнали цей факт, сказавши, що простий DES можна використовувати лише в застарілих системах.

Потрійний DES

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

Мал. Ш.5.  Блок-схема алгоритму шифрування TDES

Потрійний DES використовується або з двома, або з трьома ключами. При використанні двох ключів ключ K3 ідентичний K1. TDES є відносно швидким алгоритмом, оскільки його можна реалізувати апаратно. Його функціонування займає в три рази більше часу, чим в DES, оскільки мають місце три операції шифрування DES. У більшості додатків рекомендується використовувати TDES замість простого DES.

Примітка

TDES піддавався двом атакам. Проте, об'єм даних, потрібний для проведення атак (як і у випадку з атаками на DES), робив проведення атак на цей алгоритм практично нездійсненним в реальних ситуаціях.

Шифрування паролів

Стандартна схема шифрування паролів UNIX є різновидом DES. Хоча функція шифрування паролю є насправді однобічною функцією (не можна отримати відкритий текст з шифрованого тексту). Ми наведемо обговорення цієї функції, аби показати, яким чином алгоритм DES може використовуватися в додатках такого типу.

У кожного користувача є свій пароль. Алгоритм використовує перші вісім символів паролю. Якщо пароль довший за вісім символів, він усікається. Якщо пароль коротший за вісім символів, він доповнюється. Пароль перетвориться в 56-бітове число за допомогою перших 7 біт кожного символу. Після цього система вибирає 12-бітне число на базі системного часу. Цей елемент називається "Крупинкою солі" або розширенням. Розширення і пароль використовуються як вхідні дані у функції шифрування паролів (див. мал. Ш.6).

Мал. Ш.6.  Функція шифрування паролю UNIX

Розширення використовується для зміни однієї з таблиць перестановки в алгоритмі DES (перестановка E) будь-яким з 4096 різних способів, залежно від кількості одиниць в дванадцяти бітах. Початковий відкритий текст містить 56 нульових бітів, а ключем є 56 біт, отриманих з паролю. Алгоритм виконується 25 разів, причому вхідні дані кожного етапу є виходом попереднього етапу.

Кінцеві вихідні дані перетворяться в 11 символів, а розширення перетвориться в 2 символи і поміщається перед кінцевими даними виходу.

Головною уразливістю цієї системи є те, що вона заснована на виборі паролю. Оскільки більшість користувачів комп'ютерів використовують паролі, що складаються з символів нижнього регістра, ми маємо загальну кількість можливих комбінацій, рівною 268. Це значно менше, ніж 255 можливих ключів DES, тому злом такого шифру за допомогою "грубої сили" займе значно менше часу і обчислювальних ресурсів для розкриття паролів у системі Unix.

Примітка

Більша частина систем Unix тепер забезпечує можливість використання тіньових файлів паролів. Якщо зашифровані паролі легко зламуються за допомогою грубої сили, то за допомогою приховування зашифрованих паролів можна дещо підвищити рівень безпеки системи. Як і у випадку з останніми системами, якщо кореневий пароль є слабким, або якщо в корені системи присутня "діра", то правильність вибору паролів користувачами вже не грає ніякої ролі.

Розширений стандарт шифрування Rijndael

Натомість DES NIST анонсував в 1997 р. появу алгоритму-конкурента стандарту DES з назвою AES. У кінці 2000 р. NIST оголосили про те, що два криптографи з Бельгії (Joan Daemen і Vincent Rijmen) виграли конкурс, представивши алгоритм Rijndael. Цей алгоритм був вибраний з врахуванням його потужності, застосовності у високошвидкісних мережах, а також можливості апаратної реалізації.

Rijndael є блоковим шифром, що використовує ключі і блоки завдовжки 128, 192 або 256 біт. На сьогоднішній день така довжина ключів забезпечує практичну нездійсненність атак із застосуванням грубої сили. Алгоритм складається з 10-14 циклів, залежно від розмірів блоку відкритого тексту і розміру ключа. На малюнку Ш.7 показано, які обчислення здійснюються в кожному циклі.

Оскільки цей стандарт був схвалений, Rijndael почав з'являтися в багатьох системах. Даний алгоритм можна вважати гідною альтернативою алгоритму TDES.

Інші алгоритми шифрування з секретним ключем

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

• IDEA (International Data Encryption Algorithm). Розроблений в Швейцарії. У IDEA використовується 128-бітовий ключ; окрім цього, IDEA також використовується в Pretty Good Privacy (PGP).

• RC5. Розроблений Роном Рівестом в інституті MIT. Цей алгоритм дозволяє використовувати ключі із змінною довжиною.

• Skipjack. Розроблений урядом США для використання з Clipper Chip. У ньому використовується 80-бітовий ключ, що в найближчому майбутньому, швидше за все, стане вже неприйнятним.

Мал. Ш.7.  Схема роботи циклу алгоритму Rijndael

• Blowfish. Дозволяє використовувати змінні ключі завдовжки до 448 біт; алгоритм оптимізований для роботи на 32-бітових процесорах.

• Twofish. Використовує 128-бітові блоки, а також ключі завдовжки 128, 192 або 256 біт.

• CAST-128. Використовує 128-бітовий ключ. Застосовується в нових версіях PGP.

• Алгоритм ГОСТ (ГОСТ 28147-89). Російський стандарт шифрування, розроблений у відповідь на DES. У ньому використовується ключ завдовжки 256 біт.

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

Увага!

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

Шифрування з відкритим ключем

Шифрування з відкритим ключем є пізнішою технологією, ніж шифрування з секретним ключем. Головною відмінністю між цими двома технологіями є кількість ключів, використовуваних при шифруванні даних. У шифруванні з секретним ключем для шифрування і дешифровки даних використовується один і той же ключ, тоді як в алгоритмах шифрування з відкритим ключем використовуються два ключі. Один ключ використовується при шифруванні інформації, інший – при дешифровці.

У чому полягає шифрування з відкритим ключем?

На малюнку Ш.8 показана базова схема шифрування з відкритим ключем (асиметричного шифрування). Як видно з малюнка, обидва абоненти (і відправник, і одержувач) повинні мати ключ. Ключі зв'язані один з одним, але вони різні. Зв'язок між ключами полягає в тому, що інформація, зашифрована з використанням ключа K1, може бути дешифрована лише за допомогою його пари – ключа K2. Якщо інформація зашифрована за допомогою K2, то розшифрувати її можна лише з використанням ключа K1.

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

Мал. Ш.8.  Шифрування з відкритим ключем

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

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

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

Алгоритм обміну ключами Діффі-Хеллмана

Уїтфілд Діффі (Whitfield Diffie) і Мартін Хеллман (Martin Hellman) розробили свою систему шифрування з відкритим ключем в 1976 р. Система Діффі-Хеллмана (Diffie-Hellman) розроблялася для вирішення проблеми поширення ключів при використанні систем шифрування з секретними ключами. Ідея полягала в тому, аби застосовувати безпечний метод узгодження секретного ключа без передачі ключа яким-небудь іншим способом. Отже, необхідно було знайти безпечний спосіб здобуття секретного ключа за допомогою того ж методу зв'язку, для якого розроблявся захист. Алгоритм Діффі-Хеллмана не можна використовувати для шифрування або дешифровки інформації.

Алгоритм Діффі-Хеллмана працює таким чином.

1. Припустимо, що двом абонентам (P1 і P2) потрібно встановити між собою безпечне з'єднання, для якого необхідно погоджувати ключ шифрування.

2. P1 і P2 приймають до використання два великі цілі числа а і b, причому 1 < а < b.

3. P1 вибирає випадкове число i та обчислює I = aⁱ mod b. P1 передає I абонентові P2.

4. P2 вибирає випадкове число j та обчислює J = a^j mod b. P2 передає J абонентові P1.

5. P1 обчислює k1 = Jⁱ mod b.

6. P2 обчислює k2 = I^j mod b.

7. Маємо k1 = k2 = a^i*j mod b, отже, k1 і k2 є секретними ключами, призначеними для використання при передачі інших даних.

Примітка

У наведених вище рівняннях "mod" означає залишок. Наприклад, 12 mod 10 = 2. Два – це залишок від ділення 12 на 10.

Якщо зловмисник прослухує трафік, передаваний по кабелю, то йому будуть відомі а, b, I і J. Проте, залишаються в секреті i та j. Рівень безпеки системи залежить від складності знаходження i при відомому I = aⁱ mod b. Ця задача називається задачею дискретного логарифмування і вважається дуже складною (тобто за допомогою сучасного обчислювального устаткування її вирішити практично неможливо), якщо числа дуже великі. Отже, а і b необхідно вибирати дуже ретельно. Наприклад, обидва числа b і (b – 1) /2 мають бути простим і мати довжину не менше 512 біт. Довжина чисел, що рекомендується, складає 1024 біт.

Алгоритм обміну ключами Діффі-Хеллмана використовується в багатьох системах безпеки для реалізації обміну ключами, використовуваними для додаткового трафіку. Недоліком системи Діффі-Хеллмана є те, що вона може бути уразлива для атаки посередником (див. мал. Ш.9). Якщо той, що атакує зуміє розмістити свій комп'ютер між двома абонентами P1 і P2, підключити його до каналу зв'язку і здійснювати перехоплення всієї передаваної інформації, то він зможе виконувати обмін даними з P2, видаючи себе за P1, і з P1 під виглядом P2. Таким чином, обмін ключами відбуватиметься між P1 і зловмисником і між P2 і зловмисником. Проте, здійснення такої атаки вимагає великого об'єму ресурсів, і в реальному світі такі атаки відбуваються рідко.

Мал. Ш.9.  Атака посередником на алгоритм Діффі-Хеллмана

Алгоритм RSA

У 1978 р. Рон Рівест, Аді Шамір і Лен Адельман розробили алгоритм шифрування Rivest-Shamir-Adleman (RSA) з відкритим ключем. На відміну від алгоритму Діффі-Хеллмана RSA може використовуватися для шифрування і дешифрування. Також, на відміну від алгоритму Діффі-Хеллмана, безпека алгоритму RSA базується на факторизації великих чисел. Задача факторизації великих чисел прийнято вважати дуже складною, якщо числа дуже великі (1024 біт або більше).

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

Шифрований текст = (відкритий текст) e mod n

Відкритий текст = (шифрований текст) d mod n

Секретний ключ = {d, n}

Відкритий ключ = {e, n}

Безпека забезпечується складністю обчислення d за наявності відомих e і n. Мається на увазі, що власник пари ключів зберігає секретний ключ у таємниці, і що відкритий ключ передається у відкритому вигляді. Отже, якщо інформація зашифрована за допомогою відкритого ключа, дешифрувати її може лише власник ключової пари.

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

Шифрований текст = (відкритий текст) d mod n

Відкритий текст = (шифрований текст) e mod n

Секретний ключ = {d, n}

Відкритий ключ = {e, n}

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

Генерація ключів RSA

При генеруванні ключів RSA потрібно бути ретельним. Аби згенерувати ключову пару RSA, виконайте наступні кроки:

1. Виберіть два прості числа p і q і тримайте їх в таємниці.

2. Обчисліть n = pq.

3. Обчисліть ф(n) = (p – 1)(q – 1).

4. Виберіть таке e, аби воно було взаємно простим по відношенню до ф(n).

5. Визначте таке d, аби (d)(e) = 1 mod ф(n) і d < ф(n).

Примітка

Число n повинне містити приблизно 200 знаків або більше. Тоді обидва числа p і q повинні мати довжину, принаймні, 100 знаків. Ключі для використання на практиці повинні мати довжину 1024 біт. У випадку з секретною інформацією рекомендується використовувати ключі завдовжки 2048 біт і більше.

Реальний приклад роботи RSA

Майте на увазі, що мною вибрані числа, які відносно легко перевірити при виконанні цього прикладу. В реальному світі в алгоритмі RSA використовуються набагато більші числа.

1. Спочатку я вибрав два прості числа. В даному випадку були вибрані числа p = 11 і q = 13.

2. Тепер обчислюваний n = pq. Маємо n = 11 * 13 = 143.

3. Тепер потрібно обчислити ф(n)= (p – 1)(q – 1) = (11 – 1)(13 – 1) = 10 * 12 = 120.

4. Вибираємо число e так, щоб воно було простим відносно ф(n). Тут було вибрано значення e = 7.

5. Необхідно визначити таке d, аби (d)(e) = 1 mod ф(n). Отже (d)(7) = 1 mod 120; d має також бути менше 120. Знаходимо, що d = 103. (103 умножаємо на 7 і виходить 721. 721 ділимо на 120 і отримуємо 6 із залишком 1.)

6. Секретний ключ: {103, 143}.

7. Відкритий ключ: {7, 143}.

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

Шифрований текст = (відкритий текст) e mod n

Відкритий текст = (шифрований текст) d mod n

Припустимо, що потрібно відправити повідомлення "9". За допомогою формули шифрування отримуємо наступне:

Шифрований текст = (9)7 mod 143 = 48.

При отриманні зашифрованої інформації вона піддається обробці алгоритмом дешифровки:

Відкритий текст = (48)103 mod 143 = 9.

Інші алгоритми з відкритим ключем

Існують деякі алгоритми з відкритим ключем, що мають такі ж властивості, як RSA і алгоритм Діффі-Хеллмана. У даному параграфі ми коротко розглянемо три найбільш поширених алгоритми.

Алгоритм Ель-Гамаля

Ель-Гамаль (Taher Elgamal) розробив варіант системи Діффі-Хеллмана. Він удосконалив алгоритм Діффі-Хеллмана і отримав один алгоритм для шифрування і один для забезпечення аутентифікації. Алгоритм Ель-Гамаля не був запатентований (на відміну від RSA) і, таким чином, став дешевшою альтернативою, оскільки не була потрібна сплата ліцензійних внесків. Оскільки цей алгоритм базувався на системі Діффі-Хеллмана, безпека інформації при його використанні забезпечується складністю рішення задачі дискретного логарифмування.

Алгоритм цифрового підпису

Алгоритм Digital Signature Algorithm (DSA) був розроблений урядом США як стандартний алгоритм для цифрових підписів (для отримання додаткової інформації по цифрових підписах зверніться до наступного параграфа). Даний алгоритм базується на системі Ель-Гамаля, але дозволяє здійснювати лише аутентифікацію. Конфіденційність цим алгоритмом не забезпечується.

Шифрування з використанням еліптичних кривих

Еліптичні криві були запропоновані для використання в системах шифрування у 1985 р. Системи шифрування з використанням еліптичних кривих (ECC) базуються на іншій складнішій математичній задачі, ніж факторизація або дискретне логарифмування. Ця задача полягає в наступному: маючи дві точки A і B на еліптичній кривій, такі що A = кВ, дуже важко визначити ціле число. Існує ряд переваг використання ECC перед алгоритмом RSA або Діффі-Хеллмана. Найбільшою перевагою є те, що ключі мають меншу довжину (унаслідок складності завдання), внаслідок чого обчислення отримуються швидше із збереженням рівня безпеки. Наприклад, безпека, що забезпечується 1024-бітовим ключем RSA може бути забезпечена 160-бітовим ключем ECC. Може пройти немало часу, перш ніж ECC будуть повністю прийняті до використання, оскільки в цій області ще необхідно провести ряд досліджень, і на існуючі ECC зареєстровано декілька патентів.

Питання для самоперевірки

1. Відкритий текст перетвориться в _________________ в процесі шифрування.

2. До якого типу систем шифрування відноситься DES?

Цифрові підписи

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

Що таке цифровий підпис?

Як вже говорилося, цифрові підписи – це не зображення рукописних автографів, поставлених на паперовому документі. Цифровий підпис – це метод аутентифікації електронної інформації за допомогою шифрування.

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

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

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

Безпека і корисність цифрових підписів залежить від двох найважливіших елементів:

• Захист секретного ключа користувача.

• Безпечна хеш-кодування-функція.

Примітка

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

Мал. Ш.10.  Функціонування цифрових підписів

Безпечні хеш-функції

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

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

• украй складно сконструювати два фрагменти інформації із отримааням однакової контрольної суми при виконанні функції.

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

Безпечні хеш-функції повинні забезпечувати створення контрольної суми довжиною, принаймні, в 128 біт. Двома найбільш поширеними безпечними хеш-функціями є MD5, що генерує 128-бітову контрольну суму, і SHA, яка виробляє контрольну суму завдовжки 160 біт. Існує безліч інших хеш-функцій, проте велика їх частина визнана небезпечною. У MD5 були виявлені уразливості, які можуть використовуватися при проведенні обчислювальної атаки. Ця атака дозволить створити додатковий фрагмент інформації, що приведе до утворення тієї ж контрольної суми. Функція SHA була розроблена урядом США і в даний час вважається безпечною. У більшій частині ПЗ по інформаційній безпеці розглянуті функції MD5 і SHA доступні для використання.

Управління ключами

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

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

Створення ключів

Вочевидь, що ключі повинні створюватися з особливою ретельністю. Деякі ключі забезпечують недостатню продуктивність при роботі з певними алгоритмами. Наприклад, ключ, що складається з одних "нулів", при використанні в DES не забезпечує високий рівень захищеності інформації. Аналогічно, при створенні ключів для використання в RSA, необхідно бути уважним при виборі p і q з набору простих чисел.

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

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

Також може бути необхідним вибрати правильну довжину ключа. У деяких алгоритмах використовуються ключі фіксованої довжини (наприклад, в алгоритмі DES використовується ключ завдовжки 56 біт). Інші алгоритми можуть використовувати ключі змінної довжини. Чим довше ключ, тим вище рівень забезпечуваної безпеки. Наприклад, 1024-бітовий ключ RSA надійніший, ніж 512-бітовий ключ RSA. Проте, таким чином не можна зіставляти надійність ключа RSA з надійністю ключа DES. У таблиці Ш.2 представлені відносні міри надійності ключів для різних алгоритмів шифрування.

Аби отримати уявлення про те, наскільки надійні ключі на практиці, пригадайте машину EFF. У 1997 р. вона коштувала 250 000 доларів і забезпечувала розкриття ключа DES за 4,5 дня. У інших випадках 40-бітовий ключ RC5 був розкритий за допомогою атаки "грубої сили" за 3,5 години з використанням 250 комп'ютерів в UC Berkley. У Швейцарському Федеральному інституті технологій за допомогою "грубої сили" розкритий 48-бітовий ключ RC5 за 312 годин з використанням 3500 комп'ютерів. На даний момент рекомендується використовувати, як мінімум, 80-бітові ключі при шифруванні секретної інформації, а також мінімум 1024-бітові ключі в RSA і алгоритмі Діффі-Хеллмана. 160-бітові ключі ECC також вважаються безпечними.

Увага!

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

Поширення ключів

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

Таблиця Ш.2. Відносна надійність ключів різної довжини

Шифрування з секретним ключем(DES, RC5)	Шифрування з відкритим ключем(RSA, Діффі-Хеллман)	Шифрування за допомогою еліптичних кривих
40 біт	-	-
56 біт	400 біт	-
64 біт	512 біт	-
80 біт	768 біт	-
90 біт	1024 біт	160 біт
120 біт	2048 біт	210 біт
128 біт	2304 біт	256 біт

Такий підхід може бути корисним, якщо віддалені сайти розташовані в невеликій відстані. Але що якщо віддалені сайти розташовані на інших континентах? Проблема набуває набагато серйознішого характеру.

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

Будь-який ключ, використовуваний протягом тривалого періоду часу, вимагає забезпечення ґрунтовних запобіжних засобів. Не можна використовувати алгоритм обміну ключами Діффі-Хеллмана для передачі пар ключів RSA. У випадку з парами ключів RSA один ключ повинен міститися в секреті, а інший може знаходитися у відкритому місці. Відкритий ключ повинен публікуватися так, щоб запобігти його підміні (див. розділ нижче "Сертифікація ключів"). Якщо пари ключів генеруються центральним бюро сертифікатів, секретний ключ повинен безпечно передаватися власникові ключової пари. Якщо пара ключів генерується власником, відкритий ключ повинен передаватися в центральне бюро сертифікатів із забезпеченням заходів безпеки.

Примітка

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

Сертифікація ключів

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

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

Увага!

Без правильної сертифікації ключа і його власника зловмисник може впровадити власні ключі і, таким чином, здолати захист всієї передаваної і аутентифікованої інформації.

Мал. Ш.11.  Сертифікація відкритого ключа в бюро сертифікатів

Захист ключів

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

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

Необхідно забезпечувати захист всіх ключів системи, що використовує секретні ключі. Якщо ключ міститься у файлі, цей файл має бути захищений у будь-якому місці, де б він не знаходився (включаючи архівні носії). Якщо ключ знаходиться в пам'яті, необхідно робити заходи по захисту простору пам'яті від дослідження користувачами або процесами. Аналогічно, у випадку з дампом (скиданням даних на жорсткий диск) ядра, файл ядра має бути захищений, оскільки він може містити ключ.

Анулювання ключів

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

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

У системі шифрування з відкритим ключем справи йдуть трохи інакше. Якщо пара ключів несанкціоновано розкривається і анулюється, не існує певного способу інформування всіх потенційних користувачів відкритого ключа про те, що ключ недійсний. У деяких випадках відкриті ключі публікуються на серверах ключів. Особа, що бажає зв'язатися з власником ключа, може зайти на сервер для отримання сертифікованого відкритого ключа. Якщо ключ розкритий і анулюваний, яким чином про це взнає стороння особа? Вирішенням цієї проблеми є періодичні відвідини сервера ключів для з'ясування того, чи був він скасований; власник ключа повинен розміщувати інформацію про анулювання ключа на всіх потенційних серверах ключів. Сервери ключів повинні містити дану інформацію про відміну ключів до тих пір, поки не закінчиться термін дії оригінального сертифікату.

Довіра в інформаційній системі

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

Можливо, найсерйознішою проблемою, пов'язаною з довірою, є його встановлення і підтримка. Для забезпечення довіри в середовищі з відкритим ключем використовуються дві основні схеми – ієрархія і мережа. В обох схемах є як переваги, так і недоліки.

Ієрархія

Ієрархічна модель довіри найбільш проста для сприйняття. Кажучи звичною мовою, в даному випадку ви довіряєте людині, яка знаходиться вищим в ієрархічному ланцюзі, оскільки від нього було отримано відповідну вказівку про необхідність довіри. На малюнку Ш.12 зображена схема цієї моделі. Як видно з малюнка, користувачі User1 і User2 розташовуються під CA1. Отже, якщо CA1 говорить, що сертифікат відкритого ключа належить користувачеві User1, користувач User2 віритиме цьому. На практиці User2 передає користувачеві User1 свій сертифікат відкритого ключа, підписаний CA1. Користувач User1 перевіряє підпис CA1 з використанням відкритого ключа CA1. Оскільки CA1 знаходиться в ієрархії вище, ніж User1, то User1 довіряє CA1 і, отже, довіряє сертифікату користувача User2.

Мал. Ш.12.  Ієрархічна модель довіри

Ми розглянули досить простий випадок. Якщо користувачеві User1 потрібно перевірити інформацію від користувача User3, все дещо складніше. CA1 не знає про користувача User3, на відміну від CA2. Проте, користувач User1 не довіряє CA2, оскільки це бюро сертифікатів безпосередньо не належить ланцюжку користувача User1. Наступний рівень вгору по ланцюжку – CA4. Користувач User1 може верифікувати інформацію від користувача User3 за допомогою перевірки за допомогою CA4 таким чином.

1. Користувач User1 дивиться на сертифікат користувача User3. Він підписаний в CA2.

2. Користувач User1 отримує сертифікат користувача CA2. Він підписаний в CA4.

3. Оскільки користувач User1 довіряє CA4, відкритий ключ CA4 може використовуватися для верифікації сертифікату CA2.

4. Як тільки сертифікат CA2 верифікований, користувач User1 може верифікувати сертифікат користувача User3.

5. Як тільки буде верифікований сертифікат користувача User3, користувач User1 може використовувати відкритий ключ користувача User3 для верифікації даних.

Як бачите, все досить швидко ускладнюється. Уявіть собі, який об'єм операцій по верифікації необхідно було б виробляти, якби користувачеві User1 потрібно було верифікувати дані, що поступили від користувача User4. Два ланцюжки не перетинаються аж до CA9! Так реалізована сертифікація в X.509. Ієрархія встановлюється так, щоб між будь-якими двома нижніми об'єктами міг бути створений ланцюжок сертифікатів.

З теоретичної точки зору все виглядає непогано. Проте на практиці все інакше. Одна з причин, по якій дана технологія не функціонувала, полягає в тому, що не існувало реальних CA кореневого рівня. CA кореневого рівня – це найвища точка в ієрархії. В один час було прийнято вважати, що в кожній країні має бути своє бюро сертифікатів кореневого рівня. Також передбачалося, що компанії, що випускають кредитні карти, повинні стати кореневими CA, або що кожна організація повинна мати своє власне CA. На практиці майже нічого не було реалізовано. Виникало ще одне питання, яке було потенційною проблемою: скільки CA повинні сертифікувати кожного кінцевого користувача? Якщо кінцевий користувач живе в країні А, володіє кредитною картою компанії B і працює в організації C, чи повинні всі три об'єкти підписувати один і той же сертифікат?

Установка CA

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

• Має бути створена пара відкритого ключа CA. Ключ має бути чималим, аби забезпечувати безпеку на великий період часу (як правило, більш ніж на два роки).

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

• Секретний ключ CA має бути захищений на весь період свого існування. Якщо він коли-небудь буде розкритий, може знадобитися перебудова всієї інфраструктури.

• Необхідно створити відповідні політики і процедури для аутентифікації і підписки сертифікатів нижнього рівня.

• Необхідно реалізувати механізм, що дозволяє об'єктам нижніх рівнів верифікувати сертифікати один одного. Це означає, що сертифікат CA має бути доступний кожному об'єкту нижнього рівня. У деяких випадках це означає безпосередню взаємодію з CA. У такій структурі необхідно, аби CA було доступне протягом всього періоду часу, або це бюро сертифікатів викличе помилки в роботі всієї системи.

Питання до експерта. Чи існують CA загального користування?

Відповідь. Так, існують "загальні" бюро сертифікатів, призначені для обслуговування основної маси населення, а не певних організацій. VeriSign (http://www.verisign.com ) і Thawte (http://www.thawte.com/ ) є найбільш яскравими прикладами таких CA. Організація може створити пару відкритого ключа, наприклад для веб-сервера, і відправити відкритий ключ до CA. CA створює сертифікат і надає його організації. CA отримує прибуток від надання цієї послуги. Використання таких сертифікатів можна спостерігати при відвідинах багатьох захищених сайтів в Інтернеті. Оскільки відкриті ключі CA відомі більшій частині веб-браузерів, сертифікат веб-сайту верифікується за допомогою відкритого ключа CA.

Примітка

Системи, використовувані в CA, і сертифікати CA (особливо секретні ключі CA) мають бути добре захищені, оскільки CA є "серцем" системи. Заходи, що робляться для захисту секретного ключа CA, як правило, вимагають, аби розблокування секретного ключа виробляли дві людини.

Як видно із списку, наведеного вище, при розробці CA виникає ціла низка запитань. Якщо організація досить велика або має велику кількість об'єктів нижніх рівнів (тобто користувачів), адміністрування сертифікатів користувачів буде зовсім не простим завданням. Перед підпискою сертифікату потрібно буде перевірити особу кожного користувача. Термін дії сертифікатів періодично закінчуватиметься, і, отже, виникатиме потреба у видачі нових сертифікатів. Деякі сертифікати доведеться анулювати.

Анулювання сертифікатів

Анулювання сертифікатів може виявитися найважчою проблемою, пов'язаною з CA. Як вже згадувалося раніше, кожен об'єкт, який використовує сертифікат, повинен повідомлятися про анулювання сертифікату. Це повідомлення повинне здійснюватися своєчасно. Оскільки природа системи з відкритим ключем не дозволяє CA знати про кожного користувача, який може використовувати даний сертифікат, CA повинне довірятися тим, хто використовуватиме сертифікат, для перевірки того, що сертифікат не був анульований. При цьому буде потрібно, аби кожен об'єкт перевіряв CA перед використанням сертифікату.

Якщо організація використовує лише одне CA, все не так складно, проте при цьому CA має бути постійно доступним. Якщо ієрархія CA має великі розміри (як на мал. Ш.12), то проблема набуває комплексного характеру. Користувач User1 може повідомити CA про те, що його сертифікат анульований, і CA1 може обнародувати цю інформацію, але як ця інформація дійде до користувача User4 від CA6?

Мережа

Мережа з довірою є альтернативною моделлю довіри. Ця концепція була вперше використана в технології Pretty Good Privacy (PGP). Вона полягає в тому, що кожен користувач сертифікує свій сертифікат і передає його відомим асоційованим об'єктам. Ці об'єкти можуть підписати сертифікат іншого користувача, оскільки він відомий (див. мал. Ш.13).

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

Тепер розглянемо ситуацію, в якій User1 отримує інформацію від User3. Користувач User3 не відомий користувачеві User1, але у користувача User3 є сертифікат, підписаний користувачем User2. Таким чином, дана модель поширюється на всю комп'ютерну мережу. Єдиним рішенням, яке повинне прийматися в процесі роботи, є кількість переходів, якому довіряє користувач. Як правило, ця кількість дорівнює 3 або 4. Крім того, може виникнути ситуація, в якій для встановлення довіри іншому користувачеві є два шляхи. Наприклад, User2 може використовувати два шляхи встановлення довіри з користувачем User5: один через користувача User3 і інший через користувача User4. Оскільки обоє користувача User3 і User4 сертифікують користувача User5, користувач User2 може бути впевнений в сертифікаті користувача User5.

Мал. Ш.13.  Мережа моделі довіри

Головною проблемою, пов'язаною з даною моделлю довіри, є недолік масштабованості. Оскільки модель мережі складається з двосторонніх взаємин, кожен користувач повинен мати деяку кількість таких взаємозв'язків, аби користуватися в мережі якою-небудь довірою. На практиці такі взаємозв'язки можуть бути відсутніми, оскільки більшість користувачів працюють з невеликою кількістю зв'язків і рідко виходять на рівень три або чотирьох переходи.

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

Розробка системи шифрування

Цей проект призначений для того, щоб продемонструвати використання шифрування в інформаційній системі для забезпечення аутентифікації, конфіденційності і цілісності. У даному проекті мається на увазі використання як систем шифрування з секретним ключем (AES), так і систем з відкритим ключем (RSA або Діффі-Хеллмана).

В організації, на яку ви працюєте, потрібно приймати транзакції від партнера. На жаль, використовувана усередині організації система не підтримує роботу з комерційними VPN, і тому в організації створюється система шифрування в своєму власному спеціально розробленому додатку. Вам доручено внести пропозиції з приводу того, як повинна працювати система шифрування. У своєму поточному стані система транзакцій приймає TCP-з’єднання від партнера організації, оцінює дані, що поступають, і робить відповідні записи в базі даних. Після цього сервер передає підтвердження в систему партнера через те ж саме з'єднання. Інформація при передачі повинна зберігатися в секреті, а також захищатися від несанкціонованої зміни. Сервер повинен здійснювати аутентифікацію ініціатора транзакції, оскільки лише одна система в мережі партнера авторизована для ініціації транзакцій.

Крок за кроком

1. Визначите конкретні вимоги для системи шифрування: яка інформація повинна міститися в секреті, захищатися від несанкціонованої зміни і проходить аутентифікацію в даній системі.

2. Визначите, якого типа шифрування (з відкритим або секретним ключем) слід використовувати для відповідності кожній вимозі.

3. Визначите, де необхідно здійснювати шифрування і дешифрування.

4. Визначите вимоги до управління ключами в системі: яким чином ключі створюватимуться, поширюватимуться, верифікуватимуться і анулюватимуться.

5. Розробивши структуру системи, перевірте її на наявність вразливих місць. Чи є в ній місця, через які потенційний зловмисник може дістати доступ до системи?

6. Перевірте систему на те, що реалізовується. Чи буде система придатна до використання на практиці?

7. Що буде потрібно при використанні шифрування від інших компонентів системи, політик і процедур обох організацій?

Висновки

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

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

Контрольні питання

1. На секретності якого елементу заснований захист інформації надійними алгоритмами шифрування?

2. Які три види атак на схему шифрування?

3. Як інакше називається шифрування з секретним ключем?

4. Наведіть приклад раннього підстановлювального шифру.

5. Чи може бути зламаний правильно реалізований "одноразовий блокнот"?

6. Яку довжину мають ключі DES?

7. У чому полягає основний недолік DES?

8. За рахунок чого потрійний DES підвищує рівень безпеки алгоритму DES?

9. Для чого призначений алгоритм AES?

10. На складності якого завдання базується безпека, що забезпечується алгоритмом Діффі-Хеллмана?

11. Чи можна використовувати алгоритм Діффі-Хеллмана для шифрування трафіку?

12. Назвіть основну атаку, на яку наражається алгоритм Діффі-Хеллмана (з правильно вибраними а і b).

13. Що таке цифровий підпис?

14. Чому відкриті ключі повинні бути сертифікованими?

15. В чому полягає проблема, пов’язана с управлінням ключами, яка викликає збої в більшій частині систем PKI?

1 David Kahn. Codebreakers. The story of Secret Writing. New-York, Macmillan, 1967.

2 Т.А. Соболєва. Тайнопис в історії Росії. (Історія криптографічної служби Росії ХУШ - початку XX в.). М., 1994.

3 У. Диффи, М. Э. Хеллмэн. Защищенность и имитостойкость. Введение в криптографию. ТИИЭР.т. 67, N3,1979.