// g++ -Wall -Wextra -Wconversion -Wno-unused-label -g3 cryptopp-test.cpp -o cryptopp-test.exe -lcryptopp

#include <iostream>
using std::cout;
using std::cerr;
using std::endl;

#include <string>
using std::string;

#include <algorithm>
using std::replace;

#include <stdexcept>
using std::runtime_error;

#include <cryptopp/filters.h>
using CryptoPP::StringSink;
using CryptoPP::StringSource;

#include <cryptopp/hex.h>
using CryptoPP::HexEncoder;

#include <cryptopp/base64.h>
using CryptoPP::Base64Decoder;

#include <cryptopp/integer.h>
using CryptoPP::Integer;

#include <cryptopp/nbtheory.h>
using CryptoPP::VerifyPrime;

#include <cryptopp/osrng.h>
using CryptoPP::AutoSeededRandomPool;

string nz = "ofgWCuLjybRlzo0tZWJjNiuSfb4p4fAkd_wWJcyQoTbji9k0l8W26mPddx"
            "HmfHQp-Vaw-4qPCJrcS2mJPMEzP1Pt0Bm4d4QlL-yRT-SFd2lZS-pCgNMs"
            "D1W_YpRPEwOWvG6b32690r2jZ47soMZo9wGzjb_7OMg0LOL-bSf63kpaSH"
            "SXndS5z5rexMdbBYUsLA9e-KXBdQOS-UTo7WTBEMa2R2CapHg665xsmtdV"
            "MTBQY4uDZlxvb3qCo5ZwKh9kG4LT6_I5IhlJH7aGhyxXFvUK-DWNmoudF8"
            "NAco9_h9iaGNj8q2ethFkMLs91kzk2PAcDTW9gb54h4FRWyuXpoQ";

string ez = "AQAB";

string dz = "Eq5xpGnNCivDflJsRQBXHx1hdR1k6Ulwe2JZD50LpXyWPEAeP88vLNO97I"
            "jlA7_GQ5sLKMgvfTeXZx9SE-7YwVol2NXOoAJe46sui395IW_GO-pWJ1O0"
            "BkTGoVEn2bKVRUCgu-GjBVaYLU6f3l9kJfFNS3E0QbVdxzubSu3Mkqzjkn"
            "439X0M_V51gfpRLI9JYanrC4D4qAdGcopV_0ZHHzQlBjudU2QvXt4ehNYT"
            "CBr6XCLQUShb1juUO1ZdiYoFaFQT5Tw8bGUl_x_jTj3ccPDVZFD9pIuhLh"
            "BOneufuBiB4cS98l2SR_RQyGWSeWjnczT0QU91p1DhOVRuOopznQ";

void RSA_solve(const Integer& n, const Integer& e, const Integer& d,
        Integer& p, Integer& q,
        Integer& dmodp1, Integer& dmodq1, Integer& invqmodp);

#define UNUSED(x) ((void)x)

int main(int argc, char* argv[])
{
    UNUSED(argc); UNUSED(argv);

    string nn, ee, dd;

    // First, convert Base64URL encoding to Base64
    replace(nz.begin(), nz.end(), '-', '+');
    replace(ez.begin(), ez.end(), '-', '+');
    replace(dz.begin(), dz.end(), '-', '+');
    replace(nz.begin(), nz.end(), '_', '/');
    replace(ez.begin(), ez.end(), '_', '/');
    replace(dz.begin(), dz.end(), '_', '/');

    StringSource ss1(nz, true, new Base64Decoder(new StringSink(nn)));
    StringSource ss2(ez, true, new Base64Decoder(new StringSink(ee)));
    StringSource ss3(dz, true, new Base64Decoder(new StringSink(dd)));

    Integer n((byte*)nn.data(), nn.size());
    Integer e((byte*)ee.data(), ee.size());
    Integer d((byte*)dd.data(), dd.size());

    cout << "N: " << endl << n << endl << endl;
    cout << "E: " << endl << e << endl << endl;
    cout << "D: " << endl << d << endl << endl;

    Integer p, q;
    Integer dmodp1, dmodq1, invqmodp;

    RSA_solve(n, e, d, p, q, dmodp1, dmodq1, invqmodp);

    cout << "P: " << endl << p << endl << endl;
    cout << "Q: " << endl << q << endl << endl;

    cout << "D mod P-1: " << endl << dmodp1 << endl << endl;
    cout << "D mod Q-1: " << endl << dmodq1 << endl << endl;
    cout << "Inv Q mod P: " << endl << invqmodp << endl << endl;

    return 0;
}

/*
    From http://www.di-mgt.com.au/rsa_factorize_n.html

    1. [Initialize] Set k←de−1.
    2. [Try a random g] Choose g at random from {2,…,N−1} and set t←k.
    3. [Next t] If t is divisible by 2, set t←t/2 and x←g^t mod N. Otherwise go to step 2.
    4. [Finished?] If x>1 and y=gcd(x−1,N)>1 then set p←y and q←N/y, output (p,q) and
       terminate the algorithm. Otherwise go to step 3.
*/

void RSA_solve(const Integer& n, const Integer& e, const Integer& d,
        Integer& p, Integer& q,
        Integer& dmodp1, Integer& dmodq1, Integer& invqmodp)
{
    AutoSeededRandomPool prng;
    Integer g = 1;
    unsigned int SAFETY = 0;

STEP_1:
    const Integer k = e * d - 1;
    if(!k.IsEven())
        throw runtime_error("e * d - 1 is not even");

STEP_2:
    // g = 3, 5, 7, 11, ...
    g += 2; while(!VerifyPrime(prng, g)) g += 2;
    Integer t = k;

STEP_3:
    if(SAFETY++ > 128)
        throw runtime_error("could not factor n");

    if(!t.IsEven())
        goto STEP_2;

    t /= 2;
    Integer x = a_exp_b_mod_c(g, t, n);

STEP_4:
    if(!(x > 1))
        goto STEP_3;

    Integer y = GCD(x-1, n);
    if(!(y > 1))
        goto STEP_3;

    p = std::max(y, n/y);
    q = std::min(y, n/y);

    Integer check = p * q;
    if(n != check)
        throw runtime_error("n != p * q");

    dmodp1 = d.Modulo(p - 1);
    dmodq1 = d.Modulo(q - 1);
    invqmodp = q.InverseMod(p);
}