Застосування криптографії на еліптичних кривих в смарт-картах



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

Use of elliptic curve cryptography in smart-cards

Vadim Poltorak, Vitaliy Mykosovskyy ACTS NTUU “KPI”

Ukraine, Kyiv

Summary

Argumentation the possibility of using elliptic curve cryptography in systems with limited processing power. Description of possible advantages of using elliptic curve cryptography in smart-cards.

Keywords

Elliptic curves, elliptic curve cryptography, smart-cards, RSA.

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

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

Смарт-карти портативні і можуть бути застосовані в багатьох програмах та сервісах, і зменшити витрати в порівнянні з системами заснованими на використанні імені користувача та паролю.

Для шифрування даних смарт-карти використовують алгоритм RSA[2]. Оскільки смарт-карти обмежені в обчислювальній потужності, а вимоги до криптозахисту даних ростуть з кожним днем, необхідне нове рішення для збільшення криптостійкості даних. Збільшення крипттостійкості, при використанні RSA потребує збільшення обчислювальної потужності смарт-карт. Це призведе до збільшення собівартості карток. Для вирішення цієї проблеми пропонується застосувати криптографію на еліптичних кривих [5].

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

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

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

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

Для застосування еліптичної криптографії в смарт-картах пропонується наступний алгоритм. В якості зовнішніх параметрів вибираються еліптична крива Е і точка Р високого порядку із групи точок Е(F) [2].

Абонент А (термінал) вибирає секретний ключ ${{k}_{A}}\in {{Z}^{*}}_{N}$ (мультиплікативна група кільця лишків за модулем N), обчислює і оголошує свій відкритий ключ (Е, Р, Y), де $Y={{k}_{A}}P$.

Абонент В (смарт-карта) для передачі абоненту А секретного повідомлення m

  • отримує авторизовану копію відкритого ключа (E, N, P, Y);
  • «вкладає» повідомлення m в точку $M\in E\left( F \right)$ за певним алгоритмом[4];
  • вибирає випадкове число $r\in{Z}_{N}^{*}$ (процедура рандомізації);
  • обчислює сеансовий ключ $\Delta=rY$;
  • обчислює криптограму $C=\left({{C}_{1}},{{C}_{2}} \right)=\left( rP,M+\Delta \right)$;
  • відправляє криптограму С абоненту А.

Для розшифрування криптограми абонент А, використовуючи свій секретний ключ ${{k}_{A}}$,

  • обчислює ${{k}_{A}}{{C}_{1}}$ (отримує в результаті ${{k}_{A}}rP$), інвертує цей результат [5];
  • складає отриману точку $-{{k}_{A}}rP$ із точкою ${{C}_{2}}$, відновлюючи точку М:

\[-{{k}_{A}}rP+M+\Delta =M+r{{k}_{A}}P-{{k}_{A}}rP=M\]

Криптоаналітику (потенційному зловмиснику) відомі відкритий ключ (E, P, Y) і криптограма (${{C}_{1}}$, ${{C}_{2}}$), таким чином для отримання точки М йому необхідно обчислити точку ${{k}_{A}}rP$. Для цього йому доведеться вирішити задачу Діффі-Хелмана для еліптичної кривої[2]: знайти цюточку за відомими точками rP та Y = ${{k}_{A}}P$, або йому прийдеться вирішувати задачі дискретного логарифмування, обчислюючи секретний ключ ${{k}_{A}}$ та рандомізатор r за точками ${{k}_{A}}P$, rP і Р відомої йому еліптичної кривої Е та відомому йому порядку точки Р.

Слід зазначити, що повторне використання рандомізатора r недопустимо [4]. Якщо криптоаналітику вдалось розшифрувати одну криптограму (${{C}_{1}}$, ${{C}_{2}}$) чи дізнатись точку M іншим способом, то він з легкістю отримає і інші повідомлення, зашифровані тим же рандомізатором r, що і криптограма (${{C}_{1}}$, ${{C}_{2}}$). Перші точки в цих парах однакові, а другі зв’язані співвідношеням

\[{{{C}'}_{2}}={{C}_{2}}-M+{M}'.\]

Тому ${M}'={{{C}'}_{2}}-{{C}_{2}}+M$ і друге повідомлення знайдено.

Застосування даного алгоритму дозволить зменшити витрати на смарт-карти, збільшивши при цьому криптостійкість даних. При цьому слід дотримуватись наступних вимог[6]:

  • Криві розглядаються або надпростими полями (порядок q яких дорівнює простому числу p), або над полями характеристики два (у яких $q={{2}^{m}}$).
  • Для представлення елементів поля використовується або стандартний базис, породжений тричленом або п’ятичленом, або гаусівський нормальний базис.
  • Крива Е задається вибором двох елементів a, b поля GF(q). В випадку $p>2$ вона має вид ${{Y}^{2}}={{X}^{3}}+aX+b$,а в випадку р = 2 вид ${{Y}^{2}}+XY={{X}^{3}}+aX+b$. Таким чином, рекомендуються тільки несуперсингулярні криві.

В наступній таблиці приводиться необхідна довжина ключа (у бітах) для забезпечення однакової криптоскійкості, застосовуючи алгоритм RSA та алгоритм на еліптичних кривих [3]:

Табл. 1 – Порівняння довжини ключа RSA і еліптичної криптографії

Порівняння швидкодії алгоритмів при однаковій довжині ключа за матеріалами [3] дозволяє зробити ряд висновків:

Табл.2 – Порівняння RSA і еліптичної криптографії за швидкодією

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

Перелік літератури

  1. Rankl, W.; W. Effing (1997). Smart Card Handbook. John Wiley & Sons.ISBN 0-471-96720-3. Guthery, Scott B.; Timothy M. Jurgensen (1998). SmartCard Developer's Kit. Macmillan Technical Publishing.ISBN 1-57870-027-2.

  2. Брюс Шнаер. Прикладная криптография [Текст] / Шнаер Б. – Новгород: Триумф, 2012. – 784с. – ISBN 978-5-89392-527-2

  3. Karu P. Practical comparison of fast public-keycryptosystems / P. Karu, J. Loikkanen. – Helsinki: Helsinki University ofTechnology, 2001. – 93 с.

  4. A. Menezes, P. vanOorschot, S. Vanstone. Handbookof Applied Cryptography. — CRC-Press, 1996. — 816 p. —(Discrete Mathematics and Its Applications

  5. Болотов Анатолий Александрович. Элементарное введение в эллиптическую криптографию: Алгебраические и алгоритмические основы / Анатолий Александрович Болотов, Сергей Борисович Гашков, Александр Борисовч Фролов. –М.: КомКнига, 2006. – 328 с. - ISBN 5-484-00443-8

  6. Мао Венбо. Современная криптография. Теория и практика. — М.:Вильямс, 2005. — 768 с. ISBN 5-8459-0847-7. - ISBN 0-13-066943-1.
May 25, 2016