Цель работы: изучить один из алгоритмов асимметричного шифрования.

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

Ход работы

Описание алгоритма

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) - криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

RSA-ключи генерируются следующим образом:

1.Выбираются два различных случайных простых числа p и q заданного размера (например, 1024 бита каждое).

2.Вычисляется их произведение n=pq, которое называется модулем.

3.Вычисляется значение функции Эйлера от числа n: 

4.Выбирается целое число   - открытая экспонента, взаимно простое со значением функции . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.

5.Вычисляется число d - секретная экспонента,  мультипликативно обратное к числу e по модулю , то есть число, удовлетворяющее условию: 

6.Пара {e,n} публикуется в качестве открытого ключа RSA (англ. RSA public key).

7.Пара {d,n} играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Шифрование: .

Дешифрование: 

Листинг:

#include <stdio.h>

#include <conio.h>

int phi,M,n,e,d,C,FLAG;

void check()

{

int i;

for(i=3;e%i==0 && phi%i==0;i+2)

{

FLAG = 1;

return;

}

FLAG = 0;

}

void encrypt()

{

int i;

C = 1;

for(i=0;i< e;i++)

C=C*M%n;

C = C%n;

printf("\n\tEncrypted keyword : %d",C);

}

void decrypt()

{

int i;

M = 1;

for(i=0;i< d;i++)

M=M*C%n;

M = M%n;

printf("\n\tDecrypted keyword : %d",M);

}

void main()

{

int p,q,s;

printf("Enter Two Relatively Prime Numbers\t: ");

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

n = p*q;

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

printf("\n\tF(n)\t= %d",phi);

do

{

printf("\n\nEnter e\t: ");

scanf("%d",&e);

check();

}while(FLAG==1);

d = 1;

do{

s = (d*e)%phi;

d++;

}while(s!=1);

d = d-1;

printf("\n\tPublic Key\t: {%d,%d}",e,n);

printf("\n\tPrivate Key\t: {%d,%d}",d,n);

printf("\n\nEnter The Plain Text\t: ");

scanf("%d",&M);

encrypt();

printf("\n\nEnter the Cipher text\t: ");

scanf("%d",&C);

decrypt();

getch();

}

Вывод: я изучил алгоритм RSA.