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

Быстрая криптосистема с открытым ключом (англ. 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²) операций для алгоритма NTRU, в то время как для RSA требуется O(N³) операций. Криптографическая стойкость 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 = 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 ^{− 100}.

Криптосистема, основанная на группе кос

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

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

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

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

Шифрование

Пусть необходимо отправить сообщение $m \in \{ 0, 1 \} ^k$, зашифровав его с помощью ключа (x, y). Тогда необходимо произвольно выбрать $b \in RB_r$. Шифротекстом будет пара (c, d), где c = bxb ^{− 1} и d = H(byb ^{− 1}) + m.

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

Чтобы расшифровать сообщение (c, d), используя ключ a необходимо, вычислить 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 и . Результаты сравнения сведены в таблицу. Для шифрования RSA использовался открытый ключ e = 2¹⁶ + 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 — 1	2 — 1	$\approx 4,5 - 1$	4 — 1
Длина блока, битов	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.

См. также

• Криптосистема с открытым ключом

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

Wikimedia Foundation. 2010.