Шифрование

1. Выбираются два различных случайных простых числа {\displaystyle p} и {\displaystyle q} заданного размера (например, 1024 бита каждое).
2. Вычисляется их произведение {\displaystyle n=p\cdot q}, которое называется модулем.
3. Вычисляется значение функции Эйлера от числа {\displaystyle n}:

   {\displaystyle \varphi (n)=(p-1)\cdot (q-1).}

4. Выбирается целое число {\displaystyle e} ({\displaystyle 1<e<\varphi (n)}), взаимно простое со значением функции {\displaystyle \varphi (n)}. Обычно в качестве {\displaystyle e} берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
   • Число {\displaystyle e} называется открытой экспонентой (англ. public exponent)
   • Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в {\displaystyle e}.
   • Слишком малые значения {\displaystyle e}, например 3, потенциально могут ослабить безопасность схемы RSA.^[15]
5. Вычисляется число {\displaystyle d}, мультипликативно обратное к числу {\displaystyle e} по модулю {\displaystyle \varphi (n)}, то есть число, удовлетворяющее сравнению:

   {\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}.}

   Число  называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.

6. Пара {\displaystyle \left\{e,n\right\}} публикуется в качестве открытого ключа RSA (англ. RSA public key).
7. Пара {\displaystyle \left\{d,n\right\}} играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Реализация

Скачать исходники

// rsa.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <conio.h>
#include<fstream>
#include<vector>
#include <string>
#include "locale.h"
using namespace std;

int gcd(int a, int b)
{
	int c;
	while (b)
	{
		c = a % b;
		a = b;
		b = c;
	}
	return abs(a);
}

int code(int e, int j, int n)
{
	int h, y;
	h = 0;
	y=1;
	while (h<e)
	{
		y= y*j;
		y=y%n;
		h++;
	}
	return y;
}


int main()
{
	setlocale(LC_ALL,"Russian");//русская локаль
	int A[1000], // 
		N=20,   // граница простых чисел
		i, j, 
		count=0, // счетчик числа простых чисел
		l=1, 
		index_a,
		index_b, 
		p, // число p
		q, // число q
		m, // (p-1)*(q-1)
		n, // p*q
		d, 
		d_simple = 0,
		e=0;
	ifstream file("C:\\input.txt");
	string message;
	char ch;
	int e_simple = 0;
	string alpha=" абвгдеёжзийклмнопрстуфхцчшщъыьэюя";
	// заполняем массив чисел размерностью N нулями
	for (i=1; i<=2*N; i++) 
		A[i]=0;
	// решето Сундарама, вычеркиваем(т.е. приравниваем 1 элементы, не явл. простыми)
	i=1; 
	j=1;
	while ((2*i*j+i+j)<=N)
	{
		while (j<=(N-i)/(2*i+1))
		{
			A[2*i*j+i+j]=1;
			j++;
		}
		i++;
		j=i;
	}
	// подсчитываем число единиц
	for (i=1; i<=N; i++)
		if (A[i]==0) 
			count++;
	// создаем вектор простых чисел
	vector<int> massiv(count+1);
	// вычисляем простые числа, получая ряд до 2N+1 и сохраняем в созданный вектор
	massiv[0]=2;
	for (i=1; i<=N; i++)
		if (A[i]==0) 
		{	
			A[i]=2*i+1;
			massiv[l]=A[i];
			l++;
		}
	for(i=0; i<=count; i++)
		cout<<massiv[i]<<" "; 
	srand(time(0));
	// выбираем какое-то число от 0 до count, затем работаем с элементом, индекс равен выбранному числу
	index_a = rand() % count+1;
	index_b = rand() % count+1;

	//cout<<endl<<massiv[index_a]<<" "<<massiv[index_b];

	p=massiv[index_a];
	q=massiv[index_b];
	n=p*q;
	m=(p-1)*(q-1);
	// находим число d, взаимно простое с  m
	while (d_simple !=1)
	{
		d = rand() % 100;
		d_simple = gcd (d, m);
	}
	// находим e
	while (e_simple !=1)
	{
		e += 1;
		e_simple = (e*d)%m;
	}
	/*			debug                     */
	cout<<endl<<"p="<<p<<endl;
	cout<<endl<<"q="<<q<<endl;
	cout<<endl<<"n="<<n<<endl;
	cout<<endl<<"m="<<m<<endl;
	cout<<endl<<"d="<<d<<endl;
	cout<<endl<<"e="<<e<<endl;
	/*            end debug                */ 
	while(!file.eof())
	{
		{
			file>>ch;
			message+=ch;
			if (file.peek() == EOF) break;
		}
    }
	file.close();
	cout<<"Исходное сообщение:"<<" ";
	cout<<message<<endl;
	cout<<endl<<"Шифрограмма:"<<" ";
	//создаем вектор хранения зашифрованного текста
	vector<int> decode(message.length());
	for(i=0; i<message.length(); i++)
	{
		for(j=0; j<34; j++)
		{
			if(message[i]==alpha[j])
			{
				cout<<code(e, j, n)<<" ";
				decode[i]=code(e, j, n);
			}
		}
	}
	cout<<endl<<endl<<"Дешифровка"<<endl;
	int index_decode;
	cout<<"Расшифрованный текст"<<" ";
	for(i=0;i<decode.size();i++)
	{
		index_decode=code(d, decode[i], n);
		cout<<alpha[index_decode];
	}
	_getch();
	return 0;
}