Учитывая EC с мощностью $С=Р^3+с$ с $P$ простой $P \приблизительно \sqrt[3]{C}$ и $с>0$.
Из данного генератора $G$ мы генерируем два дополнительных генератора $F,H$ с
$$F = P \cdotG$$
$$H = P^2 \cdot G$$
(все равно будет генерироваться последовательность длины $П^3+с$)
Дан случайный участник $M_1$ этого EC мы можем создать $P\раз P\раз P$ куб из разных членов с
$$ M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$
$$ i,j,k \in [0,P-1]$$
$$|\{V_{M_1ijk}\}| = П^3$$
Каждый второй случайный участник $M_2$ может производиться из $M_1$ с:
$$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H $$
$$ i,j,k \in [0,P]$$
Вопрос:
Даны два случайных члена $М_1,М_2$ сколько шагов необходимо, чтобы найти связанный $i,j,k$ (в среднем времени)? Как это сработает?
Будет ли (намного) безопаснее, если мы выберем $P = 2\cdot p+1$ с $р$ премьер?
Было бы (намного) безопаснее, если бы мы выбрали три (секретных) простых множителя $P_1,P_2,P_3$ вместо? с $P_1 \cdot P_2 \cdot P_3 \приблизительно C$
(Я ищу приблизительные оценки, связанные с $С,Р$ в ($О$- обозначение). Мы можем, например. игнорировать различное влияние, связанное с длиной бита, при умножении на 2 числа)
Противник знает об использованных ЭК, генераторах $G,F,H$ и их обратные $G^{-1},F^{-1},H^{-1}$, случайные члены $М_1,М_2$ и внутреннюю структуру. Он не знает о $П,д$ но поскольку вариантов не так уж много, мы предполагаем, что он тоже это знает.
Он хочет найти неизвестное $i,j,k$ для случайных известных $М_1,М_2$.
Дополнительный вопрос: Существуют ли какие-либо ограничения безопасного ЭК, которые можно использовать для этого? Например.
был бы М-221 с $у^2 = х^3+117050х^2+х$ $\bmod p = 2^{221} - 3$ работать для этого?
Пробный:
Если у нас есть только один генератор $G$ это должно занять $O(\sqrt{C})$ используя детский шаг-гигантский шаг. Если $P$ известен $i,j,k$ из этого можно построить.
С $F,H$ мы могли бы сделать поверхность вокруг $M_1$ и прямая с $G$ в $M_2$ до пересечения тех. Это займет $O(P^2+P)\стрелка вправо O(P^2)$ который был бы больше, чем $O(\sqrt{C})=O(P\sqrt{P})$. Так $F,H$ здесь нет помощи.
Могут ли эти генераторы $F,H$ помогите сделать это как-то быстрее?
