Позволять $\mathbb Г$ с генератором $г$, это 256-битный простой порядок $q$, и 128-битное простое число $р$ быть известным и фиксированным.
Предположим, мы получили алгоритм $\математический А$ который на входе $(h_1,h_2)\in\mathbb G^2$, с $h_1=g^{a_1}$, $h_2=g^{a_2}$ для случайного $a_1,a_2\in\mathbb Z_q$, выходы $h_3=g^{a_1+a_2\bmod p}$ с ненулевой вероятностью, как в вопросе.
Определить алгоритм $\mathcal А'$ что на входе $h\in\mathbb G$ попытки вывести $у$ с $г^у=ч$, и к этому:
- рисует $u$ случайно в $\mathbb Z_q$, вычисляет $h_1=g^u\;h$, который теперь является случайным в $\mathbb Г$; таким образом, существует уникальный (пока неизвестный, случайный) $a_1\in\mathbb Z_q$ с $г^{а_1}=ч_1$
- рисует $a_2$ случайно в $\mathbb Z_q$, вычисляет $h_2=g^{a_2}$
- работает $\математический А$ с вводом $(ч_1,ч_2)$, получает $h_3$ предполагается (с ненулевой вероятностью) $g^{a_1+a_2\bmod p}$
- находит $x\in\mathbb Z_q$ с $0\le x<p<2^{128}$ такой, что $г^х=ч_3$, что требует в порядке $2^{66}$ групповые операции с использованием Ро Поларда с выделенными точками, возможно небольшим объемом памяти и легко распределяется
- вычисляет $r=x-a_2\bmod p$; он держит $a_1\экв г\bмод р$, и $0\le a_1<q$; пусть (sd пока неизвестно) $s\in\left[0,\left\lfloor q/p\right\rfloor\right]$ быть таким, что $a_1=r+s\,p$, таким образом $g^{r+s\,p}=h_1$, таким образом $g^{s\,p}=h_1\,g^{q-r}$, таким образом $g^s=(h_1\,g^{qr})^{p^{-1}\bmod q}$
- вычисляет $h_4=(h_1\,g^{q-r})^{p^{-1}\bmod q}$; он держит $g^s=h_4$ и $s<2^{129}$
- находит $s$ практически тем же методом, что и $х$
- вычисляет $a_1=r+s\,p$, что, таким образом, таково, что $г^{а_1}=ч_1$
- вычисляет и выводит $y=a_1-u\bmod q$, который таков, что $г^у=ч$.
Наш алгоритм $\mathcal А'$ Таким образом, он может вычислить дискретный логарифм $у$ основать $г$ любого заданного элемента $ч$ в $\mathbb Г$ с ненулевой вероятностью и практически мало работает. Это гипотетически невозможно. Отсюда наше предположение, что $\математический А$ существует ложно.
Таким образом, мы отвечаем на вопрос отрицательно.
