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

Схема шифрования с открытым ключом

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

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

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

История

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

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

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

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

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

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

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

Затем идет открытый ключ, а пара — закрытый ключ. ${\displaystyle n}$ ${\displaystyle (p,q)}$

Шифрование

Сообщение можно зашифровать, сначала преобразовав его в число с помощью обратимого преобразования, а затем вычислив . Шифрованный текст . ${\displaystyle M}$ ${\displaystyle m<n}$ ${\displaystyle c=m^{2}{\bmod {n}}}$ ${\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}$ ${\displaystyle (p,q)}$

1. Генерация случайного значения . ${\displaystyle u}$
2. Используйте криптографическую хэш-функцию для вычисления , где двойная черта обозначает конкатенацию. должно быть целым числом меньше . ${\displaystyle H}$ ${\displaystyle c=H(m\mathbin {\Vert } u)}$ ${\displaystyle c}$ ${\displaystyle n}$
3. Найдите квадратный корень из закрытого ключа . Это даст обычные четыре результата : . ${\displaystyle c}$ ${\displaystyle (p,q)}$ ${\displaystyle r_{1},r_{2},r_{3},r_{4}}$
4. Можно было бы ожидать, что возведение каждого в квадрат даст . Однако это будет верно только в том случае, если это квадратичный вычет по модулю и . Чтобы определить, так ли это, Square . Если это не дает результата , повторите этот алгоритм с новым случайным числом . Ожидаемое количество раз, которое необходимо повторить этот алгоритм, прежде чем будет найден подходящий вариант, равно 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\mathbin {\Vert } u)}$
2. Вычислить ${\displaystyle r'=c^{2}{\bmod {n}}}$
3. Подпись действительна, если она является подделкой, в противном случае. ${\displaystyle r'\mathrel {\stackrel {?}{=}} r}$

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Гэлбрейт, Стивен Д. (2012). «§24.2: Учебник по криптосистеме Рабина». Математика криптографии с открытым ключом . Издательство Кембриджского университета. стр. 491–494. ISBN 978-1-10701392-6.
2. Белларе, Михир ; Гольдвассер, Шафи (июль 2008 г.). «§2.3.4 Кандидат в функцию квадратурного люка Рабина». Конспекты лекций по криптографии (PDF) . стр. 29–32.
3. Рабин, Майкл О. (1978). «Цифровые подписи». В Демилло, Ричард А .; Добкин, Дэвид П .; Джонс, Анита К .; Липтон, Ричард Дж. (ред.). Основы безопасных вычислений . Нью-Йорк: Академическая пресса. стр. 155–168. ISBN 0-12-210350-5.
4. Рабин, Майкл О. (январь 1979 г.). Цифровые подписи и функции открытого ключа, столь же неразрешимые, как и факторизация (PDF) (Технический отчет). Кембридж, Массачусетс, США: Лаборатория компьютерных наук Массачусетского технологического института. ТР-212.
5. Белларе, Михир ; Рогауэй, Филипп (май 1996 г.). Маурер, Ули (ред.). Точная безопасность цифровых подписей — как подписывать с помощью RSA и Rabin . Достижения в криптологии – EUROCRYPT '96. Конспекты лекций по информатике. Том. 1070. Сарагоса, Испания: Спрингер. стр. 399–416. дои : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-61186-8.
6. Стинсон, Дуглас (2006). «5,8». Криптография: теория и практика (3-е изд.). Чепмен и Холл/CRC. стр. 211–214. ISBN 978-1-58488-508-5.
7. Менезес, Альфред Дж .; ван Оршот, Пол С .; Ванстон, Скотт А. (октябрь 1996 г.). «§8.3: Шифрование с открытым ключом Рабина». Справочник по прикладной криптографии (PDF) . ЦРК Пресс. стр. 292–294. ISBN 0-8493-8523-7.
8. Белларе, Михир ; Гольдвассер, Шафи (июль 2008 г.). «§2.3.5 Возводящую в квадрат перестановку, которую так же трудно инвертировать, как и факторизацию». Конспекты лекций по криптографии (PDF) . стр. 32–33.

Рекомендации

• Бухманн, Йоханнес. Einführung in die Kryptographye . Второе издание. Берлин: Springer, 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.