Файл: 2015.05.26 - Матеріали ХVІ Міжнародної науково-практичної конференції «Безпека інформації в інформаційно-телекомунікаційних системах».pdf

УДК 681.3.06:006.354 

ГЕНЕРАЦІЯ S-БЛОКІВ З ПОКРАЩЕНИМИ КРИПТОГРАФІЧНИМИ 

ВЛАСТИВОСТЯМИ 

*

М.Ю.Родінко,

**

Р.В. Олійников, д-р техн. наук, доц.;  

***

О.В.Казимиров, канд. техн. наук 

*

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

**

Приватнеакціонернетовариство «Інститутінформаційнихтехнологій» 

***

EVRYNorgeAS 

e-mail: m.rodinko@gmail.com 

Застосування  підстановок  з  оптимальними  криптографічними  показниками  дозволяє 

поліпшити  характеристики  симетричних  перетворень,  що  дає  можливість  зменшити  число 

ітерацій  алгоритму.Однак  генерація  оптимальних  S-блоків  є  обчислювально  складною 

задачею,  що  є  неприйнятним,  наприклад,  при  використанні  S-блоків  в  якості  ключових 

елементів. Таким чином, актуальною є задача оптимізації методів генерації S-блоків. 

До  сучасних  критеріїв  відбору  S-блоків[1-3]  відносяться:  максимум  в  таблиці 

розподілу  диференціальних  різниць,  максимумв  таблиці  лінійних  апроксимацій, 

алгебраїчний імунітет, мінімальна степінь S-блока та відсутність нерухомих точок

. 

Метод пошуку S-блоків, що розглядається, в загальному випадку складається з двох 

етапів:генерації  псевдовипадкової  підстановки  та  її  перевірки  на  відповідність  заявленим 

критеріям. 

Для  генерації  підстановок  був  обраний  алгоритм  [2],  який  передбачає  формування 

перестановки на основі векторної булевої функції F (x) = x

-1

та подальший обмін місцями N 

значень перестановки. 

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

застосування в ході перевірки підстановки можна істотно скоротити час розрахунків. 

Нехай  задано  m  критеріїв  відбору  підстановок.  Тоді  число  можливих  комбінацій  m 

критеріїв, які задають порядок їх застосування, дорівнює m!. 

Нехай –  множина  усіх  таких  комбінацій,  а

  –  i-

а  комбінація 

критеріїв наступного виду: 

,         (1) 

де   – j-ий критерій відбору у цій комбінації. 

Введемо  деяку  функціюT( ),  значення  якої  представляє  собою  час  генераціїоднієї 

підстановки, що задовольняє усімmкритеріям, із використанням комбінації критеріїв . Тоді 

задача  мінімізації  часу  перевірки  підстановки  на  відповідністьmкритеріям  зводиться  до 

знаходженняt

min

: 

.   (2) 

У ході експериментальних досліджень для підстановок степеня n = 2

8

були визначені 

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

- 

 – 

процент підстановок, що задовольняють критерію ; 

- 

 – 

час перевірки однієї підстановки на відповідність критерію . 

Використовуючи  введені  фактори,  отримуємо  наступне  співвідношення  для 

знаходженняT( ): 

де 

16 

Нижче  наведено  приклад  застосування  цього  підходу  для  генерації  підстановок 

зачотирманаступними критеріями (m = 4): 

1. 

– 

максимум таблиці диференціалів, що дорівнює 8. 

2. 

 – 

абсолютний максимум таблиці лінійних апроксимацій, що дорівнює 26. 

3. 

 – 

мінімальна степінь булевої функції, що дорівнює 7. 

4. 

 – 

алгебраїчний імунітет, що дорівнює 3. 

Таким чином, потужність множини комбінацій критеріїв   = 24. 

Експериментальні  значення,  отримані  для  факторівpіt  для  чотирьох  критеріїв, 

представлені в табл. 1. 

Далі за формулою (3) були розраховані значення функції  для комбінацій критеріїв 

ізнайдено мінімальне значенняt

min

= 0,0540755 при  

 = 

. 

Табл. 1. – Значення факторів для чотирьох критеріїв 

Критерій 

Фактор p, %  Фактор t, сек 

70 

0,000169 

14 

0,001655 

99,6 

0,000016 

44,5 

0,006698 

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

T

експер

для усіх комбінацій критеріїв. 

На рис. 1 представлені графіки функційТ (суцільна крива) и T

експер

(пунктирна крива). 

Рис. 1. – Графіки функцій Т и T

експер

Представлений  метод  дозволив  згенерувати  оптимальні  підстановки,  що  мають 

нелінійність  104  та  описуються  перевизначеною  системою  рівнянь  3-ої  степені  на 

персональній ЕОМ без використання розподілених обчислень. 

Таким  чином,  запропоновано  підхід  до  оптимізації  методу  генерації  S-блоків, 

заснований  на  мінімізації  часу  перевірки  підстановки  на  відповідність  набору  критеріїв. 

Експерименти показали, що при застосуванні оптимального порядку критеріїв часперевірки 
S-

блоків зменшується приблизно в 5 разів. 

Література 

1. 

Олейников  Р.В.  Выбор  S-блоков  для  симметричных  криптографических  алгоритмов 

на основе анализа алгебраических свойств / Р.В. Олейников, А. В. Казимиров // Вісн. Харк. 

нац. 

ун-ту. 

Сер. 

Математичнемоделювання. 

Інформаційнітехнології. 

Автоматизованісистемиуправління. − Х., 2010. – № 925. – С. 79–86. 

2. 

Казимиров  О.В.Методи  та  засобигенераціїнелінійнихвузлівзаміни  для  симетричних 

крипто  алгоритмів  /  О.В.  Казимиров  //  Дисертація  на  здобуттянауковогоступеня  кандидата 

технічних  наук  по спеціальності  05.13.21  –  системизахистуінформації.  ХНУРЕ.  –  Харків. – 
2014. 

3.  Nyberg K.  “Provable” security against differential and linear cryptanalysis / K. Nyberg // 

Fast Software Encryption. – V. 7549. – 2012. – pp. 1-8. 

17 

М.Ю.  Родінко,  Р.В.  Олійников,  О.В.  Казимиров.  Генерація  S-блоків  з 

покращеними криптографічними властивостями. 

У  доповіді  представлений  оптимізований  метод  генерації  S-блоків,  заснований  на 

мінімізації часу перевірки підстановок на відповідність множині критеріїв. Запропонований 

метод  дозволяє  підвищити  швидкість  генерації  підстановок  у  декілька  разів  та  отримати 

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

Ключові  слова:  S-блок,  криптоаналіз,  таблиця  розподілу  різниць,  таблиця  лінійних 

апроксимацій, алгебраїчний імунітет. 

 
M.Yu.  Rodinko,  R.V.Oliynykov,  O.V.  Kazymyrov.Generation of S-boxes with improved 

cryptographic properties. 

It is presented an optimized method of generation of S-boxes based on minimizing time of 

testing substitutions on the corresponding set of criteria. The optimized method allows speeding up 
the generation of substitutions up to several times and getting optimal substitutions without using 
distributed calculations. 

Key words:  S-box,  cryptanalysis,  distribution table of differences, linear approximation 

table, algebraic immunity. 

18 

УДК 004.056 

АЛГЕБРО-ГЕОМЕТРИЧНИЙ МЕТОД ОБЧИСЛЕННЯ  

КІЛЬКОСТІ ТОЧОК НА ЕЛІПТИЧНІЙ КРИВІЙ:  

АНАЛІЗ ТА ПЕРСПЕКТИВИ ЗАСТОСУВАННЯ В УКРАЇНІ 

І.Д. Горбенко, д-р техн. наук, проф.; **Р.С. Ганзя, аспірант 

*

Харківський національний університет ім. В.Н. Каразіна 

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

e-mail: 

roman.ganzya@gmail.com

На  даний  момент  в  Україні  надзвичайно  широко  використовуються  такі  електронні 

довірчі послуги як електронний цифровий підпис, електронна печатка та мітка часу. Суттєве 

місце  для  реалізації  електронних  довірчих  послуг  в  Україні  займає  асиметрична 

криптографія,  та  криптографія  на  еліптичних  кривих,  як  її  складова,  проте  враховуючий 

швидкий  розвиток  квантових  технологій  та  існування  квантового  алгоритму  Шора,  який 

здатен  вирішити  проблеми  факторизації  та  розв'язання  дискретного  логарифмічного 

рівняння  із  поліноміальною  складністю,  виникає  ситуація,  коли  сучасні  асиметричні 

криптосистеми можуть бути скомпрометовані. 

Одним із шляхів вирішення даної проблеми є збільшення розмірів загальносистемних 

параметрів  криптоперетворень.  Звичайно  таке  збільшення  не  дасть  підвищення  стійкості 

проти квантового криптоаналізу, проте для проведення такого аналізу необхідний квантовий 

комп'ютер  з  великою  кількістю  кубітів,  а  як  показує  аналіз  перспектива  появи  такого 

комп'ютера  в  найближчі  5-10  років  неможлива  [1].  Також  перспективним  напрямком 

протидії є дослідження постквантових криптосистем. 

Також  враховуючи  те,  що  в  Україні  були  прийняті  нові  національні  стандарти 

симетричного  шифрування  та  геш-функції  з  розмірами  блоку  повідомлення  (виходу  геш-

функції) та ключа до 512 бітів, то для досягнення однакового рівня безпеки при використанні 

системи  типу  "електронний  конверт"  необхідно  використання  асиметричних 

криптоперетворень  (електронного  цифрового  підпису  та  направленого  шифрування)  з 

розмірами загальних параметрів не менше 1024 бітів. Національний стандарт електронного 

цифрового підпису (ДСТУ 4145-2002) має загальносистемні параметри з розмірами до 431 

біта. Тому задача генерування загальносистемних параметрів великих розмірів (1024 біта та 

більше) є актуальною. 

На  момент  створення  національного  стандарту  ДСТУ-4145  найбільш  придатними 

методами  формування  загальних  параметрів  у  групі  точок  еліптичних  кривих  над  полем 

)

2

(

m

F

був  метод  Сатоха  та  метод  комплексного  множення  [2].  Інший  метод,  який  дуже 

сильно пов'язаний з методом Сатоха базується на алгебро-геометричному методі (AGM) та 

був  запропонований  Местре  [3],  даний  метод  може  бути  надзвичайно  ефективним. 
Обчислювальна складність метода AGM, що був запропонований Меcтре складає 

)

(

3

ξ

+

n

O

. 

Запропонований метод Сатоха-Ск'єрна-Тагучі (SST) має  складність 

)

(

5

.

2

ξ

+

n

O

, проте такий 

метод  вимагає  передобчислень  [3].  Для  обчислення  кількості  точок  на  еліптичній  кривій 

алгебро-геометричний  метод  та  інші  p-адичні  алгоритми  використовують  властивості 

ендоморфізму Фробеніуса. Обчислення виконується у такі етапи: 

1) 

Підняття циклу ізогінеї та коефіцієнтів кривої; 

2) 

Проведення нормування коефіцієнтів; 

3) 

Обчислення  сліду  ендоморфізму  Фробеніуса,  на  базі  якого  визначається  порядок 

кривої. 

У [2] можна детально ознайомитись з основними кроками AGM алгоритму. Першою 

основною модифікацією AGM стала заміна другого циклу обчислень AGM-послідовності, її 

можна замінити на обчислення однієї алгебро-геометричної ітерації та обчислення норми в 

скінченому полі. Тобто  

19 

)

2

(mod

)

/

(

1

0

/

N

Q

Q

a

a

N

t

p

p

≡

. 

(1) 

Для  обчислення  норми  можна  використати  декілька  алгоритмів:  аналітичний 

(запропононований Сатохом, Ск'єрною та Тагучі), а також метод на основі результанта. Було 

запропоновано використати швидкий алгоритм обчислення найбільшого спільного дільника, 

який показав Моенк [3]. Для аналізу ефективності обчислення норми через результант нами 

було  розроблено  програмний  засіб  на  мові  C ++  з  використанням  бібліотеки  NTL  Так  для 

еліптичної  кривої  з  розміром  базової  точки  1031  біт  з  використанням  ще  одного  циклу 

обчислення  AGM-послідовності  (як  запропонував  Местре)  необхідно  446  секунд  для 

нормування, а використовуючи результант для обчислення норми 160 с. 

Таким чином на даний момент існують загрози для асиметричної криптографії. Такі 

загрози  пов'язані  з  квантовим  алгоритмом  Шора.  Для  підвищення  стійкості  сучасних 

асиметричних  алгоритмів  можна  збільшити  розмір  базової  точки.  Для  цього  можуть 

використовуватися  ефективні  методи  побудови  загальносистемних  параметрів,  наприклад 

алгебро-геометричний  метод  та  його  модифікації.  Для  побудови  ефективних  алгоритмів 

генерування  загальносистемних  параметрів  для  еліптичних  кривих  важливим  є  процес 

вибору алгоритмів нормування. Крок підняття еліптичних кривих неможливо розпаралелити 

при  його  обчисленні,  тому  що  даний  крок  є  рекурсивним.  Крок  нормування  можна 

розпаралелити, при виборі відповідного алгоритму нормування. 

Література 

1) 

Ганзя,  Р.С.  Аналіз  можливостей  квантових  комп’ютерів  та  квантових 

обчислень для криптоаналізу сучасних криптосистем / Р.С. Ганзя, Ю.І. Горбенко // Харків: 

«Восточно - Европейский журнал передових технологий». –2014. – Том 6 №1(67). – 8-15 с. 

2) 

Gaudry, P. A comparison and a combination of SST and AGM algorithms for 

counting points of elliptic curves in characteristic 2 / P. Gaudry // ASIACRYPT 2002. 8th 
International Conference on the Theory and Application of Cryptology and Information Security 
Queenstown - New Zealand: Springer, 2002 – P.311-327. 

3) 

Cohen, H. Elliptic and Hyperelliptic Curve Cryptography [Text]: handbook / H. 

Cohen, G. Frey – NW.: Chapman & Hall/CRC, 2006. - 807 p. 

І.Д.  Горбенко,  Р.С.  Ганзя  Алгебро-геометричний  метод  обчислення  кількості 

точок на еліптичній кривій: аналіз та перспективи застосування в Україні 

В  роботі  проведено  аналіз  методів  генерування  загальносистемних  параметрів  для 

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

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

використання  алгебро-геометричного  методу  для  національних  криптоалгоритмів,  а  також 

показана  ефективність    обчислення  норми  через  результант.  На  практиці  було  розроблено 

програмний засіб на мові C ++ з використанням бібліотеки  NTL. Програмний засіб в змозі 

побудувати загальносистемні параметри для еліптичної кривої з розміром базової точки 1031 

біт для криптосистеми відповідно до національного стандарту. 

Ключові  слова:  електронний  цифровий  підпис,  алгебро-геометричний  метод, 

кількість точок. 

I.D. Gorbenko, R.S. Ganzya Arithmetic–geometric  mean for  counting points of elliptic 

curve: analysis and prospects of apllication in Ukraine

This work shows analysis  of  methods of generating general set of  parameters for elliptic 

curves. This work also shows an actuality of generating general set of parameters of large sizes for 
national security cryptosystem. The possibility of using  arithmetic–geometric mean  for national 
algorithms  and shows the effectiveness of counting points  by resultants. On practice we have 
developed a software tool on the C++ language using library NTL. Software is able to build elliptic 
curves with the size of the base point of 1031 bits for crypto transformation according to national 
digital signature standard. 

Keywords: digital signature, arithmetic–geometric mean (AGM), counting points. 

20