Характеристика криптосистем з відкритими ключами

У криптосистемі, що заснована на відкритому розподілі ключів (асиметричній системі) кожний користувач або застосування мають пару постійно або довгостроково використовуваних ключів: відкритий і секретний (ще особистий) ключі.

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

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

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

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

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

Обмін сеансовими ключами за схемою Диффі-Хеллмана. До початку використання ГОСТ 28147-89 або DES, як втім і будь-якої іншої симетричної криптографічної системи, щоб зашифрувати повідомлення, обидві сторони інформаційного обміну: адресант (відправник) і адресат (одержувач) повинні домовитися про секретні ключі сеансу - ключах шифрування в кожному напрямку. Процес установлення сеансового ключа називається ключовим обміном або розподілом ключів.

Перша схема відкритого розподілу ключів була запропонована У.Диффі й М.Хеллманом. Рис.2 пояснює принципи формування загального ключа за схемою Диффі-Хеллмана.

У цьому прикладі, абонент А генерує випадковий секретний ключ x_А, а абонент B генерує випадковий секретний ключ xb. Потім кожна зі сторін обчислює відкритий ключ, відповідно ya по x_А й yb по xb, які направляються по каналу зв'язку іншій стороні, на основі яких вичисляется загальний ключ сеансу.

У такий же спосіб, криптосистема, заснована на використанні відкритих ключів, може бути використана для формування сеансових ключів для симетричної криптосистеми в обох напрямках передачі.

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

Хоча в теорії x можна знайти за зв'язаним значенням y шляхом обчислення дискретного логарифма (тобто, log y mod p), але практично для великого р (від 700 і більш біт) це вимагає величезних обчислювальних ресурсів.

Криптосистема RSA. RSA - криптосистема з використанням відкритих ключів, названа по перших буквах імен її творців.

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

Кожний абонент системи має пари - відкритий і секретний ключ, значення яких лежить у діапазоні від 1024 до 4096 біт модуля n, де n= pq із секретними p і q. Відкриті ключі: n і показник експоненти e; секретний ключ: прості числа p і q, а також секретний показник експоненти d, який є інверсією e за модулем mod (p -1) (q -1).

Секретні значення p і q потрібні тільки на етапі генерації інших параметрів - показників експонент - після їхнього створення p і q вони не використовуються. Для шифрування використовується відкритий ключ адресата. Відправник шифрує блок повідомлення M, зводячи його в ступінь e (mod n). Отримувач розшифровує блок, зводячи його в ступінь d (mod n). Розшифрування відновлює первісне повідомлення, у силу залежності між e і d має властивість: (M^e mod n)^d (modn) = (M^ed mod n) = M.

Відзначимо, що авторами системи був запропонований розмір ключа від 512 до 1024 біт. Однак можна помітити, що складність задачі базується саме на розкладанні більших чисел на множники. З моменту появи системи одинаками й цілими колективами постійно проводилися атаки шляхом повного або оптимізованого перебору.

За рахунок використання зроблених методів факторизації й високопродуктивних комп'ютерів задача розкладання вже впевнено зважується на рубежі 700 бітних чисел, Для великої кількості комп'ютерів (порядку 1000) і застосування методів розпаралелювання обчислень забезпечена факторизація чисел розміром 900 біт.

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

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

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

Зашифрований секретний ключ і повідомлення оправляються адресатові. На прийомному кінці процедура виконується у зворотному порядку: розшифрування секретного ключа, зашифрування з його допомогою власне повідомлення. Зокрема, відомий застосування Internet Privacy Enhanced Mail для захисту електронної пошти крім симетричного алгоритму шифрування по стандарту DES використовує розподіл ключів по методу RSA.

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

Для формування цифрового підпису повідомлення, відправник, використовуючи деяку функцію (має назву хеш-функція), обчислює стислий образ повідомлення. Власне цифровий підпис формується на основі короткого образу повідомлення за допомогою деякого криптографічного алгоритму та особистого ключа адресанта. Після об'єднання з повідомленням вона відправляється адресатові. Механізми ЕЦП пояснюються рис. 4.

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

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

Цифровий підпис на основі алгоритму RSA.

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

Рис. 5 пояснює, принципи формування ЕЦП за допомогою алгоритму RSA. Для підпису повідомлення і його перевірки використовуються параметри адресанта: модуль n і ступені експонент e і d. Щоб підписати повідомлення, відправник створює його хеш-образ z з використанням деякої хеш-функції (наприклад, MD5).

Підпис формується шляхом піднесення образа в ступінь особистого ключа адресанта d (mod n). Отриманий підпис разом з повідомленням відправляється адресатові. На прийомному кінці розшифроване при необхідності повідомлення хешується, потім отримувач перевіряє правильність підпису, зводячи його в ступінь відкритої експоненти e(mod n) і порівнюючи отриманий результат з обчисленим хеш-образом повідомлення.

Стандарти цифрового підпису. В 1991 році NIST запропонував стандарт цифровому підпису (DSS) для урядових систем. DSS використовує алгоритм SHA для хешування повідомлень перед підписом.

В 1995 році ФАУЗІ РФ запропонувало стандарт ГОСТ Р34.10 (в Україні має індекс 34.310) цифрового підпису разом з функцією хешування за ГОСТ Р34.11 (34.311).

Ці стандарти використовують так звану схему К.Шнорра засновану на протоколі Ель-Гамаля.

І DSS, і ГОСТ Р34.10 реалізують піднесення в ступінь більших чисел у модульній арифметиці. Розмір ключа - 512 або 1024 біта, стійкість визначається складністю розв'язку задачі дискретного логарифмування, що приблизно відповідає складності розв'язку задачі факторизації (розкладання на множники), тому стійкість DSS порівнянна з RSA.

Усі асиметричні криптосистеми є об'єктом атак шляхом оптимізованого перебору ключів, що приводить до необхідності використання набагато більш довгих ключів, чому ті, які використовуються в симетричних криптосистемах, для забезпечення еквівалентного рівня захисту.

Це відразу ж позначається на обчислювальних ресурсах, необхідних для шифрування. Останнім часом активно розвивається напрямок, що пов'язаний з побудовою криптографічних алгоритмів, що використовують апарат еліптичних кривих (ECC). Саме застосування еліптичних кривих може пом'якшити проблему складності обчислень із багато розрядними числами.

Зокрема, в Україні прийнятий встановленим порядком державний стандарт ДСТУ 4145-2002, якій визначає алгоритм формування та перевірки ЕЦП на базі математичних перетворень із застосуванням еліптичних кривих.

У ряді видань наводяться дані про еквівалентні довжини ключів. З метою наочної демонстрації викладеного такі дані (умовно еквівалентні довжини ключів) наведено в таблиці 2.

Таблиця 2

Еквівалентні довжини ключів

Довжина ключа симетричної системи (біт)	Кількість варіантів ключів	Довжина ключа RSA систем (біт)	Довжина ключа ЕСС систем (біт)
56-64	1017 -1019	384-512
	1024
	1034
	1038

Стандарти функцій хешування. Хеш-функції є одним з важливих елементів криптосистем на основі ключів. Їх відносно легко обчислити, але майже неможливо розшифрувати. Вихідні дані хеш-функції мають змінну довжину, результат - рядок фіксованого розміру (іноді називану дайджестом повідомлення - MD), звичайно 128-160 біт.

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

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

У таблиці 3 наведені загальні характеристики відомих функцій хешування. Слід зауважити, що алгоритми хешування ГОСТ Р34.11 і SHA, що стискають повідомлення до рядка біт фіксованої довжини, задовольняють обом вище наведеним умовам.

Таблиця 3

Характеристика хеш-функцій

Назва	Характеристика функції
MD2	Сама повільна, розрахована для 8-бітових машин
MD4	Найшвидша, оптимізована для 32-бітних машин Є повідомлення про її розкриття
MD5	Найпоширеніша з хеш-функцій. Схожа на MD4, але засоби підвищення безпеки роблять її на третину повільніше, чим MD4 Забезпечує цілісність даних. Вважається безпечною
SHA(Secure Hash Algorithm)	Створює 160-бітне значення хеш-функції з вихідних даних змінного розміру. Запропонована NIST і прийнята урядом США як стандарт, призначена для використання в стандарті DSS