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

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

Криптосистема Рабина — это семейство шифрования с открытым ключом схем .основан на функции-ловушке , безопасность которой, как и у RSA , связана со сложностью факторизации целых чисел .

Преимущество функции-лазейки Рабина состоит в том, что математически доказано, что ее инвертирование так же сложно, как и факторизация целых чисел, в то время как для функции-лазейки RSA такого доказательства не существует.Его недостаток заключается в том, что каждый выходной сигнал функции Рабина может быть сгенерирован любым из четырех возможных входных данных; если каждый вывод представляет собой зашифрованный текст, при расшифровке требуется дополнительная сложность, чтобы определить, какой из четырех возможных входных данных был истинным открытым текстом.Наивные попытки обойти эту проблему часто либо позволяют атаковать выбранный зашифрованный текст для восстановления секретного ключа, либо, закодировав избыточность в пространстве открытого текста, делают недействительным доказательство безопасности относительно факторинга.

Схемы шифрования с открытым ключом, основанные на лазейке Рабина, используются в основном для примеров в учебниках.Напротив, RSA лежит в основе стандартных схем шифрования с открытым ключом, таких как RSAES-PKCS1-v1_5 и RSAES-OAEP , которые широко используются на практике.

История

Функция лазейки Рабина была впервые опубликована как часть схемы подписи Рабина в 1978 году Майклом О. Рабином . Схема подписи Рабина была первой схемой цифровой подписи , в которой было доказано, что подделка подписи столь же сложна, как факторинг.

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

Алгоритм шифрования

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

Генерация ключей

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

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

Затем $n$ это открытый ключ и пара $(p,q)$ это закрытый ключ.

Шифрование

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

Расшифровка

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

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

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

   ${\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}}$

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

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

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

$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$

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

Пример

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

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

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

   ${\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}}$

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

цифровой

Основная статья: подпись Рабина

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

Подписание

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

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

Проверка подписи

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

1. Вычислить $c=H(m\mathbin {\Vert } u)$.
2. Вычислить $r'=c^{2}{\bmod {n}}$
3. Подпись действительна, если $r'\mathrel {\stackrel {?}{=}} r$ а в остальном подделка.

Оценка алгоритма

Эффективность

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

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

Эффективность

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

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

Безопасность

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

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

Криптосистема Рабина небезопасна против атаки с выбранным зашифрованным текстом (даже когда сообщения-запросы выбираются равномерно случайным образом из пространства сообщений). Добавляя избыточность, например повторение последних 64 битов, можно заставить систему производить один корень. Это предотвращает атаку с выбранным зашифрованным текстом, поскольку алгоритм дешифрования создает только тот корень, который уже известен злоумышленнику. Если применить этот метод, доказательство эквивалентности с проблемой факторизации не удастся, поэтому по состоянию на 2004 год неясно, безопасен ли этот вариант. Однако «Справочник по прикладной криптографии» Менезеса, Ооршота и Ванстона считает эту эквивалентность вероятной, пока нахождение корней остается процессом, состоящим из двух частей (1. корни ${\bmod {p}}$ и ${\bmod {q}}$ и 2. применение китайской теоремы об остатках).

См. также

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

Ссылки

• Бухманн, Джон. Введение в криптографию . Второе издание. Берлин: Спрингер, 2001. ISBN   3-540-41283-2
• Менезес, Альфред; ван Оршот, Пол К.; и Ванстон, Скотт А. Справочник по прикладной криптографии . CRC Press, октябрь 1996 г. ISBN   0-8493-8523-7
• Рабин, Майкл. Цифровые подписи и функции открытого ключа, столь же неразрешимые, как факторизация (в PDF). Лаборатория компьютерных наук Массачусетского технологического института, январь 1979 г.
• Скотт Линдхерст, Анализ алгоритма Шэнка для вычисления квадратных корней в конечных полях. в Р. Гупте и К.С. Уильямсе, Proc 5th Conf Can Nr Theo Assoc, 1999 г., том 19 CRM Proc & Lec Notes, AMS, август 1999 г.
• Р. Кумандури и К. Ромеро, Теория чисел с компьютерными приложениями, Alg 9.2.9, Prentice Hall, 1997. Вероятностный метод извлечения квадратного корня из квадратичного вычета по модулю простого числа.

Внешние ссылки

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