#include <iostream>
#include <sstream>

using namespace std;

int modInverse(int a, int m)
{
    a = a%m;
    for (int x=1; x<m; x++)
       if ((a*x) % m == 1)
          return x;
}

int modPow (int a, int b, int k) {
    int result = 1 ;
    while (b--) {
       result *= a ;
       result %= k ;
    }
    return result ;
}

string konwersjaDecHex(long liczba){
    stringstream wynik;
    wynik << hex << liczba;
    return wynik.str();
}

int konwersjaHexDec(string liczba){
    int wynik = 0;
    istringstream(liczba) >> hex >> wynik;
    return wynik;
}

long klucz_publiczny;
long klucz_prywatny;
long modul;

void generujKlucze(long p, long q, long e){
    modul = p * q;
    long phi = (p-1) * (q-1);

    klucz_prywatny = modInverse(e, phi);
    klucz_publiczny = e;
}

string podpisz(string wiadomosc){
    hash<string> funkcjaHashujaca;
    long policzonyHash = funkcjaHashujaca(wiadomosc);
    string hash = konwersjaDecHex(policzonyHash);

    string podpis = "";
    for(int i = 0; i < hash.size(); i++){
        string pojedynczaCyfraHex = hash.substr(i, 1);
        int wynikModPow = modPow(konwersjaHexDec(pojedynczaCyfraHex),
                                klucz_prywatny, modul);

        if(wynikModPow < 16){
            podpis += "0";
        }

        podpis += konwersjaDecHex(wynikModPow);
    }

    return podpis;
}

string weryfikuj(string wiadomosc, string podpis){
    hash<string> funkcjaHashujaca;
    long policzonyHash = funkcjaHashujaca(wiadomosc);
    string hash = konwersjaDecHex(policzonyHash);

    string odszyfrowanyPodpis = "";
    for(int i = 0; i < podpis.size(); i+=2){ //!!!! i+= 2
        string pojedynczaLiczbaHex = podpis.substr(i, 2);//!!! 2
        int wynikModPow = modPow(konwersjaHexDec(pojedynczaLiczbaHex),
                                 klucz_publiczny, modul);
        odszyfrowanyPodpis += konwersjaDecHex(wynikModPow);
    }

    if(odszyfrowanyPodpis == hash){
        cout << "Podpis zweryfikowany";
    }
    else{
        cout << "Podpis niewazny";
    }
}

int main(){

    long p = 13;
    long q = 11;
    long e = 7;

    generujKlucze(p, q, e);

    string podpis = podpisz("Ola ma kota.");
    weryfikuj("Ola ma kota.", podpis);


    return 0;
}