Введення в криптографію, Криптографія, Security & Hack, статті

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






Передмова

Різні люди розуміють під шифруванням різні речі. Діти грають в іграшкові шифри й секретні мови. Це, однак, не має нічого спільного зі справжньою криптографією. Справжня криптографія (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).

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

Криптоаналіз і атаки на криптосистеми


Криптоаналіз – це наука про дешифрування закодованих повідомлень не знаючи ключів. Є багато криптоаналітичних підходів. Деякі з найбільш важливих для розробників наведено нижче.



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


Схожі статті:


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

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*