rsa.cpp

#include "EasyBigNum.h"
#include <iomanip>

const unsigned rsa_bits = 1024;

struct rsa_info{
    EasyBigNum p1, p2, n, totient, e, d;
};

EasyBigNum generate_rsa_prime(std::mt19937 &source, unsigned rsa_bits) {
    return EasyBigNum::generate_prime(source, rsa_bits);
}

EasyBigNum extended_gdc(EasySignedBigNum a, const EasyBigNum &b){
    EasySignedBigNum x0 = 1;
    EasySignedBigNum x1 = 0;
    EasySignedBigNum copy_b = b;
    while (!!copy_b){
        auto temp = a.div(copy_b);
        auto q = std::move(temp.first);
        a = copy_b;
        copy_b = std::move(temp.second);

        auto temp2 = x0;
        x0 = x1;
        x1 = temp2 - q * x1;
    }

    if (x0.negative())
        x0 += b;
    return x0.make_positive() % b;
}

rsa_info generate_rsa_info(std::mt19937 &source){
#if 1
    auto p = generate_rsa_prime(source, rsa_bits);
    auto q = generate_rsa_prime(source, rsa_bits);
#else
    EasyBigNum p = "15415806671052272421044292837580230728175831622037849369292157001116789018895272130874175291057585981035955564323923977058053922968522418025324496153379133436504787546194798128487667267014085982442432999778913468743831425755858815436563520291210105069017706107683616121356726092440895850528670532680918423227";
    EasyBigNum q = "139950691270603904311639042930526441126288291227855459889456283243988670454489321657214044258264071568241911430007833319320658025714533163538133969616047209837889801332002510031449488473143955238740923488157887325631668915493574487526987791408163622304995328010236531782807327611283728401478126133563162272631";
#endif
    auto n = p * q;
    auto totient = n - (p + q - 1);
    auto totient_minus_1 = totient - 1;
    EasyBigNum e = 65537;
    while (e.gcd(totient) != 1)
        e = EasyBigNum(source, totient_minus_1, 2);
    auto d = extended_gdc(e, totient);

    EasyBigNum x = 42;
    auto y = x.mod_pow(e, n);
    auto z = y.mod_pow(d, n);
    return rsa_info{ p, q, n, totient, e, d };
}

void pad(std::string &s, size_t target_length){
    auto n = s.size();
    while (s.size() < target_length)
        s.push_back(s[s.size() % n]);
}

EasyBigNum encrypt(const std::string &src, rsa_info &rsa){
    auto s = src;
    std::cout << s << std::endl;
    pad(s, rsa.n.all_bits() / 8 - 1);
    std::reverse(s.begin(), s.end());
    std::cout << s << std::endl;
    EasyBigNum base(s.c_str(), s.size());
    EasyBigNum one = 1;
    while (base.gcd(rsa.n) != one)
        base += 1;
    return base.mod_pow(rsa.e, rsa.n);
}

std::string decrypt(const EasyBigNum &cyphertext, rsa_info &rsa){
    auto plaintext = cyphertext.mod_pow(rsa.d, rsa.n);
    auto buf = plaintext.to_buffer();
    std::string ret(buf.begin(), buf.end());
    std::cout << ret << std::endl;
    std::reverse(ret.begin(), ret.end());
    return ret;
}

std::vector<char> encrypt(std::string src, const EasyBigNum &modulo, const EasyBigNum &addend, const EasyBigNum &multiplicand){
    const unsigned bits = 512;
    const unsigned bytes = bits / 8;
    src.resize((src.size() + (bytes - 1)) / bytes * bytes);
    std::vector<char> ret;
    auto current_state = multiplicand;
    for (size_t i = 0; i < src.size(); i += bytes){
        EasyBigNum operand(src.c_str() + i, bytes);
        operand *= current_state;
        operand += addend;
        operand %= modulo;
    }
    return ret;
}

int main(){
    std::random_device dev;
    std::mt19937 rng(dev());
    std::uniform_int_distribution<std::uint32_t> dist;
#if 1
    auto rsa = generate_rsa_info(rng);
    std::cout
        << "p1:      " << rsa.p1      << '\t' << rsa.p1.active_bits()      << '\t' << rsa.p1.all_bits()      << std::endl
        << "p2:      " << rsa.p2      << '\t' << rsa.p2.active_bits()      << '\t' << rsa.p2.all_bits()      << std::endl
        << "n:       " << rsa.n       << '\t' << rsa.n.active_bits()       << '\t' << rsa.n.all_bits()       << std::endl
        << "totient: " << rsa.totient << '\t' << rsa.totient.active_bits() << '\t' << rsa.totient.all_bits() << std::endl
        << "e:       " << rsa.e       << '\t' << rsa.e.active_bits()       << '\t' << rsa.e.all_bits()       << std::endl
        << "d:       " << rsa.d       << '\t' << rsa.d.active_bits()       << '\t' << rsa.d.all_bits()       << std::endl;
#else
    rsa_info rsa{
        EasyBigNum("90106117772857749592716901269590077687"),
        EasyBigNum("185774445858885219173921679633305303509"),
        EasyBigNum("16739414097748097206788086238557551313226826498008644700515208054580423703683"),
        EasyBigNum("16739414097748097206788086238557551312950945934376901731748569473677528322488"),
        EasyBigNum("65537"),
        EasyBigNum("10532980737033065788997468610184114333025178272454257497502899247074384133585"),
    };
#endif
    std::string line;
    std::cout << ">";
    std::getline(std::cin, line);
    auto cyphertext = encrypt(line, rsa);
    std::cout << cyphertext << std::endl;
    std::cout << decrypt(cyphertext, rsa) << std::endl;
}