Наукова основа

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

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

• Взагалі, в основу відомих асиметричних криптосистем кладеться одна зі складних математичних проблем, яка дозволяє будувати односторонні функції та функції - лазівки. Наприклад, криптосистеми Меркля - Хеллмана і Хору - Ривеста спираються на так звану задачу про укладання рюкзака.

4. Основні принципи побудови криптосистем з відкритим ключем

1. Починаємо з важкої задачі . Вона повинна вирішуватися складно в сенсі теорії: не повинно бути алгоритму, за допомогою якого можна було б перебрати всі варіанти рішення задачі за поліноміальний час щодо розміру задачі. Більш правильно сказати: не повинно бути відомого полиномиального алгоритму, вирішального дану задачу - оскільки ні для однієї задачі ще поки не доведено, що для неї підходящого алгоритму немає в принципі.

2. Можна виділити легку підзадачі з . Вона повинна вирішуватися за поліноміальний час і краще, якщо за лінійний.

3. " Перетасовують і збовтуємо" , Щоб отримати задачу , Зовсім не схожу на первісну. Завдання повинна принаймні виглядати як оригінальна труднорешаемие завдання .

4. відкривається з описом, як вона може бути використана в ролі ключа зашифрування. Як з отримати , Тримається в секреті як секретна лазівка.

5. Криптосистема організована так, що алгоритми розшифрування для легального користувача і криптоаналітика істотно різні. У той час як другий вирішує -Завдання, перший використовує секретну лазівку і вирішує -Завдання.

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

• У наступному прикладі показана схема, в якій Аліса шифрує повідомлення так, що тільки Боб може прочитати його, і навпаки, Боб шифрує повідомлення так, що тільки Аліса може розшифрувати його.

Нехай є 3 ключа , , , Розподілені так, як показано в таблиці.

Особа	Ключ
Аліса
Боб
Керол
Дейв	,
Еллен	,
Франк	,

Тоді Аліса може зашифрувати повідомлення ключем , А Еллен розшифрувати ключами , , Керол - зашифрувати ключем , А Дейв розшифрувати ключами, . Якщо Дейв зашифрує повідомлення ключем , То повідомлення зможе прочитати Еллен, якщо ключем , То його зможе прочитати Франк, якщо ж обома ключами і , То повідомлення прочитає Керол. За аналогією діють й інші учасники. Таким чином, якщо використовується одне підмножина ключів для шифрування, то для розшифрування потрібні залишилися ключі безлічі. Таку схему можна використовувати для n ключів.

Шифрується ключем	Розшифровується ключем
і
і
і
	,
	,
	,

• Тепер можна посилати повідомлення групам агентів, не знаючи заздалегідь складу групи.

Розглянемо для початку безліч, що складається з трьох агентів: Аліси, Боба і Керол. Алісі видаються ключі і , Бобу - і , Керол - і . Тепер, якщо отправляемое повідомлення зашифровано ключем , То його зможе прочитати тільки Аліса, послідовно застосовуючи ключі і . Якщо потрібно відправити повідомлення Бобу, повідомлення шифрується ключем , Керол - ключем . Якщо потрібно відправити повідомлення і Алісі і Керол, то для шифрування використовуються ключі і .

Перевага цієї схеми полягає в тому, що для її реалізації потрібно тільки одне повідомлення і n ключів (у схемі з n агентами). Якщо передаються індивідуальні повідомлення, тобто використовуються окремі ключі для кожного агента (всього n ключів) і кожного повідомлення, то для передачі повідомлень всім різні підмножини вимагається ключів.

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

6. Криптоаналіз алгоритмів з відкритим ключем

Здавалося б, що криптосистема з відкритим ключем - ідеальна система, що не вимагає безпечного каналу для передачі ключа шифрування. Це передбачало б, що два легальних користувача могли б спілкуватися по відкритому каналу, не зустрічаючись, щоб обмінятися ключами. На жаль, це не так. Малюнок ілюструє, як Єва, що виконує роль активного перехоплювача, може захопити систему (розшифрувати повідомлення, призначене Бобу) без виламування системи шифрування.

У цій моделі Єва перехоплює відкритий ключ , Посланий Бобом Алісі. Потім створює пару ключів і , " Маскується" під Боба, посилаючи Алісі відкритий ключ , Який, як думає Аліса, відкритий ключ, посланий їй Бобом. Єва перехоплює зашифровані повідомлення від Аліси до Боба, розшифровує їх за допомогою секретного ключа , Заново зашифровує відкритим ключем Боба і відправляє повідомлення Бобу. Таким чином, ніхто з учасників не здогадується, що є третя особа, яка може як просто перехопити повідомлення , Так і підмінити його на хибне повідомлення . Це підкреслює необхідність аутентифікації відкритих ключів. Для цього зазвичай використовують сертифікати. Розподілене управління ключами в PGP вирішує проблему за допомогою поручителів.

Ще одна форма атаки - обчислення закритого ключа, знаючи відкритий (малюнок нижче). Криптоаналітика знає алгоритм шифрування , Аналізуючи його, намагається знайти . Цей процес спрощується, якщо криптоаналітик перехопив кілька кріптотексте с, посланих особою A особі B.

Більшість криптосистем з відкритим ключем засновані на проблемі факторизації великих чисел. Приміром, RSA використовує в якості відкритого ключа n добуток двох великих чисел. Складність злому такого алгоритму полягає в труднощі розкладання числа n на множники. Але це завдання вирішити реально. І з кожним роком процес розкладання стає все швидше. Нижче наведені дані розкладання на множники за допомогою алгоритму " Квадратичне решето".

Також задачу розкладання потенційно можна вирішити за допомогою Алгоритму Шора при використанні досить потужного квантового комп'ютера.

Для багатьох методів несиметричного шифрування криптостійкість, отримана в результаті криптоаналізу, істотно відрізняється від величин, які заявляються розроблювачами алгоритмів на підставі теоретичних оцінок. Тому в багатьох країнах питання застосування алгоритмів шифрування даних знаходиться в полі законодавчого регулювання. Зокрема, в Росії до використання в державних і комерційних організаціях дозволені тільки ті програмні засоби шифрування даних, які пройшли державну сертифікацію в адміністративних органах, зокрема, в ФСБ, ФСТЕК.

7. Особливості системи