NTRUEncrypt

NTRUEncrypt (аббревиатура Nth-degree TRUncated polynomial ring или Number Theorists aRe Us) — это криптографическая система с открытым ключом, ранее называвшаяся NTRU.

Криптосистема NTRUEncrypt, основанная на решёточной криптосистеме, создана в качестве альтернативы RSA и криптосистемам на эллиптических кривых (ECC). Стойкость алгоритма обеспечивается трудностью поиска кратчайшего вектора решётки (англ.), которая более стойкая к атакам, осуществляемым на квантовых компьютерах. В отличие от своих конкурентов RSA, ECC, Elgamal, алгоритм использует операции над кольцом усечённых многочленов степени, не превосходящей :

Такой многочлен можно также представить вектором

Как и любой молодой алгоритм, NTRUEncrypt плохо изучен, хотя и был официально утверждён для использования в сфере финансов комитетом Accredited Standards Committee X9.[1]

Существует реализации NTRUEncrypt с открытым исходным кодом.[2]

ИсторияПравить

NTRUEncrypt, изначально называвшийся NTRU, был изобретён в 1996 году и представлен миру на конференциях CRYPTO (англ.), Конференция RSA, Eurocrypt (англ.). Причиной, послужившей началом разработки алгоритма в 1994 году, стала статья[3], в которой говорилось о лёгкости взлома существующих алгоритмов на квантовых компьютерах, которые, как показало время, не за горами[4]. В этом же году, математики Jeffrey Hoffstein, Jill Pipher и Joseph H. Silverman, разработавшие систему вместе с основателем компании NTRU Cryptosystems, Inc. (позже переименованной в SecurityInnovation), Даниелем Лиеманом (Daniel Lieman) запатентовали своё изобретение.[5]

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

NTRU оперирует над многочленами степени не превосходящей  

 

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

NTRU использует кольцо усечённых многочленов R совместно с делением по модулю на взаимно простые числа p и q для уменьшения коэффициентов многочленов.

В работе алгоритма также используются обратные многочлены в кольце усечённых многочленов. Следует отметить, что не всякий многочлен имеет обратный, но если обратный полином существует, то его легко вычислить.[6][7]

В качестве примера будут выбраны следующие параметры:

Обозначения параметров N q p
Значения параметров 11 32 3

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

Для передачи сообщения от Алисы к Бобу необходимы открытый и закрытый ключи. Открытый знают как Боб, так и Алиса, закрытый ключ знает только Боб, который он использует для генерации открытого ключа. Для этого Боб выбирает два «маленьких» полинома f g из R. «Малость» полиномов подразумевается в том смысле, что он маленький относительно произвольного полинома по модулю q: в произвольном полиноме коэффициенты должны быть примерно равномерно распределены по модулю q, а в малом полиноме они много меньше q. Малость полиномов определяется с помощью чисел df и dg:

  • Полином f имеет df коэффициентов равных «1» и df-1 коэффициентов равных «-1», а остальные — «0». В этом случае говорят, что  
  • Полином g имеет dg коэффициентов равных «1» и столько же равных «-1», остальные — «0». В этом случае говорят, что  

Причина, по которой полиномы выбираются именно таким образом, заключается в том, что f , возможно, будет иметь обратный, а g — однозначно нет (g (1) = 0, а нулевой элемент не имеет обратного).

Боб должен хранить эти полиномы в секрете. Далее Боб вычисляет обратные полиномы   и  , то есть такие, что:

  и  .

Если f не имеет обратного полинома, то Боб выбирает другой полином f.

Секретный ключ — это пара  , а открытый ключ h вычисляется по формуле:

 
Пример

Для примера возьмем df=4, а dg=3. Тогда в качестве полиномов можно выбрать

 
 

Далее для полинома f ищутся обратные полиномы по модулю p=3 и q=32:

 
 

Заключительным этапом является вычисление самого открытого ключа h:

 

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

Теперь, когда у Алисы есть открытый ключ, она может отправить зашифрованное сообщение Бобу. Для этого нужно сообщение представить в виде полинома m с коэффициентами по модулю p, выбранными из диапазона (-p/2, p/2]. То есть m является «малым» полиномом по модулю q. Далее Алисе необходимо выбрать другой «малый» полином r, который называется «ослепляющим», определяемый с помощью числа dr:

  • Полином r имеет dr коэффициентов равных «1» и столько же равных «-1», остальные — «0». В этом случае говорят, что  

Используя эти полиномы, зашифрованное сообщение получается по формуле:

 

При этом любой, кто знает (или может вычислить) ослепляющий полином r, сможет прочесть сообщение m.

Пример

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

 

и выбрала «ослепляющий» полином, для которого dr=3:

 

Тогда шифротекст e, готовый для передачи Бобу будет:

 

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

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

 

Если расписать шифротекст, то получим цепочку:

 

и окончательно:

 

После того, как Боб вычислил полином a по модулю q, он должен выбрать его коэффициенты из диапазона (-q/2, q/2] и далее вычислить полином b, получаемый из полинома a приведением по модулю p:

 

так как  .

Теперь, используя вторую половину секретного ключа и полученный полином b, Боб может расшифровать сообщение:

 

Нетрудно видеть, что

 

Таким образом полученный полином c действительно является исходным сообщением m.

Пример: Боб получил от Алисы шифрованное сообщение e

 

Используя секретный ключ f Боб получает полином a

 

с коэффициентами, принадлежащими промежутку (-q/2, q/2]. Далее преобразует полином a в полином b, уменьшая коэффициенты по модулю p.

 

Заключительный шаг — перемножение полинома b со второй половиной закрытого ключа  

 
 

Который является исходным сообщением, которое передавала Алиса.

Стойкость к атакамПравить

Полный переборПравить

Первая из возможных атак — атака перебором. Тут возможно несколько вариантов перебора: либо перебирать все  , и проверять на малость коэффициенты полученных результатов  , которые, по задумке, должны были быть малыми, либо перебирать все  , также проверяя на малость коэффициенты результата  . На практике пространство   меньше пространства  , следовательно стойкость определяется пространством  . А стойкость отдельного сообщения определяется пространством  .

Встреча посерединеПравить

Существует более оптимальный вариант перебора встреча посередине, предложенный Эндрю Одлыжко[en]. Этот метод уменьшает количество вариантов до квадратного корня:

Стойкости закрытого ключа =   =  ,

И стойкости отдельного сообщения =   =  .

Атака «встреча посередине» позволяет разменять время, необходимое для вычислений на память, необходимую для хранения временных результатов. Таким образом, если мы хотим обеспечить стойкость системы  , нужно выбрать ключ размера  .

Атака на основе множественной передачи сообщенияПравить

Довольно серьёзная атака на отдельное сообщение, которую можно избежать, следуя простому правилу — не пересылать многократно одно и то же сообщение. Суть атаки заключается в нахождении части коэффициентов ослепляющего многочлена r. А остальные коэффициенты можно просто перебрать, тем самым прочитав сообщение. Так как зашифрованное одно и то же сообщение с разными ослепляющими многочленами это  , где i=1, … n. Можно вычислить выражение  , которое в точности равно  . Для достаточно большого количества переданных сообщений (скажем, для n = 4, 5, 6), можно восстановить, исходя из малости коэффициентов, большую часть ослепляющего многочлена  .

Атака на основе решёткиПравить

Рассмотрим решётку, порождённую строками матрицы размера 2N×2N с детерминантом  , состоящей из четырёх блоков размера N×N:

 

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

Атака на основе подобранного шифротекстаПравить

Атака на основе подобранного шифротекста является наиболее опасной атакой. Её предложили Éliane Jaulmes и Antoine Joux[8] в 2000 году на конференции CRYPTO. Суть этой атаки заключается в подборе такого многочлена a(x), чтобы  . При этом Ева не взаимодействует ни с Бобом, ни с Алисой.

Если взять шифротекст  , где  , то получим многочлен  . Так как коэффициенты многочленов f и g принимают значения «0», «1» и «-1», то коэффициенты многочлена a будут принадлежать множеству {-2py , -py , 0, py, 2py}. Если py выбрать таким, что  , то при сведении по модулю полинома a(x) приведутся только коэффициенты равные -2py или 2py. Пусть теперь i-ый коэффициент равен 2py, тогда многочлен a(x) после приведения по модулю запишется как:

 ,

а многочлен b(x):

 ,

окончательно вычислим:

 .

Теперь, если рассмотреть все возможные i, то вместо отдельных  , можно составить полином K и расшифрованное сообщение примет вид:

 ,

или, секретный ключ:

 ,

Вероятность таким образом отыскать составляющие ключа составляет порядка 0,1 … 0,3 для ключа размера 100. Для ключей большого размера (~500) эта вероятность очень мала. Применив данный метод достаточное количество раз, можно полностью восстановить ключ.

Для защиты от атаки такого типа используется расширенный метод шифрования NTRU-FORST. Для шифрования используется ослепляющий многочлен  , где H — криптографически-стойкая хеш-функция, а R — случайный набор бит. Получив сообщение, Боб расшифровывает его. Далее Боб шифрует только что расшифрованное сообщение, таким же образом, что и Алиса. После сверяет его на соответствие с полученным. Если сообщения идентичные, то Боб принимает сообщение, иначе отбраковывает.

Параметры стойкости и быстродействиеПравить

Несмотря на то, что существуют быстрые алгоритмы поиска обратного полинома, разработчики предложили для коммерческого применения в качестве секретного ключа f брать:

 ,

где F — малый полином. Таким образом выбранный ключ обладает следующими преимуществами:

  • f всегда имеет обратный по модулю p, а именно  .
  • Так как   нам больше не нужно при расшифровке умножать на обратный полином  , и он выпадает из разряда секретного ключа.

Одно из исследований Архивная копия от 6 октября 2016 на Wayback Machine показало, что NTRU на 4 порядка быстрее RSA и на 3 порядка — ECC.

Как уже упоминалось ранее разработчики, для обеспечения высокой стойкости алгоритма, предлагают использовать только рекомендованные параметры, обозначенные в таблице:

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

Обозначение N q p df dg dr Гарантированная стойкость
NTRU167:3 167 128 3 61 20 18 Умеренный уровень стойкости
NTRU251:3 251 128 3 50 24 16 Стандартный уровень стойкости
NTRU503:3 503 256 3 216 72 55 Высочайший уровень стойкости
NTRU167:2 167 127 2 45 35 18 Умеренный уровень стойкости
NTRU251:2 251 127 2 35 35 22 Стандартный уровень стойкости
NTRU503:2 503 253 2 155 100 65 Высочайший уровень стойкости

ПримечанияПравить

  1. Security Innovation’s NTRUEncrypt Adopted as X9 Standard for Data Protection. Дата обращения: 15 марта 2022. Архивировано 13 августа 2016 года.
  2. NTRUEncrypt и NTRUSign в Java. Дата обращения: 1 ноября 2011. Архивировано 19 ноября 2011 года.
  3. Algorithms for quantum computation: discrete logarithms and factoring (недоступная ссылка). Дата обращения: 30 октября 2011. Архивировано 18 июня 2010 года.
  4. NIST demonstrates 'universal' programmable quantum processor. Дата обращения: 30 октября 2011. Архивировано 30 ноября 2011 года.
  5. NTRU Public Key Algorithms IP Assurance Statement for 802.15.3. Дата обращения: 30 октября 2011. Архивировано 9 апреля 2016 года.
  6. J. H. Silverman, Almost Inverses and Fast NTRU Key Creation Архивная копия от 24 марта 2012 на Wayback Machine, NTRU Cryptosystems Technical Report # 014.
  7. J. H. Silverman, Invertibility in Truncated Polynomial Rings Архивная копия от 14 мая 2012 на Wayback Machine, NTRU Cryptosystems Technical Report # 009.
  8. Jaulmes É., Joux A. A chosen-ciphertext attack against NTRU //Annual International Cryptology Conference. – Springer, Berlin, Heidelberg, 2000. – С. 20-35.

СсылкиПравить