NTRUEncrypt - NTRUEncrypt

Эта статья включает в себя список общих Рекомендации, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (апрель 2013) (Узнайте, как и когда удалить этот шаблон сообщения)

В NTRUEncrypt криптосистема с открытым ключом, также известный как НТРУ алгоритм шифрования, это решетчатый Альтернативой ЮАР и ECC и основан на кратчайшая векторная задача в решетке (которая, как известно, не может быть разрушена с помощью квантовые компьютеры ).

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

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

Связанный алгоритм - это NTRUSign цифровой подписи алгоритм.

В частности, операции NTRU основаны на объектах в усеченном кольце многочленов. ${ Displaystyle R = mathbb {Z} [X] / (X ^ {N} -1)}$ с умножением свертки, и все многочлены в кольце имеют целое число коэффициенты и степень не более N-1:

${ displaystyle { textbf {a}} = a_ {0} + a_ {1} X + a_ {2} X ^ {2} + cdots + a_ {N-2} X ^ {N-2} + a_ {N-1} X ^ {N-1}}$

NTRU - это фактически параметризованное семейство криптосистем; каждая система определяется тремя целочисленными параметрами (N, п, q), которые представляют максимальную степень ${ Displaystyle N-1}$ для всех многочленов в усеченном кольце р, малый модуль и большой модуль, соответственно, где предполагается, что N является основной, q всегда больше чем п, и п и q находятся совмещать; и четыре набора многочленов ${ displaystyle { mathcal {L}} _ {f}, { mathcal {L}} _ {g}, { mathcal {L}} _ {m}}$ и ${ displaystyle { mathcal {L}} _ {r}}$ (полиномиальная часть закрытого ключа, полином для генерации открытого ключа, сообщения и слепого значения, соответственно), все степени не выше ${ Displaystyle N-1}$.

История

Криптосистема с открытым ключом NTRUEncrypt - относительно новая криптосистема. Первая версия системы, которая называлась просто NTRU, была разработана примерно в 1996 году тремя математиками (Джеффри Хоффштейн, Джилл Пайфер, и Джозеф Х. Сильверман ). В 1996 г. эти математики вместе с Дэниел Лиман основал NTRU Cryptosystems, Inc. и получил патент^[1] (срок действия истек) в криптосистеме.

Последние десять лет люди работали над улучшением криптосистемы. С момента первой презентации криптосистемы были внесены некоторые изменения для улучшения как производительности системы, так и ее безопасности. Большинство улучшений производительности было сосредоточено на ускорении процесса. Вплоть до 2005 года можно найти литературу, описывающую сбои дешифрования NTRUEncrypt. Что касается безопасности, начиная с первой версии NTRUEncrypt, были введены новые параметры, которые кажутся безопасными для всех известных в настоящее время атак и разумного увеличения вычислительной мощности.

Теперь система полностью соответствует стандартам IEEE P1363 в соответствии со спецификациями решетчатой ​​криптографии с открытым ключом (IEEE P1363.1 Из-за быстродействия криптосистемы с открытым ключом NTRUEncrypt (см. http://bench.cr.yp.to для результатов тестирования) и низким потреблением памяти (см. ниже )^{[сомнительный – обсуждать]}, его можно использовать в таких приложениях, как мобильные устройства и Смарт-карты В апреле 2011 года NTRUEncrypt был принят в качестве стандарта X9.98 для использования в индустрии финансовых услуг.^[2]

Генерация открытого ключа

Для отправки секретного сообщения от Алисы Бобу требуется генерация открытого и закрытого ключей. Открытый ключ известен как Алисе, так и Бобу, а закрытый ключ известен только Бобу. Для генерации ключевой пары два многочлена ж и грамм, со степенью не выше ${ Displaystyle N-1}$ и с коэффициентами в {-1,0,1} не требуется. Их можно рассматривать как представления классов вычетов многочленов по модулю ${ Displaystyle X ^ {N} -1}$ в р. Полином ${ displaystyle { textbf {f}} in L_ {f}}$ должен удовлетворять дополнительному требованию, что обратные по модулю q и по модулю п (вычислено с использованием Евклидов алгоритм ) существуют, что означает, что ${ displaystyle { textbf {f}} cdot { textbf {f}} _ {p} = 1 { pmod {p}}}$ и ${ displaystyle { textbf {f}} cdot { textbf {f}} _ {q} = 1 { pmod {q}}}$ должен держаться. Итак, когда выбранный ж необратим, Боб должен вернуться и попробовать другой ж.

Обе ж и ${ displaystyle mathbf {f} _ {p}}$ (и ${ displaystyle g}$) - закрытый ключ Боба. Открытый ключ час генерируется вычислением количества

${ displaystyle { textbf {h}} = p { textbf {f}} _ {q} cdot { textbf {g}} { pmod {q}}.}$

Пример: В этом примере параметры (N, п, q) будет иметь значения N = 11, п = 3 и q = 32 и, следовательно, многочлены ж и грамм имеют степень не выше 10. Параметры системы (N, п, q) известны всем. Многочлены выбираются случайным образом, поэтому предположим, что они представлены

${ displaystyle { textbf {f}} = - 1 + X + X ^ {2} -X ^ {4} + X ^ {6} + X ^ {9} -X ^ {10}}$

${ displaystyle { textbf {g}} = - 1 + X ^ {2} + X ^ {3} + X ^ {5} -X ^ {8} -X ^ {10}}$

Используя алгоритм Евклида, обратное ж по модулю п и по модулю q, соответственно, вычисляется

${ displaystyle { textbf {f}} _ {p} = 1 + 2X + 2X ^ {3} + 2X ^ {4} + X ^ {5} + 2X ^ {7} + X ^ {8} + 2X ^ {9} { pmod {3}}}$

${ displaystyle { textbf {f}} _ {q} = 5 + 9X + 6X ^ {2} + 16X ^ {3} + 4X ^ {4} + 15X ^ {5} + 16X ^ {6} + 22X ^ {7} + 20X ^ {8} + 18X ^ {9} + 30X ^ {10} { pmod {32}}}$

Что создает открытый ключ час (известный как Алисе, так и Бобу) вычисление продукта

${ displaystyle { textbf {h}} = p { textbf {f}} _ {q} cdot { textbf {g}} { pmod {32}} = 8-7X-10X ^ {2} - 12X ^ {3} + 12X ^ {4} -8X ^ {5} + 15X ^ {6} -13X ^ {7} + 12X ^ {8} -13X ^ {9} + 16X ^ {10} { pmod {32}}}$

Шифрование

Алиса, которая хочет отправить секретное сообщение Бобу, помещает свое сообщение в форму многочлена м с коэффициентами в ${ displaystyle [-p / 2, p / 2]}$ . В современных приложениях шифрования полином сообщения может быть преобразован в двоичное или троичное представление. После создания полинома сообщения Алиса случайным образом выбирает полином. р с небольшими коэффициентами (не ограниченными набором {-1,0,1}), что предназначено для того, чтобы скрыть сообщение.

С открытым ключом Боба час зашифрованное сообщение е вычисляется:

${ displaystyle { textbf {e}} = { textbf {r}} cdot { textbf {h}} + { textbf {m}} { pmod {q}}}$

Этот зашифрованный текст скрывает сообщения Алисы и может быть безопасно отправлен Бобу.

Пример: Предположим, что Алиса хочет отправить сообщение, которое можно записать как полиномиальное.

${ displaystyle { textbf {m}} = - 1 + X ^ {3} -X ^ {4} -X ^ {8} + X ^ {9} + X ^ {10}}$

и что случайно выбранная «ослепляющая ценность» может быть выражена как

${ displaystyle { textbf {r}} = - 1 + X ^ {2} + X ^ {3} + X ^ {4} -X ^ {5} -X ^ {7}}$

Зашифрованный текст е который представляет ее зашифрованное сообщение Бобу, будет выглядеть как

${ displaystyle { textbf {e}} = { textbf {r}} cdot { textbf {h}} + { textbf {m}} { pmod {32}} = 14 + 11X + 26X ^ { 2} + 24X ^ {3} + 14X ^ {4} + 16X ^ {5} + 30X ^ {6} + 7X ^ {7} + 25X ^ {8} + 6X ^ {9} + 19X ^ {10} { pmod {32}}}$

Расшифровка

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

${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {q}}}$

Переписывая полиномы, это уравнение фактически представляет следующие вычисления:

${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {q}}}$

${ displaystyle { textbf {a}} = { textbf {f}} cdot ({ textbf {r}} cdot { textbf {h}} + { textbf {m}}) { pmod { q}}}$

${ displaystyle { textbf {a}} = { textbf {f}} cdot ({ textbf {r}} cdot p { textbf {f}} _ {q} cdot { textbf {g} } + { textbf {m}}) { pmod {q}}}$

${ displaystyle { textbf {a}} = p { textbf {r}} cdot { textbf {g}} + { textbf {f}} cdot { textbf {m}} { pmod {q }}}$

Вместо выбора коэффициентов при а от 0 до q - 1 они выбираются в интервале [-q/2, q/ 2], чтобы предотвратить восстановление исходного сообщения должным образом, так как Алиса выбирает координаты своего сообщения. м в интервале [-п/2, п/ 2]. Отсюда следует, что все коэффициенты при ${ displaystyle p { textbf {r}} cdot { textbf {g}} + { textbf {f}} cdot { textbf {m}}}$ уже лежат в интервале [-q/2, q/ 2], поскольку многочлены р, грамм, ж и м и премьер п все имеют коэффициенты, которые малы по сравнению с q. Это означает, что все коэффициенты остаются неизменными при приведении по модулю q и что исходное сообщение может быть восстановлено должным образом.

Следующим шагом будет вычисление а по модулю п:

${ displaystyle { textbf {b}} = { textbf {a}} { pmod {p}} = { textbf {f}} cdot { textbf {m}} { pmod {p}}}$

потому что ${ displaystyle p { textbf {r}} cdot { textbf {g}} { pmod {p}} = 0}$.

Зная б Боб может использовать другую часть своего закрытого ключа ${ displaystyle left ({ textbf {f}} _ {p} right)}$ восстановить сообщение Алисы путем умножения б и ${ displaystyle { textbf {f}} _ {p}}$

${ displaystyle { textbf {c}} = { textbf {f}} _ {p} cdot { textbf {b}} = { textbf {f}} _ {p} cdot { textbf {f }} cdot { textbf {m}} { pmod {p}}}$

${ displaystyle { textbf {c}} = { textbf {m}} { pmod {p}}}$

потому что собственность ${ displaystyle { textbf {f}} cdot { textbf {f}} _ {p} = 1 { pmod {p}}}$ требовалось для ${ displaystyle { textbf {f}} _ {p}}$.

Пример: Зашифрованное сообщение е от Алисы до Боба умножается на полином ж

${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {32}} = 3-7X-10X ^ {2} -11X ^ {3} + 10X ^ {4} + 7X ^ {5} + 6X ^ {6} + 7X ^ {7} + 5X ^ {8} -3X ^ {9} -7X ^ {10} { pmod {32}}, }$

где Боб использует интервал [-q/2, q/ 2] вместо интервала [0, q - 1] для коэффициентов полинома а чтобы предотвратить некорректное восстановление исходного сообщения.

Уменьшение коэффициентов а мод п приводит к

${ displaystyle { textbf {b}} = { textbf {a}} { pmod {3}} = - XX ^ {2} + X ^ {3} + X ^ {4} + X ^ {5} + X ^ {7} -X ^ {8} -X ^ {10} { pmod {3}}}$

что равно ${ displaystyle { textbf {b}} = { textbf {f}} cdot { textbf {m}} { pmod {3}}}$.

На последнем этапе результат умножается на ${ displaystyle { textbf {f}} _ {p}}$ из закрытого ключа Боба, чтобы получить исходное сообщение м

${ displaystyle { textbf {c}} = { textbf {f}} _ {p} cdot { textbf {b}} = { textbf {f}} _ {p} cdot { textbf {f }} cdot { textbf {m}} { pmod {3}} = { textbf {m}} { pmod {3}}}$

${ displaystyle { textbf {c}} = - 1 + X ^ {3} -X ^ {4} -X ^ {8} + X ^ {9} + X ^ {10}}$

Это действительно исходное сообщение, которое Алиса отправила Бобу!

Атаки

С момента предложения NTRU было проведено несколько атак на криптосистему с открытым ключом NTRUEncrypt. Большинство атак нацелены на полное взломание путем нахождения секретного ключа. ж вместо того, чтобы просто восстановить сообщение м.Если ж известно, что у нее очень мало ненулевых коэффициентов, Ева может успешно установить атака грубой силой попробовав все значения для ж. Когда Ева хочет знать, ж´ - секретный ключ, она просто вычисляет ${ displaystyle { textbf {f}} ^ {'} cdot { textbf {h}} { pmod {q}}}$. Если у него маленькие коэффициенты, это может быть секретный ключ ж, и Ева может проверить, ж´ является секретным ключом, с помощью которого она расшифровывает зашифрованное ею сообщение. Ева также может попробовать значения грамм и проверьте, если ${ displaystyle { textbf {g}} ^ {'} cdot { textbf {h}} ^ {- 1} { pmod {q}}}$имеет небольшие значения.

Возможна установка атака встречей посередине который более мощный. Это может сократить время поиска на квадратный корень. Атака основана на том свойстве, что ${ displaystyle { textbf {f}} cdot { textbf {h}} = p { textbf {g}} { pmod {q}}}$.

Ева хочет найти ${ displaystyle { textbf {f}} _ {1}}$ и ${ displaystyle { textbf {f}} _ {2}}$ такой, что ${ displaystyle { textbf {f}} = { textbf {f}} _ {1} + { textbf {f}} _ {2}}$ имеет место и такое, что они обладают свойством

${ displaystyle left ({ textbf {f}} _ {1} + { textbf {f}} _ {2} right) cdot { textbf {h}} = { textbf {g}} { pmod {q}}}$

${ displaystyle { textbf {f}} _ {1} cdot { textbf {h}} = { textbf {g}} - { textbf {f}} _ {2} cdot { textbf {h }} { pmod {q}}}$

Если ж имеет d один и N-d нулей, то Ева создает все возможные ${ displaystyle { textbf {f}} _ {1}}$ и ${ displaystyle { textbf {f}} _ {2}}$ в котором они оба имеют длину ${ displaystyle { frac {1} {2}} N}$ (например. ${ displaystyle { textbf {f}} _ {1}}$ охватывает ${ displaystyle { frac {1} {2}} N}$ наименьшие коэффициенты ж и ${ displaystyle { textbf {f}} _ {2}}$ самый высокий) с d/ 2 шт. Затем она вычисляет ${ displaystyle { textbf {f}} _ {1} cdot { textbf {h}} { pmod {q}}}$ для всех ${ displaystyle { textbf {f}} _ {1}}$ и упорядочивает их по ячейкам на основе первых k координат. После этого она вычисляет все ${ displaystyle - { textbf {f}} _ {2} cdot { textbf {h}} { pmod {q}}}$ и упорядочивает их в ячейках не только на основе первых k координат, но и на основе того, что произойдет, если вы добавите 1 к первым k координатам. Затем вы проверяете корзины, содержащие оба ${ displaystyle { textbf {f}} _ {1}}$ и ${ displaystyle { textbf {f}} _ {2}}$ и посмотрим, ${ displaystyle { textbf {f}} _ {1} cdot { textbf {h}} = { textbf {g}} - { textbf {f}} _ {2} cdot { textbf { h}} { pmod {q}}}$ держит.

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

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

Как это устроено:

Первая Ева создает зашифрованный текст ${ displaystyle { textbf {e}} = c { textbf {h}} + c}$ такой, что ${ displaystyle c = 0 { pmod {p}}, c <{ frac {q} {2}}}$ и ${ displaystyle 2c> { frac {q} {2}}}$ Когда Ева записывает шаги для расшифровки e (без фактического вычисления значений, поскольку она не знает f), она находит ${ displaystyle { textbf {a}} = { textbf {f}} cdot { textbf {e}} { pmod {q}}}$:

${ displaystyle { textbf {a}} = { textbf {f}} left (c { textbf {h}} + c right) { pmod {q}}}$

${ displaystyle { textbf {a}} = c { textbf {g}} + c { textbf {f}} { pmod {q}}}$

${ displaystyle { textbf {a}} = c { textbf {g}} + c { textbf {f}} - qK}$

В котором ${ Displaystyle К = сумма к_ {я} х ^ {я}}$ такой, что

${ displaystyle k_ {i} = { begin {case} 1 qquad { text {if the}} i ^ {th} { text {коэффициент}} { textbf {f}} { text {and}} { textbf {g}} { text {is}} 1 - 1 qquad { text {если}} i ^ {th} { text {коэффициент}} { textbf {f}} { text {and}} { textbf {g}} { text {is}} -1 0 qquad { text {В противном случае}} end {case}}}$

Пример:

${ displaystyle { textbf {f}} = - 1 + X + X ^ {2} -X ^ {4} + X ^ {6} + X ^ {9} -X ^ {10}}$

${ displaystyle { textbf {g}} = - 1 + X ^ {2} + X ^ {3} + X ^ {5} -X ^ {8} -X ^ {10}}$

потом K становится ${ displaystyle K = -1 + X ^ {2} -X ^ {10}}$.

Уменьшение коэффициентов многочленов а мод п действительно снижает коэффициенты ${ displaystyle c { textbf {g}} + c { textbf {f}} - qK { pmod {p}}}$. После умножения на ${ displaystyle { textbf {f}} _ {p}}$, Ева находит:

${ displaystyle { textbf {m}} = c { textbf {f}} _ {p} cdot { textbf {g}} + c { textbf {f}} _ {p} cdot { textbf {f}} - q { textbf {f}} _ {p} cdot K { pmod {p}}}$

${ displaystyle { textbf {m}} = c { textbf {h}} + c-q { textbf {f}} _ {p} cdot K { pmod {p}}}$

Поскольку c было выбрано кратным п, м можно записать как

${ displaystyle { textbf {m}} = - q { textbf {f}} _ {p} cdot K { pmod {p}}}$

Что обозначает ${ displaystyle { textbf {f}} = - qK cdot { textbf {m}} ^ {- 1} { pmod {p}}}$.

Сейчас если ж и грамм имеют несколько одинаковых коэффициентов при одних и тех же факторах, K имеет несколько ненулевых коэффициентов и поэтому мал. Пробуя разные значения K злоумышленник может восстановиться ж.

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

Улучшения безопасности и производительности

Используя последние предложенные параметры (см. ниже ) криптосистема с открытым ключом NTRUEncrypt безопасна для большинства атак. Однако продолжается борьба между производительностью и безопасностью. Трудно повысить безопасность без снижения скорости, и наоборот.

Один из способов ускорить процесс без ущерба для эффективности алгоритма - внести некоторые изменения в секретный ключ. ж. Во-первых, построить ж такой, что ${ displaystyle { textbf {f}} = 1 + p { textbf {F}}}$, в котором F является малым многочленом (т.е. коэффициентами {-1,0, 1}). Построив ж Сюда, ж обратимый мод п. Фактически ${ displaystyle { textbf {f}} ^ {- 1} = 1 { pmod {p}}}$, что означает, что Бобу не нужно фактически вычислять обратное, и что Бобу не нужно проводить второй этап дешифрования. Следовательно, построение ж таким образом экономится много времени, но он не влияет на безопасность NTRUEncrypt, потому что его легче найти ${ displaystyle { textbf {f}} _ {p}}$ но ж все еще трудно восстановить. В этом случае ж имеет коэффициенты, отличные от -1, 0 или 1, из-за умножения на п. Но поскольку Боб умножает на п для генерации открытого ключа час, а затем сокращает зашифрованный текст по модулю п, это не повлияет на метод шифрования.

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

В большинстве коммерческих приложений NTRUEncrypt параметр N= 251. Чтобы избежать решетчатых атак, атак грубой силы и атак типа "встреча посередине", ж и грамм должно иметь около 72 ненулевых коэффициентов.

Согласно последним исследованиям ^[3] следующие параметры считаются безопасными:

Таблица 1: Параметры

Рекомендации

• Jaulmes, E. и Joux, A. Атака с выбранным зашифрованным текстом против NTRU. Конспект лекций по информатике; Vol 1880. Труды 20-й Ежегодной Международной криптологической конференции по достижениям в криптографии. С. 20–35, 2000.
• Джеффри Хоффштейн, Джилл Пайфер, Джозеф Х. Сильверман. NTRU: криптосистема с открытым ключом на основе кольца. В теории алгоритмических чисел (ANTS III), Портленд, штат Орегон, июнь 1998 г., J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.
• Хоугрейв-Грэм, Н., Сильверман, Дж. И Уайт, В., Атака Meet-In-The-Middle на закрытый ключ NTRU.
• Дж. Хоффштейн, Дж. Сильверман. Оптимизация для NTRU. Криптография с открытым ключом и теория вычислительных чисел (Варшава, 11–15 сентября 2000 г.), DeGruyter, чтобы появиться.
• A. C. Atici, L. Batina, J. Fan, I. Verbauwhede. Недорогие реализации NTRU для всеобъемлющей безопасности.

внешняя ссылка

• Технический сайт НТРУ
• Домашняя страница IEEE P1363
• Security Innovation (приобретена NTRU Cryptosystems, Inc.)
• Реализация лицензии BSD с открытым исходным кодом для NTRUEncrypt
• Лицензия GPL v2 с открытым исходным кодом для NTRUEncrypt
• Решение strongSwan с открытым исходным кодом IPsec с использованием обмена ключами на основе NTRUEncrypt
• - Встроенная библиотека SSL / TLS, предлагающая наборы шифров с использованием NTRU (wolfSSL)