За допомогою спеціальних алгоритмів згенерувати два великих простих числа p і q, які необхідно тримати у тайні

1.         За допомогою спеціальних алгоритмів згенерувати два великих простих числа p і q, які необхідно тримати у тайні.

2.         Повідомити відправнику повідомлень (або розмістити у відкритому каталозі) число n=pq, а також випадкове ціле число Е, взаємно просте з добутком (p-1)(q-1).

3.         Для розшифровки повідомлень, зашифрованих на відкритому ключі n, E, отримувачу необхідно мати число D, яке є мультиплікативним оберненим числа Е за модулем (p-1)(q-1), тобто DЕ=1 mod(p-1)(q-1). Знайти таке число дуже просто, оскільки найбільший спільний дільник Е і (p-1)(q-1) якраз і рівний одиниці за вибором Е.

Таким чином, відправник знає свій закритий ключ, n, E, а отримувач, крім того, знає ще свій секретний ключ D.

Довільне відкрите повідомлення можна уявити у вигляді послідовності цілих чисел з деякого інтервалу. Будемо вважати, що відправник передає секретне повідомлення у вигляді X₁,…,X_n 0<X_i<n-1, для всіх і від 1 до k.

Відправник для кожного блоку X_i вираховує

C_i=( X_i^E) mod n (1)

і передає C_i відкритим каналом зв’язку.

Маючи n, E і C_i, отримувач може розшифрувати повідомлення, використовуючи співвідношення

X_i=(C_i^D) mod n. (2)

Розглянемо в якості прикладу випадок p=3, q=11, n=3x11=33, E=7, D=3. Легко переконатися, що кожне з чисел E=7 і DE=21 взаємно прості з (p-1)(q-1)=20. Для передачі повідомлення М=”02” відправнику треба обчислити C=(2⁷) mod 33=29. Отримувач може розшифрувати повідомлення за допомогою такої операції: X=29³ mod 33=2. =2. Якщо ж ми маємо текстове повідомлення, алфавіт якого пронумеровано від 00 до 32 (з пробілом), тоді можна зашифрувати довільне повідомлення російською мовою. Наприклад, якщо ми маємо повідомлення „ПРОВЕРИМ ЗНАНИЕ АРИФМЕТИКИ”, то у зашифрованому вигляді на ключі n=33, E=7 воно буде мати вигляд:

27 25 20 29 14 25 02 12 32 28 07 00 07 02 14 32 00 25 02 26 12 14 06 02 10 02

Зрозуміло, що шифром в даному випадку є шифр простої заміни за табл. 1.

Таблиця 1. Таблиця заміни при шифруванні.

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р	С
00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17
Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
18	19	20	21	22	23	24	25	26	27	28	29	30	31	32

Одним з відомих алгоритмів дешифрування системи RSA є метод ітерацій. Згідно з ним вихідне повідомлення можна отримати з шифрованого повторним шифруванням доти поки не отримаємо відкритий текст.

 

Приклад 1. Нехай р=383, q= 563, n=215629, E=49. В цьому випадку відкритий текст повністю отримується уже через 10 ітерацій повторного шифрування. Щоби в цьому впевнитися, достатньо довести, що 49¹⁰=1 mod (p-1)(q-1). Виконання цієї рівності можна перевірити навіть на калькуляторі: (49⁴=5764801 -> 49⁴=183017 mod 214684 … 49⁹=56957 mod 214684 -> 49¹⁰= 1 mod 214684).

Інший метод атаки на шифр RSA – метод розкриття чисел p і q. Справа в тому, що n=pq (як і самі ці числа p і q) повинні бути досить великими, щоби розкласти його на множники було дуже складно (в цьому і полягає складність цього алгоритму шифрування). Бажано, щоби p і q вибиралися випадковим чином і не були „дуже близькими” одне до одного. Покажемо, яким чином можна використати близькість значень p і q. Будемо вважати, що p > q (що не накладає зайвих обмежень). Тоді для величин x=( p + q)/2, y=( p – q)/2 справедливе співвідношення: x²-y²=n. Перебираючи у порядку зростання варіанти x >, легко знайти розв’язок рівняння x²-y²=n, так як x=( p + q)/2 буде близьким до  у випадку близькості p і q.

Приклад 2. Нехай n=pq=851. Використаємо описаний спосіб для знаходження p і q. Так як =29.17, беремо x=30 і обчислюємо 30²-851=49 і з першої спроби знаходимо розв’язок x=30 і y=7. Таким чином, p=30+7=37, q=30-7=23.

Крім вказаних обмежень на p, q, E, D накладаються й інші обмеження.

Система шифрування RSA може бути застосована для цифрового підпису. У випадку підпису повідомлення М відправник обчислює P=M^E mod n. Отримувач, який має М та Р, перевіряє справедливість співвідношення Р^D=М mod n і впевнюється у справжності повідомлення М.

Приклад 3. Нехай p=3, q=11, n=3x11=33, E=7, D=3. Тоді відправник повідомлення М=”02” обчислює цифровий підпис Р=2⁷ mod 33=29 і відправляє повідомлення „02, 29” отримувачу. Той, в свою чергу, перевіряє справжність повідомлення „02”, обчисливши М=(29³) mod 33=2.

Насправді підписують не саме повідомлення, а його т.зв. хеш-функцію. Спочатку оригінальне повідомлення обробляється деякою функцією, яка має таку властивість, що приймає на вході рядки різної довжини, а на виході видає деякий „дайджест”, як правило, однакової і меншої, ніж вхідна, довжини. Хеш-функція виконує математичні обчислення, у результаті яких обчислюється значення хеш-функції. Хеш-функція може бути дуже простою. Наприклад, вона може виконати підсумовування всіх одиниць двійкового коду, або додати значення кодів всіх літер рядка, що обробляється (т.зв. контрольна сума) і т.д. Головне полягає в тому, що значення хеш-функції повинно залежати від усього вхідного рядка, щоби не можна було (в крайньому разі було б дуже важко) підібрати два різних вхідних рядки з однаковим значенням хеш-функції. Якщо таке трапляється, то кажуть що виникла колізія. Ми будемо користуватися найпростішою хеш-функцією, яка дуже недосконала і може викликати значні колізії. Однак, вона дуже проста і не потребує витрат машинного часу, а також складного програмування. Ця функція просто сумує всі значення символів за табл. 1 за модулем 33:

H(M)= (3)

До отриманого таким чином числа застосовують алгоритм прикладу 3, отримуючи, таким чином, зашифрований цифровий підпис. Отримувач, маючи повідомлення і цифровий підпис, розшифровує текст повідомлення, знаходить хеш-функцію від нього за формулою (3), розшифровує цифровий підпис, і порівнює отримані значення. Якщо вони однакові, повідомлення і цифровий підпис є істинними.

Проблема адміністрування криптографічними ключами вважається основним недоліком симетричних криптоалгоритмів. Цю проблему можна вирішити за допомогою асиметричної криптографії, тобто взагалі не використовувати симетричні криптоалгоритми. Однак такий підхід вважають нераціональним, оскільки асиметричні алгоритми працюють значно повільніше за симетричні і не можуть використовуватися у ряді важливих криптографічних застосувань. Іншим способом розповсюдження ключів є специфічні алгоритми, розроблені спеціально для таких застосувань. Одним з таких алгоритмів відкритого розповсюдження ключів є алгоритм Діффі-Хеллмана. Нехай учасники інформаційного обміну, сторони А і В, домовилися використати цей алгоритм для обміну ключами. Для цього необхідно виконати наступні обчислення. Спочатку А і В обирають велике просте число р, модуль системи. Для цього числа р обирають первісний корінь а. Числа р і а відкрито передають по каналах зв‘язку, так щоб їх мали обидві сторони.

Далі виконується наступний протокол:

a.    А генерує ціле велике випадкове число х і відправляє В число:

;

2) В генерує велике ціле випадкове число у і відправляє А число:

;

3) А обчислює:

4) В обчислює:

.

І k, і k’ дорівнюють .

Отже сторони А і В отримали один і той самий криптографічний ключ, не пересилаючи його каналами зв‘язку. Ніхто з осіб, що прослуховують цей канал, не зможе обчислити значення ключа. Адже їм відомі тільки p, a, X, Y, а для знаходження ключа необхідно розв‘язати задачу дискретного логарифмування. Тому А і В мають цілком таємний ключ, який більше ніхто не знає. Вибір а і р може помітно впливати на безпеку системи. Найголовніше, це те, що р повинно бути великим, таким, щоби задача дискретного логарифмування у скінченому полі була складною обчислювальною проблемою. Можна обирати довільне а, яке є первісним коренем за модулем р; немає причин, за якими не можна було б обрати а найменшим з можливих, навіть однорозрядним. Навіть необов‘язково, щоби а було первісним коренем, воно повинно лише утворювати досить велику підгрупу мультиплікативної групи за модулем р. Програмний генератор двійкових послідовностей BBS (назву утворено від перших літер його авторів – Ленори та Мануеля Блум та Майка Шуба, Blum-Blum-Shub) вважають одним з найсильніших програмних генераторів псевдовипадкових послідовностей. Він вважається криптографічно стійким, і може використовуватися у серйозних криптографічних застосуваннях [2].

Нехай є два простих числа, p i q, причому p≡q≡3 mod 4. Добуток цих чисел n=pq називається цілим числом Блума. Оберемо ще одне випадкове число, х, взаємно просте з n та обчислимо x₀≡x mod n. Це число вважається стартовим числом генератора. Далі можна обчислити наступні біти послідовності за формулою: x_i≡x_i-1² mod n та s_i≡x_i mod 2. Останнє визначає, що в якості виходу генератора обирається молодший біт числа x_і . Найцікавішою властивістю генератора BBS є те, що для визначення значення і-го біту зовсім необов‘язково знати усі попередні і-1 бітів. Для безпосереднього обчислення значення і-го біту достатньо знати p та q. Безпека цієї схеми ґрунтується на складності розкладання n на множники. Число n можна опублікувати, так що кожен зможе генерувати біти за допомогою цього генератора. Однак поки криптоаналітик не розкладе n на множники, він не зможе передбачити вихід генератора. Більше того, генератор BBS непередбачуваний як в правому, так і в лівому напрямках. Це означає, що отримавши послідовність бітів, криптоаналітик не зможе передбачити ні наступний, ні попередній біти послідовності. Причиною цього є не якійсь заплутаний механізм генерації, а математика розкладання n на множники.

Приклад:

p=19;q=23

і	0	1	2	3	4	5	6	7
хi	101	150	213	358	123	271	25	188
Si	1	0	1	0	1	1	1	0

p=q≡3 mod 4

n=437

x=233

Обов’язковою умовою, що накладається на зародок х, повинно бути наступне:

а) x – просте; б) х не ділиться на р і на q.

Цей генератор повільний, але є спосіб його прискорити. Як вказано у [2], в якості бітів псевдовипадкової послідовності можна використовувати не один молодший біт, а log₂m молодших бітів, де m – довжина числа x_i. Порівняна повільність цього генератора не дозволяє використовувати його для потокового шифрування (цей недолік зі зростанням швидкодії комп‘ютерів стає менш актуальним), а от для високонадійних застосувань, як наприклад, генерування ключів, він вважається кращим за багато інших.

Правильне функціонування підсистеми безпеки комп‘ютерної системи вимагає реалізації ряду функцій загального призначення, пов‘язаних з перетворенням вмісту об‘єктів системи (файлів, записів бази даних тощо) або з обчислення деяких спеціальних функцій, які суттєво залежать від вмісту об‘єктів. До таких функцій належать алгоритми контролю цілісності об‘єктів, аутентифікації та авторизації об‘єктів, що керують процесами, а також алгоритми підтримання конфіденційності інформації, що міститься в об‘єктах комп‘ютерної системи. Міжнародні та національні стандарти описують ряд добре відомих та вивчених функцій захисного характеру, зокрема алгоритми хешування MD5, MD2, SHA тощо; алгоритми генерування та перевірки електронного цифрового підпису RSA, DSS та інших. Усі ці алгоритми мають різні механізми викликів (зокрема, різну довжину аргументів). Це, у свою чергу, означає, що вони несумісні між собою. Тому задача вбудовування тих чи інших захисних механізмів в операційну систему на основі якогось одного алгоритму буде виглядати неефективною, особливо, якщо ця ОС розповсюджується в різних регіонах земної кулі. В цьому випадку логічним є побудова «шаруватої» структури, де окремий шар, реалізований, скажемо, як набір динамічних бібліотек, відповідає за захист інформації. Цей спосіб досить універсальний і широко застосовується у сімействі операційних систем Windows. Таким способом можна розв‘язати великий клас задач, пов‘язаних з універсалізацією ОС: від національних налаштувань системи до реалізації різноманітних засобів безпеки. Зрозуміло, що такі структури повинні мати т.зв. «відкритий інтерфейс», тобто бути детально документованими для того, щоби програмісти могли використати засоби цієї структури при створенні прикладного програмного забезпечення, в тому числі і для захисту інформації. Сьогодні є достатня кількість криптографічних інтерфейсів, однак найбільшої популярності набув інтерфейс від Microsoft - Microsoft CryptoAPI. Зараз використовується CryptoAPI версії 2.0. Причина популярності цього інтерфейсу полягає в тому, що Microsoft інтенсивно впровадила захисні механізми CryptoAPI у свої операційні системи та прикладне програмне забезпечення. Сучасні ОС сімейства Windows містять багато криптографічних підсистем різного призначення як прикладного рівня, так і рівня ядра. Провідну роль в цьому грають якраз функції CryptoAPI, зокрема базові криптографічні функції, сукупність яких створює інтерфейс CryptoAPI 1.0.

Інтерфейс CryptoAPI 2.0 містить як базові криптографічні функції, так і функції, що реалізують перетворення вищого рівня – роботу з сертифікатами Х.509, обробку криптографічних повідомлень PKCS#7 та інші функції, що підтримують інфраструктуру відкритих ключів. Однак набір базових криптографічних функцій цього інтерфейсу утворює CryptoAPI 1.0. Таким чином, функції CryptoAPI 1.0 утворюють криптографічне ядро прикладного рівня для сучасних операційних систем лінійки Windows. Програміст, який працює з цим інтерфейсом, може отримати усю необхідну інформацію про певного криптопровайдера засобами функції CryptGetProvParam. Перше, що необхідно знати при цьому – це набір криптографічних стандартів, які реалізують встановлені у системі криптопровайдери. Окрім різниці у стандартах, криптопровайдери відрізняються способом фізичної організації збереження ключової інформації. З точки зору програмування спосіб зберігання ключів значення не має, однак він дуже важливий з точки зору експлуатації та безпеки комп‘ютерної системи. Існуючі криптопровайдери Microsoft зберігають ключову інформацію на жорсткому диску (у реєстрі або у файлах), а провайдери інших фірм (GemPlus, Schlumberger та Infineon) – на смарт-картках. Якщо способи фізичної організації збереження ключової інформації у криптопровайдерів відрізняється, то логічна структура, яка визначається інтерфейсами та з якою мають справу програмісти, однакова для будь-якого типу провайдера. Ключова база визначається набором ключових контейнерів, кожен з яких має ім‘я, що привласнюється йому при створенні, а потім використовується для роботи з ним. У ключовому контейнері зберігається довготривала ключова інформація, наприклад, ключові пари для цифрового підпису або несиметричної системи шифрування.

Тепер розглянемо детально, як функції інтерфейсу CryptoAPI викликають бібліотеки конкретного криптопровайдера. Кожен криптопровайдер має своє власне ім‘я та тип. Його ім‘я – просто рядок, за допомогою якого система його ідентифікує. Так, базовий криптопровайдер Microsoft має назву Microsoft Base Cryptographic Provider v1.0. Тип криптопровайдера – ціле число (у нотації С – DWORD), значення якого ідентифікує набір криптографічних алгоритмів, що підтримуються. Криптопровайдер Microsoft має тип 1, цей тип провайдера реалізує в якості алгоритмів цифрового підпису та обміну ключів алгоритм RSA. Інший базовий криптопровайдер Microsoft, „Microsoft Base DSS and Diffie-Hellman Cryptographic Provider”, має тип 13. Цей тип криптопровайдера реалізує алгоритм цифрового підпису DSS, а в якості алгоритму обміну ключами – протокол Діффі-Хелмана.

Отже, для роботи з набором криптопровайдерами у системному реєстрі міститься список імен усіх криптопровайдерів. З кожним ім‘ям пов‘язаний тип криптопровайдера та ім‘я бібліотеки, яка реалізує його алгоритми.

Окрім цього в системі міститься інформація про те, який криптопровайдер треба застосовувати, якщо користувач явно не вказав конкретне його ім‘я, лише визначивши тип провайдера. Такий криптопровайдер називають провайдером за замовчуванням для заданого типу. Наприклад, для типу 1 провайдером за замовчуванням є Microsoft Base Cryptographic Provider v1.0, а для типу 13 - Microsoft Base DSS and Diffie-Hellman Cryptographic Provider. Для визначення криптопровайдерів за замовчуванням використовують функцію CryptGetDefaultProvider, а для зміни цього параметру – функції CryptSetProvider або CryptSetProviderEx. Функції дозволяють встановити провайдера за замовчуванням як для поточного користувача, так і для системи в цілому (усіх користувачів). Ці параметри зберігаються у вулику реєстру HKEY_LOCAL_MACHINE. Параметри, встановлені для поточного користувача, мають пріоритет над параметрами, встановленими для усієї системи, та зберігаються у вулику реєстру HKEY_CURRENT_USER. Якщо параметри для поточного користувача відсутні, застосовуються загальносистемні.

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

Робота з певним провайдером починається з виклику функції CryptAcquireContext, де користувач визначає тип потрібного криптопровайдера, його назву та назву робочого ключового контейнера. В результаті роботи функція повертає користувачу дескриптор криптопровайдера (handle), за допомогою якого користувач в подальшому буде звертатися до нього та передавати його у процедури для виконання усіх необхідних криптографічних операцій. Детальний опис контексту роботи з криптопровайдерами та приклади (мовою програмування С) дивіться у книжці Щербакова Л.Ю., Домашева А.В. «Прикладная криптография».

Власне бібліотеки CryptoAPI разом з файлами заголовків та допомоги постачаються у складі бібліотек MSDN.

Література

1.   Галицкий А.В., Рябко С.Д., Шаньгин В.Ф. Защита информации в сети. – М.:ДМК Пресс, 2004.

2.   Щеглов А.Ю. Защита компьютерной информации от несанкционированного доступа. – СПб.: Наука и техника, 2004.

3.   Проскурин В.Г., Крутов С.В., Мацкевич И.В. Защита в операционных системах. – М.: «Радио и связь», 2000.

4.   Щербаков А, Домашев А. Прикладная криптография. Использование и синтез криптографических интерфейсов. М.:Русская редакция, 2003.

5.   М.А. Деднев, Д.В. Дыльнов, М.А. Иванов Защита информации в банковском деле и электронном бизнесе. М.: Кудиц-образ, 2004. – 512 с.