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

Введення в криптографію Передмова Базова термінологія Основні алгоритми шифрування Цифрові підписи Криптографічні хеш-функції Криптографічні генератори випадкових чисел Що забезпечується шифром ступінь захисту Криптоаналіз і атаки на криптосистеми Передмова

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

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

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

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

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

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

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

Метод шифрування/дешифрування називають шифром ( cipher ). Деякі алгоритми шифрування засновані на тому, що сам метод шифрування (алгоритм) є секретним. Нині такі методи представляють лише історичний інтерес і не мають практичного значення. Всі сучасні алгоритми використовують ключ для управління шифровкою і дешифровкою; повідомлення може бути успішно дешифрована тільки якщо відомий ключ. Ключ, який використовується для дешифрування може не збігатися з ключем, який використовується для шифрування, однак в більшості алгоритмів ключі збігаються.

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

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

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

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

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

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

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

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

Цифровий підпис також можна використовувати для посвідчення ( сертифікації --- To certify ) того, що документ належить певній особі. Це робиться так: відкритий ключ і інформація про те, кому він належить підписуються стороною, якій довіряємо. При цьому довіряти підписує стороні ми можемо на підставі того, що її ключ був підписаний третьою стороною. Таким чином виникає ієрархія довіри. Очевидно, що деякий ключ повинен бути коренем ієрархії (тобто йому ми довіряємо не тому, що він кимось підписаний, а тому, що ми віримо a-priori, що йому можна довіряти). У централізованої інфраструктурі ключів є дуже невелика кількість кореневих ключів мережі (наприклад, наділені повноваженнями державні агенства; їх також називають сертифікаційними агентствами --- certification authorities ). У розподіленої інфраструктурі немає необхідності мати універсальні для всіх кореневі ключі, і кожна зі сторін може довіряти своєму набору кореневих ключів (скажімо свого власного ключа та ключів, підписаним нею). Ця концепція має назву мережі довіри ( web of trust ) та реалізована, наприклад, у PGP.

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

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

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

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

Багато хороших криптографічних хеш-функцій є безкоштовно. Широко відомі включають MD5 і SHA. Криптографічні генератори випадкових чисел

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

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

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

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

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

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

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

Теоретично, будь-який шифрувальний алгоритм з використанням ключа може бути розкритий методом перебору всіх значень ключа. Якщо ключ підбирається методом грубої сили ( brute force ), необхідна потужність комп'ютера зростає експоненціально зі збільшенням довжини ключа. Ключ довжиною в 32 біта вимагає 2 ^ 32 (близько 10 ^ 9) кроків. Таке завдання під силу будь-якому дилетанту і вирішується на домашньому комп'ютері. Системи з 40-бітовим ключем (наприклад, експортний американський варіант алгоритму RC4) вимагають 2 ^ 40 кроків --- такі комп'ютерні потужності є в більшості університетів і навіть в невеликих компаніях. Системи з 56-бітними ключами (DES) вимагають для розтину помітних зусиль, проте можуть бути легко розкриті за допомогою спеціальної апаратури. Вартість такої апаратури значна, але доступна для мафії, великих компаній і урядів. Ключі довжиною 64 біта на даний момент, можливо, можуть бути розкриті великими державами і вже в найближчі кілька років будуть доступні для розтину злочинними організаціями, великими компаніями і невеликими державами. Ключі довжиною 80 біт можуть в майбутньому стати вразливими. Ключі довжиною 128 біт ймовірно залишаться недоступними для розтину методом грубої сили в доступному для огляду майбутньому. Можна використовувати і довші ключі. У межі неважко добитися того, щоб енергія, необхідна для розкриття (вважаючи, що на один крок витрачається мінімальний квантовомеханічний квант енергії) перевершить масу сонця або всесвіту.

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

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

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

Щоб дати уявлення про ступінь складності розтину RSA, скажімо, що модулі довжиною 256 біт легко факторізуются звичайними програмістами. Ключі в 384 біта можуть бути розкриті дослідницькою групою університету або компанії. 512-бітові ключі знаходяться в межах досяжності великих держав. Ключі довжиною в 768 біт ймовірно не будуть надійні тривалий час. Ключі довжиною в 1024 біт можуть вважатися безпечними до тих пір, поки не буде суттєвого прогресу в алгоритмі факторизації; ключі довжиною в 2048 більшість вважає надійними на десятиліття. Більш докладну інформацію про довжинах ключів RSA можна почерпнути зі статті Брюса Шнайер (Bruce Scheier).

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

Криптоаналіз - це наука про дешифрування закодованих повідомлень не знаючи ключів. Є багато криптоаналітичних підходів. Деякі з найбільш важливих для розробників наведені нижче. Атака зі знанням лише шифрованого тексту ( ciphertext-only attack ): Це ситуація, коли атакуючий не знає нічого про зміст повідомлення, і йому пріходтся працювати лише з самим шифрованих текстом. На практиці, часто можна зробити правдоподібні припущення про структуру тексту, оскільки багато повідомлення мають стандартні заголовки. Навіть звичайні листи і документи починаються з легко предсказумой інформації. Також часто можна припустити, що певний блок інформації містить задане слово. Атака зі знанням вмісту шифрування ( known-plaintext attack ): Атакуючий знає або може вгадати вміст всього або частини зашифрованого тексту. Завдання полягає в розшифровці решти повідомлення. Це можна зробити або шляхом обчислення ключа шифрування, або минувши це. Атака за заданим текстом ( chosen-plaintext attack ): Атакуючий має Можливість отримати шифрований документ для будь-якого потрібного йому тексту, але не знає ключа. Завданням є знаходження ключа. Деякі методи шифрування і, в Зокрема, RSA, дуже вразливі для атак цього типу. При використанні таких алгоритмів треба ретельно стежити, щоб атакуючий не міг зашифрувати заданий їм текст. Атака з підставкою ( Man-in-the-middle attack ): Атака направлена на обмін шифрованими повідомленнями і, в особливості, на протокол обміну ключами. Ідея полягає в тому, що коли дві сторони обмінюються ключами для секретної комунікації (наприклад, використовуючи шифр Діффі-Хелман, Diffie-Hellman), противник впроваджується між ними на лінії обміну повідомленнями. Далі противник видає кожній стороні свої ключі. У результаті, кожна зі сторін буде мати різні ключі, кожен з яких відомий противнику. Тепер супротивник буде розшифровувати кожне повідомлення своїм ключем і потім зашифровувати його з допомогою іншого ключа перед відправкою адресату. Сторони будуть мати ілюзію секретної листування, в той час як насправді противник читає все повідомлення.

Одним із способів запобігти такий тип атак полягає в тому, що сторони при обміні ключами обчислюють криптографічну хеш-функцію значення протоколу обміну (або щонайменше значення ключів), підписують її алгоритмом цифрового підпису та посилають підпис іншій стороні. Одержувач перевірить підпис і те, що значення хеш-функції співпадає з обчислених значень. Такий метод використовується, зокрема, в системі Фотуріс (Photuris). Атака за допомогою таймера ( timing attack ): Цей новий тип атак заснований на послідовному вимірі часів, що витрачаються на виконання операції зведення в стенень по модулю цілого числа. Їй піддані принаймні наступні шифри: RSA, Діффі-Хеллман і метод еліптичних кривих. У статті Пола Кочеров докладно розглянуто це метод.

Є безліч інших криптографічних атак і криптоаналітичних підходів. Однак наведені вище є, мабуть, найбільш важливими для практичної розробки систем. Якщо хто-небудь збирається створювати свій алгоритм шифрування, йому необхідно розуміти дані питання значно глибше. Одне з місць, де можна почати систематичне вивчення інформації --- це чудова книга Брюса Шнейера "Прикладна криптографія" (Bruce Schneier, Applied Cryptography).

Переклад статті Tatu Ylonen "Introduction to Cryptography"