Эффективными системами криптографической защиты являются криптосистемы с открытым ключом – асимметричные. В них для шифрования используется 1 ключ, для расшифрования – второй. 1 ключ является открытым и может быть опубликован для всех пользователей системы. Расшифрование с помощью этого ключа невозможно. Для расшифрования пользователь должен применить второй ключа, который является секретным.
Однонаправленная функция
Вся концепция криптосистем с открытым ключом основана на применении одинаковой функции.
Точного определения этого класса функций с математической точки зрения дать достаточно сложно.
Неформально, ее определяют следующим образом.
Пусть X,Y – произвольный множества.
Функция f(X)→Y является однонаправленной, если для всех x ϵ X легко вычислить функцию f(x) и в то же время для большинства y ϵ Y вычислить x ϵ X, такое, что f(x)→Y, достаточно сложно.
При этом полагают, что существует хотя бы одно значение x.
Основной критерий причисления функций к классу однонаправленных – это отсутствие эффективных алгоритмов обратного преобразования. Простой пример однонаправленной функции – целочисленное умножение.
Вторым важным классом функций, используемых при построении систем с открытым ключом является однонаправленные функции с черным входом.
Функция f(x) → Y относится к классу однонаправленных с черным входом в том случае, если она является однонаправленной и кроме того возможно эффективное вычисление инверсной функции, если известен «черный вход» (или секретная строка, число и другая информация, ассоциируемая с данной функцией)
Первой системой распределения открытых ключей, позволяющая своим пользователям обмениваться секретными ключами по незащищенным каналам связи стала система Диффи-Хелмана, разработанная в 1976 году и построенная на задаче о дискретном логарифмировании.
Пример:
Предположим, что 2 пользователя Алекс и Юстас, применяющие традиционную криптосистему желают связаться друг с другом. Это означает, что они должны прийти к соглашению насчет ключа К, которым будут шифроваться сообщения.
Пусть N – некое большое целое число, G – другое целое число такое, что 1 < G < N-1
Процедура обмена ключами:
1. В начале А и Ю договариваются о значениях N и G; как правило эти значения стандартны для всех пользователей системы.
2. Затем А выбирает некое большое целое число X и вычисляет XX = G^X mod N. Аналогичным образом Ю выбирает число Y и вычисляет YY = G^Y mod N. После этого они обмениваются XX и YY. Будем считать, что Мюллер их перехватил. Числа X и Y А и Ю хранят в секрете.
3. Получив от Ю число YY Алекс вычисляет k(1) = YY^X mod N, а Ю k(2)=XX^Y mod N.
YY^X mod N = G(X*Y) mod N = XX^Y mod N
k(1) = k(2) = k
Злоумышленник перехватил G, N, XX,YY и хочет определить k и его задача сводится к определению некого X’ такого, что G^X’ mod N = XX, поскольку в этом случае YY^X’ mod N = k
Однако X’ задача дискретного логарифмирования, которая является неразрешимой.
Система Диффи-Хелмана позволяет прийти к соглашению k. Однако система не влияет на то, как будет шифроваться информация. В качестве которой может быть использована любая система.
Лекция 9
Если Юстас или даже Мюллер хочет послать информацию Алексу, то он ищет в каталоге ключе алгоритм Е и использует его для шифрования передаваемой информации. А расшифровать сообщение сможет только Алекс, так как только у него есть алгоритм расшифрования D
D(E(M)) = M
Очевидно, что E и D должны удовлетворять условиям для любого сообщения M:
Здесь как для традиционных криптосистем требуется получить эффективны алгоритмы E и D. При этом необходимо, чтобы алгоритм E представлял функцию с черным входом, то есть знание алгоритма E не позволяло реализовать D.
Системы с открытым ключом могут быть реализованы, если подобрана однонаправленная функция с черным входом. Учитывая, что доказательств однонаправленности не существует.
При выборе кандидатов на однонаправленную функцию необходимо соблюдать осторожность, подкрепленную результатами тестирования.
