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

68 взаимодействии. Если это не так, совместное использование одного и того же секретного ключа может быть нежелательно.
Третья проблема связана с необходимостью проведения аутен- тификации информации и защиты от угроз, связанных с отказом от- правителя (получателя) от факта отправки (получения) сообщений.
Перечисленные проблемы являются весьма существенными, и работа над их решением привела к появлению асимметричной крип- тографии, также называемой криптографией с открытым ключом.
Рассмотрим ряд определений.
Односторонней (однонаправленной) функцией называется такая функция F: X

Y, для которой выполняются следующие условия:
1) для всякого x

X легко вычислить значение функции y = F(x), где y

Y;
2) для произвольного y

Y невозможно (чрезвычайно сложно) найти значение x

X, такое что x = F
-1
(y) (т. е. найти значение функ- ции обратной F).
Односторонней функцией с секретом k, называется такая функ- ция F
k
: X

Y, для которой выполняются следующие условия:
1) для всякого x

X легко вычислить значение функции y = F
k
(x), где y

Y, даже в том случае, если значение k неизвестно;
2) не существует легкого (эффективного) алгоритма вычисления обратной функции F
k
-1
(y) без знания секрета k;
3) при известном k вычисление F
k
-1
(y) для y

Y не представляет существенной сложности.
В частности, односторонняя функция с секретом может быть использована для шифрования информации. Пусть M — исходное со- общение. Получатель выбирает одностороннюю функцию с секретом, и тогда любой, кто знает эту функцию, может зашифровать сообще- ние для данного получателя, вычислив значение криптограммы
C = F
k
(M). Расшифровать данную криптограмму может только закон- ный получатель, которому известен секрет k.

69
Первой публикацией в области криптографии с открытым клю- чом принято считать статью Уитфилда Диффи (Whitfield Diffie) и
Мартина Хеллмана (Martin Hellman) «Новые направления в крипто- графии», вышедшую в свет в 1976 году.
В отличие от симметричных, в асимметричных алгоритмах клю- чи используются парами — открытый ключ (англ. «public key») и сек- ретный или закрытый (англ. «private key»). Схема шифрования будет выглядеть следующим образом.
Получатель B генерирует пару ключей — открытый K
B_pub
и сек- ретный K
B_pr
. Процедура генерация ключа должна быть такой, чтобы выполнялись следующие условия:
1) ключевую пару можно было бы легко сгенерировать;
2) сообщение, зашифрованное на открытом ключе, может быть расшифровано только с использованием секретного ключа;
3) зная только открытый ключ, невозможно рассчитать значение секретного.
Рис. 2.16. Асимметричное шифрование
После генерации ключей, абонент B передает открытый ключ отправителю A, а секретный ключ надежно защищает и хранит у себя
Сообщение
M
ОТПРАВИТЕЛЬ A
ПОЛУЧАТЕЛЬ B
Шифр.
C = E(M,K
B_pub
)
Сообщение
M
Криптограмма
C
Расшифр.
M = D(C,K
B_pr
)
Незащищенный
(небезопасный) канал
Генератор ключей
Секретный ключ K
B_pr
Открытый ключ K
B_pub

70
(рис. 2.16). Пересылка открытого ключа может осуществляться по незащищенному каналу связи. Отправитель A, зная сообщение M и открытый ключ, может рассчитать криптограмму C = E(M, K
B_pub
) и передать ее получателю B. Получатель, зная секретный ключ, может расшифровать криптограмму M = D(C, K
B_pr
).
Нарушитель даже в том случае, если он смог перехватить крип- тограмму и открытый ключ, не может расшифровать криптограмму.
Если использовать определение односторонней функции с сек- ретом, то алгоритм шифрования и открытый ключ задают прямое преобразование F
k
, алгоритм расшифровывания задает обратное пре- образование, а секретный ключ получателя играет роль «секрета» k.
Рассмотрим теперь вопрос аутентификации сообщений.
Электронная цифровая подпись (ЭЦП)
1
— это реквизит элек- тронного документа, предназначенный для защиты данного элек- тронного документа от подделки, полученный в результате крипто- графического преобразования информации с использованием закры- того ключа электронной цифровой подписи и позволяющий иденти- фицировать владельца сертификата ключа подписи, а также устано- вить отсутствие искажения информации в электронном документе, а также обеспечивать неотказуемость подписавшегося.
Функции ЭЦП аналогичны обычной рукописной подписи:
- удостоверить, что подписанный текст исходит от лица, поста- вившего подпись;
- не дать лицу, подписавшему документ, возможности отказать- ся от обязательств, связанных с подписанным текстом;
- гарантировать целостность подписанного текста.
Важное отличие ЭЦП заключается в том, что электронный до- кумент вместе с подписью может быть скопирован неограниченное число раз, при этом копия будет неотличима от оригинала.
Обобщенная схема системы ЭЦП представлена на рис. 2.17.
1
Определение в соответствии федеральным законом Российской Федера- ции «Об электронной цифровой подписи».

71
Рис. 2.17. Электронная цифровая подпись
В ходе преобразований здесь используется пара ключей отпра- вителя сообщения. Тот факт, что при вычислении ЭЦП применяется секретный ключ отправителя, позволяет доказать происхождение и подлинность сообщения. Получатель, имея открытый ключ отправи- теля, проверяет ЭЦП, и если подпись корректна, то он может считать, что сообщение подлинное.
2.4.2. Распределение ключей по схеме Диффи–Хеллмана
Как уже отмечалось выше, основы асимметричной криптогра- фии были заложены американскими исследователями У. Диффи и
М. Хеллманом. Ими был предложен алгоритм, позволяющий двум абонентам, обмениваясь сообщениями по небезопасному каналу свя- зи, распределить между собой секретный ключ шифрования.
Для того, чтобы лучше разобраться с особенностями данного ал- горитма, рассмотрим несколько определений из теории чисел. Два целых числа n и n’ называются сравнимыми по модулю m, если при делении на m они дают одинаковые остатки: n

n’ (mod m), m — мо- дуль сравнения. Таким образом, можно разбить множество целых чи-
Сообщение
M
ОТПРАВИТЕЛЬ A
ПОЛУЧАТЕЛЬ B
Генерация ЭЦП
S = F(M,K
A_pr
)
Сообщение
M
Подписанное сообщение M,S
Проверка ЭЦП
M = F
-1
(S,K
A_pub
)
Незащищенный
(небезопасный) канал
Генератор ключей
Открытый ключ K
A_pub
Секретный ключ K
A_pr

72 сел Z на классы чисел, сравнимых между собой по модулю m и назы-
ваемых классами вычетов по модулю m. Каждый класс вычетов имеет вид:
}
|
{
}
{
Z
k
mk
r
r
m



(2.12)
Множество всех классов вычетов по модулю m обозначается как
Z
m
или Z/mZ. Каждым двум классам {k}
m
и {l}
m
независимо от выбора их представителей можно сопоставить класс, являющийся их суммой и произведением, таким образом, однозначно определяются операции сложения и умножения. Множество
}
{


,
,
Z
m
является коммутатив- ным кольцом с единицей, а если число m — простое, то конечным по- лем.
Мультипликативная группа
}
{

,
Z
m
при m =1, 2, 4, p
k
, 2p
k
(где
k

N, p — нечетное простое число) является циклической [12], т. е. существует образующий элемент a

Z
m
, такой что степени a в опреде- ленном порядке дают все значения от 0 до m–1. Элемент a также называется первообразным корнем по модулю m.
В алгоритме Диффи–Хеллмана в качестве односторонней функ- ции используется возведение в степень по модулю простого числа:
p
a
y
x
mod

(2.13)
Здесь p — большое простое число (сейчас считается безопасным ис- пользовать модуль порядка 2 1024
или более), a — первообразный ко- рень по модулю p. Задача нахождения обратного значения, т. е. вы- числения x по известному y, называется задачей дискретного лога- рифмирования и является вычислительно сложной. Иными словами, при достаточно больших значениях модуля, показателя и основания степени функцию (2.13) можно считать необратимой.
Пусть p — простое число, p > 2, и известно разложение p–1 на простые множители:




k
j
j
j
q
p
1 1

. Число a является первообразным корнем по модулю p тогда и только тогда, когда выполняются следу- ющие условия [12]:

73 1
)
,
(

p
a
НОД
;
)
(mod
1
/
)
1
(
p
a
j
q
p


,
k
j
,...,
1

,
(2.14) где НОД(x,y) — наибольший общий делитель чисел x и y.
Рассмотрим теперь алгоритм Диффи–Хеллмана по шагам. Пусть абоненты сети Алиса и Боб предварительно согласовали значения a и
p из (2.13). При этом требуется, чтобы разложение числа (р–1) содер- жало большой простой множитель, например, (p–1)=2t, где t — про- стое.
1). Алиса выбирает секретный ключ X
A
и вычисляет соответ- ствующий ему открытый ключ
p
a
Y
A
X
A
mod

2). Боб, в свою очередь, определяет X
B
и рассчитывает
p
a
Y
B
X
B
mod

3). Абоненты обмениваются открытыми ключами Y
A
и Y
B
4). Абоненты вычисляют общий секретный ключ. Алиса пользу- ется следующим соотношением:
p
Y
K
A
X
B
AB
mod
)
(

. Боб использует формулу:
p
Y
K
B
X
A
BA
mod
)
(

. Покажем, что K
AB
= K
BA
, воспользо- вавшись свойством ассоциативности операции умножения в конеч- ном поле:
BA
X
X
X
X
X
B
AB
K
p
a
p
a
p
Y
K
B
A
A
B
A




mod
)
(
mod
)
(
mod
)
(
. (2.15)
Таким образом, стороны смогли распределить общий секретный ключ K
AB
. Нарушитель, который может перехватить передаваемые от- крытые ключи Y
A
и Y
B
, должен попытаться по ним вычислить общий секретный ключ без знания секретных ключей абонентов. На данный момент не найдено существенно лучшего пути решения данной зада- чи, чем дискретное логарифмирование, что и обеспечивает крипто- графическую стойкость алгоритма.
2.4.3. Криптографическая система RSA
Алгоритм RSA был предложен в 1977 году и стал первым пол- ноценным алгоритмом асимметричного шифрования и электронной цифровой подписи. Алгоритм назван по первым буквам фамилий ав- торов — Рональд Райвест (Ronald Rivest), Ади Шамир (Adi Shamir) и

74
Леонард Адлеман (Leonard Adleman). Стойкость алгоритма основы- вается на вычислительной сложности задачи факторизации (разложе- ния на множители) больших чисел и задачи дискретного логарифми- рования.
Криптосистема основана на теореме Эйлера, которая гласит, что для любых взаимно простых чисел M и n (M < n) выполняется соот- ношение:
)
(mod
1
)
(
n
M
n


,
(2.16) где
)
(n

— функция Эйлера. Эта функция равна количеству нату- ральных чисел, меньших n , которые взаимно просты с
n
. По опреде- лению,
1
)
1
(


. Также доказано, что для любых двух натуральных взаимно простых чисел a и b выполняется равенство
)
(
)
(
)
(
b
a
b
a






Алгоритм строится следующим образом. Пусть M — блок со- общения, 0 ≤M < n. Он шифруется в соответствии с формулой:
)
(mod n
M
C
e

(2.17)
В этом случае e — открытый ключ получателя. Тогда соответ- ствующий ему секретный ключ d должен быть таким, что
)
(mod
)
(mod
)
(
)
(mod
n
M
n
M
n
C
M
ed
d
e
d



(2.18)
Как уже отмечалось, теорема Эйлера утверждает, что
)
(mod
1
)
(
n
M
n


или, что то же самое,
)
(mod
1
)
(
n
M
M
n
k



, где k —
натуральный множитель. Сопоставив данное выражение c выражени- ем (2.18) получаем, что e и d должны быть связаны соотношением:
1
)
(




n
k
d
e


))
(
(mod
1
n
ed


(2.19)
Теперь предположим, что
q
p
n


, где p и q — простые числа, причем p

q. Нетрудно показать, что для простого числа p

1 функ- ция Эйлера будет равна
1
)
(


p
p

. Тогда, учитывая, что p и q — простые и не равны друг другу (а значит, они и взаимно простые), бу- дет справедливо равенство:
)
1
(
)
1
(
)
(
)
(
)
(







q
p
q
p
q
p



(2.20)

75
Рассмотрим теперь алгоритм RSA «по шагам». Первым этапом является генерация ключей.
1) Выбираются два больших простых числа p и q, p

q.
2) Вычисляется модуль n: n = p

q. Обратите внимание, что для криптосистемы RSA модуль n является частью открытого ключа и должен меняться при смене ключевой пары.
3) Случайным образом выбирается число d, такое, что
)
1
(
)
1
(
1





q
p
d
и НОД(d, (p–1)(q–1))=1.
4) Вычисляется значение e такое, что:
)
1
(
)
1
(
1





q
p
e
))
1
)(
1
mod((
1




q
p
d
e
Доказано, что для случая, когда НОД(d, (p–1)(q–1))=1, такое e существует и единственно.
В результате выполнения данных вычислений имеем открытый ключ, представленный парой чисел (n, e) и секретный ключ d.
Шифрование производится следующим образом.
Отправителю известен открытый ключ получателя — (n,e).
Пусть M — секретное сообщение, которое надо зашифровать M < n.
Криптограмма вычисляется по формуле:
n
M
C
e
mod

(2.21)
Криптограмма C передается получателю. Владелец секретного ключа d может расшифровать сообщение по формуле (2.22).
n
C
M
d
mod

(2.22)
Рассмотрим теперь схему построения электронной цифровой
подписи. Сообщение M подписывается с использованием секретного ключа d (но для генерации подписи используется уже ключевая пара отправителя):
n
M
S
d
mod

(2.23)
Отправитель передает получателю подписанное сообщение, т. е. пару значений (M,S). Проверка ЭЦП по открытому ключу (n,e) произ- водится так:

76
n
S
M
e
mod
'

(2.24)
Совпадение значений M и M' служит доказательством того, что сообщение получено от владельца соответствующего секретного ключа и не было изменено в процессе передачи.
Как видно, сами преобразования относительно просты. Основ- ную сложность при реализации алгоритма RSA представляет этап ге- нерации ключей. В частности, простые числа p и q выбираются таки- ми, что:
- одно из них должно быть меньше другого на несколько поряд- ков;
- (p–1) и (q–1) должны иметь как можно меньший НОД;
- хотя бы одно из чисел (p–1), (q–1) должно иметь в разложении большой простой множитель (например, (p–1) = 2t, где t — простое).
Точное определение, является ли большое число простым или нет, во многих случаях является вычислительно сложной задачей. По- этому, как правило, используются «псевдопростые» тесты, которые позволяют с достаточно большой вероятностью отбросить числа не являющиеся простыми. Один из таких тестов основан на малой тео- реме Ферма, которая гласит, что если p — простое число и 1

x
, то
p
x
p
mod
1 1


. Проверив «кандидата» в простые числа с несколькими
x, выбираемыми в соответствии со специальными требованиями, можно с большой вероятностью выяснить, является ли он простым.
Нахождение наибольшего общего делителя и определение зна- чения e на шаге 4 алгоритма генерации ключей производится в соот- ветствии с алгоритмом Евклида и обобщенным алгоритмом Евклида
[7,9,12].