Лабораторная
работа № 7. Шифрование
методом RSA.
Алгоритм RSA предложили в 1987 году три автора: Р.Райвест (Rivest),
А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм получил свое название по первым трем
буквам фамилий его авторов. Алгоритм RSA
стал первым полноценным алгоритмом с открытым ключом. В криптосистеме RSA открытый ключ Кв, секретный ключ кв, сообщение
М и криптограмма С принадлежат множеству целых чисел
Zn={0,1,2,3,….,N-1}
Где N-модуль:
N=P*Q.
Здесь P и Q –
случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P
и Q равной длины и
хранят в секрете. Открытый ключ Кв выбирают случайным образом так,
чтобы выполнялись условия:
1 <
Kв < f (N), НОД (Кв, f (N))=1
f (N)=(P-1)* (Q-1)
где f
(N) – функция Эйлера.
Она указывает количество положительных целых
чисел в интервале от 1 до N,
которые взаимно просты с N.
Второе условие означает, что открытый ключ Кв
и функция Эйлера должны быть взаимно простыми.
Далее, используя расширенный алгоритм Евклида,
вычисляют секретный ключ
кв такой,
что кв*Кв≡1(mod f(N))
или кв=Кв-1(mod
(P-1)(Q-1)).
Открытый ключ используется для шифрования
данных, а секретный ключ – для расшифрования.
Пример.
Предположим, что пользователь А хочет передать
пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в
роли отправителя сообщения, а пользователь В – в роли получателя. В этой системе пользователь
В формирует значение ключа (открытого и секретного). Открытый он отправляет отправителю а секретный оставляет у себя. Пользователь А с
помощью открытого ключа шифрует сообщение и посылает пользователю В. Тот в свою
очередь при помощи секретного ключа расшифровывает сообщение.
1 шаг.
Пользователь В вычисляет выбирает два
произвольных простых числа P и Q.
1 шаг.
Пользователь В вычисляет значение модуля N=P*Q.
3 шаг.
Пользователь В вычисляет функцию Эйлера f (N)=(P-1)* (Q-1) и выбирает случайным образом значение
открытого ключа Кв с учетом выполнения условий:
1 < Kв < f (N), НОД (Кв, f (N))=1.
4 шаг.
Пользователь В вычисляет значение секретного
ключа кв используя расширенный алгоритм Евклида при
решении сравнения
кв=Кв-1(mod (P-1)(Q-1)).
5 шаг.
Пользователь В пересылает пользователю А пару
чисел (N,Кв).
Если пользователь А хочет передать
пользователю В сообщение М, он выполняет следующие шаги.
6 шаг.
Пользователь А разбивает исходный открытый
текст М на блоки, каждый из которых может быть представлен в виде числа
Mi=0,1,2,..,N-1
7 шаг.
Пользователь А шифрует текст, представленный в
виде последовательности чисел Mi по формуле: Ci=MiКв (mod N) и отправляет криптограмму С1,С2,С3,…Сi,.. пользователю В.
8 шаг.
Пользователь В расшифровывает сообщение
используя секретный ключ кв , по
формуле Mi=CiКв
(mod N)
А теперь создадим программу в Дельфи которая будет шифровать и дешифровать сообщения при
помощи метода RSA.
Запустите Дельфи и
разместите на форме следующие компоненты (см рис 13):
Рис 13. Окончательная форма.
Для начала опишем глобальные переменные,
которые нам понадобятся в нашей программе:
enkript:array [1..1024] of integer; // допустимое кол
–во символов
ascii:array [1..26] of char; // 26 букв латинского
алфавита
a,b,k,gcd:shortint; //вспомогательные переменные
f,n:shortint; // значения открытого ключа
u1,u2,u3,v1,v2,v3,t1,t2,t3,s,q,k1,i,t:shortint; // переменные для вычисления алгоритма Евклида
g : array [1..100] of shortint;
Напишем обработчик кнопки Функция Эйлера:
a:=strtoint(edit1.text);// первое простое число
b:=strtoint(edit2.text);// второе простое число
n:=a*b; // вычисление модуля
k:=(a-1)*(b-1); функция Эйлера
memo1.Text:=inttostr(k);
// полю Memo1 присваивается значение Функции Эйлера.
После того как вы вычислили функцию Эйлера
нужно в поле Edit3 ввести значение
открытого ключа взаимно простое со значением функции Эйлера. После этого нажат
кнопку Ключ. Напишем обработчик этой кнопки. Эта кнопка формирует значения
открытого и секретного ключей при помощи расширенного алгоритма Евклида:
f:=strtoint(edit3.text);// вводится значение открытого ключа
if (f>1) and (f<=k) then
//если значение открытого ключа >1 и <= функции
//Эйлера, то идет алг.Евклида
begin
g[1]:=k;
g[2]:=f;
i:=2;
while g[i]<>0 do begin
g[i+1]:=g[i-1] mod g[i];
i:=i+1;
end;
end;
gcd:=g[i-1];
if gcd=1
then begin
u1:=0;
u2:=1;
u3:=k;
v1:=1;
v2:=0;
v3:=f;
while u3<>1
do begin
q:=u3
div v3;
t1:=u1-(v1*q);
t2:=u2-(v2*q);
t3:=u3-(v3*q);
u1:=v1;
u2:=v2;
u3:=v3;
v1:=t1;
v2:=t2;
v3:=t3;
end;
end;
if u3=1 then begin
k1:=u1+k
mod k;
label5.Caption:=floattostr(k1);// значение секретного ключа
label4.Caption:=inttostr(n) + '
è ' + inttostr(f);
// значения открытого ключа
end;
А сейчас мы напишем функции шифрования и
дешифрования. Для начала нам нужно описать эти функции. Для этого перейдите туда где вы описали глобальные переменные и вот здесь перед
словом var напишите следующее:
function cripting(m,k,g:integer):integer;
// ф-я шифрования
function decripting(c,k,g:integer):char;
// ф-я дешифрования
Напишем теперь непосредственно сами функции,
прямо в коде программы, в любом месте:
function cripting(m,k,g:integer):integer;
var i,tmp:integer;
begin
tmp:=1;
for i:=1 to k do begin
tmp:=tmp*m;
// возведение в степень
end;
result:=tmp mod g; // полученное число
делим на g и берем его остаток
end;
function decripting (c,k,g:integer):char;
var i,tmp:integer;
begin
tmp:=1;
for i:=1 to k do begin
tmp:=tmp*c;
end;
result:=ascii[tmp mod g]; // полученное число
преобразуется в букву которая
//находится под этим номером
end;
А теперь напишем обработчик кнопки Шифровать:
t:=length(memo2.Text); // считаем кол-во символов в тексте
i:=1;
for x:='A' to 'Z' do
begin
ascii[i]:=x;// нумеруем буквы т.е. А=1, B=2 и т.д.
inc(i);
end;
for i:=1 to t do
begin
tmp:=copy(memo2.Text,i,1); // копируем из текста начиная с //позиции i 1
букву
for j:=1
to 26 do begin
if ascii[j]=tmp then begin // если буквы равны то
m:=j; //запоминаем номер этой буквы в массиве ascii
enkript[i]:=cripting(m,f,n); // 1 символу массива
// присваивается значение функции
end;
end;
end;
memo2.Text:='';
for i:=1 to t do memo3.Text:=memo3.Text+' '+inttostr(enkript[i]); // выводим //зашифрованное сообщение
переменные опишите так
var
i,j,m:integer;
tmp:string;
x:char;
Обработчик кнопки Дешифровать
stroka:='';
for i:=1 to t do begin
tmp:=enkript[i];
stroka:=stroka+decripting(tmp,k1,n);
end;
memo3.Text:=stroka;
переменные опишите в этой функции следующим
образом
var
i,tmp:integer;
stroka:string;
Программа работает следующим образом:
После вычисления ключей вы вводите текст.
Затем по нажатии кнопки Шифровать происходит следующее: берется первая буква,
затем она сравнивается с массовом латинских букв и если таковая имеется, то
берется ее номер. Потом массиву чисел присваивается значение функции. У нас
функция с параметрами. В функцию мы передаем (номер буквы m, открытый ключ f, открытый ключ n ). Рассмотрим подробно функцию шифрования.
function cripting(m,k,g:integer):integer;
переменным m,k,g присваивается
соответственно (номер буквы m, открытый ключ f, открытый ключ n )
var i,tmp:integer; это у нас локальные переменные они использ-ся
только ф-ей
begin
tmp:=1;
for i:=1 to k do begin
tmp:=tmp*m;
здесь у нас вычисляется степень MiКв
сначала переменной tmp присваивается значение 1.
Затем открывается цикл от 1 до К. К у нас = f. Мы же
возводим число в степень f.
Рассмотрим
строку tmp:=tmp*m; m-это
номер буквы. Вот этот номер буквы мы должны возвести в степень f.
end;
result:=tmp mod g; переменной result присваивается остаток от деления полученного
числа на вторую часть открытого ключа.
end;
Функция Дешифрования работает аналогично.
Отличие лишь в том, что результатом является не число, а буква под искомым
номером.
Запустите программу и проверьте ее. Вводите
только большие латинские буквы и без пробелов.
Самостоятельное задание
Создайте функцию проверки простого числа.
Возможность вводить все буквы и символы.
Создать две программы: одну для шифрования, а
вторую для дешифрования.