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

Быстрая криптосистема с открытым ключом (англ. Fast public-key cryptosystem) или лёгкая криптосистема с открытым ключом (англ. Lightweight public-key cryptosystem) — асимметричная криптосистема, используемая в устройствах с ограниченными ресурсами.

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

Одна из наиболее распространенных асимметричных криптосистем — RSA. RSA плохо подходит для использования во встраиваемых устройствах, потому что требует оперирования большими числами, что не всегда можно реализовать при ограниченных ресурсах. Кроме того, RSA работает довольно медленно, особенно это касается генерации ключей, и в RSA используются более длинные ключи по сравнению с другими криптосистемами с открытым ключом. Но RSA хорошо подходит для сравнения криптографической стойкости других криптосистем. Для использования криптографии в мобильных устройствах, память и вычислительная мощность которых сильно ограничены, необходимы более эффективные алгоритмы. Самая распространенная из таких криптосистем — эллиптическая криптосистема, требует меньше ресурсов, чем RSA. Хотя эллиптическая криптосистема не настолько хорошо исследована, как RSA, она считается надежной и используется в нескольких стандартах. Криптосистемы, созданные позднее, такие как: NTRU, Braid Cryptosystem, работают быстрее, чем эллиптическая криптосистема, но их надежность недостаточно исследована.

RSA[править | править код]

ECC[править | править код]

NTRU[править | править код]

NTRU был разработан в середине 1990-х годов и впервые был представлен на конференции CRYPTO’96. NTRU запатентован NTRU Cryptosystems, Inc. 24 июля 2000 года. В этом алгоритме все операции производятся в кольце усечённых многочленов. Криптографическая стойкость алгоритма основана на сложности задачи нахождения короткого вектора в заданной решётке. NTRU работает быстрее, чем используемые в настоящее время криптосистемы с открытым ключом. Для шифрования и расшифрования сообщения длиной N символов необходимо $O(N^{2})$ операций для алгоритма NTRU, в то время как для RSA требуется $O(N^{3})$ операций. Криптографическая стойкость NTRU ещё не достаточно исследована. Кроме того NTRU является ненадёжным алгоритмом, то есть при расшифровании можно получить сообщение, отличающее от того, которое использовалось при шифровании. Криптостойкость NTRU-167 (Параметр N = 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=(a_{0}+b_{0})+(a_{1}+b_{1})X+\cdots +(a_{N-1}+b_{N-1})X^{N-1}$ .

Операция умножения определена так же, с помощью умножения коэффициентов при соответствующих степенях, с одной поправкой. При умножении многочленов $X^{N}$ необходимо заменить на 1, $X^{N+1}$ заменить на 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 (b+c)=(a\otimes b)+(a\otimes c)$ .

Кольцо многочленов с определёнными таким образом операциями сложения и умножения называется кольцом усечённых многочленов. Оно изоморфно кольцу отношений $Z[X]/(X^{N}-1)$ . В 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=pf_{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 pf_{q}^{-1}\otimes g+f\otimes m\mod q=pr\otimes g+f\otimes m\mod q$

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

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

Дополнение[править | править код]

Оптимизация[править | править код]

Во-первых, если внимательно посмотреть на используемые для шифрования и расшифрования формулы, то нетрудно заметить, что многочлен $f_{q}^{-1}$ успешно сокращается и нигде более не используется. А значит, можно не тратить время на его вычисление.
Во-вторых, раз уж нам более не нужно вычислять $f_{q}^{-1}$ , значит мы можем выбрать число q так, чтобы было наиболее удобно вести расчеты по этому модулю. Логичнее всего использовать степени двойки. Например, 64, 128, 256 и т.д. Тогда, вместо медленной операции взятия остатка от деления можно будет использовать быструю операцию побитового "и" (или аналогичную).
В-третьих, в описании алгоритма сказано, что модули p и q не обязательно должны быть простыми, достаточно, чтобы они были взаимно простыми. А это значит, что для некоторого непростого p в кольце чисел по этому модулю p обязательно найдутся необратимые элементы. Подобный недостаток может сказаться на поиске многочлена $f_{p}^{-1}$ . Чтобы избежать подобной проблемы, рекомендуется использовать простые числа. Причем не обязательно тратить время на генерирование простого числа (методы проверки на простоту слишком медленные, чтобы их использовать без причины), достаточно брать значение p из множества {3,5,7,11,...}.

Возможные ошибки[править | править код]

Во время этапа расшифровки нужно быть особенно внимательным с коэффициентами многочлена $a$ . Все коэффициенты должны находиться в интервале [-q/2, q/2], а не [0, q-1]. Если не сделать подобную проверку, то могут получиться разные результаты. В этом нетрудно убедиться. Пусть, мы имеем следующий многочлен $a$ :

{\textbf {a}}=3-7X-10X^{2}-11X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}}

Записанный таким образом многочлен полностью соответствует заявленному условию. Теперь выпишем возможный "ошибочный" вариант:

{\textbf {a}}=3+25X+22X^{2}+21X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}+29X^{9}+28X^{10}{\pmod {32}}

Казалось бы, мы не сделали никаких неравносильных преобразований. Однако, достаточно просто взять все коэффициенты по модулю p (а это, фактически, следующее действие расшифровки), как сразу станет понятна суть ошибки. Допустим, p = 3. Тогда "правильное" выражение преобразуется в следующее:

{\textbf {a}}=2X+2X^{2}+X^{3}+X^{4}+X^{5}+X^{7}+2X^{8}+2X^{10}{\pmod {3}}

А ошибочное в следующее:

{\textbf {a}}=X+X^{2}+X^{4}+X^{5}+X^{7}+2X^{8}+2X^{9}+X^{10}{\pmod {3}}

Очевидно, что дальнейшая работа с каждым из полученных многочленов даст разные результаты. Разница в том, что первый многочлен позволит вычислить правильное исходное сообщение, а второй - искаженное.

Криптосистема, основанная на группе кос[править | править код]

Идея создания криптосистемы, основанной на группе кос, была описана на конференции CRYPTO’2000. Она основана на сложности задачи поиска обобщенного сопряженного в группе кос.

Для шифрования и расшифрования используется хеш-функция $H:B_{l+r}\rightarrow \{0,1\}^{k}$ . Эта хеш-функция не должна содержать коллизий. В криптосистеме, основанной на группе кос, используется свойство коммутативности кос построенных в $LB_{l}$ , то есть в группе n-кос, построенной с использованием только генераторов меньших, чем некоторое целое число d, и в $RB_{r}$ , то есть в группе n-кос, построенной с использованием только генераторов больших, чем d.