Алгоритм криптографічного захисту інформації RSA

• Несанкціонований обмін інформацією та її модифікація.

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

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

Основні методи захисту інформації

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

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

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

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

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

Елементи теорії криптографічних систем

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

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

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

Криптографічна система  є сімейством Т_k перетворень відкритого тексту. Члени цього сімейства індексуються, або позначаються символом k, параметр k є ключем. Простір ключів К – це набір можливих значень ключа. Звичайно ключем є послідовний ряд букв алфавіту.

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

У симетричних криптосистемах і для шифрування і для дешифрування використовують один і той самий ключ.

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

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

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

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

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

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

 

Криптографічні  методи захисту

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

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

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

В основу «асиметричних методів» криптографії покладено ідею використання двох різних ключів: одного – для  шифрування, а другого – для  дешифрування. Один з цих ключів повинен зберігатися у таємниці і називається приватним або  таємним (секретним), інший робиться доступним усім бажаючим. Його можна завжди вільно отримати, і називається він публічним або відкритим. Незважаючи на те, що обидва ключі взаємопов’язані між собою математично, асиметричні методи забезпечують неможливість визначення іншого ключа за наявності одного з них.

До найпоширеніших методів  використання відкритих ключів належать: RSA (Rivest, Shamir, Adleman), OSS (Ong, Schnorr, Shamir), Ель-Гамаля (El Gamal), Рабіна (Rabin), Окамото Сіраісі (Okamoto, Shiraishi), Мацумото Імаі (Matsumoto, Imai). Захист від підробки цифрового підпису тут забезпечується обчислювальною складністю розв’язання задач дискретного логарифмування у скіненномірних полях, знаходження простих дільників великих чисел, або обчислення еліптичних кривих.

Далі розглянемо детальніше саме асиметричний метод . 

Історія методу RSA

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

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

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

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

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

З моменту свого створення RSA постійно піддавалася атакам типу Brute-force attack (атака методом грубої сили, тобто перебором). У 1978 р. автори алгоритму опублікували статтю, де призвели рядок, зашифрований щойно винайденим ними методом. Першому, хто розшифрує повідомлення, було призначено винагороду в розмірі 100$, але для цього було потрібно розкласти на два співмножники 129-значне число. Це був перший конкурс на злом RSA.

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

Компанія RSA (httр: / / www.rsa.ru) регулярно проводить конкурси на злом власних (і не тільки власних) шифрів. Попередні конкурси виграла організація Distributed.net, що є Інтернет-спільнотою добровольців.

Учасники Distributed.net завантажують до себе на ПК невелику програму-клієнт, яка приєднується до центрального сервера  і отримує шматочок даних для  обчислень. Потім усі дані завантажуються на центральний сервер, і клієнт отримує наступний блок вихідної інформації. І так відбувається до тих пір, поки всі комбінації не будуть перебрані.

Користувачі, учасники системи, об'єднуються в команди, а на сайті  ведеться рейтинг як команд, так  і країн. Наприклад, що бере участь в  конкурсі по злому RC5-64 (блочний шифр компанії RSA, що використовує ключ довжиною 64 біта) організації Distributed.net вдалося  здійснити злом через п'ять років (1757 днів) роботи. За цей час у проекті  брали участь 327 856 користувачів і потрібно було перебрати 15 268 315 356 922 380 288 варіантів ключа.

З'ясувалося, що була (не без  гумору) зашифрована фраза «some things are better left unread» - «деякі речі краще залишати непрочитаними». Загальні рекомендації по шифру RC5-64 такі: алгоритм досить стійкий для повсякденних потреб, але шифрувати їм дані, що залишаються секретними протягом більш ніж п'яти років, не рекомендується.

 

Що лежить в  основі алгоритму?

Теорема 1. (Мала теорема Ферма).

Якщо р – просте число, то x^{р – 1}= 1 (mod p) для будь – якого х, простого відносно р, і x^р=х (mod p) для будь – якого х.

Теорема 2.

Якщо n=p⋅ q (p i q – відмінні одне від одного прості числа), то φ(n)=(p – 1)(q – 1).

Теорема 3.

Якщо n=p⋅ q (p i q – відмінні один від одного прості числа), х – просте відносно p i q, то x^φ(n)=1 (mod n).

Наслідок.

Якщо n=p⋅ q, (p i q – відмінні одне від одного прості числа), е – просте відносно φ(n), то відображення E_e,n: x→x^e (mod n) буде взаємно однозначним. Очевидний і той факт, що коли е – просте відносно φ(n), то існує ціле d – таке, що ed= 1 (mod φ(n)).

На цих математичних фактах і заснований популярний алгоритм RSA.

Нехай n=p⋅ q, де p i q – відмінні прості числа. Якщо e i d задовольняють рівняння ed = 1 (mod φ(n)), то відображення E_e,n i E_d,n будуть інверсіями E_d,n i E_e,n, і легко обчислюються, якщо відомі e,d,p,q. Якщо відомі e i n, а p i q невідомі, то E_e,n є односторонньою функцією і знаходження E_d,n за заданим n рівнозначно розкладанню n. Якщо p i q – достатньо великі прості, то розкладання n практично нездійсненне. Це і закладено в основу системи шифрування RSA.

Користувач і вибирає пару різних простих p_i i q_i та розраховує пару цілих (e_i, d_i), які є простими відносно φ(n), де n_i=p_iq_i. Довідкова таблиця містить ключі {(e_i,n_i)}. Припустимо, що вихідний текст x=(x₀,x₁,…,x_{n – 1}), x Є Z_n, 0 ≤ i < n.