Обычно RSA использует показатель степени шифрования $е$ с $\gcd(e,\phi(N))=1$.
Этот вопрос показывает, почему это должно быть так: для $\ne1$ может не существовать показателя расшифровки $д$ потому что другие $m'\ne m$ может существовать с $m^e \эквив (m')^e \bmod N$.
Однако, если мы производим нашу $м$ нравиться:
$$m = m_0^{e} \mod N$$
или более общий
$$m = m_0^{e^{r_1}\cdot r_2} \mod N \tag{I}$$
Мы всегда можем (за исключением некоторых особых случаев, которые мы здесь игнорируем) найти показатель степени расшифровки $д$ за $c \эквив m^e \mod N$
$$d \equiv e^i \equiv e^{\phi(\phi(N))-1} \mod \phi(N)$$
с
$ $ c ^ d \ экв (м ^ {е}) ^ d \ экв м ^ {\ Displaystyle е ^ 1 \ cdot е ^ {{\ фи (\ фи (N)) -1}}} \ экв м ^ {\ Displaystyle е ^ {{\ фи (\ фи (N))}}} \ эквив м \ мод N $ $
Конечно это сообщение $м$ не мог передать большую часть информации о цели. Некоторая младшая битовая информация может быть передана путем генерации случайных $м$ пока первые биты не будут нести информацию о цели. Неэффективно, но здесь это не важно.
Вопрос в том, будет ли противнику (намного) проще найти показатель степени расшифровки $д$ для таких $е$?
Если $\gcd(e,\phi(N))\gg 1$ известна факторизация $N$ может стать намного проще и тем самым нарушить безопасность RSA.
Q1: Но что произойдет, если $\gcd(e,\phi(N))\gg 1$ является нет известен? Чтобы убедиться, что мы выбираем $е$ который трудно факторизовать.
Имеет ли противник все еще большое преимущество, просто зная $\gcd\ne1$ ?
Это может сильно зависеть от выбранных факторов.
Здесь мы предполагаем (целевой вариант использования)
$$N = P \cdot Q$$
$$P = 2 \cdot p_s \cdot p_b +1$$
$$Q = 2 \cdot q_s \cdot q_b +1$$
$$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b$$
$$e = (2^2 \cdot p_b \cdot q_b) \cdot e_b > 2^{3000} \text{ (трудно разложить на множители)}$$
$$\gcd(e,\phi(N))=2^2\cdot p_b \cdot q_b = 2^2\cdot (2\cdot 3\cdot b_0+1) \cdot (2\cdot 3\cdot q_0 +1) = В$$
$$B > 2^{2000} \text{ (трудно разложить на множители)}$$
$$\phi(\phi(N)) = 2^3 \cdot 3^2 \cdot \phi(p_s) \cdot \phi(q_s) \cdot (q_0\cdot b_0)$$
$$\phi(p_s) \cdot \phi(q_s) /4= S \приблизительно 2^{200} \ll B$$
(в целевом варианте использования $p_s,q_s$ иметь вид $p_s = 2\cdot p_1\cdot p_2 \cdot p_3+1$)
(все переменные простые множители уникальны)
$е$ должен быть квадратом примитивного корня по модулю $p_s$ и $q_s$.
С этим мы можем производить $S$ различные значения с $m^{e^i} \bmod N$. В зависимости от запуска $м$ мы получаем 4 непересекающихся множества такого размера (плюс некоторые более мелкие частные случаи, которые мы здесь игнорируем).
Дополнительный фактор $e_b$ необходимо скрыть отношение к $\фи(N)$ и $В$. С этим $е\гг Н$ здесь.
Мы предполагаем, что противник также знает $S$ включая его первичную факторизацию.
Q2: Вопрос, связанный с вариантом использования, также допускает целевые значения $n\ne м$ но генерируется как $(\текст{I})$ (и известно, что есть решение):
Может ли противник найти $я$ в $n\equiv m^{e^i} \bmod N$ с известным $e,n,m,N,S$ быстрее, чем $O(p_s + q_s) \ приблизительно O(\sqrt{S})$?
Этого можно достичь, найдя решение для $j,k$ в $ п ^ {\ displaystyle p_s} \equiv (m ^ {\ displaystyle {p_s}}) ^ {e ^ j} \bmod N $ и $ п ^ {\ displaystyle q_s} \ экв (м ^ {\ displaystyle {q_s}}) ^ {e ^ k} \ bmod N $ с пошаговым тестированием. Гигантский шаг не может быть сделан как $\фи(N)$ неизвестно и $е^{2^{50}}$ слишком велик для вычислений без него. Или можно быстрее?
(игрушка) – Пример:
Здесь $p_b,q_b < p_s,q_s$ используются. В целевом варианте использования они будут $p_b,q_b \gg p_s,q_s$ (и все значения намного больше)
$N=P\cdot Q = 6565236619157488809896588016937$
$P = 2 \cdot p_s \cdot p_b +1 = 2500987802965403$
$Q = 2 \cdot q_s \cdot q_b +1 = 2625057431856779$
$p_b = 2 \cdot 3 \cdot p_0 = 2 \cdot 3 \cdot 4547= 27283$
$p_s = 2 \cdot p_1 \cdot p_2 \cdot p_3 + 1 = 2 \cdot 2579\cdot 2963\cdot 2999 + 1=45834178847$
$q_b = 2 \cdot 3 \cdot q_0 = 2 \cdot 3 \cdot 4007= 24043$
$q_s = 2 \cdot q_1 \cdot q_2 \cdot q_3 + 1 = 2 \cdot 2819\cdot 3023\cdot 3203 + 1=54590887823$
$\phi(N) = 2^2 \cdot p_s \cdot p_b \cdot q_s \cdot q_b = 6565236619157483683851353194756$
$\phi(\phi(N))=2^5\cdot3^2 \cdot p_0\cdot p_1\cdot p_2 \cdot p_3\cdot q_0\cdot q_1\cdot q_2\cdot q_3$
$\фи(\фи(N)) = 3282361465954844745126356151456$
Экспоненты $е,д$ есть только один дополнительный большой фактор, который затрудняет факторизацию.
$e = 3681846424601561452716738001396 = 2^2 \cdot p_b \cdot q_b \cdot 1403217197574083942221 $
$d = 1568810657844451193145575929268 = 2^2 \cdot p_b \cdot q_b \cdot 597901661545558066493 $
Здесь $B<S$ но в целевом случае использования $B\гг S$
$S = p_1\cdot p_2\cdot p_3\cdot q_1\cdot q_2\cdot q_3 = 625532128948867853353$
$B = 2^2 \cdot p_b \cdot q_b = 2^2 \cdot 27283 \cdot 24043=2623860676$
Противник бы знал $N$,$е$,$S$ включая факторизацию $S$. Но он не знает факторизации $Н,е,В$.
