Электронная подпись на основе алгоритма rsa

Наиболее простым и распространенным инструментом электронной подписи является уже знакомый алгоритм RSA. Ниже оно будет рассмотрена в качестве примера. Кроме этого существуют еще десятки других схем цифровой подписи.

Предположим, что

d,p,q — секретные, а е, n=pq — открытые.

Замечания.

1. Разложение по n дает: j(n)=(p-1)(q-1); зная j(n) и e, можно найти d.

2. Из e и d можно найти кратность j(n); кратность j(n) позволяет определить делители n.

Пусть DATA — передаваемое сообщение от А к B.

А подписывает DATA для Б при передаче :

EeB,nB { EdA,nA {DATA}}.

При этом он использует:

закрытый ключ EdA,nA А,

открытый ключ EeB,nB B.

B может читать это подписанное сообщение сначала при помощи закрытого ключа EdВ,nВ B с целью получения

EdA,nA {DATA} = EdB,nB {EeB,nB {EdA,nA {DATA}}}

и затем — открытого ключа EeA,nA А для получения

DATA = EeA,nA { EdA,nA {DATA}}.

Таким образом, у B появляется сообщение DATA, посланное ему А.

Очевидно, что данная схема позволяет защититься от нескольких видов нарушений.

А не может отказаться от своего сообщения, если он признает, что секретный ключ известен только ему.

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

Данная схема позволяет при решении многих конфликтных ситуаций обходиться без посредников.

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

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

Для использования алгоритма RSA сообщение следует сжать функцией хеширования (алгоритм MD5 — Message Digest Algorithm) до 256-битового хеша (H). Сигнатура сообщения S вычисляется следующим образом:

S = H mod n

Сигнатура пересылается вместе с сообщением.

Процесс идентификации заключается в получении хеш-функции сообщения (H’) и сравнении с

H = S mod n

где H — хеш сообщения,

S — его сигнатура,

d — секретный ключ,

E — открытый ключ.

Проверке подлинности посвящены стандарты:

— проверка подлинности (аутентификация, authentication) — ISO 8730-90, ISO/IES 9594-90 и ITU X.509;

— целостность — ГОСТ 28147-89, ISO 8731-90;

Цифровая подпись — ISO 7498, P 34.10-94 (Россия), DSS (Digital Signature Standard, США).

Цифровая сигнатура

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

Цифровая сигнатура — это строка символов, зависящая как от идентификатора отправителя, так и содержания сообщения.

Рисунок 4.1 — Цифровая сигнатура

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

Чтобы проверить цифровую сигнатуру, пользователь В должен представить посреднику С информацию, которую он сам использовал для верификации сигнатуры.

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

Рассмотрим типичную схему цифровой сигнатуры.

Пусть Е — функция симметричного шифрования и f — функция отображения некоторого множества сообщений на подмножество мощности р из последовательности {1, …, n}.

Например р=3 и n=9. Если m — сообщение, то в качестве f можно взять функцию f(m) = {2, 5, 7}.

Для каждого сообщения пользователь А выбирает некоторое множество ключей K=[K1, …, Kn} и параметров V={v1, …,vn} для использования в качестве пометок сообщения, которое будет послано В. Множества V и V’={E(v1,K1) …, E(vn,Kn)} посылаются пользователю В и заранее выбранному посреднику С.

Пусть m — сообщение и idm — объединение идентификационных номеров отправителя, получателя и номера сообщения. Если f({idm, m}), то цифровая сигнатура m есть множество K’=[Ki, …, Kj}. Сообщение m, идентификационный номер idm и цифровая сигнатура К’ посылаются В.

Рисунок 4.2 – Использование посредника

Получатель В проверяет сигнатуру следующим образом. Он вычисляет функцию f({idm, m}) и проверяет ее равенство К’. Затем он проверяет, что подмножество {vi, …,vj} правильно зашифровано в виде подмножества {E(vi,Ki) …, E(vj,Kj)} множества V’.

В конфликтной ситуации В посылает С сообщение m, идентификационный номер idm и множество ключей K’, которое В объявляет сигнатурой m. Тогда посредник С так же, как и В, будет способен проверить сигнатуру. Вероятность раскрытия двух сообщений с одним и тем же значением функции f должна быть очень мала. Чтобы гарантировать это, число n должно быть достаточно большим, а число р должно быть больше 1, но меньше n.

Ряд недостатков этой модели очевиден:

должно быть третье лицо — посредник, которому доверяют как получатель, так и отправитель;

получатель, отправитель и посредник должны обменяться существенным объемом информации, прежде чем будет передано реальное сообщение;

передача этой информации должна осуществляться в закрытом виде;

эта информация используется крайне неэффективно, поскольку множества K, V, V’ используются только один раз.

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

Использование цифровой сигнатуры предполагает использование некоторых функций шифрования:

S = H(k, T),

где S — сигнатура, k — ключ, T — исходный текст.

Функция H(k, T) — является хэш-функцией, если она удовлетворяет следующим условиям:

1) исходный текст может быть произвольной длины;

2) само значение H(k, T) имеет фиксированную длину;

3) значение функции H(k, T) легко вычисляется для любого аргумента;

4) восстановить аргумент по значению с вычислительной точки зрения — практически невозможно;

функция H(k, T) – однозначна

При этом разделяют слабую и сильную однозначность. При слабой однозначности для заданного значения T практически невозможно отыскать другой текст Т’, для которого H(k, T) = H(k, T’). При сильной однозначности для любого текста T невозможно найти другой подходящий текст, имеющий то же значение хэш-функции

Из определения следует, что для любой хэш-функции есть тексты-близнецы — имеющие одинаковое значение хэш-функции, так как мощность множества аргументов неограниченно больше мощности множества значений. Такой факт получил название «эффект дня рождения». (Факт теории вероятностей: в группе из 23 человек с вероятностью больше 0.5 два и более человека родились в одно и то же число)

Наиболее известные из хэш-функций — MD2, MD4, MD5 и SHA.

Три алгоритма серии MD разработаны Ривестом в 1989-м, 90-м и 91-м году соответственно. Все они преобразуют текст произвольной длины в 128-битную сигнатуру.

Алгоритм MD2 предполагает:

дополнение текста до длины, кратной 128 битам;

вычисление 16-битной контрольной суммы (старшие разряды отбрасываются);

добавление контрольной суммы к тексту;

повторное вычисление контрольной суммы.

Алгоритм MD4 предусматривает:

дополнение текста до длины, равной 448 бит по модулю 512;

добавляется длина текста в 64-битном представлении;

512-битные блоки подвергаются процедуре Damgard-Merkle, причем каждый блок участвует в трех разных циклах. (В отличие от хэш-функции — этот класс преобразований предполагает вычисление для аргументов фиксированной длины также фиксированных по длине значений)

Задание к лабораторной работе

Студенты, имеющие четный вариант по журналу, реализуют шифрование файлов с помощью алгоритма RSA.

Студенты, имеющие нечетный вариант по журналу, реализуют ЭЦП на базе RSA.

Контрольные вопросы к лабораторной работе:

1. Какие асимметричные алгоритмы шифрования Вы знаете?

2. Какие системы асимметричные или симметричные являются более криптостойкими, почему?

3. В чем отличие арбитражной электронной цифровой подписи от обычной.

4. Назначение сигнатуры? Использование сигнатурного подхода при реализации ЭЦП.

Лабораторная работа №5

Тема: Стеганографические методы защиты информации.

Цель работы: Изучение стеганографических методов защиты информации. Реализация программы с использованием стеганографических принципов защиты информации.

Рандомно подобранные статьи с сайта:

Шифрования RSA, алгоритм RSA Encryption цветные ключи colored key


Похожие статьи:

  • Алгоритм цифровой подписи эль гамаля (egsa)

    Название EGSA происходит от слов El Gamal Signature Algorithm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для обоснования…

  • Алгоритм цифровой подписи dsa

    Алгоритм цифровой подписи DSA (Digital Signature Algorithm) предложен в 1991 г. в США для использования в стандарте цифровой подписи DSS (Digital…

  • Алгоритм цифровой подписи rsa

    Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA, математическая схема которой была разработана в 1977 г. в…

admin