Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння

Представлено результати аналізу аналітичних виразів трансформації несуперсингулярних еліптичних кривих у канонічній формі для криптографічних цілей. Отримано нові результати оцінки верхньої границі числа ізоморфних трансформацій еліптичної кривої в канонічній формі над кінцевим полем Галуа. Так, для...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автори:	Бессалов, А.В., Чевардін, В.Є.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2012
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/50201
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння / А.В. Бессалов, В.Є. Чевардін // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 119-123. — Бібліогр.: 3 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-50201
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-502012025-02-09T15:28:51Z Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння Число изоморфизмов эллиптической кривой при трансформациях канонической формы уравнения The number of isomorphism elliptic curve during the transformation of the canonical form of the equation Бессалов, А.В. Чевардін, В.Є. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Представлено результати аналізу аналітичних виразів трансформації несуперсингулярних еліптичних кривих у канонічній формі для криптографічних цілей. Отримано нові результати оцінки верхньої границі числа ізоморфних трансформацій еліптичної кривої в канонічній формі над кінцевим полем Галуа. Так, для поля характеристики р верхня межа числа ізоморфізмів еліптичної кривої при трансформаціях із канонічної в канонічну форму зростає пропорційно р. Для трансформації еліптичної кривої над полем характеристики р із канонічної в нормальну форму верхня границя числа ізоморфізмів зростає пропорційно р4. Використання повної множини трансформацій базової еліптичної кривої дозволяє збільшити потужність простору можливих параметрів криптосистем на еліптичних кривих, а також використовувати їх в якості додаткового джерела ентропії. Застосування отриманих результатів для криптографічних генераторів випадкових чисел може дозволити скоротити довжину модуля поля Галуа. Представлены результаты анализа аналитических выражений трансформации несуперсингулярных эллиптических кривых в канонической форме для криптографических целей. Получены новые результаты оценки верхней границы числа изоморфных трансформаций эллиптической кривой кривых в канонической форме над конечным полем Галуа. Так, для поля характеристики р верхняя граница числа изоморфизмов эллиптической кривой при трансформациях из канонической в каноническую форму растет пропорционально р. Для трансформаций эллиптической кривой над полем характеристики р из канонической в нормальную форму верхняя граница числа изоморфизмов растет пропорционально р4. Использование полного множества трансформаций базовой эллиптической кривой позволяет значительно увеличить мощность пространства возможных параметров криптосистем на эллиптических кривых, а также использовать их в качестве дополнительного источника энтропии. Применение полученных результатов для криптографических генераторов случайных чисел может позволить сократить длину модуля поля Галуа. The results of analyze of analytic expressions for transformation of nonsupersingular elliptic curves in the canonical form for cryptographic purposes are shown. New results of the estimate of an upper bound estimate of the number of isomorphic transformations of elliptic curve of the curves in the canonical form over finite Galois field were obtained. For a field with characteristic p from canonical to normal form, an upper bound of the number of isomorphisms increases proportionally to p4. The using of full set of base elliptic curve transformations gives possibility to increase cardinality of set parameters of cryptosystems on elliptic curves and also use it as additional entropy source. Implementattion of these results in cryptographic random bit generators can allow to cut size of Galois field module. 2012 Article Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння / А.В. Бессалов, В.Є. Чевардін // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 119-123. — Бібліогр.: 3 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50201 512.624.95 + 517.772 uk Системні дослідження та інформаційні технології application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
spellingShingle	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Нові методи в системному аналізі, інформатиці та теорії прийняття рішень Бессалов, А.В. Чевардін, В.Є. Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння Системні дослідження та інформаційні технології
description	Представлено результати аналізу аналітичних виразів трансформації несуперсингулярних еліптичних кривих у канонічній формі для криптографічних цілей. Отримано нові результати оцінки верхньої границі числа ізоморфних трансформацій еліптичної кривої в канонічній формі над кінцевим полем Галуа. Так, для поля характеристики р верхня межа числа ізоморфізмів еліптичної кривої при трансформаціях із канонічної в канонічну форму зростає пропорційно р. Для трансформації еліптичної кривої над полем характеристики р із канонічної в нормальну форму верхня границя числа ізоморфізмів зростає пропорційно р4. Використання повної множини трансформацій базової еліптичної кривої дозволяє збільшити потужність простору можливих параметрів криптосистем на еліптичних кривих, а також використовувати їх в якості додаткового джерела ентропії. Застосування отриманих результатів для криптографічних генераторів випадкових чисел може дозволити скоротити довжину модуля поля Галуа.
format	Article
author	Бессалов, А.В. Чевардін, В.Є.
author_facet	Бессалов, А.В. Чевардін, В.Є.
author_sort	Бессалов, А.В.
title	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння
title_short	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння
title_full	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння
title_fullStr	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння
title_full_unstemmed	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння
title_sort	число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2012
topic_facet	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
url	https://nasplib.isofts.kiev.ua/handle/123456789/50201
citation_txt	Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння / А.В. Бессалов, В.Є. Чевардін // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 119-123. — Бібліогр.: 3 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT bessalovav čisloízomorfízmívelíptičnoíkrivoípídčastransformacíjkanoníčnoíformirívnânnâ AT čevardínvê čisloízomorfízmívelíptičnoíkrivoípídčastransformacíjkanoníčnoíformirívnânnâ AT bessalovav čisloizomorfizmovélliptičeskojkrivojpritransformaciâhkanoničeskojformyuravneniâ AT čevardínvê čisloizomorfizmovélliptičeskojkrivojpritransformaciâhkanoničeskojformyuravneniâ AT bessalovav thenumberofisomorphismellipticcurveduringthetransformationofthecanonicalformoftheequation AT čevardínvê thenumberofisomorphismellipticcurveduringthetransformationofthecanonicalformoftheequation
first_indexed	2025-11-27T10:01:29Z
last_indexed	2025-11-27T10:01:29Z
_version_	1849937307659927552
fulltext	© А.В. Бессалов, В.Є. Чевардін, 2012 Системні дослідження та інформаційні технології, 2012, № 4 119 УДК 512.624.95 + 517.772 ЧИСЛО ІЗОМОРФІЗМІВ ЕЛІПТИЧНОЇ КРИВОЇ ПІД ЧАС ТРАНСФОРМАЦІЙ КАНОНІЧНОЇ ФОРМИ РІВНЯННЯ А.В. БЕССАЛОВ, В.Є. ЧЕВАРДІН Представлено результати аналізу аналітичних виразів трансформації несупер- сингулярних еліптичних кривих у канонічній формі для криптографічних ці- лей. Отримано нові результати оцінки верхньої границі числа ізоморфних трансформацій еліптичної кривої в канонічній формі над кінцевим полем Га- луа. Так, для поля характеристики р верхня межа числа ізоморфізмів еліптичної кривої при трансформаціях із канонічної в канонічну форму зростає пропор- ційно р. Для трансформації еліптичної кривої над полем характеристики р із канонічної в нормальну форму верхня границя числа ізоморфізмів зростає пропорційно р4. Використання повної множини трансформацій базової еліп- тичної кривої дозволяє збільшити потужність простору можливих параметрів криптосистем на еліптичних кривих, а також використовувати їх в якості до- даткового джерела ентропії. Застосування отриманих результатів для крипто- графічних генераторів випадкових чисел може дозволити скоротити довжину модуля поля Галуа. ВСТУП Актуальним науковим завданням є розробка нових аналітичних виразів, які дозволяють точніше оцінювати параметри та властивості криптографічних примітивів на основі перетворень у групах точок еліптичних кривих. Це зу- мовлено останніми науковими результатами, які отримані поєднанням вели- ких обчислювальних потужностей, таких як: декодування ДНК людини, ви- рішення задачі дискретного логарифмування в простому полі з розрядністю чисел 1024 біти і низки інших наукових проблем. Криптоперетворення в групі точок еліптичної кривої дозволяють задовольнити зростаючі вимоги щодо стійкос- ті та швидкодії сучасних систем захисту інформації. Відомо, що поряд зі спеціальними задачами еліптичної криптографії виникає необхідність переходу до ізоморфних кривих, які зберігають струк- туру групи точок під час трансформації їх координат. При цьому слід визна- чити точне число ізоморфізмів або дати хоча б оцінку цього числа. У цій роботі вказана задача вирішена для часткового випадку каноніч- ної форми базової кривої. Мета роботи — аналіз можливих трансформацій базової несуперсин- гулярної еліптичної кривої та отримання аналітичних виразів для оцінки граничних значень множини ізоморфних трансформацій кривої. ІЗОМОРФНІ ТРАНСФОРМАЦІЇ ЕЛІПТИЧНОЇ КРИВОЇ ТА ОЦІНКА ПОТУЖНОСТІ МНОЖИНИ ІЗОМОРФІЗМІВ ДЛЯ КАНОНІЧНОЇ ФОРМИ ЕЛІПТИЧНОЇ КРИВОЇ Нормальною формою базової кривої над полем pF у визначеннях, що прийняті в [1, 3], називається крива виду: А.В. Бессалов, В.Є. Чевардін ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 120 pk Faaxaxaxyaxyay ∈+++=++ ,64 2 2 3 31 2 , (1) яка також є афінною версією рівняння Вейєрштрасса [2]. Лінійне ізоморфне перетворення координат цієї кривої задається фор- мулами: txsuyuy ++= 23 , rxux += 2 , .}1,..,0{,,,,0 −∈≠ ptsruu (2) При довільних параметрах { tsru ,,, } перетворення отримуємо криву виду: pi FaaxaxaxyayxayE ∈+++=++ ,: 64 2 2 3 31 2 . (3) Необхідно отримати співвідношення, які пов’язують коефіцієнти ia ізоморфної кривої E з коефіцієнтами базової кривої (1). Складові рівняння (1), які отримані на основі формули (2), дорівнюють: ,222 2352242262 stxutyuyxsutxusyuy +++++= ),( 232245 11 rtxsruyruxtuxsuyxuaxya +++++= ),( 23 33 txsuyuaya ++= ,33 32224363 rxruxruxux +++= ),2( 2224 2 2 2 rxruxuaxa ++= ).( 2 44 rxuaxa += Порівнюючи коефіцієнти з (1) та (3), отримаємо: ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎪ ⎨ ⎧ −−−+++= −++−+−= −−+= ++= += .)( ,)23)(2( ,)3( ,)2( ,)2( 62 13 3 2 2 466 6 62 12344 4 62 122 2 6 133 3 6 11 uttaratrarraaau ustrarstrasaaau ussaraau utraaau usaau (4) Тепер рівняння в координатах yx , має вид: +=+++++ 36 13 3 1 526 )2()2( xuytraauyxsauyu −+−+−−++ 234 222 12 4 2()3( rasaauxssarau .)23)( 2 13 3 2 2 46 2 1 trtatararraaxstrarst −−−++++−++− Заміною yuy 3~ = та xux 2~ = це рівняння приводиться до незалежного від параметра u виду: Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння Системні дослідження та інформаційні технології, 2012, № 4 121 +−−++=+++++ 22 12 3 131 2 ~)3(~~)2(~~)2(~ xssaraxytraayxsay +−++−+−+ xstrarstrasaa ~)23)(2( 2 1234 ).( 2 13 3 2 2 46 trtatararraa −−−++++ Помноживши це рівняння на 6u з новою заміною 3~uyY = та ,~ 2uxX = отримаємо нове рівняння: ,64 2 2 3 31 2 aXaXaXYaXYaY +++=++ де ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎪ ⎨ ⎧ −−−+++= −++−+−= −−+= ++= += .)( ,)23)(2( ,)3( ,)2( ,)2( 62 13 3 2 2 466 42 12344 22 122 3 133 11 utatratrarraaa ustrarstrasaaa ussaraa utraaa usaa (5) Рівняння в координатах YX , тотожно рівнянню (1) у координатах yx , , тому ці позначення рівнозначні. Детальний вивід виразів (5) нам знадобився у зв’язку з помилкою, яку припущено в роботі [1]. У рівняннях (4), що наведені в [1], були втрачені співмножники 6u у правих частинах. Тому, співмножники iu відповідних коефіцієнтів з’явилися в лівих частинах рівнянь, а не в правих, як у рівнян- нях (5). Слід зазначити, що ця помилка не є катастрофічною, так як при 0≠u в поле pF , при 3,2≠p завжди існує зворотній елемент 1−= uv . Для базового рівняння (1), яке записане в канонічній формі маємо 321 aaa == , тоді рівняння (5) спрощується: ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎪ ⎨ ⎧ −++= −+= −= = = .)( ,)23( ,)3( ,2 ,2 623 466 42 44 22 2 3 3 1 utrraaa ustraa usra tua usa (6) Нехай 1γ — число ізоморфних кривих, які отримані трансформацією з канонічної форми в канонічну, при цьому 0321 === aaa та, відповідно, 0=== trs . Тоді 6 6 64 4 4 , auaaua == . Число 1γ визначається об’ємом А.В. Бессалов, В.Є. Чевардін ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 122 множин різних пар 64 , aa , які залежать від значень 64 , aa та порядку еле- ментів 64, uu у мультиплікативній групі * pF . Наприклад, при 7=p порядок групи # 6* 7 =F . Елемент ,7mod16 =u елемент ,7mod13 ±=u елемент }4,2,1{4∈u при 1≠u має порядок 3. Це означає, що число ізоморфізмів 11 =γ при 0,0 64 ≠= aa (порушення остан- ньої умови дає сингулярну криву), або 31 =γ при 14 ≠a . Зі збільшенням p число 1γ зростає. Так, при 11=p , 521011 ∗==F , степені елементів 64, uu парні, а самі елементи 1≠u мають порядок 5. Число різних пар елементів 64, uu також дорівнює 5, тому 5 2 1 1 = − = pγ при 11=p . Можна помітити, що пари елементів 64 )(,)( uu ±± пробігають усі значення квадратичних від’ємників у мультиплікативній групі * pF , тому для будь-якого поля верхня границя буде такою: 2 1 1 − ≤ pγ . (7) Звідси видно, що зріст числа ізоморфізмів у канонічній формі кривої лінійний зі збільшенням p. Із рівнянь (6) очевидно, що число ізоморфізмів кривої Е при ненульо- вих параметрах tsr ,, різко зростає. Тут перші 3 параметри кривих лінійно незалежні з розділеними змінними ,, sr и ,t що дозволяє знайти верхню границю числа ізоморфізмів під час трансформації з канонічної форми у нормальну: .)1( 2 1 3 2 pp −≤γ (8) Величина 2γ зростає вже пропорційно 4-му ступеню порядку p поля. Вже при 7=p можна отримати до 102973 3 =∗ кривих. Із (2) випливає, що перетворення точки в точку ізоморфної кривої має обчислювальну складність не більш п’яти множень у кінцевому полі (та не більш чотирьох множень для канонічної форми). Також використання для задач криптографії ізоморфних кривих у нормальній формі з оцінкою (8) для числа ізоморфізмів дозволяє під час фіксації цього числа приблизно в чо- тири рази скоротити довжину модуля поля та відповідно обчислювальну складність операцій у полі. ВИСНОВКИ Таким чином, у результаті проведених досліджень було отримано уточнення наведених у [1] виразів для коефіцієнтів ізоморфних еліптичних кривих під час трансформації з нормальної форми в нормальну. На їх основі було отри- мано нові результати для оцінки верхньої границі кількості ізоморфних Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння Системні дослідження та інформаційні технології, 2012, № 4 123 кривих, які наведені в канонічній формі. Так, трансформація кривої з кано- нічної форми в канонічну дає лінійну залежність (7) верхньої границі чи- сла ізоморфізмів з ростом порядку p поля. Аналогічна границя (8) під час переходу від канонічної форми в нормальну пропорційна вже .4p Це до- зволяє значно збільшити потужність простору ізоморфних кривих у галузі криптографічних додатків, або скоротити довжину модуля поля. Отримані результати мають користь для оцінки показників стійкості криптографічних алгоритмів на основі перетворень у групі точок еліптичної кривої. ЛІТЕРАТУРА 1. Husemöller D. Elliptic Curves, Second Edition. — NY: Springer–Verlag, 2002. — 487 p. 2. Смарт Н. Криптография / Пер. с англ. С.А. Кулешова под ред. С.К. Ландо. — М.: Техносфера, 2005. — 528 с. 3. Koblitz N. Primality of the number of points on an elliptic curve over a finite field. — Pacific Journal of Mathematics. — 1988. — 131, № 1. — P. 157–165. Надійшла 19.09.2011

Число ізоморфізмів еліптичної кривої під час трансформацій канонічної форми рівняння

Репозитарії

Схожі ресурси