Різні люди розуміють під шифруванням різні речі. Діти грають в іграшкові шифри й секретні мови. Це, однак, не має нічого спільного зі справжньою криптографією. Справжня криптографія (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.
Криптографічні генератори випадкових чиселКриптографічні генератори випадкових чисел виробляють випадкові числа, які використовуються у криптографічних програмах, наприклад - для генерації ключів. Звичайні генератори випадкових чисел, які є у багатьох мовах програмування і програмних середовищах, не підходять для потреб криптографії (вони створювалися з метою отримати статистично випадковий розподіл, криптоаналитики можуть передбачити поведінку таких випадкових генераторів).
В ідеалі випадкові числа повинні грунтуватися на цьому фізичному джерелі випадкової інформації, яку неможливо передбачити. Приклади таких джерел включають шумливі напівпровідникові прилади, молодші біти оцифрованого звуку, інтервали між перериваннями пристроїв або натисканнями клавіш. Отриманий від фізичного джерела шум потім "дистилюється" криптографічного хеш-функцією так, щоб кожен біт залежав від кожного біта. Досить часто для зберігання випадкової інформації використовується досить великий пул (кілька тисяч біт) і кожен біт пулу робиться залежним від кожного біта шумовий информаци і кожного іншого біта пулу криптографічно надійним (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"