47 (Вопросы по разным темам с ответами (программирование))

47. Методы шифрования с открытым ключом. Примеры использования в криптографии.

Существуют различные методы шифрования:

1. Потоковые шифры (знак текста шифровки является значением знака открытого текста).

Достоинства: простота, скорость, отсутствие размножения ошибок.

Недостатки: синхронизация для смены ключей.

1. Блочное шифрование (текст делится на независимые блоки, которые шифруются с последующей перестановкой для получения блоков шифра той же длины).

Достоинства: небольшие изменения текста приводят к сильному изменению шифра.

Недостатки: одинаковые способы шифрования для одинаковых блоков позволяют собирать статистику.

1. Шифрование с открытым ключом.

Достоинства: криптостойкость.

Недостатки: медленные.

1. Сверточное шифрование (функция шифрования зависит как от ключа, так и от одного или нескольких символов предшествующего шифра).

Достоинства: защищают от манипуляторов.

Недостатки: большая сложность разработки и реализации.

Шифрование с открытым ключом предполагает возможность публикации алгоритма шифрования без уменьшения секретности в целом. ТО есть при знании заданного алгоритма криптоаналитик будет не в состоянии расшифровать криптотекст.

Идея криптографии с открытым ключом связана с идеей односторонних функций. По заданному аргументу х легко вычислить значение функции f(x) , тогда как определение x из f(x) трудновычислимо (в смысле теории сложности) для криптоаналитика. Однако легальный получатель всегда имеет подходящий способ расшифровки.

Метод RSA (шифр Ривеста — Шамира — Алдемана).

Наиболее широкоиспользуемой криптосистемой с открытым ключом является система RSA. Идея системы в том, что легко перемножить два больших простых числа, однако крайне трудно разложить на множители их произведение. Таким образом произведение может быть открыто и использовано в качестве ключа шифрования.

Пусть p и q – два различных больших случайно выбранных простых числа. Обозначим N = pq и M = (p - 1)(q - 1) (M – функция Эйлера). Выберем большое число D, взаимно простое c M (НОД(D; M) = 1), и вычислим E, такое что D*E = 1 mod M. Числа N и D образуют открытый ключ шифрования. Е - закрытый ключ.

Метод шифрования RSA.

Имеется сообщение S.

S1 = S^D mod N - отправляют абоненту по открытой сети.

S2 = S1^E mod N – расшифровка сообщения.

Расшифровка получается на основании того, что S2 = S^D*E mod N = S^K*M+1 mod N = S (т.к. по теореме Ферма S^M = 1mod N).

Для большей криптостойкости необходимо выбирать большими (p-1)/2 и (q-1)/2 , чтобы число Эйлера было очень большим.

Метод позволяет легко решать задачу выработки ключа для всей сети.

Сами авторы RSA рекомендуют использовать следующие размеры модуля N:

768 бит - для частных лиц;

1024 бит - для коммерческой информации;

2048 бит - для особо секретной информации.

Метод обмена сообщениями по Диффи-Хелману.

Алгоритм шифрования на основе возведения в степень большого простого числа.

Пусть Q – заданное большое число.

Каждый абонент А выбирает число С_А < (Q-1) и взаимно простое с (Q-1), а затем вычисляет взаимно обратное число D_A: C_A* D_A = 1 mod (Q-1).

Аналогично абонент В определяет числа C_B и D_B такие, что C_B* D_B = 1 mod (Q-1).

Пусть абонент А собирается передать сообщение W:

1. (W^CA) mod Q – A передает В

2. ((W^CA)^СВ) mod Q – В передает обратно А

3. (((W^CA)^СВ)^DA) mod Q – А передает В.

4. ((((W^CA)^СВ)^DA)^DB) mod Q = W – расшифрованное сообщение.

То, что числа C_А и С_B взаимно просты с функцией Эйлера, гарантирует, в результате промежуточного возведения в степень никогда не получится 1.

Расшифровка сообщения получается на основании того, что:

W^CA*DA = W ^(Q-1)*L+1 = W ^(Q-1)*L*W = W, т.к. W ^(Q-1) = 1 по т. Ферма.

(W^CA*DA) ^CВ*DВ = W^CВ*DВ = W – аналогично.

Шифр Эль-Гамаля имеет большую степень защиты, чем шифр RSA. В то же время если число абонентов раскрыто, то существует угроза для всех абонентов, в отличие от алгоритма RSA.