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

Введение

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

Разные люди розуміють під шифруванням різні речі. Діти граються в іграшкові шифри й таємні мови. Це, проте, немає нічого спільного зі справжньою криптографією. Справжня криптографія (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³² (близько 10⁹) кроків. Таке завдання у змозі кожному дилетанту і вирішується домашній комп’ютері. Системи з 40-битным ключем (наприклад, експортний американський варіант алгоритму RC4) вимагають 2⁴⁰ кроків —- такі комп’ютерні потужності є у більшості університетів і навіть у невеликих компаніях. Системи з 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 «.