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

Скалярне множення або експоненціювання точки кривої у криптографічних алгоритмах. Методи вікон з алгоритмом подвоєння – додавання – віднімання. Метод еспоненціювання Монтгомері. Методи експоненціювання при фіксованій точці. Алгоритм максимальної пам'яті.

Рубрика Математика
Вид контрольная работа
Язык украинский
Дата добавления 07.02.2011
Размер файла 130,4 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

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

Алгоритм 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 оптимальним виявляється вікно шириною , а при - вікно шириною

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

Розглянемо метод Монтгомері. Нехай з Позначимо Можна перевірити, що

(1)

Отже, знаючи - координати точок й , можна обчислити координати точок й , перейти до пари , або до пари .

Кожна така ітерація вимагає одного подвоєння й одного додавання з використанням формули (1).

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

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

Алгоритм 5. Метод експоненціювання Монтгомері.

Вхід

Вихід

1.

2.

2.1

3.1

3.2

4.

Алгоритм 5 вимагає однієї інверсії, а не двох, тому що можна обчислити

, а потім отримати множенням на . Можна домогтися істотного збільшення продуктивності, якщо операцію подвоєння замінити операцією ділення точки на два. Виграш до 40% при цьому досягається у зв'язку з відсутністю операції інверсії елемента в полі. Крім того, групові операції послідовних ділень у НБ зводяться практично до однієї операції множення в полі.

Методи експоненціювання при фіксованій точці

Фіксованою точкою в криптосистемі завжди є генератор або базова точка криптосистеми порядку . Такі точки - це відкриті ключі користувачів. Якщо в системі є резерв пам'яті, його можна використати для зберігання заздалегідь розрахованих точок. Наприклад, якщо обчислити й записати в пам'яті точки , то для визначення скалярного добутку залишиться лише обчислити суми точок відповідно до двійкового подання . У середньому для цього буде потрібно лише операцій. Їхнє число можна зменшити до операцій додавання й віднімання, якщо скористатися трійковим поданням .

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

Тоді

де

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

Алгоритм 6.

Вхід ширина вікна , ,

Вихід

1. Передрозрахунки

2.

3.

3.1

3.2

4.

Середня обчислювальна складність алгоритму оцінюється кількістю додавань

.

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

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

Їхні двійкові подання дають першу пару точок й , які складаються, після чого їхня сума подвоюється.

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

Алгоритм 7.

Вхід ширина вікна , ,,

Вихід

1. Передрозрахунки обчислити всі точки й

,

2. Подати число у вигляді конкатенації фрагментів шириною

Нехай означає й біт фрагмента

3.

4.

4.1

4.2

5.

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

Обмінюючи час обчислень на пам'ять, можна й далі підвищувати продуктивність експоненціювання точки кривої. Наприклад, для кожного вікна шириною можна заздалегідь розрахувати точок, при цьому на згадку рийдеться записати точок. Операція подвоєння в цьому випадку не використовується, а складність оцінюється числом додавань. Цей алгоритм назвемо алгоритмом максимальної пам'яті. У табл.13.1 дані для порівняння величини пам'яті й тимчасової складності (числа групових операцій) алгоритму 6 й алгоритму максимальної пам'яті при . В обох випадках зі збільшенням ширини вікна збільшується пам'ять і знижується число групових операцій. Очевидно, що останній алгоритм за наявності більших резервів пам'яті дозволяє істотно прискорити операцію експоненціювання фіксованої точки

Таблиця 1 Об'єм пам'яті й тимчасова складність (число групових операцій) алгоритму 6 й алгоритму максимальної пам'яті при

Метод

W = 3

W = 4

W = 5

W = 6

M

S

M

S

M

S

M

S

Алгоритм 6

14

900

30

725

62

632

126

529

Алгоритм

максимальної пам'яті.

469

58

750

46

1280

38

2079

33

Размещено на Allbest.ru


Подобные документы

  • Використання методу Монтгомері як ефективний шлях багаторазового зведення за модулем. Складність операцій з многочленами та обчислення їх значень. Алгоритм Руфіні-Горнера. Визначення рекурсивного процесу для множення. Доведення алгоритму Тоома-Кука.

    контрольная работа [103,8 K], добавлен 07.02.2011

  • Використання методу Полларда для вирішення проблеми дискретного логарифмування, його складність і час обчислення рішення ECDLP. Аномальні криві й криві над розширеннями малого поля. MOV-атака та суперсингулярні криві над полем F. Метод спуску Вейля.

    реферат [269,5 K], добавлен 21.02.2011

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

    презентация [92,6 K], добавлен 06.02.2014

  • Обчислення довжини дуги для просторової кривої, що задана параметрично. Варіант розрахунку у випадку задання кривої в полярній системі координат. Формули для обчислення площі поверхні обертання. Вираз площі циліндричної поверхні через елементарні функції.

    научная работа [103,7 K], добавлен 12.05.2010

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

    реферат [75,3 K], добавлен 22.02.2010

  • Поняття вектора, його характерні риси та ознаки, порядок визначення координат та напряму. Додавання, віднімання та множення вектора на число. Тривимірний векторний простір і його підпростори. Колінеарність та компланарність векторів, їх скалярний добуток.

    курсовая работа [473,6 K], добавлен 17.11.2009

  • Огляд проблеми дискретного логарифмування в групі точок еліптичної кривої. Сутність та сфера використання методу Поліга-Хелмана. Особливості використання методу ділення точок на два. Можливі підходи і приклади розв’язання задач дискретного логарифмування.

    реферат [112,8 K], добавлен 09.02.2011

  • Методи багатомірної безумовної оптимізації першого й нульового порядків і їх засвоєння, порівняння ефективності застосування цих методів для конкретних цільових функцій. Загальна схема градієнтного спуску. Метод найшвидшого спуску. Схема яружного методу.

    лабораторная работа [218,0 K], добавлен 10.12.2010

  • Розгляд найбільш відомих скінченно-різнецевих методів рішення рівнянь руху з непереривною силою: чисельна ітерація рівнянь Ньютона; алгоритм Бімана і Шофілда; метод Рунге-Кутта; методи Адамса, Крилова, Чаплигіна. Програма Рунге-Кутта на мові С#.

    курсовая работа [359,5 K], добавлен 27.01.2011

  • Оцінювання параметрів розподілів. Незміщені, спроможні оцінки. Методи знаходження оцінок: емпіричні оцінки, метод максимальної правдоподібності. Означення емпіричної функції розподілу, емпіричні значення параметрів. Задача перевірки статистичних гіпотез.

    контрольная работа [57,2 K], добавлен 12.08.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.