Криптография с открытым ключом

Пример RSA-2: Вычислить a^bmodn, где a =C= 66, b = d = 77 (закрытый ключ) и n= 119.

Иначе

M = 66⁷⁷ mod 119=?

b = 77₁₀ = 1001101₂, k = 6, c = 0, d = 1, a = 66, n = 119.

1.k> 0, k = 6;

c = 2 ´c = 2 ´ 0 = 0;

d = (d ´d) mod n = (1 ´ 1) mod 119 = 1 mod 119 = 1;

b_k= b₆ = 1;

c = c + 1 = 0 + 1 = 1;

d = (d ´a)mod n = (1 ´ 66) mod 119 = 66 mod 119 = 66 - ë66 / 119û´ 119 = 66 – 0 ´119 = 66.

k = k – 1 = 6 – 1 = 5.

2.k> 0, k = 5; b₅ = 0;

c = 2 ´c = 2 ´ 1 = 2;

d = (d ´d) mod n = (66 ´ 66) mod 119 = 4356 mod 119 = 4356 - ë4356 /119û´ 119 = 4356 – (36 ´ 119) = 4356 – 4284 = 72;

k = k – 1 = 4

b_k = b₄ = 0;

c = c´ 1 = 2 ´ 2 = 4;

d = (d ´d)mod n = (72 ´ 72) mod 119 = 5184 mod 119 = 5184 - ë5184 / 119û´ 119 = 5184 – (43 ´119) = 5184 – 5117 = 67.

k = k – 1 = 4 – 1 = 3.

3.k> 0, k = 3; b₃ = 1;

c = 2 ´c = 2 ´ 4 = 8;

d = (d ´d) mod n = (67 ´ 67) mod 119 = 4489 mod 119 = 4489 - ë4489 /119û´ 119 = 4489 – (37 ´ 119) = 4489 – 4403 = 86;

c = c + 1 = 8 + 1 = 9;

d = (d ´a) mod n = (86 ´ 66) mod 119 = 5676 mod 119 = 5676 - ë5676 / 119û´ 119 = 5676 – (47 ´119) = =5676 – 5593 = 83.

k = k – 1 = 3 – 1 = 2; b₂= 1.

4.k> 0, k = 2; b₂ = 1;

c = 2 ´c = 2 ´ 9 = 18;

d = (d ´d) mod n = (83 ´ 83) mod 119 = 6889 mod 119 = 6889 - ë6889 /119û´ 119 = 6889 – (57 ´ 119) = 6889 – 6783 = 106;

c = c + 1 = 18 + 1 = 19;

d = (d ´a)mod n = (106 ´ 66) mod 119 = 6996 mod 119 = 6996 - ë6996 / 119û´ 119 = 6996 – (58 ´119) = 6996 – 6902 = 94.

k = k – 1 = 2 – 1 = 1; b₁ = 0.

5.k> 0, k = 1; b₁ = 0;

c = 2 ´c = 2 ´ 19 = 38;

d = (d ´d)mod n = (94 ´ 94) mod 119 = 8836 mod 119 = 8836 - ë8836 /119û´ 119 = 8836 – (74 ´ 119) = 8836 – 8806 = 30;

b₁= 0;

6.k> 0, k = 0; b₀= 1;c = 2 ´c = 2 ´ 38 = 76;

d = (d ´d) mod n = (30 ´ 30) mod 119 = 900 mod 119 = 900 - ë900 /119û´ 119 = 900 – (7 ´ 119) = = 900 – 833 = 67;

c = c + 1 = 76 + 1 = 77;

d = (d ´a) mod n = (67 ´ 66) mod 119 = 4422 mod 119 = 4422 - ë4422 / 119û´ 119 = 4422 – (37 ´119) = 4422 – 4403 = 19.

k = k– 1 = 0 – 1 = -1.

Так как k< 0, то получен следующий ответ.

Ответ: M= 66⁷⁷mod119 = 19.

 

 

 

 

5. Решение поставленной  задачи методом RSA на языке С.

 

Постановка  задачи.

Пользователю A необходимо зашифровать последовательность чисел с помощью метода RSA, после чего полученную последовательность пользователь B должен расшифровать и получить исходную последовательность.

 

Алгоритм.

В начале выбираем 2 простых числа p и q. Находим их произведение n=pq и высчитываем f=f(n)=(p-1)(q-1). Далее выполняется цикл для выбора подходящего простого числа 1<e<n, характеризующееся условием gsd(e,f)=1, которое является открытым ключом, где функция gsd — функция нахождения наибольшего общего делимого двух чисел. После завершения поиска соответствующего e, мы определяем переменную d, которая является мультипликативным обратным для числа e по mod , и является секретным ключом, посредством вызова соответствующей функции mult. Далее пользователь A вводит последовательность чисел m_i, которая является шифруемой, с помощью функции mod возводим каждый его член в степень e по mod n, и получаем шифрованную последовательность c_i, и посылаем ее пользователю B. Затем полученную шифрованную последовательность чисел c_i пользователь B возводит почленно в степень d по mod n и мы обратно получаем исходную шифруемую последовательность.

 

ЗАКЛЮЧЕНИЕ

 

Из всего изложенного следует, что надежная криптографическая  система должна удовлетворять таким  требованиям:

процедуры зашифровывания и расшифровывания  должны быть "прозрачны" для пользователя;

дешифрование закрытой информации должно быть максимально затруднено;

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

надежность криптозащиты не должна зависеть от содержания в секрете  самого алгоритма шифрования (примерами  этого являются как алгоритм DES).

 

 

СПИСОК  ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

 

1. Аскеров Т.М. Защита информации и информационная безопасность: Учебное пособие / Под общей редакцией К.И. Курбакова. - М.: Рос.экон. акад., 2001. 387 с.

2. Diffie, W., and Hellman, M. «Multiuser CryptographicTechniques». ProceedingsoftheAFIPSNationalComputerConference, June 1976.

3. Столингс Вильям. Криптография и защита сетей / Пер. с анг. – 2-е изд.- М.: Издательский дом «Вильямс», 2001. - 672 с.: ил. -Парал. Тит.анг.

4. Толковый словарь по вычислительной технике / Пер. с англ. - М.: Издательский отдел «Русская Редакция» ТОО «ChannelTradingLtd.», 1995. - 496 с.: ил.

5. http://allbest.ru/

6. Брайан Керниган, Деннис Ритчи   «Язык программирования C»  - М.: Издательство: «Невский диалект», 2001

 

ПРИЛОЖЕНИЯ

Приложение 1

 Коды символов по Windows 1251 и 866 [5]

 

 

Приложение 2

Реализация  метода RSA на языке С.

#include<stdio.h>

void main () {

unsigned p,q,n,f,i,l,k;

unsigned e; //открытый ключ

unsigned d; //Закрытый ключ

unsigned m1[10],m2[10]; //открытое сообщение

unsigned c; //закрытое  сообщение

unsigned gsd (unsigned, unsigned);                          // функция нахождения НОД

unsigned mult (unsigned, unsigned):                            // функция нахождения мультипликативного обратного

unsigned mod (unsigned, unsigned, unsigned);           // функция возведения в степень по mod n

 

printf ("Введите 2 простых числа");

scanf ("%d%d",&p,&q);

n=p*q;

f=(p-1)*(q-1);

do {

printf ("Введите случайное простое  число");

scanf ("%d",&e);

} while (e>f || gsd(e,f)!=1);

d=mult(e,f);

if (d<0) d=d+f;

printf (“Введите длину сообщения”);

scanf (“%d”, &l);

printf ("Введите  сообщение");

for (i=0; i<l; i++) {

scanf ("%d",&ma[i]);

}

for (i=0; i<l; i++) {  //зашифрование

c[i]=mod(ma[i],e,n);

}

for (i=0; i<l; i++) {  //расшифрование

mb[i]=mod(c[i],d,n);

} k=0;

for (i=0; i<l; i++) {

if (m1==m2) k++;

} if (k==l) printf (“Успех”);

}

 

unsigned gsd (unsigned e, unsigned f) {

int x[2];

int y[2];

int t[2];

int q;

unsigned i;

x[0]=1; x[1]=0; x[2]=f;

y[0]=0; y[1]=1; y[2]=e;

if (y[2]==0) return (x[2]);

if (y[2]==1) return (y[2]);

while (y[2]!=0 || y[2]!=1) {

q=x[2]%y[2];

for (i=0; i<=2; i++) {

t[i]=x[i]-q*y[i];

} for (i=0; i<=2; i++) {

x[i]=y[i];

y[i]=t[i];

   }

}

if (y[2]==0) return (x[2]);

if (y[2]==1) return (y[1]);

}

unsigned mult (unsigned e, unsigned f) {

int x[2];

int y[2];

int t[2];

int q;

unsigned i;

x[0]=1;x[1]=0;x[2]=f;

y[0]=0;y[1]=1;y[2]=e;

while (y[2]!=0 || y[2]!=1) {

q=x[2]%y[2];

for (i=0; i<=2; i++) {

t[i]=x[i]-q*y[i];

} for (i=0; i<=2; i++) {

x[i]=y[i];

y[i]=t[i];   }

}

if (y[1]<0) y[1]= y[1]+f;

return (y[1]);

}

unsigned mod (unsigned a, unsigned b, unsigned n) {

unsigned c,d,k;

unsigned t[100];

d=1; k=0; c=0;

while (b!=0) {

t[k]=b%2;

b/=2;

k++;}

while (k>=0) {

c*=2;

d=(d*d)%n;

if (t[k]==1) {

c++;

d=(d*a)%n;

  } k--;

} return (d);   }