Выпуск №7 (Май)
XLI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.05.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XL Международная научно-практическая конференция «Актуальные проблемы современной науки», 28.03.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

МНПК "Цифровая трансформация и инновации в экономике, праве, государственном управлении, науке и образовательных процессах", 18-21.03.2019

XXXIX Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.02.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XIII Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 31.01.2019 (Совместная конференция с Финансово-экономическим научным советом)

XXXVIII Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.01.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XXXVІI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2018 (Совместная конференция с Международным научным центром)

XXXVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2018 (Совместная конференция с Международным научным центром)

XIII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXXV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.10.2018 (Совместная конференция с Международным научным центром)

XXXIV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2018 (Совместная конференция с Международным научным центром)

ХXXIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.08.2018 (Совместная конференция с Международным научным центром)

ХXXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 31.07.2018 (Совместная конференция с Международным научным центром)

XII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХXXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2018 (Совместная конференция с Международным научным центром)

ХІ Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2018 (Совместная конференция с Международным научным центром)

XXIХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.04.2018 (Совместная конференция с Международным научным центром)

ХХVIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.03.2018 (Совместная конференция с Международным научным центром)

ІІІ МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 19-22.03.2018 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 28.02.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХХVІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2018 (Совместная конференция с Международным научным центром)

ХХVІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2018 (Совместная конференция с Международным научным центром)

XІІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.12.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2017 (Совместная конференция с Международным научным центром)

ХХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2017 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2017 (Совместная конференция с Финансово-экономическим научным советом)

XІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.09.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2017 (Совместная конференция с Международным научным центром)

X Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.07.2017 (Совместная конференция с Международным научным центром)

ХXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2017 (Совместная конференция с Международным научным центром)

"Тенденции развития национальных экономик: экономическое и правовое измерение" 18-19.05.2017 (Совместная конференция с Финансово-экономическим научным советом и ККИБиП)

ХIX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.04.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.03.2017 (Совместная конференция с Международным научным центром)

МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 20–23.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

VIII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.02.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2017 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.01.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2017 (Совместная конференция с Международным научным центром)

ХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2016 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 28.12.2016 (Совместная конференция с Финансово-экономическим научным советом)

VII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.11.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.10.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.10.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конф. «Научный диспут: вопросы экономики и финансов», 30.09.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.09.2016 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.08.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 29.07.2016 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.07.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.06.2016 (Совместная конференция с Финансово-экономическим научным советом)

ІX Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2016 (Совместная конференция с Международным научным центром)

VI Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.05.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 30.05.2016 (Совместная конференция с Международным научным центром)

V Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 29.04.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.04.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 31.03.2016 (Совместная конференция с Международным научным центром)

ІI Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 30.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 21-24.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 26.02.2016 (Совместная конференция с Финансово-экономическим научным советом)

II Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 20.02.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.12.2015 (Совместная конференция с Международным научным центром)

IV Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.12.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.11.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 29.10.2015 (Совместная конференция с Финансово-экономическим научным советом)

Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 28.10.2015 (Совместная конференция с Международным научным центром)

III Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.09.2015 (Совместная конференция с Финансово-экономическим научным советом)

III Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.08.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІІ Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 30.06.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2015 (Совместная конференция с Международным научным центром)

II Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.05.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы экономики и финансов, 29.04.2015 (Совместная конференция с Финансово-экономическим научным советом)

Научный диспут: вопросы экономики и финансов, 31.03.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы современной науки, 27.03.2015 (Совместная конференция с Международным научным центром)

Глобальные проблемы экономики и финансов, 27.02.2015 (Совместная конференция с финансово-экономическим научным советом)



Анотация. В данной статье описано модификацию алгоритма шифрования RSA с использованием китайской теоремы про остатки, а также влияние внедрения китайской теоремы об остатках на работу криптосистемы.

Ключевые слова: Алгоритм RSA, шифрование, цифровая подпись, CRT, Китайска теорема про остатки.


Отрасль науки: Технические науки
Скачать статью (pdf)

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

УДК 004.056.55

Казаченко Ольга Дмитрівна

Студентка

Національний технічний університет України

«Київський політехнічний інститут ім. Ігоря Сікорського»

Казаченко Ольга Дмитриевна

Студентка

Национальний технический университет Украины

«Киевский политехнический институт им. Игоря Сикорского»

Kazachenko Olha

Student

National technical university of Ukraine

«Igor Sikorsky Kyiv Polytechnic Institute»

РЕАЛІЗАЦІЯ АЛГОРИТМУ RSA З ЗАСТОСУВАННЯМ КИТАЙСЬКОЇ ТЕОРЕМИ ПРО ЗАЛИШКИ

РЕАЛИЗАЦИЯ АЛГОРИТМА RSA С ИСПОЛЬЗОВАНИЕМ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

RSA ALGORITHM IMPLEMENTATION USING CHINESE REMAINDER THEOREM

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

Ключові слова: Алгоритм RSA, шифрування, цифровий підпис, CRT, Китайська теорема про залишки.

Анотация. В данной статье описано модификацию алгоритма шифрования RSA с использованием китайской теоремы про остатки, а также влияние внедрения китайской теоремы об остатках на работу криптосистемы.

Ключевые слова: Алгоритм RSA, шифрование, цифровая подпись, CRT, Китайска теорема про остатки.

Summary. This article describes the modification of the RSA encryption algorithm using the Chinese remainder theorem, as well as the impact of the implementation of encryption using Chinese remainder theorem on the behavior of cryptosystem.

Keywords: RSA, encryption algorithm, digital signature, CRT, Chinese remainder theorem.

  1. Вступ

RSA (RivestShamir та Adleman) — криптографічний алгоритм з відкритим ключем. Він став першим алгоритмом такого типу, придатним і для шифрування, і для цифрового підпису [1]. Криптосистема RSA використовується у різних продуктах, на різних платформах і у багатьох галузях. В даний час вона вбудовується в комерційні продукти, число яких постійно збільшується. Також її використовують операційні системи MicrosoftApple, Sun і Novell. В апаратному виконанні RSA алгоритм застосовується в захищених телефонах, на мережних платах Ethernet, на смарт-картах. Математичний апарат, що лежить в основі роботи алгоритму дуже складний і базується на обчислювальній складності задачі факторизації великих цілих чисел. Існує багато дослідження з приводу модифікацій алгоритм та його удосконалення. Розглянемо китайську теорему про залишку та її вплив при використанні у даній криптосистемі.

  1. Алгоритм RSA

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

  • Якщо відомо х, то f(x) відносно легко розрахувати;
  • Якщо відомо, то для того щоб розрахувати х немає легко та ефективного шляху.

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

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

2.1 Генерація ключів

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

  • Для всіх допустимих відкритого та приватного ключа P та S існують відповідні функції шифрування Ер(х) та дешифрування Ds(x), такі, що
  • Це виконується для всіх повідомлень mM , де М – множина допустимих повідомлень

Для генерації ключів використовують наступний алгоритм:

  1. Вибирають два різних, довільних, простих числа p та q заданого розміру (512/1024/2048 біт кожне)
  2. Розраховується добуток, який назвається модулем
  3. Розраховується значення функції Ейлера від числа
  4. Вибирається ціле, взаємно просто число е, таке що. Воно називається відкритою експонентою. Час затрачений на шифрування пропорційний числу одиничних біт в е. Таким чином, частіше вибирають е з більшою кількістю одиниць у двійковому представленні.
  5. Розраховується число d мультиплікативно зворотне числу е по модулю f, тобто таке, що :. Воно називається секретною експонентою і зазвичай рахується з застосуванням розширеного алгоритму Евкліда.
  6. Таким чином отримується пара відкритого ключа {e, n} та приватного{d, n} [2].

2.2 Шифрування та дешифрування

Розглянемо на відомому прикладі спілкування Боба та Аліси. Припустимо, Боб хоче відправити повідомлення m Алісі.

Алгоритм шифрування зображено на рисунку 1 і виконується у такій послідовності:

  • Взяти відкритий ключ {e, n} Аліси
  • Взяти відкритий, вхідний текст m
  • Зашифрувати повідомлення з використанням відкритого ключа Аліси

Після отримання Бобом повідомлення виконується дешифровка:

  • Взяти зашифроване повідомлення
  • Взяти приватний ключ {d, n}
  • Розшифрувати по формулі :

Рисунок 1.  Схема обміну даними, зашифрованими алгоритмом RSA [розробка автора]

  1. Швидкість алгоритму та використання CRT

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

Для аналізу часу виконання операцій з приватним та відкритим ключами, візьмемо {d, n} та {e, n} , які задовольняють умовам: Тоді при їх використанні виконується відповідно O(1) та O(β) операцій множення по модулю.

Таким чином час виконання тим більший, чим більше одиниць у двійковому представленні відкритої експоненти. По евристичний оцінкам довжина секретної експоненти d нетривіальним чином пов’язана з відкритою е та модулем n. Тому дешифровка повільніша за шифрування, а перевірка цифрового підпису швидша за створення [3].

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

Оскільки p та q – числа порядку 2512 на ці дії потрібно буде зробити два піднесення у степінь з показником у 512 біт по модулю 512-бітового числа. Це набагато швидше ніж одне піднесення у степінь з 1024-бітним показником по модулю 1024-бітного числа. В кінці потрібно буде лише відновити повідомлення m використовуючи та. Це легко зробити за допомогою китайської теореми про залишки. [4]

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

  1. Висновок

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

Література:

  1. Wikipedia (https://en.wikipedia.org/wiki/RSA_(cryptosystem)).
  2. Evgeny Milanov, The RSA Algorithm, https://sites.math.washington.edu/~morrow/336_09/papers/Yevgeny.pdf
  3. G.N. Shinde,  H.S. Fadewar Faster RSA Algorithm for Decryption Using Chinese Remainder Theorem, http://www.techscience.com/doi/10.3970/icces.2008.005.255.pdf
  4. Johann Großschаdl The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip, Graz University of Technology, Institute for Applied Information Processing and Communications, Inffeldgasse 16a, A–8010 Graz, Austria.