Быстрые криптосистемы с открытым ключом

Интернет магазин китайских планшетных компьютеров

Компьютеры - Быстрые криптосистемы с открытым ключом - NTRU

23 января 2011

Оглавление:
1. Быстрые криптосистемы с открытым ключом
2. NTRU
3. Криптосистема, основанная на группе кос
4. Сравнение

NTRU был разработан в середине 1990-х годов и впервые был представлен на конференции CRYPTO’96. NTRU запатентован NTRU Cryptosystems, Inc. 24 июля 2000 года. В этом алгоритме все операции производятся в кольце усечённых многочленов. Криптографическая стойкость алгоритма основана на сложности задачи нахождения короткого вектора в заданной решётке. NTRU работает быстрее, чем используемые в настоящее время криптосистемы с открытым ключом. Для шифрования и расшифрования сообщения длиной N символов необходимо O операций для алгоритма NTRU, в то время как для RSA требуется O операций. Криптографическая стойкость NTRU ещё не достаточно исследована. Кроме того NTRU является ненадёжным алгоритмом, то есть при расшифровании можно получить сообщение, отличающее от того, которое использовалось при шифровании. Криптостойкость NTRU-167 примерно соответствует RSA-512. Стойкость NTRU-263 и NTRU-503 сопоставима со стойкостью RSA-1024 и RSA-2048 соответственно. При этом при использовании NTRU-263 длина открытого ключа равняется 1841 биту, а секретного — 834 бита. В NTRU зашифрованное сообщение больше открытого текста примерно в 4,5 раза.

Кольцо усечённых многочленов

Различные реализации NTRU характеризуются тремя целыми числами — N, p и q. Числа p и q не обязательно должны быть простыми, но необходимо, чтобы они не имели общих делителей. Базовыми объектами в NTRU являются многочлены порядка N-1 с целочисленными коэффициентами:

$a = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-1} X^{N-1}$ .

Операция сложения определена просто, как сложение коэффициентов при соответствующих степенях:

$a + b = + X + \cdots + X^{N-1}$ .

Операция умножения определена так же, с помощью умножения коэффициентов при соответствующих степенях, с одной поправкой. При умножении многочленов X необходимо заменить на 1, X заменить на X и т. д.:

$a \otimes b = c_0 + c_1 X + \cdots + c_{N-1} X^{N-1}$ , где $c_k = a_0 b_k + a_1 b_{k-1} + \cdots + a_k b_0 + a_{k+1} b_{N-1} + a_{k+2} b_{N-2} + \cdots + a_{N-1} b_{k+1}$ .

Правила сложения и умножения обладают свойством дистрибутивности:

$a \otimes = +$ .

Кольцо многочленов с определёнными таким образом операциями сложения и умножения называется кольцом усечённых многочленов. Оно изоморфно кольцу отношений Z /. В NTRU используются кольца усечённых многочленов с арифметикой по модулю p и q. Это значит, что коэффициенты a_i и b_i складываются и умножаются по модулю.

Генерация ключа

Пусть R — кольцо усечённых многочленов. Если Боб хочет создать пару ключей, он случайно выбирает многочлены $f, g \in R$ . Многочлен f должен иметь обратный многочлен по модулю p и q. Если для f не существует обратного, то Боб должен выбрать другой многочлен. Далее Боб должен вычислить обратные многочлены по модулю p и q, обозначим их $f_p^{-1}$ и $f_q^{-1}$ соответственно. Затем нужно вычислить

$h = p f_q^{-1} \otimes g \mod q$ .

Секретным ключом будет пара f, $f_p^{-1}$ , а открытым h.

Шифрование

Если Алиса хочет отправить сообщение Бобу, используя его открытый ключ h, ей необходимо представить сообщение в виде многочлена m, коэффициенты которого взяты по модулю p. Также ей необходимо произвольно выбрать многочлен r. Далее, используя эти параметры, она вычисляет многочлен

$e = r \otimes h + m \mod q$ .

Многочлен e является зашифрованным сообщением, которое хочет отправить Алиса.

Расшифрование

Предположим Боб получил зашифрованное сообщение, которое послала ему Алиса. Для начала ему необходимо вычислить

$a = f \otimes e \mod q$ ,

используя известный только ему многочлен f. Теперь Боб может восстановить сообщение Алисы, вычислив

$m = f_p^{-1} \otimes a \mod p$ .

Как это работает

Рассмотрим почему при расшифровании получается исходное сообщение:

$a = f \otimes e \mod q = f \otimes r \otimes h + f \otimes m \mod q = f \otimes r \otimes p f_q^{-1} \otimes g + f \otimes m \mod q = p r \otimes g + f \otimes m \mod q$

$m = f_p^{-1} \otimes a \mod p = f_p^{-1} \otimes p r \otimes g + f_p^{-1} \otimes f \otimes m \mod p$

Следует заметить, что при расшифровании может получиться сообщение отличающееся от исходного. Это происходит из-за того, что операции произоводятся сначала по модулю q, а потом по модулю p. На практике, если правильно выбрать параметры, вероятность возникновения такой ошибки становится меньше, чем 2 .

<<< Быстрая цифровая подпись

Бюро шифров >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие