Цифровая подпись
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
й задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.
А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой.
Возведем обе ее части в степень (-y): (x(-y)(p-1)(q-1))mod n = 1(-y) = 1.
Теперь умножим обе ее части на x: (x(-y)(p-1)(q-1)+1)mod n = 1*x = x.
А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m:
((ci)d)mod n = ((mi)e*d)mod n = mi.
На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.
Алгоритм ЭльГамаля
Общие сведения
Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P.
Задается большое простое число P и целое число A, 1<A<P. Сообщения представляются целыми числами M из интервала 1<M<P.
Шифрование сообщений
Протокол передачи сообщения M выглядит следующим образом.
абоненты знают числа A и P;
абоненты генерируют независимо друг от друга случайные числа:
Ka,Kb
удовлетворяющих условию:
1<K<P
получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:
В=AKbmоd(P)
отправитель шифрует сообщение M и отправляет полученную последовательность получателю
C=M*BKamоd(P)
получатель расшифровывает полученное сообщение
D=(AKa)-Kbmоd(P)
M=C*Dmоd(P)
В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.
Подтверждение подлинности отправителя
Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M:
абоненты знают числа A и P;
отправитель генерирует случайное число и хранит его в секрете:
Ka
удовлетворяющее условию:
1<Ka<P
вычисляет и передаёт получателю число B, определяемое последователньостью:
В=AKamоd(P)
Для сообщения M (1<M<P):
выбирает случайное число L (1<L<P), удовлетворяющее условию
(L,P-1)=1
вычисляет число
R=ALmоd(P)
решает относительно S
M=Ka*R+L*Smоd(P)
передаёт подписанное сообщение
[M,R,S]
получатель проверяет правильность подписи
AM=(BR)*(RS)mоd(P)
В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.
Алгоритм Шамира
Общее описание
Еще один интересный пример использования возведения в степень по модулю большого простого числа P для открытого шифрования предложил А.Shamir (один из авторов RSA). Как и в системе ЭльГамаля сообщения M представляются целыми числами из интервала 1<M<P.
Передача сообщений
Передача сообщения происходит следующим образом:
абоненты знают числа P;
абоненты генерируют независимо друг от друга случайные числа:
Ka,Kb
удовлетворяющих условию:
1<K<P
отправитель вычисляет значение и передаёт получателю:
C=MKamоd(P)
получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:
D=CKbmоd(P)
отправитель аннулирует свой шифр и отправляет полученную последовательность получателю
E=D(X-1) mоd(P)E=DFamоd(P)
где:
Fa=Ka-1
получатель расшифровывает полученное сообщение
M=EFbmоd(P)
где:
Fb=Kb1
Пример использования
Эта процедура ОШ может быть использована, например, для таких "экзотических" целей как игра в карты по телефону.
Действительно, если игрок A желает "сдать" игроку B, скажем, 5 карт из 52 как при игре в покер, он зашифровывает обозначения всех карт и передает их игроку B:
Ca=MaKamоd(P)
где
I=1,2,..,52
Игрок B выбирает из них 5, зашифровывает своим ключом 22 и возвращает игроку А:
Da=CaKbmоd(P)
где
I=1,2...,5
Игрок A снимает с этих 5 карт свой шифр и выдает их игроку B.
Игрок B расшифровывает полученные карты:
Ma=EaFbmоd (P)
При этом оставшаяся часть колоды C(6)...C(52) теперь находится у игрока B, но он не может раскрыть эти карты, т.к. они зашиф