( ¦ ) $\альфа\оплюс\бета$ неотличимо от случайного числа?
Обратите внимание, что нам нужно преобразовать $\альфа$ и $\бета$ к битовым строкам, чтобы применить побитовое исключающее ИЛИ. Так что на самом деле мы вычисляем $\подчеркивание\альфа\oplus\подчеркивание\бета$ куда $\подчеркивание\гамма$ is - это обозначение однозначно определенного представления произвольного элемента группы. $\гамма$ как битовую строку фиксированного размера, и задается вопрос, $\подчеркивание\альфа\oplus\подчеркивание\бета$ является случайной битовой строкой. Ответ будет зависеть от используемого представления.
Легко найти четкий контрпример со знакомой криптографической группой и представлением, таким как подгруппа квадратичные вычеты принадлежащий мультипликативная группа по модулю $(2п+1)$, когда $р$ большой случайный Софи Жермен премьер скажем, 1999 бит¹ и начальные биты 1010, а также представление элементов группы в виде 2000-битных битовых строк на обратный порядок байтов соглашение. $\подчеркивание\альфа$ и $\подчеркивание\бета$ представляют собой 2000-битные битовые строки с заметным смещением в сторону 0 в первых двух битах, и есть подобное (хотя и меньшее) смещение в первых двух битах $\подчеркивание\альфа\oplus\подчеркивание\бета$.
С другой стороны, если в приведенном выше мы заменим 1010 с 111–111 более 200 бит², тогда $\подчеркивание\альфа$ будет неотличим от случайного, за исключением представления $\альфа$ это квадратичный вычет³. Несмотря на это, и $\альфа$ и $\бета$ не будучи строго независимыми, я предполагаю, что оба эффекта достаточно слабы, чтобы $\подчеркивание\альфа\oplus\подчеркивание\бета$ вычислительно неотличима от случайной.
Для любого представления элементов группы в виде строки битов мы можем разработать другое представление того же размера, применив к представлению общедоступную, эффективно вычислимую и обратимую псевдослучайную перестановку. Свойства группы сохраняются, шифрование Эль-Гамаля по-прежнему работает и одинаково безопасно. А теперь для любого $р$ достаточно большой, чтобы DLP был жестким, $\подчеркивание\альфа\oplus\подчеркивание\бета$ можно доказать вычислительную неотличимость от случайной, используя свойства PRP.
¹ Таким образом, шифрование Эль-Гамаля является безопасным, что подразумевается в вопросе.
² Мы можем захотеть увеличить разрядность $р$ немного, чтобы компенсировать проблему дискретного логарифмирования, которая немного облегчается $р$ быть близкой к степени двойки.
³ Характеристика, которую можно эффективно проверить, проверив, что символ Лежандра $\left(\frac\alpha{2p+1}\right)\,\underset{\text{def}}=\,\alpha^p\bmod(2p+1)$ является $+1$
Обратите внимание, что $\альфа^{-1}\бета\bmod(2p+1)$ является слегка необъективным элементом группы.
