Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Введення в криптографію

  Список відмічених друкарських помилок:
У шифровці на стор. 325 надруковано: 212850а
Слід читати: 212850б

При зберіганні і передачі даних нерідко виникає вимога захистити їх від небажаного прочитання і модифікації. Якщо завдання захисту від небажаної модифікації вирішується надлишковими кодами, що обговорювалися в попередньому розділі, то з прочитанням все істотно складніше.
Найпростіше забезпечити захист даних, позбавивши потенційних зловмисників доступу до фізичного носія даних або фізичного каналу, по якому відбувається їх передача. На жаль, інколи це нездійсненно (наприклад, якщо обмін даними відбувається по радіоканалу), а частенько просто дуже дорого. В цьому випадку на допомогу приходять методики, збірна назва яких — криптографія (тайнопис). На відміну від більшості термінів комп'ютерної лексики це слово не англійського, а грецького походження.
Історія криптографії налічує тисячі років, і багато основоположних принципів сучасної криптографії відомо, можливо, з доісторичних часів, проте, істотний прогрес в теорії шифрування був досягнутий лише відносно недавно, у зв'язку з розробкою сучасної теорії інформації.
Практично всі методи криптографії зводяться до перетворення даних в набір з кінцевої кількості символів і здійснення над цими символами двох основних операцій: підстановки і перестановки. Підстановка полягає в заміні одних символів на інших. Перестановка полягає в зміні порядку символів. Як символи при цьому можуть виступати різні елементи повідомлення — так, при шифруванні повідомлень на природних мовах підстановці і перестановці можуть піддаватися як окремі букви, так і слова або навіть цілі пропозиції (як, наприклад, в алегоричних викладах магічних і священних текстів). У сучасних алгоритмах цим операціям найчастіше піддаються блоки послідовних бітів. Деякі методики можна описати як здійснення операції підстановки над повним повідомленням.
Підстановки і перестановки проводяться по певних правилах. При цьому надія покладається "на те, що ці правила і використовувані в них параметри відомі лише авторові і одержувачеві шифрованого повідомлення і невідомі стороннім особам. У докомпьютерную еру прагнули засекретити обидві складові процесу шифрування. Зараз для шифрування, як правило, використовують стандартні алгоритми, секретність же повідомлення досягається шляхом засекречування використовуваного алгоритмом параметра, ключа (key).
Прочитання секретного повідомлення сторонньою особою, теоретично, може бути здійснене двома способами: викраданням ключового значення або його вгадуванням шляхом аналізу перехопленої шифровки. Якщо перший захід може запобігти лише фізичним і організаційним захистом, то можливість другого визначається використовуваним алгоритмом. Нижче ми називатимемо процес аналізу шифровки зломом шифру, а людини, що здійснює цей процес, — зломщиком. По-науковому ця діяльність називається більш нейтрально — криптоаналіз.
Наприклад, повідомлення на природній мові, зашифроване підстановкою окремих букв, уразливо для частотного аналізу: грунтуючись на тому факті, що різні букви зустрічаються в текстах з різною частотою, зломщик легко- і з вельми високою достоверностью- може відновити таблицю підстановки. Існують і інші приклади невдалих алгоритмів, які зберігають в недоторканості ті або інші присутні в повідомленні автокореляції, — кожен такий параметр можна використовувати як основу для відновлення тексту повідомлення або виявлення ключа.
Стійкість шифру до пошуку автокореляцій в повідомленні називається кріптостойкостио алгоритму. Навіть при використанні вдалих в цьому сенсі алгоритмів, якщо зломщик знає, що вихідні (нешифровані) дані задовольняють тій або іншій вимозі, наприклад, містять певне слово або забезпечені надлишковим кодом, він може провести повний перебір простору ключів: перебирати всі значення ключа, що допускаються алгоритмом, поки не буде отримано що задовольняє вимозі повідомлення. При використанні ключів досить великої розрядності така атака виявляється надмірно дорогою, проте прогрес обчислювальної техніки постійно зрушує кордон "достатності" все далі і далі. Так, мережа розподілених обчислень Bovine в 1998 році зламала повідомлення, зашифроване алгоритмом DES з 56-розрядним ключем за 56 годин роботи [www.distributed.net]!
Простим і ефективним способом боротьби з такою атакою є розширення простору ключів. Збільшення ключа на один біт приводить до збільшення простору удвічі -- таким чином, лінійне зростання розміру ключа забезпечує експоненціальне зростання вартості перебору. Деякі алгоритми шифрування не залежать від розрядності використовуваного ключа—в цьому випадку розширення досягається очевидним способом. Якщо ж в алгоритмі присутня залежність від розрядності, розширити простір можна, всього лише застосувавши до повідомлення декілька різних перетворень, у тому числі і одним алгоритмом, але з різними ключами. Ще один спосіб істотно ускладнити роботу зломщикові — це упаковка повідомлення перед шифруванням і доповнення його випадковими бітами.
Поважно підкреслити, втім, що кількість двійкових розрядів ключа є лише оцінкою об'єму простору ключів зверху, і в багатьох ситуаціях ця оцінка завищена. Деякі алгоритми через свою природу можуть використовувати лише ключі, що задовольняють певній умові, — наприклад, RSA використовує прості Числа. Це різко звужує об'єм роботи по перебору, тому для забезпечення порівнянною кріптостойко-сті розрядність ключа RSA має бути набагато більше, ніж в алгоритмів, що допускають довільні ключі.
Низька кріптостойкость може бути обумовлена не лише алгоритмом шифрування, але і процедурою вибору ключа: якщо ключ може набувати будь-яких двійкових значень заданої розрядності, але реально для його вибору використовується страждаючий неоднорідністю генератор псевдовипадкових чи-:ел, ми можемо значно скоротити об'єм простору, який реальний аолжен буде перебрати зломщик наших повідомлень (питання генерації завномерно розподілених псевдовипадкових чисел обговорюються в другому гоме класичної книги [Кнут 2000]). Ще гірше ситуація, коли як ключ використовуються слова природної мови, що "легко запам'ятовуються": в цьому випадку реальний об'єм простору ключів навіть досить великої розрядності може вимірюватися всього лише декількома тисячами різних значень.
Сучасні алгоритми шифрування діляться на два основні класи: з секретним і з публічним ключем (протиріччя, що видається, між терміном "публічний ключ" і приведеними вище міркуваннями буде роз'яснено далі).
Алгорітми- з секретним ключем, у свою чергу, діляться на потокових (stream) і блокових (block). Потокові алгоритми зазвичай використовують підстановку символів без їх перестановки. Підвищення кріптостойкості при цьому досягається за рахунок того, що правила підстановки залежать не лише від самого замінюваного символу, але і від його позиції в потоці.
Прикладом простого — і в той же час абсолютний непіддатливого злому — потокового алгоритму є система Вернама або одноразовий блокнот (мал. 1.10). Система Вернама заснована на ключі, розмір якого дорівнює розміру повідомлення або перевершує його. При передачі двійкових даних підстановка здійснюється складанням по модулю 2 (операцією того, що виключає або) відповідних бітів ключа і повідомлення.

Мал. 1.10. Система Вернама

Якщо ключ породжений надійним генератором випадкових чисел (наприклад, правильно налагодженим оцифровщиком теплового шуму), жодна інформація про автокореляції у вихідному тексті повідомлення зломщика не допоможе: перебираючи повний простір ключів, зломщик вимушений буде перевірити всі повідомлення, співпадаючі по кількості символів з початковим, у тому числі і всі повідомлення, що задовольняють передбачуваному автокореляційному співвідношенню.
Ця перевага втрачається, якщо один і той же ключ буде використаний для кодування декількох повідомлень: зломщик, що перехопив їх всіх, зможе використовувати ці повідомлення і припущення про їх вміст при спробах відфільтрувати ключ від корисної інформації — звідси і друга назва алгоритму. Вживання системи Вернама, таким чином, зв'язане з дорогою генерацією і, головне, транспортуванням ключів величезної довжини, і тому вона використовується лише в системах екстреного урядового і військового зв'язку.
Більш практичним виявилося вживання як ключ псевдовипадкових послідовностей, що породжуються детермінованими алгоритмами. У проміжку між першою і другою світовими війнами широкого поширення набули шифрувальні машини, засновані на механічних генераторах таких послідовностей. Найчастіше використовувалися поєднання, що отримуються при обертанні коліс з взаємно простими кількостями зубців.
Основною небезпекою при використанні таких методів шифрування є можливість визначити поточну точку послідовності — взнавши її (наприклад, по непрямих ознаках здогадавшись, що в даній точці повідомлення має бути таке-то слово, і відновивши елемент ключа, що використався при її шифруванні), зломщик може продовжити генерацію з тієї ж крапки і розшифрувати весь подальший потік.
У системах цифрового зв'язку широке вживання отримали блокові алгоритми, що виконують над блоками даних фіксованої довжини послідовності -- інколи досить складні — перестановок, підстановок і інших операцій, найчастіше двійкових складань даних з ключем по якому-небудь модулю. У операціях використовуються компоненти ключового слова відносно невеликої розрядності.
Наприклад, широко вживаний блоковий алгоритм DES шифрує 64-бітові блоки даних 56-бітовим ключем. Повний опис алгоритму приводиться в документі [NBS FIPS PUB 46, 1977]. Російський переклад цього документа може бути знайдений в додатках до книги [Дейтел 1987]. Для сучасної обчислювальної техніки повний перебір 56-бітового простори — "насіннячка", тому зараз, всього більшого поширення набувають алгоритми з більшою розрядністю ключа — Blowfish, IDEAL і ін. [Анін 2000].
Шифри з відкритим ключем називаються також двохключовими. Якщо в алгоритмах з прихованим ключем для кодування і декодування повідомлень використовується один і той же ключ, то тут використовуються два ключі: публічний і приватний. Для прочитання повідомлення, закодованого публічним ключем, необхідний приватний, і навпаки.
Окрім звичайних міркувань кріптостойкості, до таких алгоритмів пред'являється додаткова вимога: неможливість відновлення приватного ключа по публічному інакше як повним перебором простору ключів.
Двохключові схеми шифрування набагато складніше в розробці, чим схеми з секретним ключем: потрібно знайти перетворення, непіддатливе зверненню за допомогою публічного ключа, що застосовувався в нім, але таке, щоб із застосуванням приватного ключа його все-таки можна було обернути. Відомі кріптоустойчивиє схеми засновані на творах простих чисел великої розрядності, дискретних логарифмах і еліптичних кривих. Найбільш широке вживання отримав розроблений в 1977 р. алгоритм RSA [www.rsa.com FAQ].
Відомі двохключові алгоритми вимагають відповідності ключів вельми специфічним вимогам, тому для досягнення кріптостойкості, порівнянної з блоковими алгоритмами, необхідно використовувати ключі набагато більшої розрядності. Так, зняті в 2000 році обмеження Міністерства торгівлі США встановлювали обмеження розрядності ключа, який міг використовуватися в програмному забезпеченні, що експортувалося за межі США: для схем з секретним ключем встановлювалася межа, рівна 48 бітам, а для схем з відкритим — 480.
Використання ключів великої розрядності вимагає значних обчислювальних витрат, тому двохключові схеми чаші всього застосовуються у поєднанні із звичайними: володар публічного ключа генерує випадкову послідовність бітів, кодує її і відправляє володареві приватного ключа. Потім ця послідовність використовується як секретний ключ для шифрування даних. При встановленні двостороннього з'єднання сторони можуть спочатку обмінятися своїми публічними ключами, а потім використовувати їх для встановлення двох різних секретних ключів, використовуваних для шифрування даних, передаваних у різних напрямах.
Така схема робить практичною часту зміну секретних ключів: так, в протоколі SSH ключ генерується на кожну сесію [www.cs.hut.fi SSH]; у протоколі віртуальних приватних мереж IPSEC час життя ключа обмежений вісьма годинами [redbooks.ibm.com sg245234.pdf].
Ще ширше вживання двохключові схеми знайшли в області аутентифікації і електронного підпису. Електронний підпис є контрольною сумою повідомлення, зашифрованою приватним ключем відправника. Кожен володар відповідного публічного ключа може перевірити автентичність підпису і цілісність повідомлення. Це може використовуватися для перевірки автентичності як повідомлення, так і самого відправника. Використання як контрольна сума звичайного CRC (див. разд. Контрольні суми) неможливо, бо генерація повідомлення із заданим CRC не представляє обчислювальної складності. Для вживання в електронному підписі були розроблені спеціальні алгоритми обчислення контрольних сум, що утрудняють підбір повідомлення з необхідною сумою [RFC 1320, RFC 1321].

 

:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017