Конахович Г.Ф., Климчук В.П., Паук С.М., Потапов В.Г. Защита информации в телекоммуникационных системах
Подождите немного. Документ загружается.
220
последнем раунде эти операции повторяются в том же порядке, однако из них
исключено линейное преобразование столбцов.
Наложение материала ключа выполняется операцией XOR. Материал из-
влекается из массива расширенного ключа К последовательно по четыре 32-
битных блока в каждом раунде. При наложении ключа прямоугольная матрица
рассматривается как 4 столбца с 32-битными записями в каждом (см. рис. 5.18).
Табличная подстановка 8x8 бит выполняется с помощью одной таблицы S над
каждым из 16 байтов независимо. После подстановки каждый байт помещается
на свое исходное место в прямоугольной матрице (рис. 5.19).
Подстановка S имеет алгоритмическую запись, однако в большинстве случаев
ее удобнее хранить уже вычисленной в виде массива из 256 байтов.
Циклический сдвиг строк выполняет функцию горизонтального распро-
странения изменений в шифруемом блоке. Нулевая (самая верхняя) строка
матрицы остается без изменений. Первая циклично сдвигается на 1 байт вправо;
байт, который был "вытолкнут" за пределы таблицы (крайний справа байт)
помещается на пустое место в самом начале строки. Вторая строка циклически
сдвигается вправо на два байта, а третья (самая нижняя) — на три байта (рис.
5.20).
221
Линейное перемешивание (рис. 5.21) внутри столбцов выполняется с по-
мощью следующего математического аппарата. Столбец представляют в виде
полинома четвертой степени с коэффициентами из диапазона 0...255, затем
выполняется его умножение на фиксированный полином
С(х)=3х
3
+х
2
+х-2
по модулю полинома (х
4
+1). Образующим полиномом, который не приводится,
разработчики избрали
М(х)=х
8
+х
4
+х
3
+х+1
Так, например, умножение двух чисел 65
16
*4A
16
будет иметь следующий вид:
65
16
*4A
16
= (01100101
2
)*(01001010
2
) =
= (х
6
+ х
5
+ х
2
+1)+ (х
6
+ х
3
+ х)mod(х
8
+ х
4
+ х
3
+ х +1) =
= (х
12
+ х
11
+ х
8
+ х
б
+ х
9
+ х
8
+ х
5
+ х
3
+ х
7
+ х
6
+ х
3
+ х) mod (х
8
+ х
4
+ х
3
+ х +1)
Коэффициенты рассчитываются по модулю 2, поэтому х
8
, х
6
и х
3
сокра-
щаются:
65
16
*4А
16
=(х
12
+х
11
+х
9
+ х
7
+х
5
+х)mod(х
8
+х
4
+х
3
+х + l) =
= (х
7
+х
6
+х
5
+х
2
+х+l)=(11100111
2
) = E7
16
Для проведения такого умножения на архитектурах с достаточным объемом
ресурсов используется табличная подстановка, что значительно быстрее
выполнения всех операций поразрядно на слабых вычислительных мощностях,
222
когда умножение двух байтов выполняется за 7 сдвигов и максимум 14 операций
XOR (для конкретных "маленьких" коэффициентов С(х), выбранных в
RIJNDAEL, требуется максимум 2 сдвига и 4 операции XOR).
Благодаря свойствам используемых криптопримитивов, полную модифи-
кацию одного столбца в раунде RIJNDAEL в ЭВМ, имеющих хотя бы 4 Кбайт
свободной оперативной памяти, можно представить в виде четырех табличных
подстановок
30
...TT
размером 8x32 бита с последующим объединением
результатов операцией XOR [16]:
'
j
A
= T0[a[0,j]]XOR T1[a[1,j-1]]XOR
T2[a[2,j - 2]] XOR T3[a[3,j - 3]] XOR K[j]
В табличной подстановке Т "спрятаны" табличная подстановка S и линейное
перемешивание столбца, выбор коэффициентов элементов а[...],
обеспечивающих циклические сдвиги строк. В результате получается очень
эффективная по скорости реализация. При этом можно отметить, что на со-
временных процессорах все 4 Кбайт таблиц Т при интенсивном использовании
размещаются в кэше процессора первого уровня.
Дешифрование выполняется выполнением в обратном порядке
криптопримитивов, инверсных к шифрующим. Наложение материала ключа
обратно самому себе. Сдвиг строк выполняется циклически в обратную сторону.
Табличная подстановка S заменяется инверсной ей S
-1
. Полином линейного
перемешивания
С(х) = 3х
3
+х
2
+х + 2
выбран таким образом, что для него существует инверсный полином
D(x) = 0B
l6
*x
3
+ 0D
16
*x
2
+ 09
l6
*x + 0E
l6
, C(x) * D(x) = 1.
5.4. Асимметричная криптография и цифровая подпись
Подводя итоги обзора симметричной криптографии, отметим, что если
пользователь желает конфиденциально вести дело с N партнерами, то ему
необходимо иметь N секретных ключей, а общее количество ключей в системе
возрастает в соответствии с количеством абонентов по формуле
N
X
{N-1)/2
Кроме того, возникают вопросы доверенной доставки ключей абонентам в
такой ситуации, когда получатель, дешифровав сообщение, может внести в него
изменения, а затем ссылаться на документ, будто бы уже полученный в таком
виде [16].
Асимметричная криптография решает этот вопрос кардинально иначе —
здесь количество ключей сокращается до 2·N. Однако асимметричную
криптографию применить для конфиденциального хранения информации на
своем личном жестком диске невозможно.
При асимметричной криптографии каждый абонент информационного поля
владеет двумя ключами: открытым (известен всем остальным абонентам) и
223
закрытым (известен только ему и хранится в строгой тайне). Открытый ключ
используется для отправки сообщений и с его помощью на основе специального
алгоритма кто угодно может провести ассиметричное шифрование, которое
необратимо без знания закрытого ключа. А вот дешифровать сообщение сможет
только тот, кто владеет закрытым ключом, то есть, только законный получатель.
Использование асимметричной схемы наоборот (то есть, когда для шиф-
рования задействован закрытый ключ) с небольшими дополнениями породило
еще одну огромную область современной криптографии: электронно-цифровую
подпись (ЭЦП). Тут пользователь вычисляет контрольную сумму сообщения,
шифрует ее тайным ключом и "приклеивает" шифрограмму к сообщению.
Во время создания электронной подписи под документом в нее закладывается
достаточно информации, чтобы любой получатель смог удостовериться с
помощью открытого ключа отправителя, что только он мог подписать и, как
следствие, отправить это сообщение. Однако при этом в подписи должно быть
недостаточно информации, чтобы добыть из нее сам тайный ключ отправителя.
Таким образом, технология ЭЦП очень напоминает асимметричный шифр,
только наоборот.
Отметим, что асимметричное шифрование и ЭЦП решают совсем разные
задачи: первая — обеспечение конфиденциальности послания, вторая — ау-
тентичность отправителя и целостность сообщения. Поэтому вполне возможно и
чисто использование шифрованного сообщении, а затем его подпись с помощью
ЭЦП.
В основе любой схемы асимметричного шифрования или ее инверсной схемы
ЭЦП лежит конкретная тяжелорешаемая математическая задача. При этом для
данной задачи, на самом деле, существует способ найти решение, однако для
этого необходимо владеть некоторой дополнительной информацией ("trapdoor"
— потайные двери).
В качестве открытого ключа в асимметричной криптографии выбирается
какое-нибудь уравнение, которое и есть этой тяжелорешаемой для всех задачей.
Однако это уравнение можно составить так, что лицо, знающее некоторую
дополнительную информацию об этом уравнении, может решить его за
разумный временной промежуток. Это позволяет так выбрать размер всех
параметров задачи, что процедуры шифрования или, скажем, подписи документа
занимают доли секунды, а на их раскрытие без знания тайного ключа требуются
десятилетия.
При асимметричном шифровании получатель сообщения публикует в ка-
честве открытого ключа часть параметров уравнения, которое, зная закрытый
ключ, сможет решить только он. Отправитель дробит сообщение на блоки
требуемой длины, преобразует их в большие натуральные числа и тем самым
завершает формирование уравнения. В качестве шифровки посылаются
некоторые параметры уравнения или его значение относительно некоторого
вектора. Этого недостаточно для злоумышленника, чтобы восстановить ис-
ходное сообщение, однако достаточно для получателя, чтобы решить с помощью
закрытого ключа уравнение и восстановить добавленный отправителем
параметр, который и является исходным текстом.
224
Во время формирования ЭЦП процесс идет несколько в другом направлении.
Отправитель добавляет к письму некоторую часть закрытого ключа в таком виде,
чтобы по ней было невозможно полностью восстановить за крытый ключ, однако
этой информации достаточно, чтобы помочь любому желающему (тому, кто
проверяет ЭЦП) решить то уравнение, на базе которого построена данная схема
ЭЦП.
В качестве остальных параметров уравнения, проверяющий подставляет
контрольную сумму полученного письма и значение из открытого ключа от-
правителя. Если уравнение было успешно решено (то есть, при подстановке всех
данных оно превратилось в равенство), то это означает, что письмо с этой
контрольной суммой отправил именно тот абонент, чья подпись стоит под
письмом. Если же равенство не получилось, то на каком-то из этапов произошел
сбой в канале связи или же злоумышленное увеличение банковского платежа в
десять раз.
Из практических схем асимметричного шифрования наиболее известна схема
RSA, изобретенная тремя исследователями (Ronald Rivest, Adi Shamir, Leonard
Adleman). [16]
Первый этап любого асимметричного алгоритма — создание пары ключей —
для схемы RSA состоит из следующих операций.
1. Выбирают два больших простых (делятся только на единицу и на самих
себя) числа р и q.
2. Выбирают п, которое равно (р·q).
3. Выбирают произвольное число е (е<п), такое, что наибольший общий
делитель (НОД) (е,(р-1)·(q-1))=1, то есть, е должно быть взаимно
простым с числом (р -1)·(q -1).
4. Методом Эвклида решается в целых числах уравнение
е·d + (р-1)·(q -1)·у = 1. Тут неизвестными являются переменные d и y, а метод
Эвклида как раз и находит множество пар (d, у), каждая из которых является
решением уравнения в целых числах.
5. Пару чисел (е, п) публикуют как открытий ключ. Число d хранят в строгой
тайне, потому что это и есть закрытый ключ, позволяющий читать
все послания, зашифрованные с помощью пары чисел (е, п).
Второй этап — это само шифрование с помощью открытого ключа.
1. Отправитель разбивает свое сообщение на блоки, равные K=[log2(n)] бит,
где квадратные скобки означают взятие целой части от дробного числа.
Такой блок может быть интерпретирован как число из диапазона (0;
K
2
-1).
2. Для каждого такого числа (назовем его
i
m ) вычисляется выражение
C
i
=((
i
m )
e
) mod n. Блоки C
i
— это и есть зашифрованное сообщение. Их
можно смело передавать по открытому каналу, потому что операция воз
ведения в степень по модулю простого числа является той самой
тяжелорешаемой математической задачей.
Третий этап — дешифрование сообщения с помощью тайного ключа. Особый
случай теоремы Эйлера утверждает, что если число п представить в виде
произведения двух простых чисел р и q, то для любого X имеет место равенство:
225
(
)
(
)
(
)
1mod
11
=
−−
nx
qp
Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем
две его части в степень (-у):
(x
(-y)(p-1)(q-1)
)mod n = 1
(-y)
=1.
После умножения обеих частей равенства на х получим
(x
(-y)(p-1)(q-1)+1
)mod n = 1х = х.
А теперь напомним как создавались открытый и закрытый ключи. Величина d
была подобрана с помощью алгоритма Эвклида так, что
e·d+(p-1)(q-1) ·y = l
то есть,
e·d =1+ (-y)(p-l)(q-l)
Как следствие, в последнем выражении степени на число (e·d) получаем
(х
{e·d)
) mod п = (х
(-y)(p-1)(q-1)+1
) mod п = 1·х = х.
То есть, для того, чтобы прочитать сообщение
i
C =((m)
e
) mod n, достаточно
возвести его в степень d по модулю п:
(
)
(
)
(
)
(
)
i
de
i
d
i
mnmnc ==
⋅
modmod
Общий вид системы RSA представлен на рис. 5.22.
226
Следует подчеркнуть, что двумя необходимыми свойствами для любой
асимметричной схемы являются:
■ невозможность прочитать сообщение, зная только открытый ключ;
■ невозможность вычислить закрытый ключ по открытому.
Для схемы RSA той самой тяжелорешаемой математической задачей, стоящей
на страже первого требования, является проблема извлечения корня высоких
степеней в конечном поле, то есть, зная, в какую степень возводилось
полученное в результате число х, найти исходное число очень сложно (обычные
методы извлечения корней не работают вследствие операции mod n, которая
применялась над результатом).
Второе требование выполняется, исходя из сложности вычисления другой
математической задачи: разложения на множители (факторизация) больших
чисел. Если бы этот процесс зашел в полиномиальное время, то злоумышленник
мог бы, разложив на делители п, вычислить самостоятельно число (p-l)(q-l) и тем
самым, зная е, вычислить секретный ключ d.
К счастью, и первая, и вторая математические задачи пока что не решаются за
полиномиальное время, однако, если выдающиеся математики решат хотя бы
одну из этих задач, то все криптографические системы, использующие схему
RSA, будут взломаны за несколько дней. В подобной зависимости от математики
находятся все без исключения схемы асимметричного шифрования и цифровой
подписи.
За последнее время были выявлены алгоритмы взлома схемы RSA для
некоторых ее параметров, поэтому сейчас принципы выбора простых чисел р и q
дополнился рядом дополнительных ограничений:
■ числа (р+1) и (q+1) должны содержать в своем разложении на множи-
тели большие простые делители (назовем их p
sup
и q
sup
);
■ числа (р-1) и (q-1) также должны содержать в своем разложении на
множители большие простые делители (назовем их р
sub
и q
sub
), причем
такие, чтобы числа (р
sub
-1) и (q
sub
-1) также содержали в своем разложении
достаточно большие делители;
■ числа р и q должны очень близко совпадать по порядку длины (это ес-
тественное требование в плане атаки полным перебором — потенциально
злоумышленник в этом случае первым найдет обязательно
меньший делитель, и, как следствие, устойчивость всей схемы зависит
от размера именно меньшего делителя), однако нежелательно, чтобы
они оказались рядом друг с другом по значениям;
■ тайный ключ d не должен в результате процедуры создания ключей
оказаться очень маленьким; если такое условие случайно выполни
лось, необходимо "перевыбрать" случайное число е и повторить процедуру
вычисления d;
■ каждый абонент сети должен использовать уникальное значение п.
Недопустимо использование схемы, при которой супервизор ключей
раздает абонентам пары (е, d) в соответствии с одним и тем же п в
надежде, что абонент не сможет разложить п на множители без знания р и
q. Это не так: по известным е, d и n последнее раскладывается на
227
множители за полиномиальное время. То есть, у любого абонента такой
сети появляется возможность читать сообщения всех остальных
пользователей.
В современной криптографии порогом раскрытия схемы RSA считается длина
п в 512 бит. Эта величина находится на "грани доверия". На сегодняшний день
специализированная микросхема стоимостью $10 млн. раскрывает RSА-ключ
длиной 1024 бита за 1 год, а микросхема стоимостью $10 тыс. — ключ длиной
512 бит за 10 минут. [16]
Рассмотрим пример работы схемы RSA на небольших числах. Понятно, что
никаких дополнительных требований на выбор чисел р и q мы не выдвигаем.
Пусть р=5, a q=11, тогда n=55. В качестве открытого ключа е выберем число 7.
Таким образом весь открытый ключ имеет вид (е=7, п=55).
Вычислим закрытый ключ d. Уравнение
e·d + (p-1)(q-1)y=1
имеет вид
7d + 40y = 1
и в целых числах решение
d = 23, y = -4 = 51
Таким образом, закрытый ключ является числом 23.
Пусть какой-нибудь отправитель желает передать абоненту комбинацию
битов
2
1001112
Ее числовой эквивалент —
10
39
. Возведем 39 в степень от-
крытого ключа е=1 по модулю
n = 55:(39
7
mod55) = 19
Число 19 — это шифрограмма, передаваемая по каналу связи. Получатель
после прихода сообщения возводит его в степень
d = 23:(19
23
mod55) = 39
Таким образом, исходное сообщение восстановлено.
Инверсия асимметричного алгоритма RSA для получения схемы цифровой
подписи является самой простой схемой из всех алгоритмов ЭЦП. Для
формирования электронной подписи отправитель выполняет над контрольной
суммой документа h те же действия, что и при шифровании, однако использует
не открытый ключ получателя, а свой личный закрытый ключ, то есть,
sign
i
= (
d
i
h
mod n)
Открытый и закрытый ключи просто меняются местами. На принимающей
стороне получатель возводит подпись в степень открытого ключа е отправителя
и получает (согласно тем же формулам, что и в асимметричном шифровании
RSA):
(
e
i
sign
mod n) = (
de
i
h
mod n) = h
i
Если значение, полученное после возведения в степень, совпадает с вы-
численной независимо на принимающей стороне контрольной суммой доку-
мента, то проверка считается выполненной, а документ — подлинным. Никто,
кроме отправителя, не зная d, не может вычислить такую подпись sign
i
чтобы
возведение ее в степень открытого ключа е дало требуемую контрольную сумму
— это такая же тяжелорешаемая задача, как и в асимметричном шифровании
228
RSA. То есть, снабдить документ такой подписью sign
i
мог только настоящий
владелец закрытого ключа. Схема ЭЦП представлена на рис. 5.23.
Использование тайного ключа для цифровой подписи (то есть, раскрытие
некоторой информации о нем) ему не повредит. Даже перехватив большое
количество подписанных сообщений, злоумышленник не сможет с их помощью
вычислить d за полиномиальное время, а длины ключа, который применяется на
данный момент, хватит на несколько десятков лет стойкости.
И все таки, при использовании ЭЦП необходимо придерживаться некоторых
правил: например, никогда не подписывать того, что не создавал сам, а принять
за правило подписывать только контрольную сумму своего сообщения, даже
если оно настолько мало, что помещается в один блок преобразований RSA. При
этом для таких целей всегда используются только крипто-устойчивые
(необратимые) контрольные суммы — так называемые хэш-функции. Они не
дают злоумышленнику возможности сформировать документ так, чтобы его
контрольная сумма совпала с желаемым значением.
Необходимо помнить, что процедуры асимметричного шифрования очень
медленные. Этот недостаток, впрочем, успешно может быть преодолен
объединением асимметричного шифрования с блочными шифрами. Весь текст
сообщения преобразуется обычным блочным шифром, но с использованием
случайного, только что созданного ключа сеанса, а вот сам ключ сеанса
шифруется как раз асимметричным алгоритмом с помощью открытого ключа
получателя и помещается в начале шифрограммы.
Среди наиболее известных практических схем асимметричного шифрования,
кроме схемы RSA, можно назвать схемы Рабина, Эль Гамаль и Мак-Элиса.
229
Глава 6
Методы закрытия речевых
сигналов
6.1. Общие положения
Наиболее радикальной мерой по предотвращению подслушивания теле-
фонных разговоров является использование криптографических методов за-
щиты. Первые технические системы защиты начали разрабатываться сразу же
после изобретения телефона.
Главной целью при разработке систем передачи речи является сохранение тех
ее характеристик, которые наиболее важны для восприятия слушателем.
Безопасность связи при передаче речевых сообщений базируется на ис-
пользовании большого количества разных методов закрытия сообщений, ко-
торые изменяют характеристики речи таким образом, что она становится не-
разборчивой и неузнаваемой для злоумышленников, подслушивающих или
перехватывающих закрытое речевое сообщение. Выбор методов закрытия
зависит от вида конкретного применения и технических характеристик канала
передачи.
В речевых системах связи известны два основных метода закрытия речевых
сигналов, которые разделяются по способу передачи каналом связи:
■ аналоговое скремблирование;
■ дискретизация речи с последующим шифрованием [12, 14].
Каждый из этих двух методов имеет свои преимущества и недостатки. Так,
например, в первых двух системах, представленных на рис. 6.1 (типа А и В), в
канале связи при передаче присутствуют фрагменты исходного, открытого
речевого сообщения, превращенные в частотной и/или временной областях. Это
означает, что эти системы могут быть атакованы криптоаналитиком противника
на уровне анализа звуковых сигналов. Поэтому раньше считалось, что наряду с
высоким качеством и разборчивостью восстановленной речи аналоговые
скремблеры могут обеспечить лишь низкую или среднюю, по сравнению с
системами цифрового кодирования и шифрования, степень закрытия
(секретности) [14]. Однако новейшие (разработанные в последние годы)
алгоритмы способны обеспечить не только средний, но иногда и очень высокий
уровень секретности в системах типа В (см. рис. 6.1) [14].