Рейтинг:5

Можно ли использовать серию треугольных отражений для криптографии?

флаг at

(Полагаю, нет, но почему это так? Есть ли способ сделать это возможным?)

Из заданного равностороннего треугольника T1 (с тремя его вершинами A,B,C, лежащими в конечном поле $\mathbb F_N^D $) другой равносторонний треугольник T2 может быть построен путем зеркального отражения одной из 3 вершин на ребре между двумя другими вершинами. Это будет повторяться несколько раз.

Имея всего два случайных треугольника T1 и T2 (и $\mathbb F_N^D $) может ли противник вычислить кратчайший путь из T1 в T2?
(Предположим, что существует способ и по модулю $N$ и размеры $Д$ выбираются достаточно высоко, чтобы проверка всего треугольника заняла слишком много времени)
Или он может сделать это (намного) быстрее, чем просто применять его шаг за шагом?
(как например на EC генератор $г$ не нужно применять $м$ раз, если мы хотим вычислить $г^м$. Я ищу более чем одномерную технику, которую нельзя свести к проблеме с одним измерением и которую необходимо вычислять шаг за шагом. «Длина» «кратчайшего пути» будет количеством необходимых (треугольных) вычислений)


Чтобы отразить точку A на ребре BC, мы ищем точку $S$ и переменная $г$ с $$S = B + г (C-B)$$ Позволять $v$ направление ребра BC: $$v = \vec{v} = C-B$$

Этот $S$ позволит нам вычислить направление от $А$ к $BC$ и с этим вычислить зеркальную точку $A_M$ $$A_M = A + 2(SA)$$

Сделать это $S-A$ должны быть ортогональны $v$. Таким образом, скалярное произведение должно быть равно 0: $$(SA)' v = 0$$ $$(B+rv-A)' v = 0$$ $$(B-A)' v = -rv'v$$ $$r = \frac{(BA)'v}{-(v'v)}$$

(так же, как и в евклидовом пространстве, за исключением конечного поля $г$ нужно вычислить с обратным $(-(v'v))^{-1}$ над $N$)

Редактировать: fgrieu указал, что существует гораздо более простой способ вычисления отражения равностороннего треугольника: $$A_M = A' = B+C-A$$ (окончание редактирования)


Я сделал несколько тестов для 2 измерений и простых чисел $N$.
Конечное поле $\mathbb F_N^2 $ может построить равносторонний треугольник только в том случае, если $N$ имеет корень для $3$.

Равносторонний треугольник с заданной длиной ребра может произвести $2 Н^2$ другие треугольники (каждый имеет одинаковую длину ребра). Каждая длина ребра имеет два таких множества. В итоге $2(N-1) (2N^2)$ которые не пересекаются друг с другом.

(Я только что вычислил квадрат длины ребра между двумя точками, как в евклидовом пространстве)


В евклидовом пространстве, отражающем треугольник вокруг точки ($С$) будет выглядеть так:
Фрист зеркало $А$ в $CB$. Затем зеркало $В$ в $CA_M$ и так далее. Если это равносторонний треугольник, он снова совпадет после того, как сделает это 6 раз.

введите описание изображения здесь

В конечном поле $\mathbb F_{11}^2 $ это может выглядеть так:
Это также совпадет после того, как вы сделаете это 6 раз (около 1 балла).
Делая это только в одном направлении, оно совпадет после $2N$

введите описание изображения здесь


Существует ли подобный криптографический алгоритм?
Почему это не безопасно? Либо это? Помогут ли дополнительные измерения?
Есть идеи, как сделать его более безопасным?

fgrieu avatar
флаг ng
Если равносторонний треугольник — это треугольник с равным расстоянием между вершинами, как определить расстояние в общем конечном поле $\mathbb F_{p^k}$ или ограничиться $\mathbb F_p$ с простым числом $p$? Также я не понимаю вашей алгебры для зеркала $A'$ точки $A$ w.r.t. ребро $BC$, включая то, что такое $T$, и если/как симметричный $A'$ $A$ определен _уникально_ (я получаю это в поле $\mathbb R^d$, где $A'=B +C-A$). Кроме того, гипотетически поиск кратчайшего пути представляет собой сложную задачу; и наличие сложной проблемы является необходимым, но недостаточным условием для построения криптосистемы.
J. Doe avatar
флаг at
@fgrieu спасибо за подсказку. Я сделал некоторое обновление. Я использовал только простые числа p для N. Я изменил алгебру на какую-то альтернативную версию с некоторыми дополнительными деталями. (T был просто транспонирован вектором). A' должен быть однозначно определен с помощью this. По крайней мере, я так думал (подумаю еще раз об этом). Я не знал, что $A' = B + C -A$. Можете ли вы привести пример для $\mathbb{R^d}$, где $A'$ не определено однозначно?
fgrieu avatar
флаг ng
В $\mathbb{R^d}$ задача сводится к плоскости, определяемой $ABC$, поэтому сводится к $\mathbb{R^2}$ заменой базиса, а $A'$ определяется однозначно , и соответствует $A'=B+C-A$ или, возможно, более строго $\vec{OA'}=\vec{OB}+\vec{OC}-\vec{OA}$. Если в ${\mathbb F_p}^d$ мы определим $A'$ тем же уравнением, то $A'$ также будет определено однозначно. Я не уверен в вашем определении (особенно части $T$), когда $d\ne2$.
J. Doe avatar
флаг at
@fgrieu Я изменил уравнение. Больше не должно быть $T$. Я думал, вы имеете в виду, что есть какое-то исключение для $A' = B + C -A$ не однозначно. Если это не так, я мог бы изменить уравнение именно на это. Было бы намного проще. Также лучше соединяется с ответом от Fractalice.
Рейтинг:7
флаг in

Из второго треугольника можно найти соседний треугольник, имеющий ту же ориентацию, что и первый (все точки будут смещены на один и тот же вектор). Итак, нас интересует поиск пути между одним выделенным углом или двумя треугольниками. Он образует двумерную решетку: например. $A_M$ можно пойти в $А$ или к его верхнему аналогу (на продолжении $BC$). Эти два вектора образуют основу. Мы также можем включить третий вектор (идущий от $A_M$ вниз через два треугольника): он «избыточен», но он нам нужен, так как мы хотим найти короткие координаты, а эти три вектора покрывают все 6 направлений.

Теперь мы просто хотим выразить вектор, соединяющий выделенные углы двух треугольников, в нашем (избыточном) базисе. Это уже должно намекать на слабость задачи, так как нам "просто" нужно найти 3 числа (координаты в базе), т.е. порядок шагов значения не имеет.

Это приводит к экземпляру CVP (близкая векторная проблема), который может быть решен с помощью алгоритма Бабая и LLL (у вас будет несколько дополнительных измерений для координат и для добавления редукции модуля в решетку).

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

J. Doe avatar
флаг at
О боже, как я мог это пропустить, я тоже думал что-то подобное (смещено на тот же вектор) и проверил это на каком-то примере. В тот момент не получилось. Я сделал ошибку, сравнив треугольники после 3 отражений, но для получения одинаковой формы нужны только 2 отражения. Спасибо, что снова указали на это. рвать идею. Я думаю, что аналогичной, но гораздо более безопасной альтернативы также не существует.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.