Практическое занятие №8 по дисцеплине Основы криптографии и стеганографии

Асимметричный алгоритм шифрования и ЭЦП RSA
.
Кафедра "ИБ"

защиты как шифрование и цифровая подпись (аутентификация – установление подлинности).
Алгоритм

был предложен в 1977 году тремя учеными Рональдом Райвестом. Ади Шамиром и Леонардом Адельманом. Он основывается на том. что нахождение больших простых чисел осуществляется сравнительно легко, но разложение на множители произведения двух таких чисел требует значительных вычислительных затрат.
В настоящее время алгоритм RSA используется во многих стандартах, среди которых: SSL, S-HТTP, S-MIME, S/WAN, STT и PCT.

Алгоритм шифрования RSA

Алгоритм работы RSA
Отправитель выбирает два очень больших простых числа p и q и вычисляет два произведения N=P*Q и M=(P-1)(Q-1).
Затем он выбирает случайное число D, взаимно простое с M, и вычисляет E, удовлетворяющее условию D*E=1 mod M.
После этого он публикует D и N как свой открытый ключ шифрования, сохраняя E (в паре с N) как закрытый ключ.
Чтобы зашифровать данные по известному ключу {D,N}, необходимо сделать следующее:
разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа S(i)=0,1, ... ,N-1;
зашифровать текст, рассматриваемый как последовательность чисел S(i) по формуле S'(i)=(S(i)D) mod N.
Чтобы расшифровать эти данные, используют секретный ключ {E,N}, необходимо выполнить следующие вычисления: S''(i)=S(i)=(S'(i)E) mod N.
В результате будет получено множество чисел S''(i), которые представляют собой исходный текст.

целостности данных, а также других угроз, являются протоколы, которые называются

цифровыми подписями.
Электронно-цифровая подпись (ЭЦП) – это результат криптографического преобразования набора электронных данных, который дает возможность подтвердить его целостность и идентифицировать подписавшегося.

Схема использования ЭЦП RSА.
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа Р и Q, затем находит их произведение N=Р*Q и значение функции (N)=(Р-1)(Q-1).
Отправитель сжимает сообщение M при помощи криптографической хеш-функции h в целое число m=h(M).
Отправитель вычисляет значение цифровой подписи S для сообщения M на основе ранее полученного значения хеш-образа m и значения своего закрытого (секретного) ключа подписи KC. Для этого используется преобразование, аналогичное преобразованию, выполняемому при расшифровывании по алгоритму RSA: S=mЕ(modN).
Пара (M, S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа E.
После приема пары (М, S) получатель вычисляет хэш-значение сообщения М двумя разными способами. Прежде всего он восстанавливает хэш-значение m', применяя криптографическое преобразование подписи S с использованием открытого ключа D: m'=SD(modN).
Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(): m=h(M).
Если соблюдается равенство вычисленных значений, т.е. SD(modN)=h(M), то получатель признает пару (М, S) подлинной.

создания ключей
Примечание 1. Использованная в таблице запись =(mod()) означает, что

при целочисленном делении числа  на число  остаток равен. Например, 7=1(mod(3)).
Примечание 2. Длина реальных размеров ключей (длина битового представления) находится в диапазоне от 512 до 4096 битов.

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

Допустим, что требуется переслать первую букву открытого сообщения, которая предварительно зашифрована методом замены числом 2. Абонент А шифрует число 2 открытым (опубликованным) ключом абонента В. Для шифрования передаваемое число 2 возводится в степень D=31:
m=231=2147483648.
Затем находят остаток от деления числа m на величину N=253, в результате которого получается число 167, то есть:
231=167(mod(253
Числа D и N являются открытым ключом абонента В. В линию передается число 167, которое является шифром исходного числа 2. Получив шифрограмму (167), абонент В использует свой секретный ключ E=71. Для дешифрации он возводит полученное число 167 в степень 71 и находит остаток от деления на число 253. Математически это записывается так:
16771≡2(mod(253)).
В данном случае остаток от деления равен 2, значит, шифрация и дешифрирование произошли правильно. Было передано число 2, и это же число было принято после всех преобразований. Предположим, что абонент В решил ответить абоненту А и направить ему букву, зашифрованную числом 3. Абонент В использует открытый (опубликованный) ключ абонента А (D=5, N=91) и выполняет шифрующее преобразование числа 3. Математически это записывается так:
35≡61(mod(91)).
В линию отправляется число 61. Получив это число, абонент А восстанавливает (дешифрирует) исходный текст с помощью своего секретного ключа t = 29:
6129≡3(mod(91)).
В результате дешифрации на приемной стороне получено число 3, которое отправил абонент В.
В приведенных примерах был рассмотрен порядок передачи одного символа с каждой стороны. Понятно, что таким образом последовательно передается целое сообщение, но преобразование над каждым символом происходит по рассмотренной схеме. Заметим, что для использования этого метода необходимо сообщение предварительно преобразовать в набор чисел, например, с помощью кодовой таблицы.

из числа 41, абоненту А (банкиру). Вначале вкладчик шифрует сообщение

открытым ключом банкира:
415≡6(mod(91)).
В результате шифрования получено число 6.
Дальше вкладчик повторно шифрует это сообщение своим секретным ключом 71:
671≡94(mod(253)).
Шифрограмма 94 отправляется банкиру.
Банкир, получив секретное сообщение, использует вначале открытый ключ вкладчика:
9431≡6(mod(253)).
Затем банкир использует свой секретный ключ:
629≡41(mod(91)).
В результате абонент А (банкир) получает сообщение, состоящее из числа 41.
При использовании электронной подписи никто другой не сможет прислать банкиру сообщение (например, поручение перевести деньги) от имени абонента В, так как на передаче нужно обязательно использовать секретный ключ вкладчика, который известен только абоненту В.

и создать ЭЦП для зашифрованного сообщения. По схеме: А передал

зашифрованное сообщение В, В передал зашифрованное сообщение А с ЭЦП, А проверяет ЭЦП В. Варианты P, Q и M представлены в таблице.

Варианты заданий

2. Рассмотреть следующие алгоритмы хэш-функции: MD2, MD4, MD5, SHA-1 и ГОСТ 34.311-95.