Сучасні інформаційні технології/4. Інформаційна безпека

Якименко І.З., Хомінчук А.А, Драбик Н.Р.

Тернопільський національний економічний університет

Дослідження часових характеристик алгоритму множення точок на еліптичних кривих (ЕК)

Пошук кратної точки (експоненціювання точки на еліптичній кривій) безсумнівно є однією з базових операцій при шифруванні на ЕК. Задача пошуку кратної точки зводиться до знаходження точки kP, де k – множник, P – базова точка на еліптичній кривій, координати якої визначаються параметрами кривої. Для знаходження кратної точки можна скористатися наступним співвідношенням (розклавши множник k в бітову послідовність довжини L):

, . (1)

Проте, як показали дослідження в статті [1], такий алгоритм (алгоритм подвоєння-додавання) є нестійким до часових атак завдяки тому, що вага Хемінга залежить від ключа, як це показано на рис. 1.

Рисунок 1 – Залежність часу виконання алгоритму подвоєння-додавання від ваги Хемінга для біт

Якщо ж використати не бітове представлення числа k, а NAF(k) (non-adjacent form), то вага Хемінга для будь-якого L буде однаковою. Алгоритм визначення NAF(k) подано нижче:

Вхід: позитивне ціле число k.

Вихід: NAF(k).

1. і←0.

2. while k≥1 do

2.1. if k is odd then: k_і←2-(k mod4), k←k-k_і;

2.2. else k_і←0;

2.3. k←k/2,i←i+1.

3. return (k₀,k₁,...,k_L-1).

Алгоритм обчислення кратної точки при використанні NAF(k) (алгоритм подвоєння-додавання-віднімання) виглядає так:

Вхід: NAF(k), РЕ.

Вихід: kP.

1. R←О.

2. for i=L-1 to 0 do

2.1. P←2P.

2.2. if k_i=1 then R←R+P.

2.3. if k_i=-1 then R←R-P.

3. return R.

Як видно з опису алгоритму, для пошуку кратної точки потрібно виконувати додавання, віднімання та подвоєння точки на ЕК. Для реалізації додавання можна використати алгоритм з стандарту P1363 А 10.1 [2], подвоєння точки записати як , віднімання - додавання точки .

Для дослідження змін часових характеристик алгоритму від множника k та бітової розмірності числа a було створено програмний продукт пошуку кратних точок. З його допомогою було проведено ряд тестів. Результати дослідження часу пошуку кратної точки в залежності від множника k (при розрядності числа a 256 біт) подано на рис. 2, а залежність від бітової довжини числа a на рис. 3.

Рисунок 2 – Залежність часу виконання множення від множника k

Рисунок 3 – Залежність часу виконання множення від бітової довжини коефіцієнта a

В даній роботі авторами проведено дослідження змін часових характеристик алгоритму пошуку кратних точок в залежності від множника k та бітової розмірності коефіцієнта еліптичної кривої a. В статті наведено графічне представлення результатів роботи програмного продукту, розробленого на основі алгоритму обчислення кратної точки з використанням NAF(k) (алгоритм подвоєння-додавання-віднімання), який є стійким до часових атак на ЕК. Отже доцільно використовувати цей алгоритм в криптосистемах, що базуються на еліптичних кривих для захисту інформації на практиці.

Література:

1. Карпінський М.П., Гіжицкі М., Якименко І.З. Оцінка продуктивності та стійкості до часового аналізу алгоритмів експоненціювання точки еліптичної кривої // Вісник Хмельницького національного університету. – 2006. – № 5. – С. 23-30.

2. IEEE P1363 / D8(Draft Version 8). Standard Specifications for Public Key Cryptography.

Автори:

Якименко Ігор Зіновійович, аспірант кафедри Безпеки інформаційних технологій, Тернопільського національного економічного університету, e-mail:iyakymenko@mail.ru

Хомінчук Арсен Андрійович, студент Тернопільського національного економічного університету, e-mail: arsenhom@gmail.com

Драбик Наталія Романівна, студентка Тернопільського національного економічного університету, e-mail:Natali_tern@yahoo.com