Атака на NTRU

[Alex_CAPS]

Дамы и господа, поздравляю всех с новым годом! А теперь к делу.
Ныне мне пришлось разбираться с криптосистемой NTRU. Затруднения возникли при атаке на основе решёток. Дело в том, что мне не удалось найти никакого практического примера. Тогда я решил взять для опыта параметры криптосистемы из вики https://ru.wikipedia.org/wiki/NTRUEncrypt и попытаться восстановить закрытый ключ.
http://www.math.brown.edu/~jpipher/grenoble.pdf например здесь, есть описание атаки
http://m.mathnet.or.kr/mathnet/kms_tex/982882.pdf или здесь.
Решетки, алгоритмы и современная криптография даже на русском.

Первым делом надо построить матрицу, строки которой будут образовывать решётку:

(Оффтоп)

lat = {
{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 25, 22, 20, 12, 24, 15, 19, 12, 19, 16},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 8, 25, 22, 20, 12, 24, 15, 19, 12, 19},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 19, 16, 8, 25, 22, 20, 12, 24, 15, 19, 12},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 12, 19, 16, 8, 25, 22, 20, 12, 24, 15, 19},
{0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 19, 12, 19, 16, 8, 25, 22, 20, 12, 24, 15},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 15, 19, 12, 19, 16, 8, 25, 22, 20, 12, 24},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 24, 15, 19, 12, 19, 16, 8, 25, 22, 20, 12},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 12, 24, 15, 19, 12, 19, 16, 8, 25, 22, 20},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 20, 12, 24, 15, 19, 12, 19, 16, 8, 25, 22},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 22, 20, 12, 24, 15, 19, 12, 19, 16, 8, 25},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 25, 22, 20, 12, 24, 15, 19, 12, 19, 16, 8},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32}};

(синтаксис wolfram mathematica)
Далее необходимо редуцировать базис решётки. В результате получается следующая матрица:

(Оффтоп)

LatticeReduce[lat]
{{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{-1, 0, 0, 1, 0, -1, -1, -1, 2, 1, -2, -3, 0, 0, 0, 3, 0, 0, -3, 3, 0, 0},
{1, 0, -1, -1, -1, 2, 1, -2, -1, 0, 0, 0, 3, 0, 0, -3, 3, 0, 0, -3, 0, 0},
{-2, 2, 2, -3, 1, 0, -1, 3, -1, -1, 1, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, -3},
{1, -2, -1, 2, 1, 0, 0, -1, 0, 1, 1, 3, -3, 0, 0, 3, 0, 0, 0, -3, 0, 0},
{-1, -1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -3, -3, 0, 3, 3, 0, 3, 0, 0, -3, 0},
{-2, -1, 2, 1, 0, 0, -1, 0, 1, 1, 1, -3, 0, 0, 3, 0, 0, 0, -3, 0, 0, 3},
{0, -1, 0, 1, 1, 1, -2, -1, 2, 1, 0, 0, 0, -3, 0, 0, 3, -3, 0, 0, 3, 0},
{0, 1, 0, 1, -1, 0, 3, -1, -1, 2, 0, -3, 0, 0, 0, -3, 0, 3, 0, 0, 0, 3},
{-1, 0, 3, -1, -1, 2, 0, 0, 1, 0, 1, -3, 0, 3, 0, 0, 0, 3, -3, 0, 0, 0},
{1, -1, 0, 3, -1, -1, 2, 0, 0, 1, 0, 0, -3, 0, 3, 0, 0, 0, 3, -3, 0, 0},
{-1, -1, -3, -1, -1, -2, 4, 1, 2, 2, 3, -3, 0, -3, 2, 1, -1, 0, 0, 2, 1, 1},
{-3, 1, 3, -1, 3, 2, -3, -3, 0, 0, -2, -2, 3, 2, -2, 4, -2, 1, -1, -3, -1, 1},
{-2, -1, 2, 3, -1, -2, -1, 1, -3, 3, -2, 1, 2, 0, 0, 0, -1, 3, -1, -4, 0, 0},
{1, -2, -3, 1, 2, 1, -1, 3, -3, 2, 2, -2, 0, 0, 0, 1, -3, 1, 4, 0, 0, -1},
{0, -1, 0, 3, -3, -2, -3, 6, -3, -2, 3, 0, 0, 3, 1, -1, 0, 0, 0, -2, -2, 1},
{-3, 0, -1, 2, 4, -1, -1, -2, 1, 0, 2, 0, 1, 5, -3, 0, 0, -1, 0, -1, -1, 0},
{-3, 1, -1, 0, -1, 0, 2, -5, 3, 2, 2, 0, -1, -1, -1, 3, 0, 0, 2, 1, -3, 0},
{1, -1, -2, -1, 0, 2, 1, 3, 1, -3, -2, 0, -1, 1, -2, 0, -4, -2, 4, -2, 1, 5},
{2, -2, 4, 1, 1, 0, 0, 0, -4, 2, -1, -2, 3, 1, 0, 3, -2, 1, 2, -1, -3, -2},
{1, -2, 0, -3, 0, -2, 1, 3, 2, 2, 3, 1, 3, 0, 1, -4, 2, 0, 0, 0, -2, -1},
{-2, -2, 1, -3, -1, 0, 3, 0, 0, 1, 1, 3, 0, 0, 5, 3, 3, 3, 6, 2, 4, 3}}

(синтаксис wolfram mathematica)
Насколько я понял, после редуцирования можно относительно просто найти кратчайший вектор, который будет равен вектору $\tau = (\alpha f, g)$, который и является нашей целью. Но найти способ нахождения кратчайшего вектора для меня оказался весьма сложной задачей. Да и не вижу я в полученной матрице ничего похожего на $f$.
Подскажите, как добиться положительного результата.

Заранее благодарю всех за внимание и прошу прощения за оффтопик. Не нашёл лучшего решения для изображения матрицы 22 на 22.

[maxal]

Поиграйтесь со значением $\alpha$.

[Alex_CAPS]

maxal в сообщении #957759 писал(а):

Поиграйтесь со значением $\alpha$.

Я правильно понимаю, что при адекватном выборе $\alpha$ одна из строк матрицы после редуцирования решётки будет в точности соответствовать $\tau$?

[maxal]

Alex_CAPS в сообщении #957780 писал(а):

maxal в сообщении #957759 писал(а):

Поиграйтесь со значением $\alpha$.

Я правильно понимаю, что при адекватном выборе $\alpha$ одна из строк матрицы после редуцирования решётки будет в точности соответствовать $\tau$?

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