Xreferat.com » Рефераты по математике » Складність деяких методів експоненціювання точки кривої

Складність деяких методів експоненціювання точки кривої

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

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

З метою підвищення продуктивності під час обчислення точки Складність деяких методів експоненціювання точки кривої багатьма авторами запропоновано різні методи. Дамо стислий опис й оцінку складності найпоширеніших з них.

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

Нехай порядок Складність деяких методів експоненціювання точки кривої і число Складність деяких методів експоненціювання точки кривої подано у двійковій системі


Складність деяких методів експоненціювання точки кривої


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

експоненціювання алгоритм скалярне множення

Алгоритм подвоєння-додавання


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


Складність деяких методів експоненціювання точки кривої


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

Алгоритм 1.

Вхід: Складність деяких методів експоненціювання точки кривої

Вихід: Складність деяких методів експоненціювання точки кривої

1. Складність деяких методів експоненціювання точки кривої

2. Складність деяких методів експоненціювання точки кривої

2.1 Складність деяких методів експоненціювання точки кривої

2.2 Складність деяких методів експоненціювання точки кривої

3. Складність деяких методів експоненціювання точки кривої.

Реалізація методу вимагає Складність деяких методів експоненціювання точки кривої операцій Складність деяких методів експоненціювання точки кривої подвоєння точки й Складність деяких методів експоненціювання точки кривої додавань Складність деяких методів експоненціювання точки кривої, де Складність деяких методів експоненціювання точки кривої - вага Хеммінга двійкового вектора Складність деяких методів експоненціювання точки кривої (число одиниць цього вектора). Оскільки в середньому число одиниць випадкового вектора дорівнює Складність деяких методів експоненціювання точки кривої, загальне число групових операцій оцінюється величиною Складність деяких методів експоненціювання точки кривої


Алгоритм подвоєння-додавання-віднімання


Попередній алгоритм можна вдосконалити, якщо вести додаткову операцію-віднімання точки. Цей метод запропонований в 1990 році Ф. Морейном і Дж. Олівосом. Наприклад, число Складність деяких методів експоненціювання точки кривої у двійковій системі має вага у Складність деяких методів експоненціювання точки кривої, але його можна подати як Складність деяких методів експоненціювання точки кривої з вагою Складність деяких методів експоненціювання точки кривої Ця ідея знижує вагу Хеммінга і, відповідно, число групових операцій. Реалізувати алгоритм подвоєння - додавання віднімання можна переходом від двійкового подання числа Складність деяких методів експоненціювання точки кривої до трійкового Складність деяких методів експоненціювання точки кривої з коефіцієнтами Складність деяких методів експоненціювання точки кривої Складність деяких методів експоненціювання точки кривої Одне із властивостей подання Складність деяких методів експоненціювання точки кривої - відсутність у ньому суміжних пар ненульових елементів, завдяки чому зростає питома вага нульових елементів Складність деяких методів експоненціювання точки кривої. Для розрахунку Складність деяких методів експоненціювання точки кривої використовується наступний алгоритм.

Алгоритм 2.

Вхід: позитивне ціле число Складність деяких методів експоненціювання точки кривої

Вихід: Складність деяких методів експоненціювання точки кривої

1. Складність деяких методів експоненціювання точки кривої

2. Складність деяких методів експоненціювання точки кривої

2.1 Складність деяких методів експоненціювання точки кривої

2.2 Складність деяких методів експоненціювання точки кривої

2.3 Складність деяких методів експоненціювання точки кривої

3. Складність деяких методів експоненціювання точки кривої

Після розрахунку Складність деяких методів експоненціювання точки кривої обчислюється точка Складність деяких методів експоненціювання точки кривої методом ліворуч-праворуч за допомогою алгоритму 3.

Алгоритм 3.

Вхід: Складність деяких методів експоненціювання точки кривої

Вихід: Складність деяких методів експоненціювання точки кривої

1. Складність деяких методів експоненціювання точки кривої

2. Складність деяких методів експоненціювання точки кривої

2.1 Складність деяких методів експоненціювання точки кривої

2.2 Складність деяких методів експоненціювання точки кривої

2.3 Складність деяких методів експоненціювання точки кривої

3. Складність деяких методів експоненціювання точки кривої.

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


Метод вікон з алгоритмом подвоєння - додавання - віднімання


Якщо в криптосистемі є резерви пам'яті, їх можна задіяти для подальшого збільшення швидкості обчислень. Ідея в тому, що замість точки Складність деяких методів експоненціювання точки кривої можна експоненціювати і надалі складати суміжні блоки або вікна шириною Складність деяких методів експоненціювання точки кривої в Складність деяких методів експоненціювання точки кривої - поданні точки Складність деяких методів експоненціювання точки кривої

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

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


Складність деяких методів експоненціювання точки кривої


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

У загальному випадку в пам'яті зберігається Складність деяких методів експоненціювання точки кривої точок. Число Складність деяких методів експоненціювання точки кривої може бути визначене за допомогою модифікованого алгоритму 2. Модифікація полягає в тому, що: на кроці 2.1 замість Складність деяких методів експоненціювання точки кривої необхідно записати Складність деяких методів експоненціювання точки кривої, де Складність деяких методів експоненціювання точки кривої означає ціле число Складність деяких методів експоненціювання точки кривої, певне в інтервалі Складність деяких методів експоненціювання точки кривої. Далі обчислюється точка Складність деяких методів експоненціювання точки кривої згідно з алгоритмом 4.

Алгоритм 4.

Вхід: Складність деяких методів експоненціювання точки кривоїСкладність деяких методів експоненціювання точки кривої

Вихід: Складність деяких методів експоненціювання точки кривої

1. Складність деяких методів експоненціювання точки кривої

2. Складність деяких методів експоненціювання точки кривої

3. Складність деяких методів експоненціювання точки кривої

3.1 Складність деяких методів експоненціювання точки кривої

3.2 Складність деяких методів експоненціювання точки кривої

Складність деяких методів експоненціювання точки кривої

Складність деяких методів експоненціювання точки кривої

4. Складність деяких методів експоненціювання точки кривої.

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

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


Метод Монтгомері


Розглянемо метод Монтгомері. Нехай Складність деяких методів експоненціювання точки кривоїСкладність деяких методів експоненціювання точки кривої з Складність деяких методів експоненціювання точки кривоїПозначимо Складність деяких методів експоненціювання точки кривої Складність деяких методів експоненціювання точки кривої Можна перевірити, що


Складність деяких методів експоненціювання точки кривої

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

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

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

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