Современные алгоритмы шифрования

Государственным стандартом шифрования в России является алгоритм, зарегистрирован‐

ный как ГОСТ 28147‐89. Он является блочным шифром, то есть шифрует не отдельные символы, а

64‐битные блоки. В алгоритме предусмотрено 32 цикла преобразования данных с 256‐битным ключом, за счет этого он очень надёжен (обладает высокой криптостойкостью). На современных

компьютерах раскрытие этого шифра путем перебора ключей («методом грубой силы») займет не менее сотен лет, что делает такую атаку бессмысленной. В США используется аналогичный блоч‐

ный шифр AES.

В Интернете популярен алгоритм RSA, названный так по начальным буквам фамилий его ав‐

торов – Р. Райвеста (R. Rivest), А. Шамира (A. Shamir) и Л. Адлемана (L. Adleman). Это алгоритм с

7 Однако такой пароль сложно запомнить.

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

раскрытия шифра требуется много лет работы современных компьютеров.

Для применения алгоритм RSA требуется построить открытый и секретный ключи следую‐

щим образом.

1. Выбрать два больших простых числа, p и q.

2. Найти их произведение n = p ⋅ q

и значение ϕ= (p −1) ⋅ (q −1).

3. Выбрать число e (1 < e < ϕ), которое не имеет общих делителей с ϕ.

4. Найти число d, которое удовлетворяет условию d ⋅ e = k ϕ+ 1 для некоторого целого k.

5. Пара значений

(e, n)

– это открытый ключ RSA (его можно свободно публиковать), а пара

(d, n) – это секретный ключ.

Передаваемое сообщение нужно сначала представить в виде последовательности чисел в интер‐

вале от 0 до n – 1. Для шифрования используют формулу

y = xe mod n,

где x – число исходного сообщения, (e,n) – открытый ключ, y – число закодированного сообщения,

а запись xe mod n обозначает остаток от деления xe на n. Расшифровка сообщения выполняется по формуле

x = yd mod n.

Это значит, что зашифровать сообщение может каждый (открытый ключ общеизвестен), а прочитать его – только тот, кто знает секретный показатель степени d.

Для лучшего понимания мы покажем работу алгоритма RSA на простом примере. Возьмем

p = 3

и q = 7, тогда находим n = p ⋅ q = 21 и ϕ= (p −1) ⋅ (q −1) = 12. Выберем e = 5, тогда ра

венство d ⋅ e = k ϕ+ 1 выполняется, например, при d = 17

ли открытый ключ (5,21) и секретный ключ (17,21).
(и k = 7). Таким образом, мы получи

Зашифруем сообщение «123» с помощью открытого ключа (5,21). Получаем

1 ⇒ 15 mod 21 = 1, 2 ⇒ 25 mod 21 = 11, 3 ⇒ 35 mod 21 = 12,

то есть зашифрованное сообщение состоит из чисел 1, 11 и 12. Зная секретный ключ (17,21), мож‐

но его расшифровать:

1 ⇒ 117 mod 21 = 1, 11 ⇒ 1117 mod 21 = 2, 12 ⇒ 1217 mod 21 = 3.

Мы получили исходное сообщение.

Конечно, вы заметили, что при шифровании и расшифровке приходится вычислять остаток от деления очень больших чисел (например, 1217) на n. Оказывается, само число 1217 в этом случае находить не нужно. Достаточно записать в обычную целочисленную переменную, например, x,

единицу, а потом 17 раз выполнить преобразование x = 12⋅ x mod 21. После этого в переменной x

будет значение 1217 mod 21 = 3. Попробуйте доказать правильность этого алгоритма.

Для того, чтобы расшифровать сообщение, нужно знать секретный показатель степени d. А

для этого, в свою очередь, нужно найти сомножители p и q, такие что n = p ⋅ q. Если n велико, это

очень сложная задача, ее решение перебором вариантов на современном компьютере займет

сотни лет. В 2009 году группа ученых из разных стран в результате многомесячных расчетов на сотнях компьютеров смогла расшифровать сообщение, зашифрованное алгоритмом RSA с 768‐

битным ключом. Поэтому сейчас надежными считаются ключи с длиной 1024 бита и более. Если

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

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

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

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

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

Во многих современных программах есть возможность шифровать данные с паролем. На‐ пример, офисные пакеты OpenOffice.org и Microsoft Office позволяют шифровать все создаваемые документы (для их просмотра и/или изменения нужно ввести пароль). При создании архива (на

 

 

пример, в архиваторах, WinRAR, WinZip) также можно установить пароль, без которого извлечь файлы невозможно.

В простейших задачах для шифрования файлов можно использовать бесплатную программу Шифровальщик (www.familytree.ru/ru/cipher.htm), версии которой существуют для Linux и Windows. Программы TrueCrypt (www.truecrypt.org), BestCrypt (www.jetico.com) и FreeOTFE (freeotfe.org) создают логические диски‐контейнеры, информация на которых шифруется. Свободно распространяемая программа DiskCryptor (diskcryptor.net) позволяет шифровать разделы жестких дисков и даже создавать шифрованные флэш‐диски и CD/DVD диски.

Программа GnuPG (gnupg.org) также относится к свободному программному обеспечению. В ней поддерживаются симметричные и несимметричные шифры, а также различные алгоритмы электронной цифровой подписи.

Контрольные вопросы

1. Какой алгоритм шифрования принят в России в качестве государственного стандарта?

2. Что такое блочный алгоритм шифрования?

3. К какому типу относится алгоритм RSA? На чем основана его криптостойкость?

4. Что такое цифровая подпись?

5. Как можно использовать алгоритм RSA для цифровой подписи?

Дата добавления: 2015-05-31