Я делаю проект, где мне нужно реализовать криптосистему открытого ключа NTRUEncrypt. Это первый шаг в соответствии с их руководством по шифрованию - «Алиса, которая хочет отправить секретное сообщение Бобу, ставит свое сообщение в виде полинома m с коэффициентами {-1,0,1}». Я хочу знать, как я могу превратить свое сообщение в полином. Спасибо.Как сделать сообщение в полином?
Вы можете сделать это, как вам нравится. Пожалуй, самые простой способ, чтобы преобразовать ваше сообщение в тройное представление
"Hello" -> 72, 101, 108, 108, 111 -> 02200, 10202, 11000, 11000, 11010
Так я превращающий символы в их ASCII представление, а затем преобразование этих представлений в их тройном представления (при условии, что я ограничен в 7-битное пространство ASCII Мне нужны только пять тройных цифр).
Затем преобразовать трехкомпонентное представление в виде многочлена на {-1, 0, 1} путем сопоставления тройной цифры 0 к 0, тройной цифре 1 к 1 и тройной цифре 2 к -1 и предполагая, что цифра, соответствующая 3^к является коэффициентом х^к :
02200 -> p1(x) = 0 + 0 * x + (-1) * x^2 + (-1) * x^3 + 0 * x^4
10202 -> p2(x) = (-1) + 0 * x + (-1) * x^2 + 0 * x^3 + 1 * x^4
11000 -> p3(x) = 0 + 0 * x + 0 * x^2 + 1 * x^3 + 1 * x^4
11000 -> p4(x) = 0 + 0 * x + 0 * x^2 + 1 * x^3 + 1 * x^4
11010 -> p5(x) = 0 + 1 * x + 0 * x^2 + 1 * x^3 + 1 * x^4
, а затем мое сообщение
p1(x) + x^5 * p2(x) + (x^5)^2 * p3(x) + (x^5)^3 * p4(x) + (x^5)^4 * p5(x)
так, что коэффициенты моего полиномиальных являются
(0, 0, -1, -1, 0, -1, 0, -1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1).
Независимо от того, как вы это делаете, дело в том, что вы можете представить ваше сообщение в виде полинома, как вам нравится. Это просто предпочтителен, что вы найдете биекцию из вашего пространства сообщений в пространство полиномов по {-1, 0, 1}, которое легко вычисляется и имеет легко вычисляемый обратный.
Это суть трансформации. Пять-значный номер тройная a4a3a2a1a0 точно соответствует оценке полинома a4* x^4 + a3* x^3 + a2* x^2 +a1* x + a0* x^0 в x = 3. Таким образом, существует очевидное взаимно однозначное соответствие между многочленами на {-1, 0, 1} и тройными числами.
Хороший ответ. Мог бы указать более общий подход к генерации случайного симметричного ключа, а затем шифрование _that_ с помощью алгоритма с открытым ключом. –
Это действительно полезный ответ, но я хотел бы указать несколько деталей, которые мне непонятно. Почему вы выражаете пятизначную тройку как a4a3a2a1a0, а не назад, от 0 до 4? Это важно как-то? Также я не понимаю, почему x = 3. Что это значит? И когда вы делаете свое сообщение как p1 (x) + x^5 * p2 (x) + (x^5)^2 * p3 (x) + (x^5)^3 * p4 (x) + (x^5)^4 * p5 (x) - мощность x - это сообщение с пятью причинами, состоящее из 5 символов, верно? Извините за то, что задал все эти глупые вопросы, но мне действительно нужно понять, как работает материал. –
@ Андрей Чернуха: * Почему вы выражаете пятизначную тройку как a4a3a2a1a0, а не назад, от 0 до 4? * Стандартная практика - дать индекс индекса (т. Е. 0, 1, 2 и т. Д.). то же значение, что и значение экспоненты (т. е. 'a_j" соответствует коэффициенту 'x^j'). * Это важно как-то? * Только постольку, поскольку это стандартная практика, и это облегчает последующие действия. Вы могли бы, если хотите, написать 'a33a52a21a104a69' и объявить, что' a69' является коэффициентом 'x^0' и т. Д., Но вы быстро потеряете читателей, так как гораздо труднее следовать. – jason
Я работаю для NTRU, поэтому я рад видеть этот интерес.
Стандарт IEEE 1363.1-2008 указывает, как реализовать NTRUEncrypt с самыми последними наборами параметров.Метод он определяет для бинарно> преобразования Trinary является:
Преобразовать каждое три-битное число до двух тройных коэффициентов следующего образом, а конкатенации результирующих тройных количеств, чтобы получить [выход].
{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}
Для того, чтобы преобразовать обратно:
Преобразования каждый набора из двух тройных коэффициентов к трем битам следующим образом, и конкатенация результирующему биту количеств, чтобы получить [выход]:
{0, 0} -> {0, 0, 0}
{0, 1} -> {0, 0, 1}
{0, -1} -> {0, 1, 0}
{1, 0} -> {0, 1, 1}
{1, 1} -> {1, 0, 0}
{1, -1} -> {1, 0, 1}
{-1, 0} -> {1, 1, 0}
{-1, 1} -> {1, 1, 1}
{-1, -1} -> set "fail" to 1 and set bit string to {1, 1, 1}
Обратите внимание, что на e ncrypt сообщение безопасно, вы не можете просто преобразовать сообщение в trinary и применить необработанное шифрование NTRU. Сообщение должно быть предварительно обработано перед шифрованием и после обработки после шифрования для защиты от активных злоумышленников, которые могут модифицировать сообщение в пути. Необходимая обработка указана в IEEE Std 1363.1-2008 и обсуждена в нашей статье 2003 года «NAEP: Обеспечиваемая безопасность при наличии ошибок дешифрования» (доступно от http://www.ntru.com/cryptolab/articles.htm#2003_3, хотя имейте в виду, что это описание ориентировано на двоичные полиномы, а не на триниальный) ,
Надеюсь, это поможет.
@Bert: в разное время мы рекомендовали бинарные или триниальные полиномы. Триномиальные многочлены допускают одну и ту же безопасность с более короткими ключами. Однако в прошлом мы думали, что бинарные полиномы позволили q (большой модуль) быть 256. Это было привлекательно для 8-битных процессоров. С тех пор мы установили, что принятие q = 256 снижает безопасность неприемлемо (в частности, это приводит к ошибкам дешифрования). Поскольку у нас больше нет цели q, мы можем использовать триниальные полиномы, чтобы дать более мелкие ключи в целом.
Если вы намерены полагаться на эту реализацию для обеспечения безопасности, а не на то, что она носит педагогический характер, вы находитесь в мире обид. – retracile