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

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

Криптосистема Рабина представляет собой семейство схем шифрования с открытым ключом, основанных на функции-лазейке , безопасность которой, как и у 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 mod 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. Можно было бы ожидать, что возведение каждого из них в квадрат даст . Однако это будет верно только в том случае, если окажется квадратичным вычетом по модулю и . Чтобы определить, так ли это, возведите в квадрат . Если это не даст , повторите этот алгоритм с новым случайным . Ожидаемое количество повторений этого алгоритма, прежде чем найдется подходящее, равно 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. Galbraith, Steven D. (2012). "§24.2: Учебник криптосистемы Рабина". Математика криптографии с открытым ключом . Cambridge University Press. стр. 491–494. ISBN 978-1-10701392-6.
2. Белларе, Михир ; Гольдвассер, Шафи (июль 2008 г.). «§2.3.4 Кандидат в функцию квадратурного люка Рабина». Конспекты лекций по криптографии (PDF) . стр. 29–32.
3. Рабин, Майкл О. (1978). «Оцифрованные подписи». В DeMillo, Ричард А .; Добкин, Дэвид П .; Джонс, Анита К.; Липтон , Ричард Дж. (ред.). Основы безопасных вычислений . Нью-Йорк: Academic Press. стр. 155–168. ISBN 0-12-210350-5.
4. Рабин, Майкл О. (январь 1979 г.). Цифровые подписи и функции открытого ключа, столь же неразрешимые, как факторизация (PDF) (технический отчет). Кембридж, Массачусетс, США: Лаборатория компьютерных наук Массачусетского технологического института. TR-212.
5. Bellare, Mihir ; Rogaway, Phillip (май 1996 г.). Maurer, Ueli (ред.). The Exact Security of Digital Signatures — How to Sign with RSA and Rabin . Advances in Cryptology – EUROCRYPT '96. Lecture Notes in Computer Science. Vol. 1070. Saragossa, Spain: Springer. pp. 399–416. doi : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-61186-8.
6. Stinson, Douglas (2006). "5.8". Криптография: теория и практика (3-е изд.). Chapman & Hall/CRC. стр. 211–214. ISBN 978-1-58488-508-5.
7. Менезес, Альфред Дж .; Ван Ооршот, Пол К.; Ванстоун , Скотт А. (октябрь 1996 г.). "§8.3: Шифрование с открытым ключом Рабина". Справочник по прикладной криптографии (PDF) . CRC Press. стр. 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 г.
• Скотт Линдхерст, Анализ алгоритма Шенка для вычисления квадратных корней в конечных полях. в R Gupta и KS Williams, Proc 5th Conf Can Nr Theo Assoc, 1999, т. 19 CRM Proc & Lec Notes, AMS, август 1999.
• Р. Кумандури и К. Ромеро, Теория чисел с компьютерными приложениями, Alg 9.2.9, Prentice Hall, 1997. Вероятностная функция для квадратного корня из квадратичного вычета по модулю простого числа.

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

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