#include <iostream>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <ctime>
#include "InfInt.h"


/////35742549198872617291353508656626642567
/////359334085968622831041960188598043661065388726959079837

/////19417091861583877910490308387583607491604123508745646291616809803288063839914277427844396698129011691681486302256267788924072838297914608887914403084151733

//////24848401783389118830883536511746092086211663600625721820978008915738591540866418413678832001037346516549789719402507891354266759914154881730210759626584581



//////////генерация
InfInt generate() {
    InfInt t = 1;
    for (int i = 0; i < 512; i++) {
        t *= 2;
        t += rand() % 2;
    }
    return(t);
}
///////////

///////быстрое возведение в степень по модулю
InfInt modPow(InfInt base, InfInt exponent, InfInt mod) {
    InfInt x = 1;
    InfInt y = base;
    while (exponent > 0) {
        if (exponent % 2 == 1)
            x = (x * y) % mod;
        y = (y * y) % mod;
        exponent = exponent / 2;
    }
    return x % mod;
}
////////


////////Миллер-Рабин
bool MillerRabinTest(const InfInt n1, int k) {
    InfInt n = n1;
    // если n == 2 или n == 3 - эти числа простые, возвращаем true
    if (n == 2 || n == 3)
        return true;

    // если n < 2 или n четное - возвращаем false
    if (n < 2 || n % 2 == 0)
        return false;

    // представим n − 1 в виде (2^s)·t, где t нечётно, это можно сделать последовательным делением n - 1 на 2
    InfInt t = n - 1;

    int s = 0;

    while (t % 2 == 0) {
        t /= 2;
        s += 1;
    }

    // повторить k раз
    for (int i = 0; i < k; i++)
    {
        // выберем случайное целое число a в отрезке [2, n − 2]

        InfInt a;

        do {
            a = generate() - 100;
        }
        while (a < 2 || a >= n - 2);

        // x ← a^t mod n, вычислим с помощью возведения в степень по модулю
        InfInt x = modPow(a, t, n);

        // если x == 1 или x == n − 1, то перейти на следующую итерацию цикла
        if (x == 1 || x == n - 1)
            continue;

        // повторить s − 1 раз
        for (int r = 1; r < s; r++) {
            // x ← x^2 mod n
            x = modPow(x, 2, n);

            // если x == 1, то вернуть "составное"
            if (x == 1)
                return false;

            // если x == n − 1, то перейти на следующую итерацию внешнего цикла
            if (x == n - 1)
                break;
        }

        if (x != n - 1)
            return false;
    }

    // вернуть "вероятно простое"
    return true;
}
//////////

//////////НОД
InfInt GCD(InfInt num1, InfInt num2) {
    while ((num1 != 0) && (num2 != 0)) {
        if (num1 > num2) {
            num1 = num1 % num2;
        }
        else {
            num2 = num2 % num1;
        }
    }
    return (num1 + num2);
}
///////////

//////////
InfInt calculateE(InfInt fi) {
    // Выбирается целое число e ( 1 < e < fi ) // взаимно простое со значением функции Эйлера (fi)

    for (InfInt e = 2; e < fi; e++) {
        if (GCD(e, fi) == 1) {
            return e;
        }
    }
    return -1;
//    InfInt e;
//    do {
//        e = generate();
//    } while (e != fi && GCD(e, fi) == 1);
//    return e;
    //&& !MillerRabinTest(e, 20)
}
//////////

//////////
InfInt calculateD(InfInt e, InfInt fi) {
    // Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее сравнению:
    //    d ⋅ e ≡ 1 (mod φ(n))

    InfInt d;
    InfInt k = 1;

    while (true) {
        k += fi;

        if (k % e == 0) {
            d = (k / e);
            return d;
        }
    }
}
///////////

///////////
InfInt encrypt(InfInt i, InfInt e, InfInt n) {
    InfInt current, result;

    current = i;
    result = 1;

    result = modPow(current, e, n);

    return result;
}
//////////

//////////
InfInt decrypt(InfInt i, InfInt d, InfInt n) {
    InfInt current, result;

    current = i;
    result = 1;

    result = modPow(current, d, n);

    return result;
}
///////////

///////////
int main() {
    srand(unsigned(time(nullptr)));

    //Cоздание открытого и секретного ключей

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

    ///////////
    InfInt p;

    do {
        p = generate();
    } while (!MillerRabinTest(p, 20));

    //p = "1303253110366565616703329909559";

    std::cout << "p = " << p << "\n";

    InfInt q;

    do {
        q = generate();
    } while (!MillerRabinTest(q, 20));

    //q = "359334085968622831041960188598043661065388726959079837";

    std::cout << "q = " << q << "\n";
    //////////

    // 2. Вычисляется их произведение n = p ⋅ q, которое называется модулем.
    InfInt n = p * q;
    std::cout << "n = " << n << "\n";

    // 3. Вычисляется значение функции Эйлера от числа n: φ(n) = (p−1)⋅(q−1)
    InfInt fi = (p - 1)*(q - 1);
    std::cout << "fi = " << fi << "\n";

    // 4. Выбирается целое число e ( 1 < e < φ(n) ), взаимно простое со значением функции Эйлера (t)
    //	  Число e называется открытой экспонентой
    InfInt e = calculateE(fi);
    std::cout << "e = " << e << "\n";

    // 5. Вычисляется число d, мультипликативно обратное к числу e по модулю φ(n), то есть число, удовлетворяющее сравнению:
    //    d ⋅ e ≡ 1 (mod φ(n))
    InfInt d = calculateD(e, fi);
    std::cout << "d = " << d << "\n";

    // 6. Пара {e, n} публикуется в качестве открытого ключа RSA
    // 7. Пара {d, n} играет роль закрытого ключа RSA и держится в секрете


    std::cout << "ENTER THE MESSAGE\n";

    std::string msg;
    getline(std::cin, msg);
    std::vector <InfInt> encrypted(msg.length());

    //шифрование c=m^e(mod n)
    for (long long int i = 0; i < msg.length(); i++) {
        encrypted[i] = encrypt(msg[i], e, n);
    }

    std::cout << "\nTHE ENCRYPTED MESSAGE IS: ";

    for (long long i = 0; i < msg.length(); i++) {
        std::cout << (char)encrypted[i].toInt();
    }

    std::vector <InfInt> decrypted(msg.length());
    //дешифрование c^d = (m^e)^d = m(mod n)
    for (long long i = 0; i < msg.length(); i++) {
        decrypted[i] = decrypt(encrypted[i], d, n);
    }

    std::cout << "\nTHE DECRYPTED MESSAGE IS: ";
    for (long long int i = 0; i < msg.length(); i++) {
        std::cout << (char)decrypted[i].toInt();
    }
}