Криптосистема Рабина

Криптосистемы Рабина является асимметричный криптографический метод, чья безопасность, как и RSA , связана с трудностью целочисленной факторизации . Однако криптосистема Рабина имеет то преимущество, что математически доказана ее вычислительная безопасность против атаки с выбранным открытым текстом до тех пор, пока злоумышленник не может эффективно разложить на множители целые числа, в то время как для RSA такое доказательство не известно. ^{[1] : 145} Недостатком этого метода является то, что каждый выход функции Рабина может быть сгенерирован любым из четырех возможных входов; если каждый вывод представляет собой зашифрованный текст, требуется дополнительная сложность при расшифровке, чтобы определить, какой из четырех возможных входов был истинным открытым текстом.

История [ править ]

Алгоритм был опубликован в январе 1979 года Майклом О. Рабином . ^[2] Криптосистема Рабина была первой асимметричной криптосистемой, в которой восстановление открытого текста из зашифрованного текста оказалось столь же сложной задачей, как факторинг.

Алгоритм шифрования [ править ]

Как и все асимметричные криптосистемы, система Рабина использует пару ключей: открытый ключ для шифрования и закрытый ключ для дешифрования. Открытый ключ публикуется для всех, а закрытый ключ остается известным только получателю сообщения.

Генерация ключей [ править ]

Ключи для криптосистемы Рабина генерируются следующим образом:

1. Выберите два больших различных простых числа и такие, что и .${\ displaystyle p}$${\ displaystyle q}$${\ Displaystyle п \ эквив 3 {\ bmod {4}}}$${\ Displaystyle д \ эквив 3 {\ bmod {4}}}$
2. Вычислить .${\ displaystyle n = pq}$

Тогда это открытый ключ, а пара - закрытый ключ.${\ displaystyle n}$${\ displaystyle (p, q)}$

Шифрование [ править ]

Сообщение можно зашифровать, сначала преобразовав его в число с помощью обратимого отображения, а затем вычислив . Зашифрованный текст есть .${\ displaystyle M}$${\ Displaystyle м <п}$${\ Displaystyle с = м ^ {2} {\ bmod {п}}}$${\ displaystyle c}$

Расшифровка [ править ]

Сообщение может быть восстановлено из зашифрованного текста , извлекая его квадратный корень по модулю следующим образом.${\ displaystyle m}$${\ displaystyle c}$${\ displaystyle n}$

1. Вычислите квадратный корень по модулю и используя эти формулы:${\ displaystyle c}$${\ displaystyle p}$${\ displaystyle q}$

   ${\displaystyle {\begin{aligned}m_{p}&=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}\\m_{q}&=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}\end{aligned}}}$

2. Используйте расширенный алгоритм Евклида, чтобы найти и такое, что .${\displaystyle y_{p}}$${\displaystyle y_{q}}$${\displaystyle y_{p}\cdot p+y_{q}\cdot q=1}$
3. Воспользуйтесь китайской теоремой об остатках, чтобы найти четыре квадратных корня по модулю :${\displaystyle c}$${\displaystyle n}$

   ${\displaystyle {\begin{aligned}r_{1}&=\left(y_{p}\cdot p\cdot m_{q}+y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{2}&=n-r_{1}\\r_{3}&=\left(y_{p}\cdot p\cdot m_{q}-y_{q}\cdot q\cdot m_{p}\right){\bmod {n}}\\r_{4}&=n-r_{3}\end{aligned}}}$

Одно из этих четырех значений является исходным открытым текстом , хотя какое из четырех является правильным, не может быть определено без дополнительной информации.${\displaystyle m}$

Вычисление квадратных корней [ править ]

Мы можем показать, что формулы на шаге 1 выше фактически дают квадратные корни из следующего. Для первой формулы мы хотим это доказать . Поскольку показатель степени является целым числом. Доказательство тривиально , поэтому мы можем предположить, что не делится . Заметим, что это означает, что c - квадратичный вычет по модулю . потом${\displaystyle c}$${\displaystyle m_{p}^{2}\equiv c{\bmod {p}}}$${\displaystyle p\equiv 3{\bmod {4}},}$${\textstyle {\frac {1}{4}}(p+1)}$${\displaystyle c\equiv 0{\bmod {p}}}$${\displaystyle p}$${\displaystyle c}$${\displaystyle c\equiv m^{2}{\bmod {pq}}}$${\displaystyle c\equiv m^{2}{\bmod {p}}}$${\displaystyle p}$

${\displaystyle m_{p}^{2}\equiv c^{{\frac {1}{2}}(p+1)}\equiv c\cdot c^{{\frac {1}{2}}(p-1)}\equiv c\cdot 1\mod p}$

Последний шаг оправдан критерием Эйлера .

Пример [ править ]

В качестве примера возьмем, а затем . Возьмем за наш открытый текст. Зашифрованный текст таков .${\displaystyle p=7}$${\displaystyle q=11}$${\displaystyle n=77}$${\displaystyle m=20}$${\displaystyle c=m^{2}{\bmod {n}}=400{\bmod {77}}=15}$

Расшифровка происходит следующим образом:

1. Вычислить и .${\displaystyle m_{p}=c^{{\frac {1}{4}}(p+1)}{\bmod {p}}=15^{2}{\bmod {7}}=1}$${\displaystyle m_{q}=c^{{\frac {1}{4}}(q+1)}{\bmod {q}}=15^{3}{\bmod {11}}=9}$
2. Используйте расширенный алгоритм Евклида для вычисления и . Мы можем это подтвердить .${\displaystyle y_{p}=-3}$${\displaystyle y_{q}=2}$${\displaystyle y_{p}\cdot p+y_{q}\cdot q=(-3\cdot 7)+(2\cdot 11)=1}$
3. Вычислите четырех кандидатов в виде открытого текста:

   ${\displaystyle {\begin{aligned}r_{1}&=(-3\cdot 7\cdot 9+2\cdot 11\cdot 1){\bmod {77}}=64\\r_{2}&=77-64=13\\r_{3}&=(-3\cdot 7\cdot 9-2\cdot 11\cdot 1){\bmod {77}}=\mathbf {20} \\r_{4}&=77-20=57\end{aligned}}}$

и мы видим, что это желаемый открытый текст. Обратите внимание, что все четыре кандидата являются квадратными корнями из 15 по модулю 77. То есть для каждого кандидата , поэтому каждый шифрует одно и то же значение, 15.${\displaystyle r_{3}}$${\displaystyle r_{i}^{2}{\bmod {77}}=15}$${\displaystyle r_{i}}$

Алгоритм цифровой подписи [ править ]

Криптосистема Рабина может использоваться для создания и проверки цифровых подписей . Для создания подписи требуется закрытый ключ . Для проверки подписи требуется открытый ключ .${\displaystyle (p,q)}$${\displaystyle n}$

Подписание [ править ]

Сообщение может быть подписано закрытым ключом следующим образом.${\displaystyle m<n}$${\displaystyle (p,q)}$

1. Сгенерируйте случайное значение .${\displaystyle u}$
2. Для вычисления используйте криптографическую хеш-функцию , где полоса обозначает конкатенацию. должно быть целым числом меньше .${\displaystyle H}$${\displaystyle c=H(m|u)}$${\displaystyle c}$${\displaystyle n}$
3. Считайте значение, зашифрованное Рабином, и попытайтесь расшифровать его, используя закрытый ключ . Это будет производить обычные четыре результата, .${\displaystyle c}$${\displaystyle (p,q)}$${\displaystyle r_{1},r_{2},r_{3},r_{4}}$
4. Можно было бы ожидать , что шифрование каждого будет производить . Тем не менее, это будет верно только в том случае , случается, квадратичный вычет по модулю и . Чтобы определить, так ли это, зашифруйте первый результат дешифрования . Если он не шифруется , повторите этот алгоритм с новым случайным образом . Ожидаемое количество повторений этого алгоритма перед поиском подходящего - 4.${\displaystyle r_{i}}$${\displaystyle c}$${\displaystyle c}$${\displaystyle p}$${\displaystyle q}$${\displaystyle r_{1}}$${\displaystyle c}$${\displaystyle u}$${\displaystyle c}$
5. Найдя, что зашифровывает , подпись есть .${\displaystyle r_{1}}$${\displaystyle c}$${\displaystyle (r_{1},u)}$

Проверка подписи [ править ]

Подпись для сообщения может быть проверена с помощью открытого ключа следующим образом.${\displaystyle (r,u)}$${\displaystyle m}$${\displaystyle n}$

1. Вычислить .${\displaystyle c=H(m|u)}$
2. Зашифруйте с помощью открытого ключа .${\displaystyle r}$${\displaystyle n}$
3. Подпись действительна тогда и только тогда, когда шифрование равно .${\displaystyle r}$${\displaystyle c}$

Оценка алгоритма [ править ]

Эффективность [ править ]

Расшифровка дает три ложных результата в дополнение к правильному, поэтому необходимо угадать правильный результат. Это главный недостаток криптосистемы Рабина и один из факторов, не позволивших ей найти широкое практическое применение.

Если открытый текст предназначен для представления текстового сообщения, угадать несложно; однако, если открытый текст предназначен для представления числового значения, эта проблема становится проблемой, которую необходимо решить с помощью какой-либо схемы устранения неоднозначности. Для устранения этой проблемы можно выбрать открытые тексты со специальной структурой или добавить отступы . Способ устранения неоднозначности инверсии был предложен Блюмом и Уильямсом: два используемых простых числа ограничиваются простыми числами, конгруэнтными 3 по модулю 4, а область возведения в квадрат ограничивается набором квадратичных вычетов. Эти ограничения превращают функцию возведения в квадрат в перестановку лазейки , устраняя двусмысленность. ^[3]

Эффективность [ править ]

Для шифрования необходимо вычислить квадрат по модулю n . Это более эффективно, чем RSA , который требует вычисления хотя бы куба.

Для дешифрования применяется китайская теорема об остатках , а также два модульных возведения в степень . Здесь эффективность сопоставима с RSA.

Устранение неоднозначности приводит к дополнительным вычислительным затратам, и это то, что не позволяет криптосистеме Рабина найти широкое практическое применение. ^{[ необходима цитата ]}

Безопасность [ править ]

Было доказано, что любой алгоритм, который расшифровывает зашифрованное Рабином значение, может быть использован для факторизации модуля . Таким образом, расшифровка Рабина не менее сложна, чем проблема целочисленной факторизации, что не было доказано для RSA. Обычно считается, что не существует алгоритма полиномиального времени для факторизации, что означает, что не существует эффективного алгоритма для дешифрования зашифрованного Рабином значения без закрытого ключа . ${\displaystyle n}$${\displaystyle (p,q)}$

Криптосистема Рабина не обеспечивает неотличимости от выбранных атак с открытым текстом, поскольку процесс шифрования является детерминированным. Злоумышленник, учитывая зашифрованный текст и сообщение кандидата, может легко определить, кодирует ли зашифрованный текст сообщение кандидата (просто проверив, дает ли шифрование сообщения кандидата данный зашифрованный текст).

Криптосистема Рабина не защищена от выбранной атаки зашифрованного текста (даже когда сообщения с вызовом выбираются равномерно случайным образом из пространства сообщений). ^{[1] : 150 За} счет добавления избыточности, например, повторения последних 64 бит, система может быть создана для создания единого корня. Это предотвращает эту конкретную атаку с выбранным зашифрованным текстом, поскольку алгоритм дешифрования затем создает только корень, который злоумышленник уже знает. Если применить этот метод, доказательство эквивалентности с проблемой факторизации не удастся, поэтому с 2004 года неясно, является ли этот вариант безопасным. Справочник по прикладной криптографииМенезесом, Oorschot и Ванстоун считает эту эквивалентность вероятно, однако, до тех пор , как нахождение корней остается из двух частей процесса (1. Корни и и 2. Применение китайской теоремы об остатках).${\displaystyle {\bmod {p}}}$${\displaystyle {\bmod {q}}}$

См. Также [ править ]

• Темы в криптографии
• Блюм Блюм Шуб
• Алгоритм Шанкса – Тонелли
• Криптосистема Шмидта-Самоа
• Криптосистема Блюма – Гольдвассера

Заметки [ править ]

Ссылки [ править ]

• Бухманн, Йоханнес. Einführung in die Kryptographie . Второе издание. Берлин: Springer, 2001. ISBN 3-540-41283-2. 
• Менезеш, Альфред; van Oorschot, Paul C .; и Ванстон, Скотт А. Справочник по прикладной криптографии . CRC Press, октябрь 1996 г. ISBN 0-8493-8523-7 
• Рабин, Майкл. Оцифрованные подписи и функции открытого ключа как неразрешимые, как факторизация (в формате PDF). Лаборатория компьютерных наук Массачусетского технологического института, январь 1979 г.
• Скотт Линдхерст, Анализ алгоритма Шанка для вычисления квадратных корней в конечных полях. in R Gupta and KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, vol 19 CRM Proc & Lec Notes, AMS, август 1999.
• Р. Кумандури и К. Ромеро, Теория чисел с компьютерными приложениями, Alg 9.2.9, Прентис Холл, 1997. Вероятностная функция для квадратного корня из квадратичного вычета по простому модулю.

Внешние ссылки [ править ]

• Менезес, Оршот, Ванстон, Скотт: Справочник по прикладной криптографии (бесплатные загрузки в формате PDF), см. Главу 8