XTR (алгоритм)

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

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

Теоретическая основа XTR 
Алгоритм работает в конечном поле . Рассмотрим группу порядка , и её подгруппу порядка q, где p — простое число, такое, что другое достаточно большое простое число q является делителем . Группа порядка q называется XTR-подгруппой. Эта циклическая группа  является подгруппой  и имеет генератор g.

Арифметические операции в  
Пусть p — простое число, такое, что p ≡ 2 mod 3, а p2 — p + 1 делится на достаточно большое простое q. Так как p2 ≡ 1 mod 3, p порождает . Таким образом, круговой многочлен  является неприводимым в . Следовательно, корни  и  образуют оптимальный нормальный базис  над  и
 
С учетом p ≡ 2 mod 3:
 
Таким образом, стоимость арифметических операций следующая:

 Вычисление xp не требует умножения
 Вычисление x2 требует двух операций умножения в 
 Вычисление xy требует трех операций умножения в 
 Вычисление xz-yzp требует четырёх операций умножения в .:

Использование следов в  
Элементами, сопряженными с  в  являются: сам  и , а их сумма — след .
 
Кроме того:
 
Рассмотрим генератор  XTR-группы порядка , где  — простое число. Так как  — подгруппа группы порядка , то . Кроме того,
 
и
 .
Таким образом,
 
Отметим также, что сопряженным к элементу  является , то есть,  имеет норму равную 1.
Ключевой особенностью XTR является то, что минимальный многочлен  в 
 
упрощается до
 
Иными словами, сопряженные с  элементы, как корни минимального многочлена в , полностью определяются следом .
Аналогичные рассуждения верны для любой степени :
 
— этот многочлен определяется следом .

Идея алгоритма в том, чтобы заменить  на , то есть вычислять  по  вместо  по  Однако для того, чтобы метод был эффективен, необходим способ быстро получать  по имеющемуся .

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

Определение:
Пусть  — корни  в , а . Обозначим:
 

Свойства  и :
 
 
  для 
  для 
 Либо все  имеют порядок, являющийся делителем  и , либо все  — в поле . В частности,  — неприводим тогда и только тогда, когда его корни имеют порядок, являющийся делителем  и .
  приводим в поле  тогда и только тогда, когда 

Утверждение:
Пусть даны .
 Вычисление  требует двух операций произведения в поле .
 Вычисление  требует четырёх операций произведения в поле .
 Вычисление  требует четырёх операций произведения в поле .
 Вычисление  требует четырёх операций произведения в поле .

Определение:
Пусть .

Алгоритм для вычисления  при заданных  и  
 При  алгоритм применяется для  и , затем используется свойство 2 для получения конечного результатаю
 При , .
 При , .
 При , воспользуемся выражениями для  и , чтобы найти  и, соответственно, .
 При , чтобы вычислить , введем
 
 и  если не  нечетно и  если четно. Положим  и найдем , используя Утверждение, и . Пусть, в дальнейшем,
 
 где  и . Для  последовательно выполним следующее:
 При , воспользуемся  чтобы найти .
 При , воспользуемся  чтобы найти .
 Заменим  на .
По завершении итераций, , а . Если n — четно, воспользуемся  чтобы найти .

Выбор параметров

Выбор поля и размера подгруппы 
Чтобы воспользоваться преимуществами представления элементов групп в виде их следов и обеспечить достаточную защищенность данных, необходимо найти простые  и , где  — характеристика поля , причем , а  — размер подгруппы и делитель .
Обозначим как  и  размеры  и  в битах. Чтобы достичь уровня безопасности, который обеспечивает, к примеру, RSA с длиной ключа в 1024 бита, требуется выбрать  таким, что , то есть  а  может быть около 160.
Первый алгоритм, который позволяет вычислить такие простые  и  — Алгоритм А.

Алгоритм А
 Найдём  такое, что число  — простое число длиной в  бит.
 Найдем  такое, что число  — простое длиной  бит, а также .

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

От этого недостатка избавлен более медленный Алгоритм Б.

Алгоритм Б
 Выберем простое число  длиной в  бит, такое, что .
 Найдем корни  и  .
 Найдем  такое, что , - простое -битовое число и при этом  для 

 Корректность Алгоритма Б:
 Как только мы выбираем , автоматически выполняется условие  (Так как  и ). Из этого утверждения и квадратичного закона взаимности следует, что корни  и  существуют.
 Чтобы проверить, что  снова рассмотрим  для  и заметим, что .Значит  и  -корни  и, следовательно, .

Выбор подгруппы 
В предыдущем разделе мы нашли размеры  и  конечного поля  и мультипликативной подгруппы в . Теперь следует найти подгруппу  в  для некоторых  таких, что .
Однако, необязательно искать явный элемент , достаточно найти элемент  такой, что  для элемента  порядка . Но при данном , генератор  XTR-группы может быть найден путём нахождения корня .
Чтобы найти это , рассмотрим свойство 5 . Найдя такое  следует проверить, действительно ли оно порядка , однако сначала нужно выбрать c\in GF(p²), такое, что F(c,\ X) — неприводимо.
Простейший подход в том, чтобы выбирать  случайным образом.

Утверждение: Для случайно выбранного  вероятность, что  — неприводимо, больше 1/3.

Базовый алгоритм для поиска :
 Выберем случайное .
 Если  — приводим, вернемся на первый шаг.
 Воспользуемся алгоритмом для поиска . Найдем .
 Если  имеет порядок не равный , вернемся на первый шаг.
 Пусть .
Данный алгоритм вычисляет элемент поля  эквивалентный  для некоторых  порядка .

Примеры

Протокол Диффи-Хеллмана 
Предположим, у Алисы и Боба есть открытый XTR-ключ  и они хотят сгенерировать общий закрытый ключ .
 Алиса выбирает случайное число  такое, что , вычисляет  и посылает  Бобу.
 Боб получает  от Алисы, выбирает случайное  такое, что , вычисляет  и посылает  Алисе.
 Алиса получает  от Боба, вычисляет  и получает  — закрытый ключ .
 Точно так же, Боб вычисляет  и получает  — закрытый ключ .

Схема Эль-Гамаля 
Предположим, у Алисы есть часть публичного ключа XTR: . Алиса выбирает секретное целое число  и вычисляет и публикует . Получив публичный ключ Алисы , Боб может зашифровать сообщение , предназначенное Алисе, используя следующий алгоритм:
 Боб выбирает случайное  такое, что  и вычисляет .
 Затем Боб вычисляет.
 Боб определяет симметричный ключ  основанный на .
 Боб шифрует сообщение  ключом , получая зашифрованное сообщение .
 Пару  Боб посылает Алисе.
Получив пару , Алиса расшифровывает её следующим образом:
 Алиса вычисляет .
 Алиса определяет симметричный ключ  основанный на .
 Зная, что алгоритм шифрования сообщения — симметричный, Алиса ключом  расшифровывает , получая исходное сообщение .
Таким образом, сообщение передано.

Примечания 

Криптография с открытым ключом
Шифры