Возведение в степень линейных конгруэнтных генераторов

Линейные конгруэнтные генераторы, класс псевдослучайных генераторов с рекурсивным правилом.

$x_{n+1}\equiv a\cdot x_n +b\ \ (\mod m)$, $a,b,x_n\in Z/mZ$, $m,n\in N$

считаются непригодными для использования в криптографии, так как константы $а$, $b$ можно вывести из небольшого набора выходных данных $x_n$. Теперь, когда вы выбираете $m=p-1$ для некоторого нечетного простого числа $р$, последовательность $(x_n)_{n\in N}$ могут жить как экспоненты некоторого генератора $г$ мультипликативной циклической группы $Z/pZ^*$, как $y_n:=g^{x_n}, n\in N$:

$y_{n+1}\equiv g^{x_{n+1}}\equiv g^{a\cdot x_n+b}\equiv (g^{x_n})^a\cdot g^b\equiv y_n ^а\cdot g^b\ (\mod p)$

Это эквивалентный степенной ряд.

Равное распределение идет с максимальным периодом. Условия на максимальный период $м$ последовательности $(y_n)_{n\in N}$ даются теоремой Кнута

1. $gcd(m,b)=1$
2. Для простого разложения $m=:\prod p_i^{\alpha_i}$ и все основные факторы $p_i$: $\ \ \ p_i/(a-1)$
3. $m\equiv 0\ (\mod 4) \подразумевает a-1\equiv 0\ (\mod 4)$

Как $m=p-1$ четно и очень мало простых чисел с формой $р=2^к+1$, самый простой общий состав $p-1$ из простых чисел было бы $p-1=2^k\cdot p'$, $k\geq 1$ с $р'$ другой премьер.

По 2-му условию наименьший выбор $а$ является по $a-1=2\cdot p'$. Во избежание тривиального случая $а-1=м$, $k\geq 2$ необходимо. При этом мы сталкиваемся с 3-м условием, так что $а-1$ имеет как минимум двукратный коэффициент $2$. Опять же, избегание тривиального случая требует $k\geq 3$.

Теперь главная пара $(р,р')$ подгонка линейного уравнения $р=8р'+1$ допускает нетривиальный выбор $a-1=4p'$ и с этим силовым рядом $(y_n)$ может иметь максимальный период $м$.

Вопрос: Так как у нас есть 3 скрытых параметра $ г, г ^ а, г ^ б $ и нахождение логарифмов в мультипликативных группах считается трудным, может ли случайная последовательность $(y_n){n\in N}$ считаться безопасным для использования в криптографии; есть ли лучший выбор для постоянного $а$?

РЕДАКТИРОВАТЬ $г$ на самом деле не важен как параметр, так как мы поднимаем степени до $а$, где дополнительно $р$ неизвестно из вывода, т. е. неизвестные параметры $(р, а, г^б)$ .

Несколько наблюдений:

• Хранение $а$ тайна имеет решающее значение. Если противник это знает и видит $y_i, y_{i+1} = (y_i^a) \cdot g^b$, он может вычислить $g^b = y_{i+1} \cdot y_i^{-a}$, а затем продолжайте вычислять остальную часть последовательности.

Вы можете сказать: «Но мы предполагаем, что дискретный журнал труден», однако вы также предлагаете $р = 8р'+1$ и $a-1 = 4p'$, это, $а = (р+1)/2$; что бы выздороветь $а$ легкий.

• Настоящим лакмусовым тестом для CSRNG является то, сможет ли противник (который знает все, кроме секретных значений) отличить выходные данные CSRNG от действительно случайной последовательности с тем же распределением вероятностей.

Сейчас если $г$ является образующей всей группы, оказывается несложным определить, является ли $х$ четно или нечетно от $g^x \bmod p$. С вашим генератором этот младший бит всегда будет чередоваться между «четным» и «нечетным» с последовательным $y_i$ значения, что делает его различимым.

Что мы обычно делаем при использовании конечных полей, так это преднамеренно работаем в подгруппе простого размера (которая, очевидно, не может быть всей группой). $\mathbb{Z}_p^*$ группа); что не позволяет злоумышленнику восстановить любую информацию о $х$ от $г^х$.

Конечно, это уменьшает размер периода, однако до тех пор, пока период длиннее, чем, скажем, $2^{64}$ (что намного больше, чем количество выходных данных, которое мы могли бы сгенерировать на практике), оно достаточно велико.

Собрав это вместе, я бы предложил аналогичную альтернативную идею:

• Уронить $b$; вместо этого используйте простой $y_{i+1} = (y_i)^a \bmod p$ генератор.

• Выберите простое число $р = кр' + 1$, куда $р'$ является простым числом Софи-Жермен, т. е. $(p'-1)/2$ также является простым. $р$ должен быть достаточно большим, чтобы усложнить задачу дискретного журнала (например, не менее 2048 бит), и $р'$ должен быть достаточно большим, чтобы проблема дискретного журнала внутри подгруппы была сложной (например, не менее 256 бит; однако он может быть намного больше, например, $к=2$ является практичным).

• Выбирать $y_0$ быть членом (кроме 1) подгруппы размера $р'$

• Выбирать $а > 0$ быть случайным значением, для которого $a^{(p'-1)/2} \bmod p' \ne 1$ (что будет справедливо для половины возможных значений $а$)

Это создаст последовательность периода $p'-1$ (что достаточно долго); см. теорему 3.2.1.2.C Кнута. И потому что $а$ можно выбрать из большого количества возможностей, его нельзя угадать.

Теперь ни одна из версий не будет практичный CSRNG (выполнение модульного возведения в степень для каждого вывода довольно медленно — у нас есть гораздо лучшие CSRNG); Я считаю, что это отвечает на ваш вопрос.