Введение

Криптосистема с открытым ключом на основе решёток

Криптосистема с открытым ключом NTRUEncrypt, также известная как алгоритм шифрования NTRU, является альтернативой RSA и криптографии на эллиптических кривых (ECC), основанной на решётках NTRU, и базируется на задаче о кратчайшем векторе в решётке (которая, как считается, не может быть взломана с использованием квантовых компьютеров). Она опирается на предполагаемую сложность факторизации определенных многочленов в усеченном кольце многочленов на частное двух многочленов с очень маленькими коэффициентами. Взлом криптосистемы тесно связан, хотя и не эквивалентен, алгоритмической задаче редукции решёток в определенных решётках. Для противодействия некоторым опубликованным атакам необходим тщательный выбор параметров. Поскольку как шифрование, так и расшифрование используют только простое умножение многочленов, эти операции очень быстры по сравнению с другими асимметричными схемами шифрования, такими как RSA, ElGamal и криптография на эллиптических кривых. Однако NTRUEncrypt ещё не подвергался сопоставимому объёму криптографического анализа в развёрнутом виде. Связанным алгоритмом является алгоритм цифровой подписи NTRUSign. В частности, операции NTRU основаны на объектах в усеченном кольце многочленов со свёрточной операцией умножения, и все многочлены в кольце имеют целочисленные коэффициенты и степень не более N-1. Умножение многочлена на в этом кольце приводит к циклическому сдвигу коэффициентов многочлена. Отображение вида для фиксированного , таким образом, создаёт новый многочлен, где каждый коэффициент зависит от такого же количества коэффициентов из , как и ненулевых коэффициентов в .

NTRU имеет три целочисленных параметра (N, p, q), где N – ограничение на степень многочлена, p называется малым модулем, а q – большим модулем; предполагается, что N является простым числом, q всегда (значительно) больше p, а p и q взаимно просты. Открытые текстовые сообщения являются многочленами по модулю p, а зашифрованные сообщения – многочленами по модулю q. Конкретно, зашифрованный текст состоит из открытого текстового сообщения плюс случайным образом выбранное кратное открытого ключа, но сам открытый ключ может рассматриваться как кратное малого модуля p, что позволяет владельцу закрытого ключа извлечь открытый текст из зашифрованного текста.

История

Криптосистема с открытым ключом NTRUEncrypt является относительно новой. Первая версия системы, просто названная NTRU, была разработана примерно в 1996 году тремя математиками (Джеффри Хоффштейн, Джилл Пифер и Джозеф Х. Сильверман). В 1996 году эти математики вместе с Дэниелом Лиманом основали компанию NTRU Cryptosystems, Inc. и получили патент (в настоящее время истекший) на данную криптосистему. В течение последних десяти лет велась работа по улучшению криптосистемы. С момента первой публикации криптосистемы были внесены изменения для повышения как производительности, так и безопасности. Большинство улучшений были направлены на ускорение процессов. До 2005 года существовала литература, описывающая ошибки при расшифровке NTRUEncrypt. Что касается безопасности, то с момента появления первой версии NTRUEncrypt были введены новые параметры, которые представляются безопасными против всех известных на данный момент атак и при разумном увеличении вычислительной мощности. В настоящее время система полностью соответствует стандартам IEEE P1363 в соответствии со спецификациями для криптографии с открытым ключом на основе решёток (IEEE P1363.1). Благодаря высокой скорости работы криптосистемы NTRUEncrypt (см. http://bench.cr.yp.to для результатов тестирования) и её низкому потреблению памяти, она может использоваться в таких приложениях, как мобильные устройства и смарт-карты. В апреле 2011 года NTRUEncrypt был принят в качестве стандарта X9.98 для использования в индустрии финансовых услуг.