Обсуждение:Криптосистема Рабина

Откуда параметр?

Сначала, используя алгоритм Эвклида, из уравнения $y_{p}\cdot p+y_{q}\cdot q=1$ находим числа $y_{p}$ и $y_{q}$. Далее, используя китайскую теорему об остатках, можно вычислить числа

${\begin{matrix}r&=&(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-r&=&n-r\\s&=&(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p})\,{\bmod {\,}}n\\-s&=&n-s\end{matrix}}$ Один из этих корней r, -r, s, -s является истинным открытым текстом m .

Вопрос, откуда здесь появляется $m_{p}$ и $m_{q}$? Titch 21:00, 25 декабря 2010 (UTC)

Параметры Mp и Mq

Первый раз на вики, делаю как понял. См. источник, если кратко.

Mp - это квадратный корень C по модулю p. Mq - это квадратный корень C по модулю q.

Mx = C^((p + 1) / 4) mod x. Где x это p, или q.

Существует доказательство того, что при простом p конгруэнтном 3 по модулю 4, квадратных корня ровно два для x принадлежащего [0..p) (если существует хотя бы один). Один из которых равен остатку от x в степени (1/4)*(p+1) делённого на p.

Источник: https://en.wikipedia.org/wiki/Rabin_cryptosystem#Decryption

BookCake (обс.) 13:14, 20 февраля 2020 (UTC)

• И что?.. adamant.pwn — contrib/talk 13:21, 20 февраля 2020 (UTC)
  • Видимо, это ответ на (вполне справедливый) вопрос выше. Изменил уровень заголовка, чтобы это было ясно. — Браунинг (обс.) 14:55, 21 февраля 2020 (UTC)