Криптосистемы с открытым ключом — rsa
В качестве второго примера криптографического алгоритма рассмотрим широко используемую систему с открытым ключом — RSA, названную в честь ее изобретателей — Ривеста (Rivest), Шамира (Shamir) и Альдемана (Aldeman). ЗащитаRSAвытекает из того факта, что в настоящее время не существует эффективного метода нахождения простых множителей больших чисел. Можно показать, что любое целое число можно записать в виде произведения простых чисел. Так, например, 2100 может быть записано как:
2100 = 2 × 2 × 3 × 5 × 5 × 7.
Таким образом, 2, 3, 5 и 7 являются простыми множителями числа 2100. В RSAоткрытый и закрытый ключи создаются из очень больших простых чисел (содержащих сотни десятичных цифр). ВзломRSAэквивалентен обнаружению этих чисел. В настоящее время подобная задача неразрешима, несмотря на то, что математики работают над ней уже несколько столетий.
Создание открытых и закрытых ключей происходит в четыре этапа.
1. Выбираются два больших простых числа, р и q.
2. Вычисляется их произведение n = p×q и z = (p – 1)×(q – 1).
3. Выбирается число d, взаимно простое сz.
4. Вычисляется число е, такое, чтоe×d = 1 mod z.
Одно из чисел, например d, может впоследствии использоваться для расшифровки, а е — для шифрования. Только одно из этих двух чисел будет открытым, какое именно — зависит от используемого алгоритма.
Рассмотрим вариант, когда Алиса хочет, чтобы сообщение, которое она посылает Бобу, было конфиденциально. Другими словами, она хочет быть уверена в том, что никто кроме Боба не сможет перехватить и прочитать ее сообщение. RSAрассматривает любое сообщениет как строку битов. Каждое сообщение сначала разбивается на блоки фиксированной длины, и каждый очередной блокmi представляется в виде числа в двоичном виде, лежащего в интервале 0 ≤mi<п.
Для шифрования сообщеният отправитель вычисляет для каждого блокаmiзначениеci =mei(mod п), которое и отправляется получателю. Расшифровка на стороне получателя производится путем вычисленияmi =cdi(mod п). Отметим, что для шифрования необходимыeиn, в то время как для расшифровки— d и n.
Сравним RSAс симметричными криптосистемами, такими какDES. ДляRSAхарактерен недостаток — сложность вычислений, которая приводит к тому, что расшифровка сообщений, зашифрованных по алгоритмуRSA, занимает в 100–1000 раз больше времени, чем расшифровка сообщений, зашифрованных по алгоритмуDES. Точный показатель зависит от реализации. В результате многие криптографические системы используютRSAтолько для безопасного обмена общими секретными ключами, избегая применять этот способ для шифрования «обычных» данных.
Хэш-функции — md5
В качестве последнего примера широко используемого криптографического алгоритма мы рассмотрим MD5.MD5 — это хэш-функция для вычисления 128-битныхдайджестов сообщений (message digests) фиксированной длины из двоичных исходных строк произвольной длины. Сначала исходная строка дополняется до общей длины в 448 бит (по модулю 512), после чего к ней добавляется длина исходной строки в виде 64-битового целого числа. В результате исходные данные преобразуются в набор 512-битных блоков.
Структура алгоритма приведена на рис. 8.9. Начиная с определенного постоянного 128-битового значения, алгоритм включает в себя k фаз, гдеk — число 512-битных блоков, получившихся из дополненного согласно алгоритму сообщения. В ходе каждой из фаз из 512-битного блока данных и 128-битного дайджеста, вычисленного на предыдущей фазе, вычисляется новый 128-битный дайджест. Фаза алгоритмаMD5 состоит из четырех циклов вычислений, на каждом из которых используется одна из следующих четырех функций:
F(x, y, z) = (х AND у) OR ((NOT х) AND z),
G(x, y, z) = (х AND z) OR (у AND (NOT z)),
H(x, y, z) = x XOR у XOR z,
I(x, y, z) = y XOR (x OR (NOT z)).
Каждая из этих функций работает с 32-битными переменными x,yиz. Чтобы проиллюстрировать, как используются эти функции, рассмотрим 512-битный блокb дополненного сообщения на фазеk. Блокb разделяется на 16 32-битных подблоковb0,b1, …,b15. Как показано на рис. 8.10, в ходе первого цикла для изменения четырех переменных (назовем ихp,q,rиsсоответственно) в ходе 16 итераций используется функцияF. Эти переменные переносятся на очередной цикл, а после окончания этой фазы передаются на следующую. Всего существует 64 заранее определенных константCi. Для указания циклического сдвига влево используется записьх <<< п: биты вх сдвигаются нап позиций, причем биты, ушедшие за левую границу числа, добавляются справа.
Рис. 8.10. 16 итераций первого цикла MD5
Во втором цикле подобным же образом используется функция G, аHиI — соответственно в третьем и четвертом циклах. Каждый шаг, таким образом, включает в себя 64 итерации, и в очередной фазе используются вычисленные на предыдущей фазе значения р,q,rиs.