Xreferat.com » Рефераты по математике » Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

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

дискретного логарифмування в групі точок еліптичної кривої" width="19" height="21" align="BOTTOM" border="0" /> й, відповідно до розв’язання Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Злом криптосистеми, у такий спосіб зводиться до вирішення еквівалентних проблем:

– визначення, у якому пів кола групи <P> перебуває деяка точка цієї групи;

– визначення співвідношення (більше - менше) між двома довільними
точками Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої й Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої групи <P>;

– визначення парності ( непарності) числа Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої для точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої;

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

Доки відповісти на ці запитання не вдається ECC залишається стійкою криптосистемою з експоненційною складністю розв’язання Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Для криптоаналізу зовсім необов'язково прийти до точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої або Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, достатньо знайти точку з Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої-координатою точки, що раніше зустрічалася в цій процедурі, або будь-якої іншої відомої точки групи <P>. У першому випадку рішення Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої при колізії Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої близько до Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої- методу Полларда, у другому – до методу Шенкса.

Доцільно використовувати максимально можливу кількість інформації (передрозрахунки) з метою збільшення ймовірності колізій, однак це веде до збільшення кількості перевірок і розширення пам'яті.


крива поле дискретний логарифмування атака

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

Рисунок 2 - Геометрична ілюстрація методу ділення точок кривої на два


Якщо в 1 залишити лише одну операцію ділення на два з вибором точки із групи Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, то ітераційна процедура ділення на два в остаточному підсумку також призведе до точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (або іншої відомої точки), якщо 2 є примітивним елементом поля Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Послідовне ділення точок на два вимагає в НБ лише одне множення в полі на кожному кроці, інші операції практично не вимагають витрат. При цьому, імовірно, можна досягти максимальної швидкості криптоаналізу. Цей метод, однак, рівносильний повному перебору всіх точок. Більш доцільним, можливо, є випадковий пошук колізій зі складністю Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої.


4. Аномальні криві й криві над розширеннями малого поля


Аномальні криві над розширеннями поля Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (криві Коблиця) виду Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої мають особливості структури групи E, що дозволяють зменшити в Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої раз об'єм аналізованих точок кривої (у порівнянні із групою загальної структури) і, відповідно, у Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої раз обчислювальну складність пошуку колізій. Це пов'язано з виникненням класів еквівалентності точок кривої, породжуваних послідовним піднесенням у квадрат координат вихідної точки.

Позначимо функцію Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої при цьому Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої Для будь-якої точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої порядку Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої кривої Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої над полем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої визначається ендоморфізм Фробеніуса (відображення поля в поле), який задовольняє характеристичне рівняння


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


Тут операція додавання визначена як додавання в групі E, а параметр Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої називають слідом ендоморфізма Фробеніуса. Зокрема, для кривої Коблиця з коефіцієнтами з поля Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої й параметром Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої маємо


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


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

Розв’язання цього квадратного рівняння в кільці Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої дає значення параметра Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, що визначає всі точки класу еквівалентності


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


Через те, що їхні координати визначаються послідовним піднесенням у квадрат, простіше всього їх виразити в НБ, у якому їх Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої-бітовий запис утворює циклічний код із Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої слів для кожної координати. Такі точки називають помітними. Задача розв’язання Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, таким чином, зводиться до пошуку класу еквівалентності з точністю до циклічного зсуву, що практично не вимагає додаткових обчислень. Неважко переконатися, що для підгрупи Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої точок цієї кривої порядку Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої коренем рівняння


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


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


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


Для точок максимального порядку Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої корінь рівняння


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


дорівнює Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої Один із класів еквівалентності точок даного порядку включає точки Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Їхні координати утворюються послідовним піднесенням у квадрат. Усього є 4 класи еквівалентності точок максимального порядку.

В порівнянні із загальним типом груп Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої аномальні бінарні криві поступаються у стійкості в Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої раз, що не є катастрофічною втратою. Для полів з розширенням Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої втрата складає не більше 4-х біт. Тому з урахуванням високої технологічності такі криві не виключаються із криптографічних застосувань і входять у відомі стандарти. Подібні ж міркування справедливі, якщо як вихідну прийняти криву Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої над малим полем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, після чого ту ж криву розглядати над розширенням Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (при цьому як і раніше Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої). Слід Фробеніуса Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої визначає порядок кривої над підполем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (і розв’язання характеристичного рівняння для скаляра Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої), а слід Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої - порядок кривої над полем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Виникнення класів еквівалентності точок кривої над таким розширенням приводить до втрати складності криптоатаки в Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої раз. Крім того, поле Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої є композиційним і містить принаймні підполя Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Такі криві уразливі стосовно атаки методом спуску Вейля.

Аномальні криві над простим полем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої, Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої визначаються як криві з порядком Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої й, відповідно, слідом Фробеніуса Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Такі криві виявилися криптографічно слабкими, тому що порядки групи Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої й адитивної групи поля Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої рівні, що дозволяє порівняно просто побудувати атаку ізоморфізму, що переводить точки кривої в елементи групи Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Цей метод уперше був запропонований І. Семаєвим, а також незалежно авторами Т. Сатохом, К. Араки й Н. Смартом. Складність Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої при цій атаці стає поліноміальною, що робить аномальні криві даного типу неприйнятними в криптографії.


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


Під час вивчення властивостей суперсингулярних кривих виявилося, що порядок групи Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої над полем Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої ділить порядок мультиплікативної групи розширень Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої або Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої. Це дозволяє побудувати ізоморфізм між елементами групи E й мультиплікативної групи розширеного поля, після чого розв’язувати більше просту задачу визначення дискретного логарифма в полі. Ця атака ізоморфізму заснована на використанні Іспарювання ВейляІ і була запропонована А. Менезисом , Т. Окамото й С. Ванстоном, у зв'язку із чим називається Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої- атакою.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: