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