Криптосистема рабина: НОУ ИНТУИТ | Лекция | Криптосистемы

alexxlabРазноеLeave a Comment on Криптосистема рабина: НОУ ИНТУИТ | Лекция | Криптосистемы

Содержание

НОУ ИНТУИТ | Лекция | Криптосистемы

< Лекция 14 || Лекция 15: 1234567

Аннотация: В этой лекции рассматриваются несколько асимметрично-ключевых криптографических систем: Рабина (Rabin), Эль-Гамаля (ElGamal), криптосистемa на основе метода эллиптических кривых (ECC — Elliptic Curve Cryptosystem).

Ключевые слова: криптосистема, RSA, шифрование, дешифрование, открытый ключ, секретный ключ, кортеж, генерация ключей, интегральная схема, вычет, получатель сообщения, криптографическая система, дискретный логарифм, первообразный корень, инверсия, безопасность, curve, cryptosystem, ECC, эллиптические кривые, псевдокод, полином, симметричный ключ, математическая функция, односторонняя функция, коммутативность, первообразная

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

Криптосистема Рабина (М. Rabin) является вариантом криптосистемы RSА. RSА базируется на возведении в степень сравнений. Криптосистема Рабина базируется на квадратичных сравнениях, и ее можно представить как криптографическую систему RSA, в которой значениям e и d присвоены значения e = 2 и d = 1/2. Другими словами, шифрование — и дешифрование — P = C1/2 (mod n).

Открытый ключ доступа в криптосистеме Рабина — n, секретный ключ является кортежем (p, q). Каждый может зашифровать сообщение, используя n, но только Боб может расшифровать сообщение, используя p и q. Дешифрование сообщения неосуществимо для Евы, потому что она не знает значения p и q. Рисунок 15.1 показывает шифрование и дешифрование.

Рис. 15.1. Шифрование, дешифрование и генерация ключей в криптосистеме Рабина

Мы должны подчеркнуть, что если Боб использует RSA, он может сохранить d и n и отказаться после генерации ключей от p, q и . Если Боб использует криптосистему Рабина, он должен сохранить p и q.

Процедура

Генерация ключей, шифрование и дешифрование показаны ниже.

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

intuit.ru/2010/edi»>Боб использует шаги, показанные в алгоритме 15.1, чтобы создать свой открытый ключ доступа и секретный ключ.

15.1.
 Генерации ключей для криптосистемы Рабина
Хотя два простых числа, p  и q, могут быть в форме 4k + 1  или 4k + 3, процесс дешифрования становится более трудным, если используется первая форма. Рекомендуют применять вторую форму, 4k + 3, для  того чтобы сделать дешифрование для Алисы намного проще.
Шифрование
Любой может передать сообщение Бобу, используя его открытый ключ доступа. Процесс шифрования показан алгоритмом 15.2.
 
Rabin_Encryption (n, P)        // n — открытый ключ доступа; 
P — зашифрованный текст  Z*n
{
C <- P2 mod n       // C — зашифрованный текст
return C
}
15.2.
 Шифрование в криптографической системе Рабина
 intuit.ru/2010/edi»>Хотя исходный текст P  может быть выбран из множества Zn,  но  чтобы сделать  дешифрование более простым, мы определили множество, которое находится в Zn*.
Шифрование в криптосистеме Рабина очень простое. Операция нуждается только в одном умножении, что может быть сделано быстро. Это выгодно, когда ресурсы ограничены: например, при использовании карт с интегральной схемой, содержащей микропроцессор с ограниченной  памятью, и при необходимости задействовать центральный процессор на короткое время.
 
Дешифрование
Боб может использовать алгоритм 15.3, чтобы расшифровать полученный зашифрованный текст.
Rabin_Decryption (p, q, C)      // C — зашифрованный текст; p и q — секретные ключи
a1 <- + (C(p+1)/4) mod p
a2 <- - (C(p+1)/4) mod p
b1 <- + (C(q+1)/4) mod q
b2 <- - (C(q+1)/4) mod q
// Алгоритм китайской теоремы об остатках вызывается четыре раза. 
P1 <-  Китайский_остаток (a1, b1, p, q)
P2 <-  Китайский_остаток (a1, b2, p, q)
P3 <-  Китайский_остаток (a2, b1, p, q)
P4 <-  Китайский_остаток (a
 2, b2, p, q)
return P1, P2, P3 и P4
15.3.
 Дешифрование в криптосистеме Рабина
Мы должны подчеркнуть здесь несколько моментов. Дешифрация базируется на решении квадратичного сравнения, которое рассмотрено в лекциях 12-13. Поскольку полученный зашифрованный текст — квадрат исходного текста, это гарантирует, что C  имеет корни (квадратичные вычеты) в Zn*. Алгоритм китайской теоремы об остатке используется, чтобы найти четыре квадратных корня.
Самый важный пункт в криптосистеме Рабина — это то, что она недетерминирована. Дешифрование имеет четыре ответа. Задача получателя сообщения — точно выбрать один из четырех ответов как конечный ответ. Однако во многих ситуациях получатель может легко выбрать правильный ответ.
 
Криптосистема Рабина не детерминирована — дешифрование создает четыре одинаково вероятных исходных текста.
Пример 15.1
Вот очень тривиальный пример, чтобы проиллюстрировать идею.
1. Боб выбирает p = 23  и q = 7. Обратите внимание, что оба являются сравнениями 3 mod 4.
2. Боб вычисляет .
3. Боб объявляет n  открытым и сохраняет p  и q  в секрете.
4. Алиса хочет передать исходный текст P = 24. Обратите внимание, что 161  и 24  являются взаимно простыми; 24  находится в Z161*. Она вычисляет C =  от 242 = 93 mod 161  и передает зашифрованный текст 93  Бобу.
  
5. Боб получает 93  и вычисляет четыре значения:
а. a1 = + (93  (23+1)/4) mod 23 = 1 mod 23
b. a2 = – (93 (23+1)/4) mod 23 = 22 mod 23
с. b 1 =  + (93  (7+1)/4) mod 7 = 4 mod 7
d. b2 = – (93  (7+l)/4) mod 7 =  3 mod 7
  1. Боб имеет четыре возможных ответа — (a1, b 1), (a1, b2),
  2.  (a2, b 1), (a2, b2)   и  использует китайскую теорему об остатках, чтобы найти четыре возможных исходных текста: 116, 24, 137  и 45  (все из них взаимно простые к 161 ). Обратите внимание, что  только второй ответ — исходный текст Алисы.
     
     
     Боб должен принять решение исходя из ситуации. Обратите внимание также, что все четыре ответа при возведении во вторую степень по модулю n дают зашифрованный текст 93, переданный Алисой.
1162 = 93 mod 161    242 = 93 mod 161    1372 = 93 mod 161   452 = 93 mod 161
Безопасность криптографической  системы Рабина
Криптографическая система Рабина  безопасна, пока p  и q  — большие числа. Сложность криптографической системы Рабина  — такая же,  как и у процедуры разложения на множители  больших чисел n  на  два простых сомножителя p  и q. Другими словами, криптографическая система Рабина  так же  безопасна, как и RSA.
Дальше >>
< Лекция 14 || Лекция 15: 1234567
Криптосистема Рабина | это… Что такое Криптосистема Рабина?
Криптосистема Рабина – криптографический алгоритм с открытым ключом. Ее безопасность, как и у RSA, связана с трудностью разложения на множители.
Безопасность схемы Рабина опирается на сложность поиска квадратных корней по модулю составного числа. Сложность этого алгоритма аналогична проблеме разложения на множители.
 
Главным неудобством практического применения криптосистемы Рабина является то, что при расшифровке текста получается четыре различных сообщения. И нужно применить дополнительные усилия для нахождения истинного исходного текста.
Содержание
  • 1 История
  • 2 Генерация ключа
  • 3 Шифрование
  • 4 Расшифрование
  • 5 Оценка алгоритма
    • 5.1 Эффективность
    • 5.2 Скорость вычислений
    • 5.3 Безопасность
  • 6 См. также
  • 7 Литература
 История
Данный алгоритм был опубликован в январе 1979 Майклом О. Рабином. Криптосистема Рабина была первой асимметричной криптосистемой, для которой было доказано, что восстановление исходного текста от зашифрованного столь же трудно как факторизация больших чисел. Точнее, она связана с трудностью извлечения квадратного корня по модулю составного числа N = р • q. Эти две задачи эквивалентны, т. е. — зная простые делители числа N, мы можем извлекать квадратные корни по модулю N, — умея извлекать квадратные корни по модулю N, мы в состоянии разложить N на простые множители.
 Генерация ключа
Как любая асимметричная криптосистема, система Рабина использует и открытый и закрытый ключи. Открытый ключ необходим для шифрования документов и может быть опубликован для всеобщего обозрения. Закрытый ключ должен быть известен только получателям зашифрованных сообщений.
Процесс генерации ключей следующий:
  • Выбираются два больших простых числа p и q, которые удовлетворяют условию . Такой специальный вид простых чисел сильно ускоряет процедуру извлечения корней по модулю р и q.
    •  
  • Тогда . n — открытый ключ. Числа p и q — закрытый ключ.
Для шифрования сообщения необходим открытый ключ n. Чтобы расшифровать зашифрованный текст нужны p и q.
Рассмотрим простой пример. Пусть  и , тогда . Открытый ключ, 77, публикуется для всеобщего обозрения, с помощью его шифруются сообщения. Закрытые ключи, 7 и 11, остаются известны только владельцу, и с помощью их расшифровываются сообщения. Такой выбор ключей – хорошо подходит для примера. Но плохой для практического использования, т.к. разложение на множители 77 тривиально.
 Шифрование
Для шифрования используется только открытый ключ n. С помощью его исходный текст преобразовывается в зашифрованный. Для шифрования сообщения m нужно просто вычислить:
.
Таким образом, шифрование состоит из операции умножения по модулю N, что обеспечивает более высокую скорость шифрования, чем в RSA, даже если в последней выбирают небольшую шифрующую экспоненту.
 
В нашем примере. Пусть исходным текстом является . Тогда зашифрованным текстом будет:
.

 Расшифрование
Расшифрование в этом алгоритме более сложное. Для него нужен закрытый ключ p и q. Процесс выглядит следующим образом:
Сначала, используя алгоритм Эвклида, из уравнения  находим числа  и .
Далее, используя китайскую теорему об остатках, можно вычислить числа
.
Один из этих корней r, -r, s, -s является истинным открытым текстом m .

Вернемся в нашему примеру: В результате расшифровки получаем: . Видим, что один из корней является исходным текстом m.
 Оценка алгоритма
 Эффективность
Расшифровка текста кроме правильного приводит еще к трем ложным результатам. Это является главным неудобством криптосистемы Рабина и одним из факторов, которые препятствовали тому, чтобы она нашла широкое практическое использование.
Если исходный текст представляет собой текстовое сообщение, то определение правильно текста не является трудным. Однако, если сообщение является потоком случайных битов (например, для генерации ключей или цифровой подписи), то определение нужного текста становится реальной проблемой. Одним из способов решить эту проблему является добавление к сообщению перед шифрованием известного заголовка или некой метки.
 Скорость вычислений
Алгоритм Рабина похож на кодирование RSA, но вместо возведения сообщения в степень е при шифровании используется операция возведения блока сообщения в квадрат, что благоприятно сказывается на скорости выполнения алгоритма без ущерба криптостойкости.
Для декодирования китайская теорема об остатках применена вместе с двумя возведениями в степень по модулю. Здесь эффективность сопоставима RSA.
Выбор нужного текста из четырех приводит к дополнительным вычислительным затратам. И это послужило тому, что криптосистема Рабина не получила широкого практического использования.
 Безопасность
Большое преимущество криптосистемы Рабина состоит в том, что случайный текст может быть восстановлен полностью от зашифрованного текста только при условии, что дешифровщик способен к эффективной факторизации открытого ключа n.
Криптосистема Рабина является доказуемо стойкой к атаке на основе подобранного открытого зашифрованного текста в рамках подхода “все или ничего”, тогда и только тогда, когда задача о разложении целого числа на простые множители является трудноразрешимой.
Стойкость по принципу “все или ничего” заключается в том, что, имея текст, зашифрованный определенным алгоритмом, атакующий должен восстановить блок исходного текста, размер которого, как правило, определяется параметром безопасности криптосистемы. Имея исходный и зашифрованный текст, атакующий должен восстановить целый блок секретного ключа. При этом атакующий либо добивается полного успеха, либо не получает ничего. Под словом «ничего» подразумевается, что атакующий не имеет никакой секретной информации ни до, ни после безуспешной атаки.
Криптосистема Рабина является абсолютно беззащитной перед атакой на основе выбранного шифротекста. Как правило, атакующий использует все имеющие у него возможности. Он вступает в контакт с атакованным пользователем, посылают ему зашифрованный текст для последующей расшифровки и требуют вернуть исходный текст.
К примеру, при добавлении избыточности, например, повторение последних 64 бита, можно сделать корень единственным. Алгоритм расшифрования в этом случае выдает единственный корень, который уже известен атакующему.
Процесс дополнительно уязвим, так как при кодировании используются только квадратные остатки. В примере при n = 77 только используется только 23 из 76 возможных состояний.
 См. также
Криптосистема с открытым ключом
Ранцевая криптосистема Меркля-Хеллмана
 Литература
1. http://www.ssl.stu.neva.ru/pws/crypto/appl_rus/ac_18_20.pdf
2. http://www.williamspublishing.com/PDF/5-8459-0847-7/part.pdf
 Криптосистемы Рабина и Пайе 
 
 Подраздел 4.1 Криптосистема Рабина 
 Существует другая криптосистема, основанная на сложности разложения больших целых чисел на множители из-за Рабина. Если \(N=p\cdot q\) является произведением двух больших простых чисел, то извлечение квадратных корней по модулю \(N\) является сложной вычислительной задачей. Шифрование и дешифрование аналогичны тем, которые используются в RSA, однако в случае показателя степени RSA \(e\) мы имеем, что \(\gcd(e,\varphi(N))=1.\) Здесь показатель степени равен зафиксировано, это 2. Шаги, связанные с шифрованием, следующие. 92\pmod{N}.\)
 Расшифровка работает, как описано ниже.
  •  Боб вычисляет квадратный корень из \(c\) по модулю \(N.\)
  •  Имеется 4 корня, поэтому важно иметь некоторую избыточность в сообщении, например, все младшие значащие биты \(k\) двоичного представления \(m\) равны единицам.
 Расшифровка особенно проста, если мы выберем простые числа \(p\) и \(q\) так, что \(p\equiv q\equiv 3\pmod{4}.\) В этом случае критерий Эйлера дает, что 9{(19+1)/4}&\equiv & 3\pmod{19}.\end{выровнено}
\end{уравнение*}
 Наконец, мы определяем решения системы сравнений с помощью китайской теоремы о напоминаниях:
 \begin{уравнение*}
\begin{выровнено}
х\экв 9\пмод{11}&&х\экв 16\пмод{19},\\
х\экв 9\пмод{11}&&х\экв 3\пмод{19},\\
х\экв 2\пмод{11}&&х\экв 16\пмод{19},\\
x\equiv 2\pmod{11}&&x\equiv 3\pmod{19}. \\\end{выровнено}
\end{уравнение*}
 Получаем, что
 92)}\equiv\frac{313}{64}\equiv 28\pmod{N},
\end{уравнение*}
 видим, что сообщение расшифровано.
 Сводка по SageMath. 
 крт()
 Применяет китайскую теорему о напоминании.
 лкм()
 Возвращает наименьшее общее кратное.
 рандинт()
 Возвращает случайное целое число из диапазона.
 random_prime()
 Возвращает случайное простое число из диапазона.
 Упражнения 4.3 Упражнения 
 1. 
 Боб использует криптосистему с открытым ключом Рабина с \(N= 1817 = 23\cdot 79.\) Алиса сообщает Бобу, что двузначное сообщение будет дополнено начальными цифрами «11», и она отправляет 882 в зашифрованном виде. сообщение. Расшифруйте сообщение.
 2. 
 Криптосистема Пайе обладает свойством аддитивной гомоморфности, которое мы проверим на конкретном примере. Пусть \((N,g)=(2501,92)\) и \((m_1,r_1)=(34,5),(m_2,r_2)=(16,7).\) Вычислить два закодированных сообщения \(c_1, c_2\) и показать, что \(c_1\cdot c_2\) совпадает с зашифрованным текстом \(m_1+m_2\) со случайным целым числом \(r=35.\)
 Implementasi Algoritma Rabin Cryptosystem dan Variable Length Encoding Untuk Enkripsi dan Kompresi Citra 
  •  Идентификатор корпуса: 213961519
 @inproceedings{Nasution2019ImplementasiAR,
  title={Реализовать Алгоритм Криптосистемы Рабина и Кодирование Переменной Длины для Enkripsi dan Kompresi Citra},
  автор={Вахью Афанди Насутион},
  год = {2019}
} 
  •  W. Nasution
  •  Опубликовано в 2019 г.
  •  Информатика
 Передача данных, особенно изображений, позволяет людям обмениваться информацией. Данные не всегда являются общедоступными, но есть и секретные данные, поэтому для секретных данных требуется безопасность. Для обеспечения безопасности данных одним из методов является криптография. Криптосистема Рабина — это один из криптографических алгоритмов, использующий открытый ключ и закрытый ключ. Сила этого алгоритма в результате расшифровки, он имеет четыре возможных результата, но только один является реальным… 
 Implementasi Algoritma Kunci Public Rabin Cryptosystem dan Extended Polybius Square Dalam Pengamanan PDF 
     Chitra Meidhantie Utami
     Computer Science
  •  2016
 имеет ряд недостатков, вызвавших несоответствие значения R, S, T и U были получены, когда была получена китайская теорема об остатках.
 Атака модуля сбоя на модульное возведение в квадрат для криптосистемы Рабина 
     М. Каминага, Х. Йошикава, А. Шикода, Тошинори Судзуки
     Информатика, математика
     IEEE Transactions on Rependable and Secure Computing
  •  2018
 новая атака ошибок на модульное возведение в квадрат во время шифрования Рабина, для которого требуется только одна ошибка в открытом ключе, если можно учесть его искаженный открытый ключ.
 Упрощенная криптография 
     N. Smart
     Информатика, математика
     Информационная безопасность и криптография
  •  2016
 В этом вводном учебнике автор объясняет ключевые темы криптографии. Он использует современный подход, в котором определение того, что подразумевается под «безопасным», так же важно, как и создание чего-то, что… Доказано, что для любого заданного n, если авторы могут инвертировать функцию y = E (x1) даже для небольшого процента значений y, то они могут факторизовать n, что, по-видимому, является первым доказанным результатом такого рода. .
 Криптосистема с открытым ключом, использующая усовершенствованный алгоритм Рабина для беспроводных сенсорных сетей 
     A. Siddiqui, Praveen Sen, Jagdish Pimple
     Информатика
  •  2014
 батарея сенсорных узлов эффективно и проверяется на конфиденциальность и целостность данных и подлинность при общении.
 Алгоритмы быстрого декодирования кодов переменной длины 
     Й. Вальдер, М. Краткий, Радим Бача, Й. Платош, В. Снасэль
     Информатика
     Инф. науч.
  •  2012
 Современная криптография 
     Р. Опплигер
     Информатика
     Серия компьютерной безопасности Artech House
  •  2005
 Покрытие без ключа, секретный ключ и криптосистемы с открытым ключом, этот авторитетный справочник обеспечивает прочные практические знания о последних и наиболее важные концепции, методы и системы в современной криптографии.
 Кодирование больших текстов с переменной длиной в фиксированную с использованием алгоритма повторной пары с общими словарями 
     Кей Секин, Хирохито Сасакава, С. Йошида, Т. Кида
     Информатика
     Конференция по сжатию данных 2013
     9000 7 2013
 В этом документе реализован алгоритм Re-Pair с использованием кодов переменной и фиксированной длины, и эмпирически показано, как скорость и степень сжатия метода изменяются путем настройки трех параметров: размера блока, размера словаря и размера общего словаря.
Добавить комментарий 
Ваш адрес email не будет опубликован. Обязательные поля помечены *