Циклическая последовательность может быть получена с помощью
$$s_{i+1} = s_i^a \mod N$$
с $N = P \cdotQ$ и $P = 2\cdot p+1$ и $Q = 2\cdot q\cdot r+1$ и $r = 2\cdot u \cdot v \cdot w +1$ с $P,Q,p,q,r,u,v,w$ разные простые числа
Теперь мы можем спроецировать случайное число $x_R$ в подпространство размера $2(r-1)+4$ с
$$s_R = x_R^{\бета} \mod N$$
$$\beta = 2\cdot p \cdot q \cdot n \mod \phi(N)$$
с фактором $n$ выбора.
Если мы теперь используем примитивный корень $\альфа$ от $г$ мы можем создать циклическую последовательность с:
$$s_{R_{i+1}} = s_{R_i}^\alpha \mod N $$
В большинстве случаев он будет иметь длину $r-1$. Если $s_r =0$ или же $s_r =1$ или для $n \equiv r \mod \phi(N)$ мы получаем только длину цикла $1$. Их можно протестировать и игнорировать (всего $4$ различные такие значения).
Таким образом, почти во всех случаях мы проецируем случайное значение $x_R$ члену одной из двух последовательностей длиной $r-1$.
В большинстве случаев член последовательности $S_1$ если только $X_R$ является кратным $P \mod N$ чем это будет частью последовательности $S_2$ (кроме упомянутых выше особых случаев).
Как мы определили $r=2\cdot u \cdot v \cdot w +1$ с простыми числами $u,v,w$ мы можем использовать $г$примитивный корень $\альфа$ произвести 3 направления
$$\alpha_1 = \alpha^{2vw} \mod \phi(N)$$
$$\alpha_2 = \alpha^{2uw} \mod \phi(N)$$
$$\alpha_3 = \alpha^{uv} \mod \phi(N)$$
с этим $\альфа_1$,$\альфа_2$,$\альфа_3$ охватывать $u \раз v \раз 2w$ пространство.
Три функции $f_1,f_2,f_3$ с $f_d: s\mapsto s^{\alpha_d} \mod N$ может пройти через каждую точку последовательности ($f_0 : s\mapsto s^\alpha \mod N$).
Вопрос:
Даны случайные значения $x_A$ и $x_B$ и с этим их проецируют($х^\бета$) ценности $s_A$, $s_B$ насколько сложно было бы найти $к$ в $s_B \equiv s_A^{\alpha^k} \mod N$ или же $k_1,k_2,k_3$ в $s_B \equiv s_A^{\alpha_1^{k_1}\cdot \alpha_2^{k_2} \cdot \alpha_3^{k_3} } \mod N$ (при условии, что они являются частью одной и той же последовательности)
Или, другими словами, есть ли более быстрый способ, чем применение $f_0$ или же $f_1,f_2,f_3$ несколько раз до совпадения?
(противник также знает обратные функции $f_d$ с их родственными $\бар{\alpha_d}$)
Цель состоит в том, чтобы зашифровать взаимосвязь между трехмерными точками, не сводя ее к одномерной задаче (как это делается для $g^i \mod P_{rime}$)
побочные вопросы:
Насколько большой такой $г$ нужно быть в безопасности?
Будет ли знание $\бета$, $\альфа$ помочь противнику разложить на множители $N$ (при условии, что мы выбрали большой фактор $n$)?
В случае, если есть гораздо более быстрый способ, фактор $г=2у+1$ с 3 первообразным корнем лучше?
Решение пробной версии:
Чтобы быть в безопасности $N$ должны быть достаточно большими, чтобы избежать факторизации. При таком подходе мы масштабируем $N$ настолько большим, насколько мы хотим, сохраняя размер целевой последовательности $r-1$.
Без факторизации противник не мог бы вычислить $\фи(N)$ и с этим он не может делать большие шаги.
Чтобы найти совпадение $s_A$, $s_B$ он может вычислить все элементы поверхности, созданной с помощью $f_1,f_2$ (применительно к $s_A$) и строку с $f_3$ (применительно к $s_B$).
Если мы определим вычисление $f_d$ в качестве одного шага вычисления (с постоянной стоимостью) потребовалось бы $O(u\cdot v +w)$ шаги, чтобы найти совпадение.
В цифрах будет, например. 150-битный $г$ с $4096$ кусочек $N$ достаточный? Если нет более быстрого способа $\приблизительно 2^{100}$ шаги, необходимые для вычисления $s_A$ снаружи $s_B$.
Или можно быстрее?
Примеры номеров (для тестирования):
$N = 4151547901$, $П = 54959$, $Q=75539 = 2\cdot179 \cdot 211 +1$
$r = 211 = 2 \cdot 3 \cdot 5 \cdot 7 +1$
$\бета = 2qp = 9837482$
$\alpha = 17, \alpha_1 = 882104001, \alpha_2 = 2662481205, \alpha_3 = 3818265481$
(некоторые связанные вопрос с дополнительной информацией)
