Как превратить сообщение в полином?

Question

Я делаю проект, в котором мне нужно внедрить криптосистему с открытым ключом NTRUEncrypt. Это первый шаг согласно их руководству по шифрованию - «Алиса, которая хочет отправить секретное сообщение Бобу, помещает свое сообщение в виде полинома m с коэффициентами {-1,0,1}». Я хочу знать, как я могу превратить свое сообщение в полином. Спасибо.

Answer 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 ^ k, является коэффициентом x ^ k ¹ :

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} и троичными числами.

Answer 2

Я работаю в NTRU, поэтому я рад видеть этот интерес.

Стандарт IEEE 1363.1-2008 определяет, как реализовать NTRUEncrypt с самыми последними наборами параметров. Метод, который он определяет для двоичного-> тройного преобразования:

Преобразовать каждое трехразрядное число в два троичные коэффициенты следующим образом, и объединить полученную тройную количества, чтобы получить [выход].

{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}

Обратите внимание, что для безопасного шифрования сообщения вы не можете просто преобразовать сообщение в триное и применить необработанное шифрование NTRU. Сообщение должно быть предварительно обработано перед шифрованием и постобработано после шифрования для защиты от активных злоумышленников, которые могут изменить сообщение при передаче. Необходимая обработка указана в стандарте IEEE 1363.1-2008 и обсуждается в нашей статье 2003 года «NAEP: Обеспечиваемая безопасность при наличии ошибок дешифрования» (доступно из http://www.ntru.com/cryptolab/articles.htm#2003_3,, хотя следует учитывать, что это описание предназначено для двоичных полиномов а не трина).

Надеюсь, это поможет.

@ Берт: в разное время мы рекомендовали двоичные или тройные полиномы. Тройной многочлен обеспечивает одинаковую защиту с более короткими ключами. Однако в прошлом мы думали, что двоичные полиномы позволяют q (большой модуль) быть 256. Это было привлекательным для 8-битных процессоров. С тех пор мы установили, что принятие значения q = 256 неприемлемо снижает безопасность (в частности, слишком высока вероятность ошибок дешифрования). Поскольку у нас больше нет маленькой буквы q в качестве цели, мы можем воспользоваться тройными полиномами, чтобы получить меньшие ключи в целом.