ip2

#include <iostream>
#include <cmath>
#include <random>

using namespace std;

// Вычисление НОД (алгоритм Евклида)
int gcdCalc(int x, int y) {
    return (y == 0) ? x : gcdCalc(y, x % y);
}

// Быстрое возведение в степень по модулю (алгоритм "быстрого" возведения)
long long modPow(long long base, long long exp, long long m) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % m;
        }
        base = (base * base) % m;
        exp /= 2;
    }
    return result;
}

// Проверка числа на простоту (проверка делителями до корня)
bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

// Генерация ключей RSA (случайный выбор двух простых, вычисление n, e, d)
void makeRsaKeys(int& n, int& e, int& d) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dist(50, 100);

    int p, q;
    do {
        p = dist(gen);
    } while (!isPrime(p));

    do {
        q = dist(gen);
    } while (!isPrime(q) || q == p);

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

    do {
        e = dist(gen) % phi + 2;
    } while (gcdCalc(e, phi) != 1);

    int k = 1;
    while ((1 + k * phi) % e != 0) {
        ++k;
    }
    d = (1 + k * phi) / e;
}

// Шифрование числа: message^e mod n
long long encryptValue(int message, int e, int n) {
    return modPow(message, e, n);
}

// Расшифровка числа: cipher^d mod n
long long decryptValue(long long cipher, int d, int n) {
    return modPow(cipher, d, n);
}

int main() {
    int n, e, d;
    makeRsaKeys(n, e, d);

    cout << "Public key:  (" << e << ", " << n << ")" << endl;
    cout << "Private key: (" << d << ", " << n << ")" << endl;

    // Зашиваем исходное сообщение в код
    int originalMsg = 123; 
    cout << "Original message:       " << originalMsg << endl;

    // Шифрование
    long long encMsg = encryptValue(originalMsg, e, n);
    cout << "Encrypted message:      " << encMsg << endl;

    // Расшифровка
    long long decMsg = decryptValue(encMsg, d, n);
    cout << "Decrypted message:      " << decMsg << endl;

    return 0;
}