 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Алгоритм RSA
|
|
Алгоритм RSA защищен патентом США № 4405829. Разработан в 1977 году в Массачусетском технологическом институте (США). Получил название по первым буквам фамилий авторов (Rivest, Shamir, Adleman). Криптостойкость алгоритма RSA основана на вычислительной сложности задачи разложения большого числа на простые множители. Открытый и закрытый ключи являются функциями двух больших простых чисел, разрядностью 100-200 десятичных цифр. Предполагается, что восстановление открытого текста по шифрованному тексту и открытому ключу равносильно разложению числа на два больших простых множителя.
Для генерации двух ключей применяются два больших случайных простых числа р и q. Для обеспечения максимальной безопасности р и q должны иметь одинаковую длину. Рассчитывается произведение п = pq.
Затем случайным образом выбирается ключ шифрования е так, чтобы е и (р -1)(q-1) являлись взаимно простыми числами. С помощью расширенного алгоритма Евклида вычисляется ключ расшифрования d, такой что:
еd ≡ 1(mod(p -1)(q - 1)).
Другими словами:
d = e-1(mod(p- 1)(q - 1)).
Заметим, что d и n также взаимно простые числа.
Числа е и п — это открытый ключ, а число d — закрытый. Числа р и q могут быть отброшены, но они не должны быть раскрыты.
При шифровании сообщение т разбивается на цифровые блоки mi, размерами меньше п (для двоичных данных выбирается самая большая степень числа 2, меньшая п). Зашифрованное сообщение C будет состоять из блоков Ci,причем длина блока Ci,- равна длине блока mi. Таким образом, формула шифрования имеет вид:
Ci = mie mod n
При расшифровке сообщения для каждого зашифрованного блока Ci вычисляется:
mi = Cid mod n
Так как Cid = (mie)d = mik(p-1)(q-1)+1 = mi, все по mod n, то формула восстанавливает сообщение.
Таким образом,
d = e-1(mod(p - 1)(q - 1)) - закрытый ключ
C = те mod n - шифрование
т = Cd mod n - расшифрование.
Чтобы организовать передачу шифрованных сообщений с помощью криптосистемы RSA получатель должен сделать следующее:
с помощью специального алгоритма сгенерировать два больших простых числа p,q, которые необходимо держать в секрете;
сообщить отправителю (или поместить в некоторый общедоступный каталог) число n, равное произведению р и q, а также случайным образом выбранное целое число e, взаимно простое с произведением
(p - 1)(q - 1).
Для расшифрования сообщений, зашифрованных на открытом ключе п, e получателю необходимо иметь число d являющееся мультипликативным обратным числа e по модулю (p-1)(q-1), т.е. остаток от деления произведения de на (p-1)(q-1) должен быть равен единице: de ≡1(mod(p-1)(q-1)). Найти такое число получателю легко, так как наибольший общий делитель e и (p-1)(q-1) равен единице по выбору e.
Таким образом, отправитель знает открытый ключ: п и e, а получатель, кроме этого, имеет секретный ключ d.
Любое передаваемое сообщение можно представить в виде последовательности целых чисел из заданного интервала. Будем считать, что отправитель передает секретное сообщение, представленное последовательностью чисел Х1,...Хк, 0 ≤ Хi≤ n-1, для всех i от 1 до к.
Отправитель для каждого блока Xi передаваемого сообщения вычисляет Сi = (Xie) mod n и передает Сi, по открытому каналу связи.
Имея п, e и Сi,, получатель может расшифровать сообщение, воспользовавшись соотношением
Xi = (Cid) mod n. (2.2)
Докажем сначала выполнение равенства (2.2) для чисел Xi взаимно простых с п.
Так как числа e и d связаны соотношением ed = 1 (mod(p- 1 )(q- 1)), то для некоторого целого к справедливо равенство ed=1+k(p-1)(q-1). Отсюда и из соотношения Cid ≡ Xied(mod n) вытекает, что
Cid ≡ Xi1+k(p-1)(q-1)(mod n). (2.3)
Из теоремы Эйлера следует, что в случае, если числа Xi, и п взаимно просты
Xik(p-1)(q-1) ≡ 1(mod n).
Отсюда и из (2.3) следует выполнение соотношения (2.2) для случая, когда Xi взаимно просто с п.
Предположим теперь, что Xi, имеет общий делитель с числом п, не совпадающий с единицей. В этом случае Xi, делится либо на р, либо на q, так как п у нас равно произведению двух простых чисел р и q. Для определенности будем считать, что Xi, делится на р и Xi=kp, где k - некоторое целое число. Тогда Xi взаимно просто с q и по теореме Эйлера
Xi ≡ Xied(mod q). (2.4)
Обозначим через s остаток от деления Xied-1 на q. Так как Х=kр, для некоторого целого r справедливо представление Xied=kp(rq +s). Отсюда и из (2.4) вытекает соотношение kprq+kps ≡ Xi (mod q).
Следовательно, pks ≡ рк(mod q). Тогда (s-1)pk делится на q, и отсюда s=1, так как k<q и s <q.
В итоге, имеем представление Xied = kprq + kp, из которого вытекает выполнение соотношения Xi ≡ Xied(mod pq), эквивалентного (2.2).
Таким образом, получатель, вычислив (Cid) mod n, действительно получит i-й блок первоначального сообщения.
Рассмотрим в качестве примера случай р=3, q=11, n =3*11=33, e =1 и d=3. Легко убедиться, что каждое из чисел e =7 и DE=21 взаимно просто с (p-1)(q-1)=20. Для передачи сообщения М="02" отправителю необходимо вычислить C ≡27 (mod 33)≡29. Получатель может расшифровать сообщение 29, возведя его в степень dпо модулю п: 293 ≡2(mod 33). Пусть, как и ранее, наш алфавит состоит из букв русского языка (без буквы Ё) и пробела. Занумеровав элементы этого алфавита числами от 0 до 32, можно зашифровать произвольное сообщение на русском языке. Например, сообщение "ПРОВЕРИМ ЗНАНИЕ АРИФМЕТИКИ" в зашифрованном виде на ключе n =33, e=7 будет выглядеть следующим образом: "27 25 20 29 14 25 02 12 32 28 07 00 07 02 14 32 00 25 02 26 12 14 06 02 10 02".
Очевидно, что шифр в нашем примере является шифром простой замены. Мы уже знаем, что такой шифр можно вскрыть, исследовав частоты встречаемости и взаимное расположение чисел в криптограмме. Однако в данном случае дешифровать получившуюся криптограмму можно гораздо быстрее, если составить полную таблицу зашифрования (см. табл. 2.10). При таком маленьком значении n, противнику легко это сделать, так как по предположению открытый ключ: п=33, e =7 - ему известен.
Таблица 2.10
Полная таблица зашифрования
| А | Б | В | Г | Д | Е | Ж | И | И | К | Л | М | Н | О | П | ||
| Р | С | Т | У | Ф | X | Ц | Ч | Ш | Щ | Ъ | Ы | Ь | Э | Ю | Я | |
Из этой таблицы зашифрования легко получить таблицу расшифрования (табл. 2.11), отсортировав столбцы таблицы 2.10 по последней строке.
Таблица 2.11
Таблица дешифрования
| А | Б | И | Ы | Я | Ъ | Т | Н | С | Г | К | Л | М | У | Е | И | Д |
| Э | Ш | Ь | О | X | Ц | Ч | Ю | Р | Ф | П | В | Ж | Щ |
Сложность составления такой таблицы дешифрования пропорциональна количеству различных блоков, которые могут встретиться в шифруемом сообщении. Поэтому, для того чтобы шифр, основанный на криптосистеме RSA, не допускал дешифрование при неизвестном ключе, необходимо (но не достаточно) выполнение следующих двух условий. Во-первых, должно быть большим число п, которое ограничивает максимальный размер блока, а следовательно, и количество различных блоков. Во-вторых, шифруемые сообщения должны быть достаточно разнообразны. Недопустимо использование системы RSA (а также других криптосистем с открытым ключом) в случае, если сообщения являются комбинацией относительно небольшого количества стандартных фраз. При выполнении указанных выше требований невозможно будет также дешифрование на основе анализа частоты встречаемости и взаимного расположения различных блоков шифрованного сообщения.
Возможность описанной выше атаки служит дополнительным аргументом в пользу того, чтобы системы с открытым ключом применять не для шифрования непосредственно сообщений, а только для передачи секретного ключа, на котором сообщение шифруется с помощью обычной системы шифрования с симметричным ключом.
Другим известным приемом дешифрования системы RSA является метод дешифрования итерациями, заключающийся в повторном шифровании до тех пор, пока вновь не будет получен открытый текст.
Доказано, что вероятность успешной атаки методом дешифрования итерациями маловероятна, если p-1 и q-1 имеют большие простые сомножители p' и q' и, в свою очередь, р'- 1 и q'-1 также имеют большие простые сомножители.
Рассмотрим теперь "лобовой метод" вскрытия системы RSA, который заключается в нахождении числа d, мультипликативного обратного e по модулю (р-1)(q-1). Это легко сделать, если известны числа p и q. Следовательно, решив задачу разложения на сомножители целого числа п, можно дешифровать систему RSA. Для того чтобы усложнить задачу разложения п на простые сомножители, числа р и q должны выбираться случайным образом и иметь достаточно большие значения. Кроме того, числа р и q не должны быть "слишком близкими" друг к другу.
Покажем, каким образом можно использовать близость значений р и q. Без ограничения общности можно считать, что p>q. Для величин x=(p+q)/2 и y=(p-q)/2 справедливо соотношение
x2 –у2 = п. (2.5)
Для того чтобы найти разложение n на простые сомножители, достаточно подобрать целые числа х и у, удовлетворяющие соотношению (2.5). Данное уравнение в нашем случае имеет единственное решение, так как (х+у)(х-у)=п, а п единственным образом раскладывается на простые сомножители. Перебирая в порядке возрастания варианты х > 
, легко найти это решение, так как x=(p+q)/2 будет близким к при условии, что р и q близки. В итоге находим: р=х+у, q=x-y.
Рассмотрим еще один пример. Пусть n=pq = 851. Воспользуемся описанным выше способом, чтобы разложить n на простые сомножители р и q. Так как ≈29.17, берем х=30, вычисляем 302 - 851 = 49 и с первой попытки находим решение уравнения (2.5): х=30, у=7. Отсюда p=30+7=37, q=30 - 7=23.
Кроме указанных выше ограничений на выбор р, q, e и d к данным параметрам предъявляются и другие требования, влияющие на стойкость криптосистемы RSA. Более подробно эти требования изложены в [20].
Далее в учебном пособии объясняется, каким образом можно использовать криптосистему RSA для построения системы цифровой подписи.
В этом случае параметры р, q, e и d должен вырабатывать не получатель, а отправитель сообщений (придерживаясь ранее введенных обозначений, будем считать, что e является ключом зашифрования, a d -расшифрования). Чтобы подписать сообщение М, отправитель вычисляет P=(Me)mod n. Получатель, имея М и Р, вычисляет Рd ≡ М(mod n) и убеждается таким образом в подлинности документа.
Пример. Пусть р=3, q=11, n=33, e=7 и d=3. Отправитель сообщения M="02" вычисляет цифровую подпись 29=(27)mod 33 и посылает получателю пару "02, 29". Чтобы проверить подлинность сообщения "02", получателю достаточно убедиться в том, что 2=(293)mod 33.
Для приведенного алгоритма цифровой подписи противник может использовать следующий способ атаки: взять произвольное Р1 и вычислить сообщение М1=(P1) mod n, имеющее цифровую подпись Р1. Однако при таком способе атаки он не сможет предвидеть полученное значение М1. Скорее всего, сообщение М1, будет совершенно не похоже на открытый текст и, следовательно, противник не сможет ввести получателя в заблуждение. Данная атака представляет реальную опасность в случае передачи каких-либо числовых данных, для которых допустимы все возможные значения подписываемых блоков (или, по крайней мере, существенная доля). Использование хорошей хеш-функции не позволит осуществить данный способ подделки сообщений, так как противник не сможет подобрать текст, имеющий подписанный им хеш-код.
Дата публикования: 2014-11-02; Прочитано: 1793 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
