#include "stdafx. h"
#include <stdio. h>
#include <stdlib. h>
#include <time. h>
#include <conio. h>
#include <iostream>
using namespace std;
struct rsa_public_key {
int e, m;
};
struct rsa_private_key {
int d, m;
};
// Нахождение общего делителя
int gcd(int a, int b)
{
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// Решение Диофантова уравнения a*x + b*y = 1
void SolveDiophant(int a, int b, int &x, int &y)
{
int a11=1, a12=0, a21=0, a22=1;
while (1) {
int r = a % b;
if (r == 0) {
x = a12;
y = a22;
return;
}
else {
int q = a/b;
int save12 = a12;
int save22 = a22;
a12 = a11-save12*q;
a22 = a21-save22*q;
a11 = save12;
a21 = save22;
a = b;
b = r;
}
}
}
// Поиск числа y, такого что (x*y)%m == 1
int FindInvert(int x, int m)
{
int y, sux;
SolveDiophant(x, m, y, sux);
while (y < 0)
y += m;
return y;
}
// вычисление (a в степени b)%m
int Power(int a, int b, int m)
{
a %= m;
int res = a;
for (int i = 1; i < b; i++)
res = (res * a) % m;
return res;
}
// Генерируем пару ключей.
// GCD(e, p-1) = GCD(e, q-1) = 1
void GenKeyPair(int p, int q, int e, rsa_public_key &pub,
rsa_private_key &pri)
{
if ((gcd(e, p-1) != 1) || (gcd(e, q-1) != 1)) {
printf("GenerateKeyPair: Invalid parameters\n");
exit(1);
}
pub. m = p*q;
pub. e = e;
pri. m = p*q;
// Функция Эйлера phi(m)
int phi_m = (p-1)*(q-1);
pri. d = FindInvert(e, phi_m);
}
// Сообщение должно быть < key. m
int Encode(int source, rsa_public_key &key)
{
return Power(source, key. e, key. m);
}
int Decode(int source, rsa_private_key &key)
{
return Power(source, key. d, key. m);
}
int main ()
{
setlocale (LC_CTYPE, "Russian_Russia.1251");
int p;
int q;
int e=59;
int vvod;
cout<<"Введите чило P:"<<endl;
cin>>p;
cout<<"Введите чило Q, близкое к P:"<<endl;
cin>>q;
cout<<"Введите сообщение, которое будет закодировано:"<<endl;
cin>>vvod;
rsa_public_key pub_key;
rsa_private_key pri_key;
GenKeyPair(p, q, e, pub_key, pri_key);
srand(time(NULL));
int source = vvod % pub_key. m;
int enc = Encode(source, pub_key);
int dec = Decode(enc, pri_key);
if (dec!= source)
printf("Ошибка! Недостаточно памяти для сообщения\n");
else
printf("Исходное сообщение: %d, Закодированное: %d, Декодированное: %d\n",
source, enc, dec);
printf("Публичный ключ: %d, Секретный ключ: %d",
pub_key. m, pri_key);
getch();
}
