Evaluation of the reverse transformation methods complexity of the residual number system for secure data storage

Abstract

В тенденціях сучасного світу однією із актуальних проблем у сфері інформаційних технологій є підвищення ефективності методів зберігання інформації в розподілених та хмарних сервісах. При використанні їх зазвичай виникає проблема підвищення довіри до даних сервісів, забезпечення конфіденційності та цілісності даних у процесі передавання, опрацювання та зберігання. У світі активно проводяться дослідження, направлені на розроблення та використання методів гомоморфного шифрування з метою забезпечення довіри до хмарних сервісів. Не зважаючи на існуючі дослідження, залишається чимало невирішених завдань, які знижують довіру до сучасних хмарних та віддалених сервісів зберігання даних. Одним із напрямків підвищення надійності та захищеності систем зберігання даних є використання системи залишкових класів (СЗК). У попередніх роботах досліджено використання СЗК для захищеного розподіленого зберігання даних. Суть підходу полягає в поділі даних на фрагменти та зберігання окремих фрагментів на різних хмарних чи розподілених сервісах. Таким чином, захист даних досягається завдяки тому, що для їх відновлення необхідно отримати доступ до всіх фрагментів, які зберігаються у хмарних сховищах різних провайдерів або на фізично розподілених носіях. Для поділу даних на фрагменти використовується метод прямого перетворення СЗК, тобто ділення інформаційного пакета чи вмісту файла на систему взаємно простих модулів, а самі фрагменти розподіляються на відповідних хмарних чи віддалених сховищах. У СЗК відновлення даних зазвичай виконується шляхом зворотного перетворення з використанням китайської теореми про залишки. У роботі проведено порівняльний аналіз методів на основі класичної китайської теореми про залишки (КТЗ) та її модифікацій: нової китайської теореми про залишки І (КТЗ I) та нової китайської теореми про залишки ІІ (КТЗ IІ). Слід відзначити, що кожен з вище згаданих методів має свою послідовність виконання операцій. Деякі змінні, такі, як базисні числа bi, коефіцієнти kі та tі для багаторазового зворотного перетворення не потрібно обчислювати кожного разу і можна обчислити заздалегідь та зберегти для подальшого використання. Це дозволяє зменшити кількість кроків та відповідно збільшити швидкодію роботи системи в цілому. Деякі із запропонованих методів мають значні переваги при реалізації у розподілених системах. На основі проведених обчислень для порівняння ефективності використання різних варіантів КТЗ побудовано графік залежності часових складностей із врахуванням розрядності та кількості модулів. Для оцінювання складності методів зворотного перетворення в роботі проведено порівняння для СЗК із чотирьох модулів різної розрядності. В результаті проведених аналітичних розрахунків слід відмітити, що при невеликій розрядності модулів кожен із методів характеризується практично однаковою часовою складністю, а при збільшенні розрядності модулів суттєво зростає складність обчислення зворотного перетворення. Тому використання КТЗ I і КТЗ II згідно з результатами досліджень є значно ефективнішим для використання в системах захищеного зберігання даних. Проведено дослідження часової складності методів зворотного перетворення СЗК для використання в системах розподіленого зберігання даних підвищеної захищеності та надійності. На основі проведених досліджень часової складності обґрунтовано вибір ефективного методу зворотного перетворення, а саме класичної теореми про залишки І (КТЗ I) та ІІ (КТЗ II), які характеризуються меншою часовою складністю при зростанні розрядності модулів. При максимальній розглянутій розрядності складність обчислень при використанні КТЗ I у 2 рази нижча, ніж при КТЗ, а використання КТЗ IІ забезпечує складність, нижчу в 1,6 раза в порівнянні із КТЗ I.

The methods of conversion from the residual number system to the decimal number system based on the classical Chinese remainder theorem (CRT) and its improvements CRT I, CRT II are considered in this paper. Analytical dependences of the time complexity of the specified methods are analyzed and constructed. As the result of carried out investigation, it is established that CRT II is characterized by greater efficiency compared to the other methods mentioned above. Examples of the implementation of direct and reverse conversion of RNS based on the application of CRT, CRT I, CRT II are given.