я займусь делом $е=2$; если $\gcd(e, \phi(n)) = 2$, то этого достаточно (так как достаточно было бы найти квадратный корень из $с$ (зашифрованный текст), а затем взять $е/2$корень этого.
Итак, нам дано $с$ и хочу найти значения $м$ с.т. $m^2 = c \pmod {p^2}$.
Начнем с поиска значений $м'$ с.т. $m'^2 = c \pmod p$; это модульный квадратный корень, и для него существуют известные алгоритмы. Проще всего, если $p \экв 3 \pmod 4$; в этом случае, $m' = \pm c^{(p+1)/4} \bmod p$. $p \экв 1 \pmod 4$ случае также выполнимо, но больше работы.
Учитывая эти значения, мы конвертируем их в значения по модулю $р^2$. Это оказывается еще проще, потому что если у нас есть $m = m' + xp$ (и $м$ всегда будет эквивалентен одному из $м'$ значения по модулю $р$), то имеем:
$$m^2 = (m' + xp)^2 = m'^2 + 2m'xp = c \pmod {p^2}$$
И с тех пор $cm'^2$ является кратным $р$, мы можем сократить это до:
$2m'x = (c - m'^2)/p \pmod p$, или же $x = (2m')^{-1} (c - m'^2)/p \pmod p$
И, $m = m' + px$ дает вам значения $м$ (и помните, есть два возможных значения $м'$ и, следовательно, два возможных значения $м$).
Также обратите внимание, что, поскольку нам удалось обойтись без какой-либо личной информации, это не работает как «шифрование с открытым ключом».
