12. Алгоритм Эль Гамаля

Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

y = g^x mod p

Общедоступными ключами являются y, g и p, а секретным ключом являетсях. Для подписи сообщения M выбирается случайное число k, которое является простым по отношению к p-1. После этого вычисляется a = g^k mod p. Далее из уравнения M = (xa + kb) mod (p-1) находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число kследует хранить в секрете. Для верификации подписи необходимо проверить равенство:

y^aa^b mod p = g^M mod p.

Пара a и b представляют собой зашифрованный текст. Следует заметить, что зашифрованный текст имеет размер в два раза больше исходного. Для дешифрования производится вычисление:

M = b/a^x mod p

13. Электронная подпись. Основные понятия и принципы формирования.

электронная цифровая подпись - реквизит электронного документа, предназначенный для защиты данного электронного документа от подделки, полученный в результате криптографического преобразования информации с использованием закрытого ключа электронной цифровой подписи и позволяющий идентифицировать владельца сертификата ключа подписи, а также установить отсутствие искажения информации в электронном документе, а также обеспечивает неотказуемость подписавшегося.

Принцип: Это так называемая система криптографического преобразования с симметричным ключом. Она предполагает наличие одного закрытого ключа как у Отправителя, так и у Получателя. Отправитель на закрытом ключе Ks зашифровывает передаваемое сообщение M с помощью определенного криптографического алгоритма и, в зашифрованном виде, отправляет его Получателю. Алгоритм криптографического преобразования определяется соответствующим стандартом. Получатель с помощью точно таких же закрытого ключа Ks и криптографического алгоритма расшифровывает (восстанавливает) принятое шифрованное сообщение M(K). Такая криптосистема обладает хорошей устойчивостью к дешифрованию. Недостаток такой криптосистемы в том, что закрытым ключом владеют минимум два человека, при компрометации ключа у одного из них, компрометируется вся система в целом. Это приводит также к тому, что в такой криптографической системе невозможно определить, кто ответственен за компрометацию закрытого ключа.

В отличие от криптографической системы с симметричным ключом, в системе с асимметричными ключами зашифрование и расшифрование осуществляются на разных, математически связанных (парных) ключах. В такой системе Отправитель изготавливает себе ключевую пару - закрытый Ks и открытый Kp ключи. Закрытый ключ Ks остается у отправителя, открытый Kp передается всем получателям. Сообщение, зашифрованное на закрытом ключе Ks, может быть расшифровано только на открытом ключе Kp:

Таким образом, в этой криптографической системе закрытым ключом Ks владеет только один человек. Соответственно, так зашифровать сообщение M, что оно будет расшифровано с помощью парного открытого ключа Kp, может только владелец закрытого ключа Ks. Алгоритмы асимметричного криптографического преобразования также стандартизированы. Главным достоинством такой системы является владение закрытым ключом Ks только одного человека и его единоличная ответственность за компрометацию этого ключа. Недостаток этой системы - сложность алгоритмов, что снижает скорость криптографического преобразования.

Свойство криптографической системы с асимметричными ключами предоставлять закрытый ключ Ks только одному человеку используется для формирования реквизита электронного документа - электронной цифровой подписи.

Механизм формирования электронной цифровой подписи представлен на рисунке ниже. Владелец закрытого ключа подписи Ks вычисляет по стандартному алгоритму хэш-функцию от подписываемого сообщения. Хэш-функция похожа на контрольную сумму символов сообщения, но обладает чувствительностью даже к перестановке символов сообщения. Далее хэш-функция зашифровывается на закрытом ключе Ks асимметричным криптографическим алгоритмом.

Проверка электронной цифровой подписи производится с использованием парного открытого ключа Kp. Механизм проверки представлен на рисунке ниже:

Назначение ЭЦП.

Электронная цифровая подпись может иметь следующее назначение:

Контроль целостности передаваемого документа: при любом случайном или преднамеренном изменении документа подпись станет недействительной, потому что вычислена она на основании исходного состояния документа и соответствует лишь ему.

Защиту от изменений (подделки) документа: гарантия выявления подделки при контроле целостности делает подделывание нецелесообразным в большинстве случаев.

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

Доказательное подтверждение авторства документа: Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец пары ключей может доказать своё авторство подписи под документом. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д.