Доброго времени суток!
Ныне мне пришлось разбираться с криптосистемой 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 или здесь.
http://discopal.ispras.ru/img_auth.php/2/23/%D0%A0%D0%B5%D1%88%D0%B5%D1%82%D0%BA%D0%B8,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0% B8_%D1%81%D0%BE%D0%B2%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0 %B0%D1%8F_%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D 0%B0%D1%84%D0%B8%D1%8F.pdf даже на русском.
Первым делом надо построить матрицу, строки которой будут образовывать решётку:
(синтаксис wolfram mathematica)
Далее необходимо редуцировать базис решётки. В результате получается следующая матрица:
(синтаксис wolfram mathematica)
Насколько я понял, после редуцирования можно относительно просто найти кратчайший вектор, который будет равен вектору , который и является нашей целью. Но найти способ нахождения кратчайшего вектора для меня оказался весьма сложной задачей. Да и не вижу я в полученной матрице ничего похожего на .
Подскажите, как добиться положительного результата.
Заранее благодарю всех за внимание
Ныне мне пришлось разбираться с криптосистемой NTRU. Затруднения возникли при атаке на основе решёток. Дело в том, что мне не удалось найти никакого практического примера. Тогда я решил взять для опыта параметры криптосистемы из вики
Первым делом надо построить матрицу, строки которой будут образовывать решётку:
Скрытый текст |
---|
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}}; |
Далее необходимо редуцировать базис решётки. В результате получается следующая матрица:
Скрытый текст |
---|
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}} |
Насколько я понял, после редуцирования можно относительно просто найти кратчайший вектор, который будет равен вектору , который и является нашей целью. Но найти способ нахождения кратчайшего вектора для меня оказался весьма сложной задачей. Да и не вижу я в полученной матрице ничего похожего на .
Подскажите, как добиться положительного результата.
Заранее благодарю всех за внимание