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

Поделись знанием:
Перейти к: навигация, поиск

Криптосистема Рабина — криптографическая система с открытым ключом, безопасность которой обеспечивается сложностью поиска квадратных корней составного числа. Безопасность системы, как и безопасность метода RSA, обусловлена сложностью разложения на множители больших чисел. Зашифрованное сообщение можно расшифровать 4 способами. Недостатком системы является необходимость выбора истинного сообщения из 4-х возможных.





История

В январе 1979 года Майкл О. Рабин опубликовал описание своей системы. Было доказано, что восстановление исходного текста из зашифрованного столь же трудно, как факторизация больших чисел. Система Рабина стала первой асимметричной криптосистемой, для которой было выполнено такое доказательство. Сложность восстановления связана с трудностью извлечения квадратного корня по модулю составного числа N = р · q. Задача факторизации и задача по извлечению квадратного корня эквивалентны, то есть:

  • зная простые делители числа N можно извлекать квадратные корни по модулю N;
  • умея извлекать квадратные корни по модулю N, можно разложить N на простые множители.

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

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

Процесс генерации ключей следующий:

  • выбираются два случайных числа p и q с учётом следующих требований:
    • числа должны быть большими (см. разрядность);
    • числа должны быть простыми;
    • должно выполняться условие: pq ≡ 3 mod 4.
Выполнение этих требований сильно ускоряет процедуру извлечения корней по модулю р и q;
  • вычисляется число n = p · q;
  • число n — открытый ключ; числа p и q — закрытый.

Пример. Пусть p = 7 и q = 11. Тогда n = p · q = 7 · 11 = 77. Число n = 77 — открытый ключ, а числа p = 7 и q = 11 — закрытый. Получатель сообщает отправителям число 77. Отправители шифруют сообщение, используя число 77, и отправляют получателю. Получатель расшифровывает сообщение с помощью чисел 7 и 11. Приведённые ключи плохи для практического использования, так как число 77 легко раскладывается на простые множители (7 и 11).

Шифрование

Исходное сообщение m (текст) шифруется с помощью открытого ключа — числа n по следующей формуле:

c = m² mod n.

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

Пример (продолжение). Пусть исходным текстом является m = 20. Тогда зашифрованным текстом будет: c = m² mod n = 20² mod 77 = 400 mod 77 = 15.

Расшифровка

Для расшифровки сообщения необходим закрытый ключ — числа p и q. Процесс расшифровки выглядит следующим образом:

<math>\begin{matrix}

r & = & ( y_p \cdot p \cdot m_q + y_q \cdot q \cdot m_p) \, \bmod \, n \\ -r & = & n - r \\ s & = & ( y_p \cdot p \cdot m_q - y_q \cdot q \cdot m_p) \, \bmod \, n \\ -s & = & n - s \end{matrix}</math>

Одно из этих чисел является истинным открытым текстом m.

Пример (окончание). В результате расшифровки получаем: <math>m \in \{ 64, \mathbf{20}, 13, 57 \}</math>. Видим, что один из корней является исходным текстом m.

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

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

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

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

Скорость вычислений

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

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

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

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

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

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

Стойкость по принципу «все или ничего» заключается в том, что, имея текст, зашифрованный определенным алгоритмом, атакующий должен восстановить блок исходного текста, размер которого, как правило, определяется параметром безопасности криптосистемы. Имея исходный и зашифрованный текст, атакующий должен восстановить целый блок секретного ключа. При этом атакующий либо добивается полного успеха, либо не получает ничего. Под словом «ничего» подразумевается, что атакующий не имеет никакой секретной информации ни до, ни после безуспешной атаки.

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

К примеру, при добавлении избыточности, например, повторение последних 64 бита, можно сделать корень единственным. Алгоритм расшифрования в этом случае выдает единственный корень, который уже известен атакующему.

Процесс дополнительно уязвим, так как при кодировании используются только квадратные остатки. В примере при n = 77 используется только 23 из 76 возможных состояний.

См. также

Напишите отзыв о статье "Криптосистема Рабина"

Литература

  • Ошибка Lua : attempt to index local 'entity' (a nil value).
  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.


Отрывок, характеризующий Криптосистема Рабина

– Знаешь ли ты или не знаешь, где это завещание? – спрашивал князь Василий еще с большим, чем прежде, подергиванием щек.
– Да, я была глупа, я еще верила в людей и любила их и жертвовала собой. А успевают только те, которые подлы и гадки. Я знаю, чьи это интриги.
Княжна хотела встать, но князь удержал ее за руку. Княжна имела вид человека, вдруг разочаровавшегося во всем человеческом роде; она злобно смотрела на своего собеседника.
– Еще есть время, мой друг. Ты помни, Катишь, что всё это сделалось нечаянно, в минуту гнева, болезни, и потом забыто. Наша обязанность, моя милая, исправить его ошибку, облегчить его последние минуты тем, чтобы не допустить его сделать этой несправедливости, не дать ему умереть в мыслях, что он сделал несчастными тех людей…
– Тех людей, которые всем пожертвовали для него, – подхватила княжна, порываясь опять встать, но князь не пустил ее, – чего он никогда не умел ценить. Нет, mon cousin, – прибавила она со вздохом, – я буду помнить, что на этом свете нельзя ждать награды, что на этом свете нет ни чести, ни справедливости. На этом свете надо быть хитрою и злою.
– Ну, voyons, [послушай,] успокойся; я знаю твое прекрасное сердце.
– Нет, у меня злое сердце.
– Я знаю твое сердце, – повторил князь, – ценю твою дружбу и желал бы, чтобы ты была обо мне того же мнения. Успокойся и parlons raison, [поговорим толком,] пока есть время – может, сутки, может, час; расскажи мне всё, что ты знаешь о завещании, и, главное, где оно: ты должна знать. Мы теперь же возьмем его и покажем графу. Он, верно, забыл уже про него и захочет его уничтожить. Ты понимаешь, что мое одно желание – свято исполнить его волю; я затем только и приехал сюда. Я здесь только затем, чтобы помогать ему и вам.
– Теперь я всё поняла. Я знаю, чьи это интриги. Я знаю, – говорила княжна.
– Hе в том дело, моя душа.
– Это ваша protegee, [любимица,] ваша милая княгиня Друбецкая, Анна Михайловна, которую я не желала бы иметь горничной, эту мерзкую, гадкую женщину.
– Ne perdons point de temps. [Не будем терять время.]
– Ax, не говорите! Прошлую зиму она втерлась сюда и такие гадости, такие скверности наговорила графу на всех нас, особенно Sophie, – я повторить не могу, – что граф сделался болен и две недели не хотел нас видеть. В это время, я знаю, что он написал эту гадкую, мерзкую бумагу; но я думала, что эта бумага ничего не значит.
– Nous у voila, [В этом то и дело.] отчего же ты прежде ничего не сказала мне?
– В мозаиковом портфеле, который он держит под подушкой. Теперь я знаю, – сказала княжна, не отвечая. – Да, ежели есть за мной грех, большой грех, то это ненависть к этой мерзавке, – почти прокричала княжна, совершенно изменившись. – И зачем она втирается сюда? Но я ей выскажу всё, всё. Придет время!


В то время как такие разговоры происходили в приемной и в княжниной комнатах, карета с Пьером (за которым было послано) и с Анной Михайловной (которая нашла нужным ехать с ним) въезжала во двор графа Безухого. Когда колеса кареты мягко зазвучали по соломе, настланной под окнами, Анна Михайловна, обратившись к своему спутнику с утешительными словами, убедилась в том, что он спит в углу кареты, и разбудила его. Очнувшись, Пьер за Анною Михайловной вышел из кареты и тут только подумал о том свидании с умирающим отцом, которое его ожидало. Он заметил, что они подъехали не к парадному, а к заднему подъезду. В то время как он сходил с подножки, два человека в мещанской одежде торопливо отбежали от подъезда в тень стены. Приостановившись, Пьер разглядел в тени дома с обеих сторон еще несколько таких же людей. Но ни Анна Михайловна, ни лакей, ни кучер, которые не могли не видеть этих людей, не обратили на них внимания. Стало быть, это так нужно, решил сам с собой Пьер и прошел за Анною Михайловной. Анна Михайловна поспешными шагами шла вверх по слабо освещенной узкой каменной лестнице, подзывая отстававшего за ней Пьера, который, хотя и не понимал, для чего ему надо было вообще итти к графу, и еще меньше, зачем ему надо было итти по задней лестнице, но, судя по уверенности и поспешности Анны Михайловны, решил про себя, что это было необходимо нужно. На половине лестницы чуть не сбили их с ног какие то люди с ведрами, которые, стуча сапогами, сбегали им навстречу. Люди эти прижались к стене, чтобы пропустить Пьера с Анной Михайловной, и не показали ни малейшего удивления при виде их.
– Здесь на половину княжен? – спросила Анна Михайловна одного из них…
– Здесь, – отвечал лакей смелым, громким голосом, как будто теперь всё уже было можно, – дверь налево, матушка.
– Может быть, граф не звал меня, – сказал Пьер в то время, как он вышел на площадку, – я пошел бы к себе.
Анна Михайловна остановилась, чтобы поровняться с Пьером.
– Ah, mon ami! – сказала она с тем же жестом, как утром с сыном, дотрогиваясь до его руки: – croyez, que je souffre autant, que vous, mais soyez homme. [Поверьте, я страдаю не меньше вас, но будьте мужчиной.]
– Право, я пойду? – спросил Пьер, ласково чрез очки глядя на Анну Михайловну.
– Ah, mon ami, oubliez les torts qu'on a pu avoir envers vous, pensez que c'est votre pere… peut etre a l'agonie. – Она вздохнула. – Je vous ai tout de suite aime comme mon fils. Fiez vous a moi, Pierre. Je n'oublirai pas vos interets. [Забудьте, друг мой, в чем были против вас неправы. Вспомните, что это ваш отец… Может быть, в агонии. Я тотчас полюбила вас, как сына. Доверьтесь мне, Пьер. Я не забуду ваших интересов.]
Пьер ничего не понимал; опять ему еще сильнее показалось, что всё это так должно быть, и он покорно последовал за Анною Михайловной, уже отворявшею дверь.
Дверь выходила в переднюю заднего хода. В углу сидел старик слуга княжен и вязал чулок. Пьер никогда не был на этой половине, даже не предполагал существования таких покоев. Анна Михайловна спросила у обгонявшей их, с графином на подносе, девушки (назвав ее милой и голубушкой) о здоровье княжен и повлекла Пьера дальше по каменному коридору. Из коридора первая дверь налево вела в жилые комнаты княжен. Горничная, с графином, второпях (как и всё делалось второпях в эту минуту в этом доме) не затворила двери, и Пьер с Анною Михайловной, проходя мимо, невольно заглянули в ту комнату, где, разговаривая, сидели близко друг от друга старшая княжна с князем Васильем. Увидав проходящих, князь Василий сделал нетерпеливое движение и откинулся назад; княжна вскочила и отчаянным жестом изо всей силы хлопнула дверью, затворяя ее.
Жест этот был так не похож на всегдашнее спокойствие княжны, страх, выразившийся на лице князя Василья, был так несвойствен его важности, что Пьер, остановившись, вопросительно, через очки, посмотрел на свою руководительницу.