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

Утверждение 1. На кривой Эдвардса порядка 4n не существует точек деления на 2 

для точек < Р > максимального порядка и точек F четвертого порядка, и существуют по 

две точки деления – для всех других точек кривой. 

Пример.  Рассмотрим  кривые  Эдвардса  с  модулем  р=19,  для  которого  выполняются 

оба  условия  теоремы  2.  Три  суперсингулярные  кривые  с  порядком  N

E

=

р+1=20  сразу 

определяются при значениях d∈{ –1, 2, 10 = 2

-1

}. Если исключить также кривые с порядком, 

кратным 8 (для них 1 – d – квадратичный вычет), останутся лишь две кривые с параметрами   
d 

= 8 и d

–1

= 12, которые дают пару кривых кручения с порядками N

E

соответственно 28 и 12 . 

Точки первой из этих кривых  x

2 

+ y

2

 = 1 + 8x

2

y

2

располагаются 

на  четырех  окружностях:  4  базовых  точки  на  единичной 

окружности  (на  осях  х  и  у)  и  по  8  точек  (семейства  точек)  на 
окружностях с радиусами 

  , 

и 

.  

Формально  циклическую  группу  точек  кривой  kP  можно 

расположить  на  окружности  в  порядке  нарастания  по  часовой 

стрелке    скалярного  числа  k  = 0, 1, 2,…, N

E 

– 

1.  Для  нашего 

примера  такая  точечная  окружность  представлена  на  рис.1. 

Назовем этот график колесом точек. 

Знание  приблизительно  1/8  части  всех  точек  позволяет 

реконструировать  все  другие  точки  кривой.  А  именно:  при  известных  4-х  точках  (причем 

одна из них базовая –F) мы без вычислений получили координаты всех 28 точек kP кривой 

Эдвардса.  Разумеется,  этот  метод  годится  для  кривой  любого  порядка,  при  этом 

предвычисления состоят в расчете координат точек kP для k = 2,3,…,(n + 1)/2. Это составляет 

практически 1/8-ю часть порядка кривой. 

Утверждение 2. Для кривой Эдвардса порядка 4n любое семейство из 8 точек (±x

1

, 

±y

1

), (

±y

1

, 

±x

1

), 

лежащих  на  одной  окружности,  содержит  4  точки  порядка  4n, 2 точки 

порядка 2n  и 2 точки порядка n. 

Заметим,  что  существует  лишь  2  точки  максимального  порядка,  порождающие 

известный генератор G подгруппы точек простого порядка n – это точки Р и Р*, для которых 
2

Р*=2Р,  G  =4Р.  Все  четные  точки  колеса  рис.2  при  переходе  к  порождающей  точке  Р* 

сохраняют свои координаты, а нечетные Р*, 3Р*, 5Р*… меняют знаки обеих координат. 

Література 

1.  Edwards  H.M.  A  normal  form  for  elliptic  curves.  Bulletin  of  the  American  Mathematical 

Society, Volume 44, Number 3, July 2007, Pages 393-422. 

2. 

Бессалов  А.В.  Деление  точки  на  два  для  кривой  Эдвардса  над  простым  полем. 

Прикладная радиоэлектроника, 2013, Том 12, №2  С. 278-279. 

3. 

Бессалов  А.В.,  Телиженко  А.Б.  Криптосистемы  на  эллиптических  кривых:  Учеб. 

пособие. – К.: ІВЦ «Політехніка», 2004. – 224с. 
 

А.В.  Бессалов,  О.В.  Циганкова  Властивість  точок  високих  порядків  кривої 

Едвардса 

Запропоновано модифікацію закону додавання точок на кривій Едвардса над простим 

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

парі  кривих  кручення.  Запропоновано  алгоритм  реконструкції  усіх  невідомих  точок  kP 

кривої Едвардса, якщо лише 1/8 частина точок відома. 

Ключові слова: еліптична крива, крива Едвардса, порядок кривої, порядок точці. 
Updating of the addition law of Edwards's curve points over a simple field is offered. 3 

theorems of properties of the big order point-coordinates and degenerate pair of twisted curves are 
proved. The algorithm of reconstruction of all unknown points kP of Edwardscurve is offered, if 
only at 1/8 parts of points is known. 

Key words: elliptic curve, Edwards curve, curve order, points order. 

31 

УДК 691.321 

ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ГЕНЕРАЦІЇ БАЗОВОЇ ТОЧКИ НА 

КРИВІЙ ЕДВАРДСА 

*

Л.В. Ковальчук, д.т.н; *А.В. Бессалов, д.т.н; *О.Ю. Беспалов 

*

Фізико-технічний інститут НТУУ «КПІ» 

e-mail: alexb5dh@gmail.com 

У  сучасній  асиметричній  криптології  центральне  місце  посідають  криптосистеми, 

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

Едвардса  [1],  які  мають  ряд  переваг  у  порівнянні  з  класичними  еліптичними  кривими. 

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

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

обміну ключами та цифрового підпису. 

В основі стійкості всіх криптосистем на еліптичних кривих лежить так звана задача 

дискретного  логарифмування.  Тому  для  побудови  будь-якої  криптосистеми  у  першу  чергу 

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

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

У доповіді наведено три різних алгоритми генерації базової точки кривої. Перший з 

них є класичним. Він використовується, зокрема, у алгоритмі ДСТУ 4145-2002 [2]. Другий 

алгоритм  був  кілька  місяців  тому  запропонований  одним  з  авторів  цієї  доповіді.  Він 

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

[3]. Третій алгоритм запропоновано авторами цієї доповіді. Він базується на доведеній ними 

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

Також наведено порівняльний аналіз простоти реалізації та швидкодії цих алгоритмів, 

як у найгіршому випадку, так і в середньому. 

Крім  цього,  наведено  критерії  подільності  точки  кривої  Едвардса  на  довільне 

натуральне число, а також алгоритми ділення точки на довільне натуральне число. 

Література 

1.  Edwards, H.M.: A normal form for elliptic curves / Bulletin of the AMS - 44(3) – 2007 - P. 

393–422 

2. 

ДЕРЖАВНИЙ СТАНДАРТ УКРАЇНИ ДСТУ 4145 – 2002 

Інформаційні  технології.  Криптографічний  захист  інформації.  Цифровий  підпис,  що 

ґрунтується на еліптичних кривих. Формування та перевірка. 

3. 

Бессалов  А.В.  Взаимосвязь  семейств  точек  больших  порядков  кривой  Эдвардса  над 

простым полем / А.В. Бессалов, О.В. Цыганкова // Захист інформації - Том 17, №1, січень-

березень 2015 - C.73-80. 

Л.В.  Ковальчук,  А.В.  Бессалов,  О.Ю.  Беспалов  Порівняльний  аналіз  алгоритмів 

генерації базової точки на кривій Едвардса 

У доповіді наведено три різних алгоритми генерації базової точки кривої. Перший з 

них  є  класичним.  Він  використовується,  зокрема,  у  алгоритмі  ДСТУ  4145-2002.  Другий 

алгоритм  був  кілька  місяців  тому  запропонований  одним  з  авторів  цієї  доповіді.  Він 

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

два. Третій алгоритм запропоновано авторами цієї доповіді. Він базується на доведеній ними 

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

Наведено порівняльний аналіз простоти реалізації та швидкодії цих алгоритмів, як у 

найгіршому випадку, так і в середньому. 

Ключові слова: крива Едвардса, алгоритми генерації базової точки. 
 
 

32 

L.V. Kovalchuk, A.V. Bessalov, A.U. Bespalov  Comparative analysis of algorithms for 

base point generation on Edwards curve 

Three algorithms are proposer for base point generation on elliptic curve. The first one is 

classical. It is used, for example, in DSTU 4145-2002. The second one was proposed by one of the 
authors a few months ago. It is based on his theorem about necessary and sufficient conditions of 
divisibility of point by two. The third one is proposed by the authors of this report and is based on 
the theorem about necessary and sufficient conditions of divisibility of point by four. 

Comparative analysis of these algorithms is proposed. 
Keywords: Edwards curve, base point generation algorithms. 

33 

УДК 621.391:519.2 

ПОБУДОВА ВЕРХНІХ ОЦІНОК СЕРЕДНІХ ІМОВІРНОСТЕЙ 

ЦІЛОЧИСЕЛЬНИХ ДИФЕРЕНЦІАЛІВ КОМПОЗИЦІЙ КЛЮЧОВОГО СУМАТОРА, 

БЛОКУ ПІДСТАНОВКИ ТА ЛІНІЙНОГО (НАД ДЕЯКИМ КІЛЬЦЕМ) ОПЕРАТОРА 

*Л.В. Ковальчук, д-р техн. наук, доц.; **Н.В. Кучинська 

*

Фізико-технічний інститут НТУУ «КПІ» 

**

Інститут спеціального зв’язку та захисту інформації НТУУ «КПІ» 

e-mail: n.kuchisnka@gmail.com 

Більшість  сучасних  блокових  шифрів  (AES,  "Калина")  містять  у  своїй  структурі 

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

здебільшого над полем 

2

F  

або його розширенням) оператора. Задача оцінювання стійкості 

таких шифрів  до  лінійного,  білінійного  та  різних  модифікацій  різницевого криптоаналізу 
[1-

3]  або  зводиться  до  задачі  побудови  верхніх  оцінок  середніх  імовірностей  таких 

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

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

багатьох  інших  роботах,  у  тому  числі  і  в  тих  випадках,  коли  імовірність  побітових 

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

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

(побітові) диференціали. Достатньо повний перелік посилань та обґрунтування вибору саме 

цілочисельних диференціалів можна знайти у [4]. 

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

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

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

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

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

додавання. 

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

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

n

2

, блок підстановки є довільним, 

а лінійний оператор описується матрицею, обернена до якої містить лише нулі та одиниці. Ці 

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

попередніх  роботах  ([5]  та  посилання  в  ній)  .  Також  отримано,  строго  обгрунтовані, 

параметри,  що  залежать  від  s-блоків  та  характеризують  дані  оцінки,  побудовано 

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

різницеві  властивості  раундових  функцій  блокових  алгоритмів  шифрування,  що  мають 

відповідну структуру. 

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

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

суматора, блока підстановки та оператора перестановки у випадку, коли лінійний оператор є 

довільним (зокрема, має довільну обернену матрицю або коли цей оператор є лінійним над 

деяким полем характеристики два). 

Література 
1. 

Ковальчук  Л.  Обобщёные  марковские  шифры:  оценка  практической  стойкости  к 

методу  дифференциального  криптоанализа  //  Труды  Пятой  Общероссийской  научной 

Конференции “Математика и безопасность информационных технологий” – (МаБИТ-06), 25-

27 октября 2006. – С. 595-599.  

2. 

Олексійчук  А.Н.  Криптографічні  параметри  вузлів  заміни,  що  характеризують 

стійкість  ГОСТ-подібних  блокових  шифрів  відносно  методів  лінійного  та  різницевого 

криптоаналізу  /  Олексійчук  А.Н.,  Ковальчук  Л.В.,  Пальченко  С.В.//  Захист  інформації.  – 
2007. – 

№ 2. – С. 12 – 23  

34 

3. 

Алексейчук  А.  Оценки  практической  стойкости  блочного  шифра  «Калина» 

относительно разностного, линейного билинейного методов криптоанализа. / Алексейчук А., 

Ковальчук  Л.,  Шевцов  А.,  Скрыпник  Л.//Труды  Седьмой  Общероссийской  научной 

Конференции “Математика и безопасность информационных технологий” – (МаБИТ-08), 30 

октября – 2 ноября 2008. – С. 15-20.  

4. S. Cotini Security of the RC6

TM

 Block Cipher,/ S. Cotini, R.L. Riverst, M.J.B. Robshaw, 

Y. Lisa Yin 

// Режим доступу: http//www.rsasecurity.com/rsalabs/rc6/. 

5. 

Ковальчук  Л.  Побудова  верхніх  оцінок  середніх  імовірностей  цілочисельних 

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

оператора, що має блокову структуру. /Ковальчук Л., Кучинська Н., Бездітний В. //Науково-

технічний  збірник  «Правове,  нормативне  та  метрологічне  забезпечення  системи  захисту 

інформації в Україні» – 2014, – №28, C.47 – 52. 

Л.В.  Ковальчук,  Н.В.  Кучинська  Побудова  верхніх  оцінок  середніх  імовірностей 

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

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

Вперше  отримано  верхні  оцінки  середніх  імовірностей  цілочисельних  диференціалів 

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

деяким  кільцем)  оператора,  а  також  визначено  параметри  s-блоків,  від  яких  залежать  дані 

оцінки, та умови, що забезпечують якомога менші значення цих оцінок. Отримані результати 

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

шифрування, а, отже, і всього алгоритму. 

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

шифри, раундова функція, вузли заміни, s-блоки. 

L.V. Kovalchuk, N.V. Kuchinska The upper bounds  of the  integer  differentials average 

probabilities  for  composition  of the modular  key  adder,  substitution blocks  and the block-
structured linear operator  

In this work, the upper bounds are obtained for the integer differentials average probability of 

maps which are compositions of the key adder, substitution blocks, and the linear (over some ring) 
operator.  The  parameters  of  s-blocks,  on which these  bounds are  depended,  are  defined  and 
conditions, to ensure the least possible values of these parameters, are given. Obtained results allow 
us to analyze the  differential  properties of  the round function  of  block  encryption algorithm  and 
therefore the differential properties of the whole block encryption algorithm. 

Keywords:  differential  cryptanalysis,  integer  differential  cryptanalysis,  block cipher, block 

encryption algorithms, round function, s-block. 

35