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

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

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

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

RSAПравить

Основная статья: RSA

ECCПравить

Основная статья: Эллиптическая криптография

NTRUПравить

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

$a\otimes <!--\; \otimes \; -->b=c_0+c_{1}X+\cdots <!--\; \cdots \; -->+c_{N-<!--\; -\; -->1}{X}^{N-<!--\; -\; -->1}$$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 <!--\; \cdots \; -->+a_k{b}_0+a_{k+1}{b}_{N-<!--\; -\; -->1}+a_{k+2}{b}_{N-<!--\; -\; -->2}+\cdots <!--\; \cdots \; -->+a_{N-<!--\; -\; -->1}{b}_{k+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 <!--\; \otimes \; -->(b+c)=(a\otimes <!--\; \otimes \; -->b)+(a\otimes <!--\; \otimes \; -->c)$$a\otimes (b+c)=(a\otimes b)+(a\otimes c)$ .

Кольцо многочленов с определёнными таким образом операциями сложения и умножения называется кольцом усечённых многочленов. Оно изоморфно кольцу отношений $Z[X]/(X^N-<!--\; -\; -->1)$$Z[X]/(X^{N}-1)$ . В NTRU используются кольца усечённых многочленов с арифметикой по модулю p и q. Это значит, что коэффициенты $a_i$$a_{i}$  и $b_i$$b_{i}$  складываются и умножаются по модулю.

Генерация ключаПравить

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

$h=p{f}_q^{-<!--\; -\; -->1}\otimes <!--\; \otimes \; -->g\mathrm{mod}q$$h=pf_{q}^{-1}\otimes g\mod q$ .

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

ШифрованиеПравить

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

$e=r\otimes <!--\; \otimes \; -->h+m\mathrm{mod}q$$e=r\otimes h+m\mod q$ .

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

РасшифрованиеПравить

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

$a=f\otimes <!--\; \otimes \; -->e\mathrm{mod}q$$a=f\otimes e\mod q$ ,

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

$m=f_p^{-<!--\; -\; -->1}\otimes <!--\; \otimes \; -->a\mathrm{mod}p$$m=f_{p}^{-1}\otimes a\mod p$ .

Как это работаетПравить

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

$a=f\otimes <!--\; \otimes \; -->e\mathrm{mod}q=f\otimes <!--\; \otimes \; -->r\otimes <!--\; \otimes \; -->h+f\otimes <!--\; \otimes \; -->m\mathrm{mod}q=f\otimes <!--\; \otimes \; -->r\otimes <!--\; \otimes \; -->p{f}_q^{-<!--\; -\; -->1}\otimes <!--\; \otimes \; -->g+f\otimes <!--\; \otimes \; -->m\mathrm{mod}q=pr\otimes <!--\; \otimes \; -->g+f\otimes <!--\; \otimes \; -->m\mathrm{mod}q$$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 <!--\; \otimes \; -->a\mathrm{mod}p=f_p^{-<!--\; -\; -->1}\otimes <!--\; \otimes \; -->pr\otimes <!--\; \otimes \; -->g+f_p^{-<!--\; -\; -->1}\otimes <!--\; \otimes \; -->f\otimes <!--\; \otimes \; -->m\mathrm{mod}p$$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}$$2^{-100}$ .

ДополнениеПравить

РекомендацииПравить

1. Авторы криптосистемы NTRU рекомендуют использовать в качестве коэффициентов для многочленов f, g и m числа из множества {-1,0,1}. Такой подход позволяет оптимизировать хранение данных в памяти компьютера, ускорить некоторые вычисления и не сказывается на криптостойкости системы.
2. В то же время, данная рекомендация не распространяется на многочлен r. Напротив, для улучшения обфускации оригинального сообщения рекомендуется не ограничиваться числами из множества {-1,0,1}. Однако и слишком большие числа брать не следует, ведь вычисления все равно будут проводиться по модулю.
3. Использование числа -1 в качестве коэффициента опционально, так как оно особенно удобно в троичной системе счисления, но не слишком - в двоичной.
4. Что касается больших чисел, то криптостойкость алгоритма NTRU основана не на длинах модулей p и q, а на значении числа N. Из этого следует, что не обязательно использовать большие целые числа в качестве модулей. Можно ограничиться числами до 512 включительно. Однако N следует брать относительно большое. На данный момент (конец 2011 года) для максимальной криптостойкости рекомендуется брать $N⩾<!--\; ⩾\; -->500$$N\geqslant 500$ . Здесь 500 - не длина числа N в битах, а непосредственное значение.

ОптимизацияПравить

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

Возможные ошибкиПравить

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

$\mathbf{\text{a}}=3-<!--\; -\; -->7X-<!--\; -\; -->10X^2-<!--\; -\; -->11X^3+10X^4+7X^5+6X^6+7X^7+5X^8-<!--\; -\; -->3X^9-<!--\; -\; -->7X^{10}(\mathrm{mod}32)$${\textbf {a}}=3-7X-10X^{2}-11X^{3}+10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}}$ 

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

$\mathbf{\text{a}}=3+25X+22X^2+21X^3+10X^4+7X^5+6X^6+7X^7+5X^8+29X^9+28X^{10}(\mathrm{mod}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. Тогда "правильное" выражение преобразуется в следующее:

$\mathbf{\text{a}}=2X+2X^2+X^3+X^4+X^5+X^7+2X^8+2X^{10}(\mathrm{mod}3)$${\textbf {a}}=2X+2X^{2}+X^{3}+X^{4}+X^{5}+X^{7}+2X^{8}+2X^{10}{\pmod {3}}$ 

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

$\mathbf{\text{a}}=X+X^2+X^4+X^5+X^7+2X^8+2X^9+X^{10}(\mathrm{mod}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}\to <!--\; \to \; -->\{0,1{\}}^k$$H:B_{l+r}\rightarrow \{0,1\}^{k}$ . Эта хеш-функция не должна содержать коллизий. В криптосистеме, основанной на группе кос, используется свойство коммутативности кос построенных в $L{B}_l$$LB_{l}$ , то есть в группе n-кос, построенной с использованием только генераторов меньших, чем некоторое целое число d, и в $R{B}_r$$RB_{r}$ , то есть в группе n-кос, построенной с использованием только генераторов больших, чем d.

Генерация ключаПравить

Выбирается достаточно сложная (l+r)-коса $x\in <!--\; \in \; -->B_{l+r}$$x\in B_{l+r}$ . Далее выбирается коса $a\in <!--\; \in \; -->L{B}_l$$a\in LB_{l}$ . Открытым ключом является пара (x, y), где $y=ax{a}^{-<!--\; -\; -->1}$$y=axa^{-1}$ . Секретным ключом является a.

ШифрованиеПравить

Пусть необходимо отправить сообщение $m\in <!--\; \in \; -->\{0,1{\}}^k$$m\in \{0,1\}^{k}$ , зашифровав его с помощью ключа (x, y). Тогда необходимо произвольно выбрать $b\in <!--\; \in \; -->R{B}_r$$b\in RB_{r}$ . Шифротекстом будет пара (c, d), где $c=bx{b}^{-<!--\; -\; -->1}$$c=bxb^{-1}$  и $d=H(by{b}^{-<!--\; -\; -->1})+m$$d=H(byb^{-1})+m$ .

РасшифрованиеПравить

Чтобы расшифровать сообщение (c, d), используя ключ a необходимо, вычислить $m=H(ac{a}^{-<!--\; -\; -->1})+d$$m=H(aca^{-1})+d$ .

СравнениеПравить

ECC и RSA на восьмибитном процессореПравить

ECC, по сравнению с RSA, лучше подходит для применения в мобильных устройствах, так как она работает быстрее, использует ключи меньшей длины и потребляет меньше памяти и энергии. В RSA используется арифметика в кольце целых чисел, и в её основу положена трудность разложения больших целых чисел на множители. В ECC используются группы точек эллиптических кривых, и её стойкость основана на сложности дискретного логарифмирования. В настоящее время не известны алгоритмы нахождения дискретного логарифма на эллиптической кривой с суб-экспоненциальной сложностью, в то время как для разложения на множители такие алгоритмы существуют. Это позволяет использовать ключи для ECC меньшей длины, чем для RSA. ECC-160 обеспечивает примерно такой же уровень безопасности, как RSA-1024. Но в то же время увеличение длины ключа ECC в два раза приводит к большему увеличению криптостойкости, чем увеличение в два раза длины ключа RSA. Из-за этого ECC-224 примерно соответствует RSA-2048, а значит в будущем преимущества ECC только возрастут. Также увеличение длины ключа и уменьшение разрядности процессора приводит к увеличению преимущества в производительности ECC перед RSA.

В статье «Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs» проводилось сравнение производительности и использования памяти ECC и RSA реализованных для восьмибитных процессоров. Производительность сравнивается на двух процессорах: Chipcon CC1010 и Atmel ATmega128. Результаты сравнения сведены в таблицу. Для шифрования RSA использовался открытый ключ $e=2^{16}+1$$e=2^{16}+1$ .

Алгоритм	ATmega128 @ 8МГц	CC1010 @ 14,7456 МГц
	Время, с	Память под данные, байтов	Память под код, байтов	Время, с	Память под данные, байтов	Память под код, байтов
ECC-160	0,81	282	3682	4,58	180+86	2166
ECC-192	1,24	336	3979	7,56	216+102	2152
ECC-224	2,19	422	4812	11,98	259+114	2214
RSA-1024 шифрование	0,43	542	1073	> 4,48
RSA-1024 расшифрование	10,99	930	6292	~ 106,66
RSA-2048 шифрование	1,94	1332	2854
RSA-2048 расшифрование	83,26	1853	7736

RSA, ECC, NTRU и криптосистема в группе косПравить

В статье «Practical comparison of fast public-key cryptosystems» было проведено сравнение четырех криптосистем. Авторы написали свои реализации ECC, NTRU и криптосистемы в группе кос. Результаты для RSA были взяты из тестов производительности библиотеки J/Crypto, поэтому код RSA был лучше оптимизирован, чем код остальных криптосистем.

	RSA-1024	ECC-168	NTRU-263	Криптосистема в группе кос
Увеличение сообщения	1	2	$\approx <!--\; \approx \; -->4,5$$\approx 4,5$	4
Длина блока, битов	1024	160	416	1088
Длина открытого ключа, битов	1024	169	1841	1000
Скорость генерации ключа, мс	1432	65	19,8	8,5
Скорость шифрования, мс	4,28	140	1,9	29,8
Скорость расшифрования, мс	48,5	67	3,5	14,9

ИсточникиПравить

• Priit Karu, Jonne Loikkanen. Practical comparison of fast public-key cryptosystems. Helsinki University of Technology, 2001.
• Ki Hyoung Ko, Sang Jin Lee, Jung Hee Cheon, Jae Woo Han, Ju-sung Kang, and Choonsik Park. New Public-key Cryptosystem Using Braid Groups. Proceedings of Crypto 2000, LNCS 1880 (2000).
• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: A Ring-Based Public Key Cryptosystem. Proceedings of ANTS , Portland (1998), Springer-Verlag.
• Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman. NTRU: A Public Key Cryptosystem. August 1999.
• Joseph H. Silverman, W. Whyte. NTRU Report 018. Estimating Decryption Failure Probabilities for NTRUEncrypt. June 20, 2003.
• Nils Gura, Arun Patel, Arvinderpal Wander, Hans Eberle, Sheueling Chang Shantz. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), LNCS 3156, pp. 119–132, 2004.

См. такжеПравить

• Криптосистема с открытым ключом
• Быстрая цифровая подпись