Розподіл результатів поділу точки групи точок кривої Едвардса на 4 за суміжними класами

Abstract

У сучасній криптології еліптичні криві в формі Едвардса (криві Едвардса) є перспективними для використання в асиметричних криптосистемах. Ці криві у порівнянні з відомими еліптичними кривими у канонічній формі мають ряд переваг, таких як швидкодія, універсальність закону додавання та наявність афінних координат нейтрального елемента (нуля) абелевої групи точок. Із симетрії точок кривих Едвардса відносно обох координатних осей випливають властивості цих кривих, які знайшли застосування в криптографії. На сьогодні криві Едвардса активно досліджуються у всьому світі, зокрема, вивчається можливість розробки нових стандартів цифрового підпису, що базуються на кривих Едвардса. Найбільш цікавими для практичного використання є криві Едвардса, у яких порядок дорівнює 4n, де n – велике просте число. Стійкість цифрового підпису на кривих Едвардса базується на складності розв’язання задачі дискретного логарифмування у підгрупі групи точок еліптичної кривої. Саме перспектива використання кривих Едвардса для побудови нових стандартів цифрового підпису робить актуальним питання криптографічного аналізу таких криптосистем. Серед атак на криптосистеми, що базуються на задачі дискретного логарифмування, особливе місце займають спеціальні атаки, що використовують особливості самої циклічної групи, в якій розглядається ця задача. Тому при побудові такої криптосистеми необхідно дослідити структуру відповідної групи та її особливості. Однією із алгебраїчних задач, яка може бути корисною у криптографічному аналізі є представлення точок кривої Едвардса через ліві (праві) суміжні класи за підгрупами порядку 4 та максимального простого порядку n. Одним з алгоритмів криптографічного аналізу систем на кривих Едвардса є алгоритм поділу точки групи точок кривої Едвардса на чотири. Результати поділу тісно пов’язані із розбиттям групи точок кривої Едвардса за суміжними класами за підгрупами максимального простого порядку та порядку 4. Структура групи точок кривої Едвардса дозволяє однозначно визначати знаходження будь-якої точки цієї групи одночасно в двох суміжних класах за підгрупами максимального простого порядку та порядку 4. Наведений приклад розв’язання задачі дискретного логарифмування з використанням поділу точки на чотири і класифікація результатів поділу за суміжними класами для групи точок кривої Едвардса порядку 28 і 76.