Современные системы шифрования (Лабораторная работа № 1), страница 2

Криптосистема RSA

Метод шифрования RSA предложен в 1977 году Ривестом, Шамиром и Адлеманом (Rivest, Shamir, Adleman), как реализация идеи Диффи и Хеллмена.

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

Предположим, что некоторый пользователь (Борис) желает, чтобы ему передали секретное сообщение. Для этого он делает общедоступными два числа: и  (открытый ключ), которые подчинены двум условиям:

1.  , где  и  – большие простые числа, которые Борис держит в секрете. Числа  и  обычно выбираются порядком не ниже, чем .

2.  Число  берется взаимно простым с .

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

Чтобы восстановить исходный текст, Борис поступает так:

1.  Находит число  такое, что  и . Это сравнение разрешимо единственным образом, поскольку . Здесь как раз и проявялется особенность RSA. Для решения сравнения  Борис должен вычислить , что для него не составит труда, так как . Любой другой пользователь, который знает только , вынужден находить  и , т.е. разлагать число  на простые сомножители, а эта задача при больших  и  имеет большую вычислительную сложность.

2.  Далее, имея в распоряжении число , Борис вычисляет , которая и есть представление  исходного текста. Действительно, применяя теорему Эйлера, получаем .

Атаки на криптосистему RSA

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

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

2.  Малый открытый показатель. Поскольку время вычислений в алгоритме RSA для данного модуля целиком зависит от размера показателей  и , очень хочется выбрать эти показатели как можно меньше. Например, при показателе, равном 3 (наименьший возможный показатель), требуется всего одно возведение в квадрат и одно умножение по модулю  – так почему бы не сэкономить время вычислений?

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

, , .

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

.

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