ФЭНДОМ


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

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

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

NTRU Править

NTRU был разработан в середине 1990-х годов и впервые был представлен на конференции CRYPTO’96. NTRU запатентован NTRU Cryptosystems, Inc. 24 июля 2000 года. В этом алгоритме все операции производятся в кольце усечённых многочленов. Криптографическая стойкость алгоритма основана на сложности задачи нахождения короткого вектора в заданной решётке. NTRU работает быстрее, чем используемые в настоящее время криптосистемы с открытым ключом. Для шифрования и расшифрования сообщения длиной N символов необходимо O(N^2) операций для алгоритма NTRU, в то время как для RSA требуется O(N^3) операций. Криптографическая стойкость NTRU ещё не достаточно исследована. Кроме того NTRU является нестабильным алгоритмом, т.е. при расшифровании можно получить сообщение, отличающее от того, которое использовалось при шифровании.

Кольцо усечённых многочленов Править

Различные реализации 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 \oplus 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 \oplus c) = (a \otimes b) \oplus (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 и f_q соответственно. Затем нужно вычислить

h = p f_q \otimes g \mod q.

Закрытым ключом будет пара f, f_p, а открытым h.

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

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

e = r \otimes h \oplus m \mod q.

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

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

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

a = f \otimes e \mod q,

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

m = f_p \otimes a \mod p.

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

Идея создания криптосистемы основанной на группе кос была описана на конференции 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 = a x a^{-1}. Закрытым ключом является a.

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

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

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

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

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

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики