Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Если бы существовали эффективные методы разложения на сомножители
(факторинга), то, разложив n на сомножители (факторы) p и q, можно было бы получить частный (private) ключ d. Таким образом надежность криптосистемы
RSA основана на трудноразрешимой – практически неразрешимой – задаче разложения n на сомножители (то есть на невозможности факторинга n) так как в настоящее время эффективного способа поиска сомножителей не существует.

Ниже описывается использование системы RSA для шифрования информации и создания цифровых подписей (практическое применение немного отличается).

2. Шифрование

Предположим, Алиса хочет послать Бобу сообщение M. Алиса создает зашифрованный текст С, возводя сообщение M в степень e и умножая на модуль n: C = M[pic] (mod n), где e и n – открытый (public) ключ Боба. Затем Алиса посылает С (зашифрованный текст) Бобу. Чтобы расшифровать полученный текст,
Боб возводит полученный зашифрованный текст C в степень d и умножает на модуль n: M = cd(mod n); зависимость между e и d гарантирует, что Боб вычислит M верно. Так как только Боб знает d, то только он имеет возможность расшифровать полученное сообщение.

3. Цифровая подпись

Предположим, Алиса хочет послать Бобу сообщение M , причем таким образом, чтобы Боб был уверен, что сообщение не было взломано и что автором сообщения действительно является Алиса. Алиса создает цифровую подпись S возводя M в степень d и умножая на модуль n: S = M[pic] (mod n), где d и n
– частный ключ Алисы. Она посылает M и S Бобу.

Чтобы проверить подпись, Боб возводит S в степень e и умножает на модуль n: M = S[pic] (mod n), где e и n – открытый (public) ключ Алисы.

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

4. Скорость работы алгоритма RSA

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

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

Если k – количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым
(public) ключом пропорционально второй степени k, количество шагов для операций частного (private) ключа – третьей степени k, количество шагов для операции создания ключей – четвертой степени k.

Методы "быстрого умножения" – например, методы основанные на Быстром
Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из- за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования реализующих алгоритм RSA быстро увеличиваются.

Алгоритм RSA намного медленнее чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее по крайней мере в
100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благодаря ведущимся разработкам, работа алгоритма
RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блокового шифрования.

5. Способы взлома криптосистемы RSA

Существует несколько способов взлома RSA. Наиболее эффективная атака: найти закрытый ключ, соответствующий необходимому открытому (public) ключу.
Это позволит нападающему читать все сообщения, зашифрованные открытым
(public) ключом и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудонразрешимой задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления частного (private) ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот можно использовать n для поиска d.
Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = M[pic] (mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная закрытый ключ.
Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако, в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

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

Самое простое нападение на единственное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, например,
"Нападение на рассвете", затем шифрует предполагаемый текст открытым
(public) ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака единственного сообщения применяется в том случае если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападаюший может перехватить эти сообщения и расшифровать сообщение M.
Такую атаку можно предотвратить вводя в сообщение перед каждым шифрованием несколько случайных бит. Также существуют несколько атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение.

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

6. Устойчивые числа и их применение в криптосистеме RSA

В литературе, описывающей алгоритм RSA, часто указывается, что при выборе пары чисел для создания модуля n необходимо, чтобы выбранные числа p и q являлись “устойчивыми". Устойчивые числа имеют некоторые свойства, которые затрудняют разложение на множители их произведение n определенными методами факторинга; одно из этих свойств, например, существование больших главных делителей (факторов) p - 1 и p + 1. Причиной таких мер являются некоторые методы факторинга (разложения на множители) например, метод
Pollard (p – 1) и Pollard (p + 1) особенно подходят для таких чисел p, когда (p – 1) или (p + 1) имеют только маленькие делители (факторы); устойчивые числа устойчивы в частности к таким атакам. Требование использовать устойчивые числа выдвигается в частноси стандатом ANSI X9.31.

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

7. Рекомендуемая длина ключа

Рекомендуем скачать другие рефераты по теме: контрольные работы, экологические рефераты.



Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки