Паралельне обчислення в задачах криптоаналізу

Автор: , та

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

Бібліографічний опис статті:

, та . Паралельне обчислення в задачах криптоаналізу//Наука онлайн: Міжнародний електронний науковий журнал - 2020. - №12. - https://nauka-online.com/publications/technical-sciences/2020/12/paralelne-obchislennya-v-zadachah-kriptoanalizu/

Стаття опублікована у: : Наука Онлайн No12 декабрь 2020

Технічні науки

УДК 004.04

Олійник Олена Володимирівна

старший викладач кафедри програмної інженерії

Харківський національний університет радіоелектроніки

Тітова Маргарита Костянтинівна

студентка третього курсу

Харківського національного університету радіоелектроніки

Лузан Микита Олександрович

студент четвертого курсу

Харківського національного університету радіоелектроніки 

ПАРАЛЕЛЬНЕ ОБЧИСЛЕННЯ В ЗАДАЧАХ КРИПТОАНАЛІЗУ

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

Ключові слова: криптоаналіз, розподілені багатопроцесорні обчислення, розпаралелювання, шифрування, декодування.

Майже всі програмно-апаратні методи захисту інформації тісно пов’язані з криптографією. Можна припустити, що провідним (хоча і не єдиним) напрямом розвитку сучасної криптографії є ​​створення стійких алгоритмів шифрування. Будь-який алгоритм шифрування, що розробляється віддається ретельному аналізу з метою виявлення його слабких місць і можливості в цілому, це і є суть поняття криптоаналіз [2-4]. За принципом побудови і використання секретного ключа існує два види шифрів, розроблених на даний момент: симетричні і асиметричні. У наш час з’являється все більш потужні обчислювальні ресурси і таким чином завдання аналізу сучасних криптосистем перетворилося з виключно теоретичного в практичне. При цьому багато з методів придатні для розпаралелювання, а значить, можуть працювати в кілька разів швидше при використанні відповідних обчислювальних засобів. Одним із способів підвищення продуктивності при аналізі різних криптосистем є використання розподілених багатопроцесорних обчислень (РБО) для прискорення процесу аналізу і більш швидкого отримання результату. Застосування РБО можливо як при криптоанализі симетричних блокових шифрів, так і при використанні методів аналізу сучасних асиметричних криптосистем [5].

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

Способи і технології обгрунтування криптографічної стійкості засновані на накопиченому досвіді розкриття «секретів» криптоалгоритмів. Крім стійкості криптоалгоритми повинні задовольняти ряду інших умов, наприклад економічності, швидкості реалізації і т.п. Сукупність підходів, які дозволяють задовольнити даний набір умов, становить теорію синтезу криптоалгоритмів, на якій засновані методи реалізації криптографічної підсистеми захисту інформації. Способи вивчення і синтезу засновані на сучасних математичних методах. Найчастіше потреби вивчення і синтезу криптоалгоритмів обслуговують дискретна математика, теорія чисел, алгебра і теорія ймовірностей. Відповідно до традиції сучасної криптографії індивідуальність реалізації криптографічних систем заснована на оцінках стійкості, придбаних за допомогою найбільш відомих універсальних способів криптоаналізу, методів аналізу блокових і потокових шифрів, аналізу хеш-функцій і алгоритмів з несиметричним ключем. Всі перераховані способи можна втілити на обчислювальних системах з високою обчислювальної продуктивністю, описаних в роботі [5]. Наведемо ряд прикладів використання традиційних способів криптоаналізу і створимо висновки щодо трудомісткості обчислювальних задач і можливості застосування методів паралельних обчислень до вирішення цих завдань.

Як перший приклад хотілося б показати історичний випадок, який вніс неймовірний внесок у поширення схеми RSA. Для того, щоб показати свій метод, RiverstR.L., ShamirA. і AdlemanL. зашифрували за допомогою нього англійську фразу, яка не несе в собі ніякого сенсу. Перш за все даний текст звичайним чином [1; 3] був перекодований в ціле х. При цьому, очікувано, вийшло ціле число, що містить 78десятічних цифр. Після цього до отриманого числа була застосована процедура кодування RSA f(x) = xe mod m при заданих, досить великих e і m, тим самим була отримана шифрограма. Закодований текст був опублікований разом з позначеними значеннями використаних параметрів е і m. В якості додаткової інформації повідомлялося, що m = pq, де p і q – якісь прості числа, 64 і 65 розрядні відповідно. Тому, хто перший дешифрує вихідну фразу, було покладено винагороду в 100 доларів. Дана історія закінчилася через 16 років в 1994 р, коли D. Atkins, M. Graff, A.K. Lenstra і P.C. Leyland виклали про дешифрування англійського повідомлення, створеного Riverst, Shamir і Adleman. Числа p і q вийшли астрономічно великими. Відтворення обчислень зажадало найбільших ресурсів. В ході роботи, якою керували чотири автори проекту і тривалою після попередньої теоретичної підготовки 220 днів, на добровільній основі брало участь близько 600 чоловік і приблизно 1600 комп’ютерів, об’єднаних мережею Internet. Головна проблема проекту полягала в розкладанні 129-значного числа на прості множники. Детальна інформація про обчислення була надрукована в статті, в назву якої автори вписали закодований шістнадцять років тому і декодований ними англійський вираз. Даний приклад демонструє застосування паралельних обчислень, які вперше були використані в 1994 р. для дешифрування.

Можна навести ще один приклад. В останні кілька років широке поширення набули глобальні мережі ЕОМ. Можна створити програму (вірус), який буде виконувати такі завдання: випробує ключі у вільний час процесора, починаючи з деякого номера і в тому випадку, якщо рішення позитивне, передає відповідь і самознищується, а також поширює програму-вірус, який всім іншим працюючим над випробуванням вірусам наказує самознищитися. Подібна ідея розпаралелювання продемонстрована в «китайській лотереї». У кожен телевізор або радіоприймач на внутрішньому ринку Китаю вмонтований чіп, який приймає відкритий і закодований текст і починає випробування заданої ділянки ключів DES. Якщо ключ знайдений, то апарат дає сигнал, а його власник повинен повідомити про сигнал в урядовий орган, там його чекає приз. Коли уряду потрібен черговий ключ, то через широкомовну програму передаються відкритий і закодовані тексти, за якими включаються чіпи в телевізорах і радіоприймачах. За даними, на 1995 «китайська лотерея» при використанні чіпа в 1 млн операцій в секунду могла дозволити розкрити ключ DES в Китаї за 280 с, а в США – за 97 с.

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

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

Література

  1. Алексеев А. П., Дикарева К. Н., Макаров М. И. Аналіз швидкодії алгоритмів обчислення секретного ключа в асиметричній криптосистемі RSA // Системи управління зв’язку та безпеки. 2015. №3. C. 186-209.
  2. Бабенко Л.К., Ищукова Е.А. Сучасні алгоритми блокового шифрування і методи їх аналізу. М.: Геліос АРВ, 2006. 376 с.
  3. Бабенко Л.К., Ищукова Е.А. Паралельні алгоритми для вирішення задач захисту інформації. М.: Геліос АРВ, 2014. 304 с.
  4. Грушо А.А., Применко Э.А., Тимонина Е.Е. Теоретичні основи комп’ютерної безпеки. М.: Видавничий центр «Академія», 2009. 272 с.
  5. Лацис А.О. Паралельна обробка даних. М.: Видавничий центр «Академія», 2010. 336 с.

Перегляди: 308

Коментарі закрито.

To comment on the article - you need to download the candidate degree and / or doctor of Science

Підготуйте

наукову статтю на актуальну тему, відповідно до роздлів журналу

Відправте

наукову статтю на e-mail: editor@inter-nauka.com

Читайте

Вашу статтю на сайті нашого журналу та отримайте сертифікат