На головну

Атаки на шифри певні еліптичними кривими

  1.  II. Обчислити певні інтеграли.
  2.  Атаки на найпростіші парольні системи
  3.  Атаки на систему RSA
  4.  Атаки на систему відкритого шифрування NTRU
  5.  Атаки на рівні додатків
  6.  Атаки на рівні мережного програмного забезпечення

нехай  кінцеве поле, характеристика p  2. Розглянемо многочлен  виду

,

 . через  позначимо безліч коренів многочлена Е в поле  разом з нескінченної точкою ?. Таким чином,

.

Очевидно, що якщо  , то  . Раніше в параграфі §5.7било показано, що на  (Зокрема, на  ) Вводиться групова операція.

У криптографічного практиці використовують циклічні підгрупи груп точок еліптичної кривої над кінцевим полем. Стійкість відповідних криптографічних протоколів визначається складністю проблеми дискретного логарифмування в цих підгрупах. Центральним параметром тут є порядок циклічної підгрупи. Якщо це число складене, то група містить власні підгрупи. Тому завдання обчислення дискретного логарифма в циклічній групі зводиться до однієї або декількох завдань дискретного логарифмування в власних підгрупах, тобто групах меншого порядку. В даний час відомий ефективний алгоритм обчислення порядку груп  для будь-яких еліптичних кривих Е над довільним кінцевим полем  . Цей алгоритм заснований на застосуванні теорії модулярних функцій, тому його виклад виходить за рамки цієї книги. Знаючи порядок групи  , Легко отримати порядок будь-якій її циклічної підгрупи.

Наведемо тут алгоритм, вирішальний наступне завдання. Нехай G кінцева абелева група в мультипликативной записи. заданий елемент  і потрібно обчислити його порядок n в групі G. Припустимо, що відома межа зверху для порядку групи G, тобто  . тоді  . У разі еліптичної кривої виконується очевидне нерівність  . Наведемо алгоритм, що належить Шенкс.

Вхідні дані алгоритму. Група G (кінцева абелева) в мультипликативной записи, число В таке, що  і елемент  . Вихідні дані алгоритму. .

Крок 1. Обчислити  . Обчислити елементи 1, g, ..., gr-1, Упорядкувати масив пар ,  по другій координаті.

Крок 2. Обчислити  . Для кожного b,  обчислити  і перевірити чи є цей елемент групи другий координатою будь-якої пари з упорядкованого масиву пар. Якщо це так і  , То запам'ятати число .

Крок 3. Число n є найменше серед чисел  , Обчислених на попередньому кроці. Алгоритм закінчує свою роботу.

Доведемо тепер, що алгоритм завжди дасть правильний результат. Для цього достатньо зауважити, що невідоме число n може бути записано у вигляді  , де  . Дійсно, розділимо n на r із залишком. З урахуванням значення r неважко отримати, що і приватна і залишок лежать між 0 і r-1: .

Складність алгоритму оцінюється наступним чином. Вважають, що час виконання однієї операції і час порівняння двох елементів в групі G збігаються. На кроці 1 потрібно обчислити r елементів групи G і впорядкувати масив, що складається з r пар. Це вимагає не більше  операцій. На кроці 2 потрібно r раз провести пошук в упорядкованому масиві пар. Це також вимагає не більше  операцій порівняння в групі G. Таким чином, загальна оцінка складності алгоритму Шенкса має вигляд  операцій. При цьому обсяг використаної пам'яті становить  осередків. Слід згадати, що в закритій друку цей алгоритм відкритий Шенксом в 1969 році був опублікований раніше Шенкса в 1962 році А. О. Гельфонду. Для атаки на проблему дискретного логарифма істотно використовують розкладання порядку групи. Відповідний алгоритм і оцінки були отримані і опубліковані в 1965 році в закритій друку В. І. Нечаєвим. У 1977 році близький до нього алгоритм був опублікований поліг і Хеллманом і незалежно Зільбером. Стосовно до мультиплікативної групі обидва алгоритму прекрасно представлені в книзі [Нечаєв В. І. Елементи криптографії. М .: Вища школа, 1999]. Стосовно до еліптичних кривих вони описані в книзі [А. А. Блотова, С. Б. Гашкова, А. Б. Фролова. Елементарне введення в еліптичну криптографію. Протоколи криптографії на еліптичних кривих. М., КомКніга, 2006].

Стверджується, що алгоритм Шенкса можна істотно прискорити, якщо відомо, що  для деяких В, С.

Вхідні дані алгоритму. Група G (кінцева абелева) в мультипликативной записи, елемент ,  для деякого n і  для деяких В, С. Вихідні дані алгоритму. Найменше натуральне n0 таке, що и .

Крок 1. Обчислити  . Обчислити елементи gc, gc + 1, ..., Grc + r-1, Упорядкувати масив пар ,  по другій координаті.

Крок 2. Обчислити  . Для кожного b,  обчислити  і перевірити чи є цей елемент групи другий координатою будь-якої пари з упорядкованого масиву пар. Якщо це так і  , То запам'ятати число .

Крок 3. Число n0 є найменше серед чисел  , Обчислених на попередньому кроці. Алгоритм закінчує свою роботу.

Доводиться, що алгоритм дійсно обчислює необхідну n0. Очевидно також, що число n0 яке знаходить алгоритм, не обов'язково є точним порядком елемента g. Це число може бути кратним точного порядку g. Доводиться, що складність алгоритму становить  операцій в групі G. Обсяг використаної пам'яті становить  осередків. Відзначимо, що цей алгоритм не має відношення до прискорення власне алгоритму Шенкса (обчислення дискретного логарифма при певному порядку групи, що характерно для протоколів на еліптичних кривих), так як лише уточнює порядок групи. З точки зору атаки принципове прискорення досягається при використанні розкладання порядку групи в разі, коли в цьому розкладанні відсутня великий множник. Звідси і криптографічне вимога до порядку групи - обов'язковість великого множника.

Повернемося до еліптичної кривої. Нехай Р точка з  . Потрібно дізнатися точний порядок l точки Р в групі  . Відома наступна теорема Хассе

ТЕОРЕМА. нехай  . тоді .

З теореми Хассе слід, що існує натуральне n кратне l таке, що  (Наприклад, таким n може бути  ). Значить, застосувавши викладений вище алгоритм, можна знайти таке n за  операцій в  . Число n слід далі розкласти на прості множники. Потім вже легко обчислити точний порядок Р в  . Викладений алгоритм є експоненціальним, тобто він не ефективний при великих q. Однак при порівняно невеликих  він цілком прийнятний.


Глава 50.



 Атака на протокол передачі відкритого ключа з відкритого каналу від В до А з метою подальшої передачі від A до В ключа k симетричною системи. |  дискретних логарифмів

 Атаки на найпростіші парольні системи |  Атаки на систему RSA |  Назад. З (3) випливає, що |  Ця система еквівалентна системі |  Шифрування Меркля-Хеллмана |  Атаки на систему відкритого шифрування NTRU |  Методи обчислення колізій для хеш-функцій |  компрометація криптопротоколів |  Звідси отримуємо. |  методи факторизації |

© um.co.ua - учбові матеріали та реферати