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

Последнее сообщение: 4 года назад от Colt browning в теме «Откуда параметр?»

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

править

Сначала, используя алгоритм Эвклида, из уравнения   находим числа   и  . Далее, используя китайскую теорему об остатках, можно вычислить числа

  Один из этих корней r, -r, s, -s является истинным открытым текстом m .

Вопрос, откуда здесь появляется   и  ? 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)Ответить