Алгоритм використовує генератор відносно малої підгрупи порядку ( — просте) підгрупи . За правильного вибору , дискретне логарифмування в групі, породженій , має таку ж обчислювальну складність, що й у . 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 вимагає чотирьох операцій множення в .[1]
Елементами, сполученими з в є: сам і , а їх сума — слід.
Крім того:
Розглянемо генератор XTR-групи порядку , де — просте число. Оскільки — підгрупа групи порядку , то . Крім того,
і
.
Таким чином,
Відзначимо також, що зв'язаним до елементу є , тобто, має норму рівну 1. Ключовою особливістю XTR є те, що мінімальний многочлен в
спрощується до
Іншими словами, пов'язані з елементи, як корені мінімального многочлена в , повністю визначаються слідом . Аналогічні міркування вірні для будь-якого степеня :
- цей многочлен визначається слідом .
Ідея алгоритму в тому, щоб замінити на , тобто обчислювати за замість за . Однак для того, щоб метод був ефективним, потрібен спосіб швидко отримувати за наявним .
або всі мають порядок, який є дільником і , або всі — в полі . Зокрема, — є таким, що не переводиться тоді і тільки тоді, коли його корені мають порядок, який є дільником і .
звідне в полі тоді і тільки тоді, коли
Лема: Нехай дано .
обчислення вимагає двох операцій множення в полі .
обчислення вимагає чотирьох операцій множення в полі .
обчислення вимагає чотирьох операцій множення в полі .
обчислення вимагає чотирьох операцій множення в полі .
Щоб скористатися перевагами подання елементів груп у вигляді їх слідів і забезпечити достатню захищеність даних, необхідно знайти прості і , де — характеристика поля , причому , а — розмір підгрупи і дільник . Позначимо як і розміри і в бітах. Щоб досягти рівня безпеки, який надає, наприклад, RSA з довжиною ключа 1024 біти, потрібно вибрати таким, що , тобто а може бути близько 160. Перший алгоритм, який дозволяє обчислити такі прості і — Алгоритм А.
Алгоритм А
Знайдемо таке, що число — просте число довжиною в біт.
Знайдемо таке, що число — просте довжиною біт, а також .
Коректність Алгоритму А:
Необхідно перевірити лише те, що , оскільки всі решта властивостей очевидно виконані через специфіку вибору і .
Неважко помітити, що , отже .
Алгоритм А дуже швидкий, однак може бути небезпечним, оскільки вразливий щодо атаки з використанням решета числового поля.
Цього недоліку позбавлений повільніший Алгоритм Б.
Алгоритм Б
Виберемо просте число довжиною в біт, таке, що .
Знайдемо корені і .
Знайдемо таке, що , — просте -бітове число і при цьому для
Коректність Алгоритму Б:
Як тільки ми вибираємо , автоматично виконується умова (оскільки і ). З цього твердження і квадратичного закону взаємності випливає, що корені і існують.
Щоб перевірити, що знову розглянемо для і зауважимо, що . Тобто і — корені і, отже, .
У попередньому розділі ми знайшли розміри і скінченного поля і мультиплікативної підгрупи в . Тепер слід знайти підгрупу в для деяких таких, що . Однак, необов'язково шукати явний елемент , досить знайти елемент такий, що для елемента порядку . Але при цьому , генератор XTR-групи може бути знайдений шляхом знаходження кореня . Щоб знайти це , розглянемо властивість 5 . Знайшовши таке слід перевірити, чи дійсно воно має порядок , проте спочатку потрібно вибрати , таке, що — незвідне. Найпростіший підхід в тому, щоб вибирати випадковим чином.
Лема: Для випадково вибраного ймовірність, що — є незвідним, більша 1/3.
Базовий алгоритм для пошуку :
Виберемо випадкове .
Якщо — звідне, повернемося на перший крок.
Скористаємося алгоритмом для пошуку . Знайдемо .
Якщо має порядок не рівний , повернемося на перший крок.
Нехай .
Даний алгоритм обчислює елемент поля еквівалентний для деяких порядку .[1]
Припустимо, Аліса має частину публічного ключа XTR: . Аліса вибирає секретне ціле число і обчислює і публікує . Отримавши публічний ключ Аліси , Боб може зашифрувати повідомлення , Призначене Алісі, використовуючи такий алгоритм:
Боб вибирає випадкове таке, що і обчислює .
Потім Боб обчислює .
Боб визначає симетричний ключ на основі .
Боб шифрує повідомлення ключем , отримуючи зашифроване повідомлення .
Пару Боб посилає Алісі.
Отримавши пару , Аліса розшифровує її таким чином:
Аліса обчислює .
Аліса визначає симетричний ключ на основі .
Знаючи, що алгоритм шифрування повідомлення — симетричний, Аліса ключем розшифровує , отримуючи початкове повідомлення .