XTR (скорочення від ECSTR — «Efficient and Compact Subgroup Trace Representation») — алгоритм шифрування з відкритим ключем, який базується на обчислювальній складності задачі дискретного логарифмування. Перевагами цього алгоритму перед іншими, що використовують цю ідею, є більша швидкість і менший розмір ключа.

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

Теоретична основа XTR Алгоритм працює в скінченному полі . Розглянемо групу порядку , і її підгрупу порядку q, де p — просте число, таке, що інше досить велике просте число q є дільником . Група порядку q називається XTR-підгрупою. Ця циклічна група є підгрупою і має генератор g.

Арифметичні операції в Нехай p — просте число, таке, що p ≡ 2 mod 3, а p 2 — p + 1 ділиться на досить велике просте q. Оскільки p 2 ≡ 1 mod 3, p породжує . Таким чином, коловий многочлен є таким, що не переводиться в . Отже, корені і утворюють оптимальний нормальний базис над і

З урахуванням p ≡ 2 mod 3:

Лема. Вартість арифметичних операцій така:

Обчислення xp не вимагає множення Обчислення x2 вимагає двох операцій множення в Обчислення xy вимагає трьох операцій множення в Обчислення xz-yzp вимагає чотирьох операцій множення в .

Використання слідів в Елементами, сполученими з в є: сам і , а їх сума — слід .

Крім того:

Розглянемо генератор XTR-групи порядку , де  — просте число. Оскільки  — підгрупа групи порядку , то . Крім того,

і

.

Таким чином,

Відзначимо також, що зв'язаним до елементу є , тобто, має норму рівну 1. Ключовою особливістю XTR є те, що мінімальний многочлен в

спрощується до

Іншими словами, пов'язані з елементи, як корені мінімального многочлена в , повністю визначаються слідом . Аналогічні міркування вірні для будь-якого степеня :

- цей многочлен визначається слідом .

Ідея алгоритму в тому, щоб замінити на , тобто обчислювати за замість за . Однак для того, щоб метод був ефективним, потрібен спосіб швидко отримувати за наявним .

Алгоритм швидкого обчислення за Означення: Для кожного з визначимо:

Означення: Нехай  — корені в , а . Позначимо:

Властивості і :

для для або всі мають порядок, який є дільником і , або всі  — в полі . Зокрема,  — є таким, що не переводиться тоді і тільки тоді, коли його корені мають порядок, який є дільником і . звідне в полі тоді і тільки тоді, коли

Лема: Нехай дано .

обчислення вимагає двох операцій множення в полі . обчислення вимагає чотирьох операцій множення в полі . обчислення вимагає чотирьох операцій множення в полі . обчислення вимагає чотирьох операцій множення в полі .

Визначення: Нехай .

Алгоритм для обчислення при заданих і

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

і якщо непарне і якщо парне. Покладемо і знайдемо , використовуючи твердження, і . Нехай, надалі,

де і . Для послідовно виконаємо таке: Якщо , скористаємося щоб знайти . Якщо , скористаємося щоб знайти . Замінимо на .

По завершенні ітерацій, , а . Якщо n — парне, скористаємося щоб знайти .

Вибір параметрів

Вибір поля і розміру підгрупи Щоб скористатися перевагами подання елементів груп у вигляді їх слідів і забезпечити достатню захищеність даних, необхідно знайти прості і , де  — характеристика поля , причому , а  — розмір підгрупи і дільник . Позначимо як і розміри і в бітах. Щоб досягти рівня безпеки, який надає, наприклад, RSA з довжиною ключа 1024 біти, потрібно вибрати таким, що , тобто а може бути близько 160. Перший алгоритм, який дозволяє обчислити такі прості і  — Алгоритм А.

Алгоритм А

Знайдемо таке, що число  — просте число довжиною в біт. Знайдемо таке, що число  — просте довжиною біт, а також .

Коректність Алгоритму А: Необхідно перевірити лише те, що , оскільки всі решта властивостей очевидно виконані через специфіку вибору і . Неважко помітити, що , отже .

Алгоритм А дуже швидкий, однак може бути небезпечним, оскільки вразливий щодо атаки з використанням решета числового поля.

Цього недоліку позбавлений повільніший Алгоритм Б.

Алгоритм Б

Виберемо просте число довжиною в біт, таке, що . Знайдемо корені і . Знайдемо таке, що ,  — просте -бітове число і при цьому для

Коректність Алгоритму Б: Як тільки ми вибираємо , автоматично виконується умова (оскільки і ). З цього твердження і квадратичного закону взаємності випливає, що корені і існують. Щоб перевірити, що знову розглянемо для і зауважимо, що . Тобто і  — корені і, отже, .

Вибір підгрупи У попередньому розділі ми знайшли розміри і скінченного поля і мультиплікативної підгрупи в . Тепер слід знайти підгрупу в для деяких таких, що . Однак, необов'язково шукати явний елемент , досить знайти елемент такий, що для елемента порядку . Але при цьому , генератор XTR-групи може бути знайдений шляхом знаходження кореня . Щоб знайти це , розглянемо властивість 5 . Знайшовши таке слід перевірити, чи дійсно воно має порядок , проте спочатку потрібно вибрати , таке, що  — незвідне. Найпростіший підхід в тому, щоб вибирати випадковим чином.

Лема: Для випадково вибраного ймовірність, що  — є незвідним, більша 1/3.

Базовий алгоритм для пошуку :

Виберемо випадкове . Якщо  — звідне, повернемося на перший крок. Скористаємося алгоритмом для пошуку . Знайдемо . Якщо має порядок не рівний , повернемося на перший крок. Нехай .

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

Приклади Припустимо, Аліси і Боб мають відкритий XTR-ключ і вони хочуть згенерувати спільний закритий ключ .

Аліса вибирає випадкове число таке, що , обчислює і посилає Бобу. Боб отримує від Аліси, вибирає випадкове таке, що , обчислює і посилає Алісі. Аліса отримує від Боба, обчислює і отримує  — закритий ключ . Так само, Боб обчислює і отримує  — закритий ключ .

Схема Ель-Гамаля Припустимо, Аліса має частину публічного ключа XTR: . Аліса вибирає секретне ціле число і обчислює і публікує . Отримавши публічний ключ Аліси , Боб може зашифрувати повідомлення , Призначене Алісі, використовуючи такий алгоритм:

Боб вибирає випадкове таке, що і обчислює . Потім Боб обчислює . Боб визначає симетричний ключ на основі . Боб шифрує повідомлення ключем , отримуючи зашифроване повідомлення . Пару Боб посилає Алісі.

Отримавши пару , Аліса розшифровує її таким чином:

Аліса обчислює . Аліса визначає симетричний ключ на основі . Знаючи, що алгоритм шифрування повідомлення — симетричний, Аліса ключем розшифровує , отримуючи початкове повідомлення .

Таким чином, повідомлення надіслано.

Примітки