Схема Рабина
Схема Рабина — эта схема очень похожая на алгоритм RSA, но при этом сообщение m возводит не в большую степень е, а только в квадрат: c = (m2mod n). Число n так как и в схеме RSA есть произведением двух больших простых чисел p и q. На приемной же стороне можно декодировать сообщение с помощью RSA, но чаще всего используется другое быстрое извлечение квадратного корня по модулю n.
Схема извлечения квадратного корня при заранее известном разложении n на сомножители нужно некоторое время. Если q и p выбраны таким образом, что остаток от деления на 4 и чисел равен — трем(3), то расчет квадратного корня решается:
- алгоритмом Евклида решается уравнение a × p + b × q = 1;
- r = c(p+1)/4mod p;
- s = c(p+1)/4mod p;
- x = (a × p × s + b × q × r)mod n;
- y = (a × p × s — b × q × r)mod n;
- корнями числа c есть 4 значения: (±x mod n) и (±y mod n).
В качестве плюсов такой схемы Рабина можно отметить уменьшение открытого ключа. Ключ состоит из одного числа n, что сильно ускоряет процесс шифрования. Все же есть и недостатки, это получение четырех различных значений на приемной стороне: m1, m2, m3, m4. Одно из этих значений есть зашифрованный текст, три других же издержки модульной арифметики. Такая особенность требует перед процессом шифрования в сообщение добавлять метки, или применять избыточное кодирование, что бы при розшифровании с большой вероятностью могли определить сообщение. Схема Рабина показана на рис.1.
Рисунок — 1
Также смотрите:
Загрузка...