Асиметричні алгоритми кодування

Асиметричні алгоритми шифрування — алгоритми шифрування, які використовують різні (і такі які важко обчислити один з одного) ключі для шифрування та розшифрування даних.

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

Головне досягнення асиметричного шифрування в тому, що воно дозволяє людям, що не мають існуючої домовленості про безпеку, обмінюватися секретними повідомленнями. Необхідність відправникові й одержувачеві погоджувати таємний ключ по спеціальному захищеному каналі цілком відпала. Прикладами криптосистем з відкритим ключем є Elgamal (названа на честь автора, Тахіра Ельгамаля), RSA (названа на честь винахідників: Рона Рівеста, Аді Шаміра і Леонарда Адлмана), Diffie-Hellman і DSA, Digital Signature Algorithm (винайдений Девідом Кравіцом).

Історія

Історія криптографії налічує близько 4 тисяч років. В якості основного критерію періодизації криптографії можливо використовувати технологічні характеристики використовуваних методів шифрування.

Перший період (приблизно з третього тисячоліття до н. Е..) Характеризується пануванням моноалфавітних шифрів (основний принцип — заміна алфавіту вихідного тексту іншим алфавітом через заміну літер іншими літерами або символами). Другий період (хронологічні рамки — з IX століття на Близькому Сході (Ал-Кінді) і з XV століття в Європі (Леон Баттіста Альберті) — до початку XX століття) ознаменувався введенням в обіг поліалфавітних шифрів. Третій період (з початку і до середини XX століття) характеризується впровадженням електромеханічних пристроїв в роботу шифрувальників. При цьому продовжувалося використання поліалфавітних шифрів.

Принцип роботи

Початок асиметричним шифру було покладено в роботі «Нові напрямки в сучасній криптографії» Уітфілд Діффі та Мартіна Хеллмана, опублікованій в 1976 році. Перебуваючи під впливом роботи Ральфа Меркле (Ralph Merkle) про поширення відкритого ключа, вони запропонували метод отримання секретних ключів, використовуючи відкритий канал. Цей метод експоненціального обміну ключів, який став відомий як обмін ключами Діффі-Хеллмана, був першим опублікованим практичним методом для встановлення поділу секретного ключа між завіреними користувачами каналу. У 2002 році Хеллмана запропонував називати даний алгоритм «Діффі — Хеллмана — Меркле», визнаючи внесок Меркле в винахід криптографії з відкритим ключем. Ця ж схема була розроблена Малькольмом Вільямсоном в 1970-х, але трималася в секреті до 1997 року. Метод Меркле з розповсюдження відкритого ключа був винайдений в 1974 році і опублікований в 1978, його також називають загадкою Меркле.

У 1977 році вченими Рональдом Рівестом (Ronald Linn Rivest), Аді Шамір (Adi Shamir) і Леонардом Адлеманом (Leonard Adleman) з Массачусетського Технологічного Інституту (MIT) був розроблений алгоритм шифрування, заснований на проблемі про розкладанні на множники. Система була названа за першими літерами їхніх прізвищ. Ця ж система була винайдена Клиффордом Коксом (Clifford Cocks) в 1973 році, що працював в центрі урядового зв'язку (GCHQ). Але ця робота зберігалася лише у внутрішніх документах центру, тому про її існування було не відомо до 1977 року. RSA став першим алгоритмом, придатним і для шифрування, і для цифрового підпису.

Криптографія з відкритим ключем

Проблема керування ключами була вирішена криптографією з відкритим, або асиметричним, ключем, концепція якої була запропонована Уітфілдом Діффі і Мартіном Хеллманом у 1975 році. Криптографія з відкритим ключем — це асиметрична схема, у якій застосовуються пари ключів: відкритий (public key), що зашифровує дані, і відповідний йому закритий (private key), що їх розшифровує. Ви поширюєте свій відкритий ключ по усьому світу, у той час як закритий тримаєте в таємниці. Будь-яка людина з копією вашого відкритого ключа може зашифрувати інформацію, що тільки ви зможете прочитати. Хто завгодно. Навіть люди, з якими ви ніколи не зустрічалися.

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

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

Ідея створення

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

Але сама одностороння функція марна в застосуванні: нею можна зашифрувати повідомлення, але розшифрувати не можна. Тому криптографія з відкритим ключем використовує односторонні функції з лазівкою. Лазівка — це якийсь секрет, який допомагає розшифрувати. Тобто існує такий y, що знаючи f (x), можна обчислити x. Приміром, якщо розібрати годинник на безліч складових частин, то дуже складно зібрати знову працюючий годинник. Але якщо є інструкція по зборці (лазівка), то можна легко вирішити цю проблему.

Дивіться також