Файл: Основыинформационнойбезопасности.pdf

39 0,5 0,5
,5 0
1 1







q
q
C
p
)
(
)
(
(2.4)
Таким образом, вероятность появления в криптограмме единицы не зависит от статистических свойств исходного сообщения. И анали- зируя криптограмму, нарушитель не сможет получить дополнитель- ной информации об исходном сообщении. Надо отметить, что подоб- ными свойствами обладает только случайный бесконечный равно- мерно распределенный ключ. Если вероятность появления в ключе единицы отлична от 0,5, то q в формуле (2.4) не удастся исключить из результата.
Рассмотрим, какими же свойствами должен обладать хороший шифр. Во-первых, шифрование и расшифровывание должно осу- ществляться достаточно быстро в тех условиях, в которых применя- ется шифр (с использованием ЭВМ, при шифровании вручную и т. п.). Во-вторых, шифр должен надежно защищать сообщение, т. е. быть стойким к раскрытию.
Криптостойкость — стойкость шифра к раскрытию методами криптоанализа. Она определяется вычислительной сложностью алго- ритмов, применяемых для атаки на шифр. Вычислительная сложность измеряется временной и емкостной сложностями [8].
Для определения сложности алгоритма с конкретной задачей связывается число, называемое размером задачи, которое характери- зует количество входных данных. Например, для задачи умножения чисел размером может быть длина наибольшего из сомножителей.
Временная сложность (или просто сложность) — это время, за- трачиваемое алгоритмом для решения задачи, рассматриваемое как функция от размера задачи. Нередко сложность измеряют количе- ством некоторых элементарных операций. Емкостная сложность — объем памяти, необходимой для хранения полученных в ходе работы данных, как функция от размера задачи.
Очень важное требование к стойкому шифру было сформулиро- вано в XIX веке голландским криптографом Огюстом Керкгоффсом
(Auguste Kerckhoffs). В соответствии с ним, при оценке надежности

40 шифрования необходимо предполагать, что противник знает все об используемой системе шифрования, кроме применяемых ключей.
Данное правило отражает важный принцип организации защиты ин- формации: защищенность системы не должна зависеть от секретности долговременных элементов (т. е. таких элементов, которые невоз- можно было бы быстро изменить в случае утечки секретной инфор- мации).
Существует несколько обобщенных постановок задачи крипто- анализа. Все они формулируются в предположении, что криптоанали- тику известны применяемый алгоритм шифрования и полученные криптограммы. Могут рассматриваться:
- атака при наличии только известной криптограммы;
- атака при наличии известного фрагмента открытого текста. В этом случае, криптоаналитик имеет доступ к криптограммам, а также к соответствующим некоторым из них исходным сообщениям. Зада- ча — определить использующийся при шифровании ключ или рас- шифровать все остальные сообщения. Разновидность данного класса атак — атака с возможностью выбора открытого текста (когда крип- тоаналитик может навязать текст для шифрования и получить соот- ветствующую ему криптограмму);
- атаки, использующие особенности реализации аппаратных шифраторов. В частности, может анализироваться тепловое и элек- тромагнитное излучение от устройств, распространение ошибок после однократного воздействия на аппаратуру (по цепи электропитания или иным образом) и т. д.;
- атака методом полного перебора множества возможных клю- чей. Данная атака также называется «атака методом грубой силы»
(от англ. «brute force»).
Виды шифров
Рассмотрим классификации шифров по разным признакам. По типу преобразований шифры можно разделить на следующие группы:
- шифры замены (подстановки);

41
- шифры перестановки;
- шифры гаммирования;
- шифры на основе аналитических преобразований.
При этом надо учитывать, что некоторые современные шифры совместно используют преобразования различных типов.
Шифры замены (подстановки): преобразование заключается в том, что символы шифруемого текста заменяются символами того или иного алфавита (алфавита криптограммы) в соответствии с зара- нее обусловленной схемой замены.
Подстановки разделяются на одноалфавитные и многоалфа-
витные. В первом случае определенному символу алфавита исходно- го сообщения всегда ставится в соответствие один и тот же символ алфавита криптограммы. Один из наиболее известных шифров данно- го класса — шифр Цезаря. В нем каждая буква алфавита заменялась на следующую через одну после нее. В случае русского алфавита, «а» меняется на «в», «б» на «г» и т. д. Алфавит «замыкался», поэтому «я» надо было заменять на «б». В качестве ключа в данном случае высту- пает число, на которое надо «сдвигать» символ алфавита, в нашем примере — 2. К достоинству таких шифров относится простота пре- образования. Но они легко взламываются путем сравнения частоты появления различных символов в естественном языке и криптограм- ме.
При использовании многоалфавитных подстановок учитывают- ся дополнительные параметры (например, положение преобразуемого символа в тексте), и в зависимости от них символ исходного алфави- та может заменяться на один из нескольких символов алфавита шиф- ртекста. Например, нечетные символы сообщения заменяются по од- ному правилу, четные — по другому.
Шифры перестановок: шифрование заключается в том, что символы исходного текста переставляются по определенному прави- лу в пределах блока этого текста. При достаточной длине блока и

42 сложном, неповторяющемся порядке перестановки можно достичь приемлемой стойкости шифра.
Шифрование гаммированием заключается в том, что символы шифруемого текста складываются с символами некоторой случайной последовательности, называемой гаммой шифра или ключевой гам- мой. Стойкость шифрования определяется длиной (периодом) непо- вторяющейся части гаммы шифра, а также сложностью предугадыва- ния следующих элементов гаммы по предыдущим.
Шифрование аналитическими преобразованиями подразумевает использование аналитического правила (формулы) по которому пре- образуется текст.
По типу использования ключей шифры делятся на:
- симметричные, использующие для шифрования и расшифро- вывания информации один и тот же ключ;
- асимметричные, использующие для шифрования и расшифро- вывания два различных ключа. Данный тип шифров будет подробно рассматриваться в разделе 2.4.
По размеру преобразуемого блока шифры делятся на блочные и потоковые.
Блочные шифры осуществляют преобразование информации блоками фиксированной длины. Если длина шифруемого сообщения некратна размеру блока, то его добавляют до нужной длины последо- вательностью специального вида. Например, это может быть после- довательность 100…0. После расшифровки последний блок просмат- ривают справа налево и отбрасывают «хвост» до первой единицы включительно. Чтобы подобное дополнение было применимо во всех случаях, если сообщение кратно длине блока, в его конец надо доба- вить целый блок указанного вида.
Потоковые шифры предназначены для преобразования сообще- ния поэлементно (элементом может быть бит, символ и т. п.). Приме- ром такого вида шифров являются шифры гаммирования.

43
2.2. СИММЕТРИЧНЫЕ ШИФРЫ
2.2.1. Схема Фейстеля
Современные блочные шифры часто строятся на базе много- кратного повторения некоторого набора операций преобразования, называемых раундом шифрования.
В каждом раунде используется некоторая часть ключа, называе- мая раундовым ключом. Порядок генерации и использования раундо- вых ключей называется расписанием использования ключа шифрова-
ния.
В общем виде подобное итеративное преобразование может быть описано следующей формулой:
)
,
(
1
i
i
i
K
B
E
B


,
(2.5) где E — раундовая функция шифрования,
i
B — выходной блок,
1

i
B
— входной блок для i -го раунда,
i
K — ключ, используемый на
i
-м раунде;
N
i

1

, где N — число раундов. Преобразование
E
должно быть обратимо. Пусть D — раундовая функция дешифро- вания. Тогда раунд обратного преобразования описывает формула:
)
,
(
1 1




i
N
i
i
K
B
D
B
(2.6)
Здесь надо обратить внимание на расписание использования ключей в случае прямого и обратного преобразования. Так, в первом раунде при шифровании будет использоваться первый раундовый ключ, а в первом раунде при расшифровывании — последний.
Для разработки итерационных блочных шифров широко исполь- зуется схема, предложенная в начале 1970-х годов Хорстом Фейсте- лем (Horst Feistel). Данная схема, также называемая сетью Фейстеля, приведена на рис. 2.2. Ее достоинство заключается в том, что она поз- воляет использовать любые (в том числе необратимые) функции F для реализации обратимых шифрующих преобразований.
Входной блок сообщения разбивается на два равных по длине полублока: левый L и правый R.

44
Рис. 2.2. Прямое преобразование по схеме Фейстеля
Прямое преобразование осуществляется в соответствии со сле- дующими соотношениями:
1


i
i
R
L
,
)
,
(
1 1
i
i
i
i
K
R
F
L
R




,
(2.7) где

— операция побитного сложения по модулю 2 (в табл. 2.1 при- ведено ее определение). Тогда исходный блок данных — это
0 0
| R
L
, а
N
N
R
L |
— это выходной блок данных.
Т а б л и ц а 2 . 1
Операция сложения по модулю 2
X
Y
X

Y
0 0
0 0
1 1
1 0
1 1
1 0
Как видно из табл. 2.1, для всех возможных значений операндов выполняется соотношение: (X

Y)

Y = X. Именно это свойство и позволяет при преобразовании использовать в числе прочих необра-
L
i-1
R
i-1
L
i
R
i
F(R
i-1
,K
i
)
+
K
i

45 тимые функции F и, несмотря на это, иметь возможность провести обратное преобразование. Обратное преобразование по схеме Фей- стеля представлено на рис. 2.3 и описывается формулами:
1


i
i
L
R
,
)
,
(
1 1
1






i
N
i
i
i
K
L
F
R
L
(2.8)
Рис. 2.3. Обратное преобразование по схеме Фейстеля

46 ляются только 56 бит — каждый 8-й разряд использовался для кон- троля четности (шифр разрабатывался тогда, когда аппаратура была не слишком надежной и подобные проверки были необходимы).
Обобщенная схема алгоритма представлена на рис. 2.4.
Рис. 2.4. Обобщенная схема шифра DES
Конечная перестановка — IP
-1
— является обратной по отноше- нию к начальной — IP. Задающие их таблицы жестко определены стандартом (таблицы можно узнать из официального описания стан- дарта, также они приводятся, например в [9]).
Раунды шифрования стоятся в соответствии с рассмотренной ранее схемой Фейстеля (рис. 2.2). Шифрование производится в 16 ра- ундов. Схема раундовой функции F представлена на рис. 2.5.
Сначала 32-битный правый полублок преобразуемого текста расширяется до 48 бит с помощью функции расширения E. Эта функ- ция производит дублирование и перестановку некоторых элементов блока. В табл. 2.2 показано, как эта функция работает. После расши- рения в первых позициях полученного 48-битного блока будут стоять
32-й, 1-й и т. д. биты входного блока.
16 раун- дов ключ
Исходный текст
Перестановка IP
Шифрование
Перестановка IP
-1
Криптограмма

47
Рис. 2.5. Схема раундовой функции шифра DES
Т а б л и ц а 2 . 2
Функция E — расширение блока
32 1 2
3 4
5 4
5 6
7 8
9 8
9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1
После расширения полученный 48-разрядный блок складывает- ся побитно по модулю 2 с раундовым ключом K
i
, схема генерации ко- торого будет рассмотрена ниже.
Далее производится подстановка по таблицам S
1
, …, S
8
, в ре- зультате которой каждому 6-разрядному входному значению ставится
R
i-1
(32 бита)
Расширение E
48 бит
+
K
i
(48 бит)
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8 32 бита
Перестановка P
F(R
i-1
,K
i
)