У этого термина существуют и другие значения, см.
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 требует четырёх операций умножения в
.:[1]
Использование следов в
Элементами, сопряженными с
в
являются: сам
и
, а их сумма — след
.
-
Кроме того:
-
Рассмотрим генератор
XTR-группы порядка
, где
— простое число. Так как
— подгруппа группы порядка
, то
. Кроме того,
-
и
-
.
Таким образом,
-
Отметим также, что сопряженным к элементу
является
, то есть,
имеет норму равную 1.
Ключевой особенностью XTR является то, что минимальный многочлен
в
-
упрощается до
-
Иными словами, сопряженные с
элементы, как корни минимального многочлена в
, полностью определяются следом
.
Аналогичные рассуждения верны для любой степени
:
-
— этот многочлен определяется следом
.
Идея алгоритма в том, чтобы заменить
на
, то есть вычислять
по
вместо
по
Однако для того, чтобы метод был эффективен, необходим способ быстро получать
по имеющемуся
.
Алгоритм быстрого вычисления
по
[2]
Определение:
Для каждого
определим:
-
Определение:
Пусть
— корни
в
, а
. Обозначим:
-
Свойства
и
:
-
-
-
для
-
для
- Либо все
имеют порядок, являющийся делителем
и
, либо все
— в поле
. В частности,
— неприводим тогда и только тогда, когда его корни имеют порядок, являющийся делителем
и
.
-
приводим в поле
тогда и только тогда, когда
Утверждение:
Пусть даны
.
- Вычисление
требует двух операций произведения в поле
.
- Вычисление
требует четырёх операций произведения в поле
.
- Вычисление
требует четырёх операций произведения в поле
.
- Вычисление
требует четырёх операций произведения в поле
.
Определение:
Пусть
.
Алгоритм для вычисления
при заданных
и
- При
алгоритм применяется для
и
, затем используется свойство 2 для получения конечного результатаю
- При
,
.
- При
,
.
- При
, воспользуемся выражениями для
и
, чтобы найти
и, соответственно,
.
- При
, чтобы вычислить
, введем
-
- и
если не
нечетно и
если четно. Положим
и найдем
, используя Утверждение, и
. Пусть, в дальнейшем,
-
- где
и
. Для
последовательно выполним следующее:
- При
, воспользуемся
чтобы найти
.
- При
, воспользуемся
чтобы найти
.
- Заменим
на
.
По завершении итераций,
, а
. Если n — четно, воспользуемся
чтобы найти
.
Выбор параметров
Выбор поля и размера подгруппы
Чтобы воспользоваться преимуществами представления элементов групп в виде их следов и обеспечить достаточную защищенность данных, необходимо найти простые
и
, где
— характеристика поля
, причем
, а
— размер подгруппы и делитель
.
Обозначим как
и
размеры
и
в битах. Чтобы достичь уровня безопасности, который обеспечивает, к примеру, RSA с длиной ключа в 1024 бита, требуется выбрать
таким, что
, то есть
а
может быть около 160.
Первый алгоритм, который позволяет вычислить такие простые
и
— Алгоритм А.
Алгоритм А
- Найдём
такое, что число
— простое число длиной в
бит.
- Найдем
такое, что число
— простое длиной
бит, а также
.
- Корректность Алгоритма А:
- Необходимо проверить лишь то, что
, так как все оставшиеся свойства очевидно выполнены из-за специфики выбора
и
.
- Нетрудно заметить, что
, значит
.
Алгоритм А очень быстрый, однако может быть небезопасен, так как уязвим против атаки с использованием решета числового поля.
От этого недостатка избавлен более медленный Алгоритм Б.
Алгоритм Б
- Выберем простое число
длиной в
бит, такое, что
.
- Найдем корни
и
.
- Найдем
такое, что
,
- простое
-битовое число и при этом
для
- Корректность Алгоритма Б:
- Как только мы выбираем
, автоматически выполняется условие
(Так как
и
). Из этого утверждения и квадратичного закона взаимности следует, что корни
и
существуют.
- Чтобы проверить, что
снова рассмотрим
для
и заметим, что
.Значит
и
-корни
и, следовательно,
.
Выбор подгруппы
В предыдущем разделе мы нашли размеры
и
конечного поля
и мультипликативной подгруппы в
. Теперь следует найти подгруппу
в
для некоторых
таких, что
.
Однако, необязательно искать явный элемент
, достаточно найти элемент
такой, что
для элемента
порядка
. Но при данном
, генератор
XTR-группы может быть найден путём нахождения корня
.
Чтобы найти это
, рассмотрим свойство 5
. Найдя такое
следует проверить, действительно ли оно порядка
, однако сначала нужно выбрать c\in GF(p²), такое, что F(c,\ X) — неприводимо.
Простейший подход в том, чтобы выбирать
случайным образом.
Утверждение: Для случайно выбранного
вероятность, что
— неприводимо, больше 1/3.
Базовый алгоритм для поиска
:
- Выберем случайное
.
- Если
— приводим, вернемся на первый шаг.
- Воспользуемся алгоритмом для поиска
. Найдем
.
- Если
имеет порядок не равный
, вернемся на первый шаг.
- Пусть
.
Данный алгоритм вычисляет элемент поля
эквивалентный
для некоторых
порядка
.[1]
Примеры
Протокол Диффи-Хеллмана
Предположим, у Алисы и Боба есть открытый XTR-ключ
и они хотят сгенерировать общий закрытый ключ
.
- Алиса выбирает случайное число
такое, что
, вычисляет
и посылает
Бобу.
- Боб получает
от Алисы, выбирает случайное
такое, что
, вычисляет
и посылает
Алисе.
- Алиса получает
от Боба, вычисляет
и получает
— закрытый ключ
.
- Точно так же, Боб вычисляет
и получает
— закрытый ключ
.
Схема Эль-Гамаля
Предположим, у Алисы есть часть публичного ключа XTR:
. Алиса выбирает секретное целое число
и вычисляет и публикует
. Получив публичный ключ Алисы
, Боб может зашифровать сообщение
, предназначенное Алисе, используя следующий алгоритм:
- Боб выбирает случайное
такое, что
и вычисляет
.
- Затем Боб вычисляет
.
- Боб определяет симметричный ключ
основанный на
.
- Боб шифрует сообщение
ключом
, получая зашифрованное сообщение
.
- Пару
Боб посылает Алисе.
Получив пару
, Алиса расшифровывает её следующим образом:
- Алиса вычисляет
.
- Алиса определяет симметричный ключ
основанный на
.
- Зная, что алгоритм шифрования сообщения — симметричный, Алиса ключом
расшифровывает
, получая исходное сообщение
.
Таким образом, сообщение передано.