2018-01-08
780
Преимущества применения криптографических систем, использующих концепцию инфраструктуры открытых ключей в основном связано с управлением ключами: их выработкой и рассылкой.
Как уже было упомянуто ранее, при использовании симметричного шифрования отправитель и получатель должны обладать одинаковым секретным ключом, передача которого может произойти либо при личной встрече, либо по отдельному закрытому каналу. Есть еще вариант формирования ключа по определенным правилам и оговоренным ранее алгоритмам, но это повышает его детерминированность, сильно снижая криптостойкость системы в целом.
При использовании криптосистемы с открытыми ключами обе стороны не встречаются, они могут даже не знать друг друга, используя любые каналы связи. Это преимущество особенно ощутимо при большом количестве пользователей, в случае необходимости связи двух конкретных пользователей. Тогда пользователи просто могут извлечь необходимую информацию из общего для всех банка данных.
Можно сравнить симметричные и асимметричные криптосистемы с точки зрения длины используемого ключа. В случае использования симметричного шифрования пересылка по закрытому каналу секретного ключа большей разрядности, чем само шифруемое сообщение, мы не получаем никакого выигрыша, т.к. легче переслать по закрытому каналу необходимую информацию без ее преобразования. В случае использования криптосистемы с открытым ключом закрытый ключ и его разрядность не влияет на процесс пересылки, он не пересылается, а просто хранится в секретном месте.
Сертификат открытого ключа
Сертификаты обеспечивают механизм надежной связи между открытым ключом и субъектом, которому принадлежит соответствующий личный ключ. Сертификат — это цифровой документ, который содержит открытый ключ субъекта (subject public key) и подписан электронной цифровой подписью его издателя (issuer). Сертификат также содержит сведения о владельце открытого ключа, например, информацию, которая его дополнительно идентифицирует. Таким образом, выдавая сертификат, издатель удостоверяет подлинность связи между открытым ключом субъекта и информацией, его идентифицирующей.
Алгоритмы с открытыми ключами
RSA
Первый полноценный алгоритм с открытым ключом, который можно использовать для шифрования и цифровых подписей называется RSA.
Названный в честь трех изобретателей - Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Эдлмана (Leonard Adleman) - этот алгоритм многие годы противостоит интенсивному криптоанализу. Хотя криптоанализ ни доказал, ни опроверг безопасность RSA, он, по сути, обосновывает уровень доверия к алгоритму.
Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших (100 - 200 разрядов или даже больше) простых чисел.
1. Для генерации двух ключей используются два больших случайных простых числа, p и q. Для максимальной безопасности необходимо выбирать p и q равной длины.
2. Рассчитывается произведение: n = p q.
3. Вычисляется функция Эйлера u(n) = (p-1)*(q-1). Особенность функции Эйлера в том, что первообразный корень в степени u(n) по mod n =1.
4. Затем случайным образом выбирается ключ шифрования e, такой что e и u(n) являются взаимно простыми числами, т.е. НОД(u(n), e) = 1.
5. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифрирования d, такого что
ed mod u(n) =1
Заметим, что d и n также взаимно простые числа.
Числа e и n - это открытый ключ, а число d - закрытый. Два простых числа p и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты.
Для шифрования сообщения m оно сначала разбивается на цифровые блоки, меньшие n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть, если p и q - 100-разрядные простые числа, то n будет содержать около 200 разрядов, и каждый блок сообщения mi должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение c будет состоять из блоков ci той же самой длины.
Формула шифрования выглядит так:
ci = mie mod n
Для расшифровки сообщения возьмите каждый зашифрованный блок ci и вычислите
mi = cid mod n
Так как
cid = (mie)d = mied = mik(p-1)(q-1)+1 = mimik(p-1)(q-1) = mi*1 = mi; все (mod n)
формула восстанавливает сообщение.
Открытый ключ:
n произведение двух простых чисел p и q (p и q должны храниться в секрете)
e число, взаимно простое с (p-1)(q-1)
Закрытый ключ:
d e-1 mod ((p-1)(q-1))
Шифрование:
c = me mod n
Дешифрирование:
m = cd mod n
Точно также сообщение может быть зашифровано с помощью d, а зашифровано с помощью e, возможен любой выбор.
ElGamal
Схему EIGamal можно использовать как для цифровых подписей, так и для шифрования, его безопасность основана на трудности вычисления дискретных логарифмов в конечном поле. Для генерации пары ключей сначала выбирается простое число p и два случайных числа, g и x, оба эти числа должны быть меньше p. Затем вычисляется
y = gx mod p
Открытым ключом являются y, g и p. И g, и p можно сделать общими для группы пользователей. Закрытым ключом является x.
1. Подписи ElGamal
Чтобы подписать сообщение M, сначала выбирается случайное число k, взаимно простое с p-1. Затем вычисляется
a = gk mod p
и с помощью расширенного алгоритма Эвклида находится b в следующем уравнении:
M = (xa + kb) mod (p - 1)
Подписью является пара чисел: aи b. Случайное значение k должно храниться в секрете. Для проверки подписи нужно убедиться, что
yaab mod p = gM mod p
Каждая подпись или шифрование EIGamal требует нового значения k, и это значение должно быть выбрано случайным образом. Если когда-нибудь Ева раскроет k, используемое Алисой, она сможет раскрыть закрытый ключ Алисы x. Если Ева когда-нибудь сможет получить два сообщения, подписанные или зашифрованные с помощью одного и того же k, то она сможет раскрыть x, даже не зная значение k. Описание ElGamal сведено в Таблице 3.2.
Открытый ключ:
| p | простое число (может быть общим для группы пользователей) |
| g | <p (может быть общим для группы пользователей) |
| y | = gx mod p |
Закрытый ключ:
| x | <p |
Подпись:
| k | выбирается случайным образом, взаимно простое с p-1 |
| a | (подпись) = gk mod p |
| b | (подпись), такое что M= (xa + kb ) mod (p - 1) |
Проверка:
| Подпись считается правильной, если yaabmod p= g M mod p |
2. Шифрование ElGamal
Модификация EIGamal позволяет шифровать сообщения. Для шифрования сообщения Mсначала выбирается случайное число k, взаимно простое с p - 1. Затем вычисляются
a = gk mod p
b = yk M mod p
Пара (a,b) является шифротекстом. Обратите внимание, что шифротекст в два раза длиннее открытого текста. Для дешифрирования (a,b) вычисляется
M = b/ax mod p
Так как ax º gkx (mod p) и b/ax º yk M/ax º gxk M/ gkx = M (mod p), то все работает (см. Таблица 3.3.).
Открытый ключ:
| p | простое число (может быть общим для группы пользователей) |
| g | <p (может быть общим для группы пользователей) |
| y | = gx mod p |
Закрытый ключ:
| x | <p |
Шифрование:
| k | выбирается случайным образом, взаимно простое с p-1 |
| a | (шифротекст) = gk mod p |
| b | (шифротекст)= yk Mmod p |
Дешифрирование:
| M (открытый текст) = b/axmod p |
DIFFIE-HELLMAN
Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году. Этот алгоритм позволяет по открытым каналам связи двум сторонам получить единый закрытый ключ на основе двух закрытых частны ть
Одна из сторон выбирают большие простые числа n и g так, чтобы g первообразным корнем по mod n. Возведение первообразного корня в разные степени даст равномерное распределение чисел от 1 до n.
Стороны взаимодействия придумывают свои секретный ключи x и y.
Затем выполняется следующий протокол:
(1) Первая сторона передает второй значения n и g, а также, рассчитанное значение
X = gx mod n
(2) Вторая сторона передает первой
Y = gy mod n
(3) Первая сторона рассчитывает общий ключ
k = Yx mod n
(4) Вторая сторона расчитыает общий ключ
k' = Xy mod n
И k, и k' равны gxy mod n. Никто из подслушивающих этот канал не сможет вычислить это значение, им известно только n, g, X и Y. Пока они не смогут вычислить дискретный логарифм и раскрыть x или y, они не смогут решить проблему. Поэтому, k - это секретный ключ, который Алиса и Боб вычисляют независимо.
Выбор g и n может заметно влиять на безопасность системы. Число (n-1)/2 также должно быть простым. И, самое главное, n должно быть большим: безопасность системы основана на сложности разложения на множители чисел того же размера, что и n. Можно выбирать любое g, которое является примитивом mod n; нет причин, по которым нельзя было бы выбрать наименьшее возможное g - обычно одноразрядное число. (К тому же, на самом деле, g не должно даже быть примитивом, оно только должно генерировать достаточно большую подгруппу мультипликативной группы mod n.)
