import hashlib

klucz_publiczny = 0
klucz_prywatny = 0
modul = 0

def generuj_klucze(p, q, e):
    global klucz_publiczny
    global klucz_prywatny
    global modul

    modul = p * q
    phi = (p - 1) * (q - 1)

    klucz_prywatny = pow(e, -1, phi)
    klucz_publiczny = e

def podpisz(wiadomosc):
    global klucz_prywatny
    global modul

    wiadomosc_binarna = wiadomosc.encode('utf-8')
    hasz = hashlib.sha1(wiadomosc_binarna).hexdigest()

    podpis = ''
    for i in range(0, len(hasz)):
        wynik_mod_pow = pow(int(hasz[i], 16), klucz_prywatny, modul)
        wynik_hex = hex(wynik_mod_pow)
        podpis += wynik_hex
    return podpis

def weryfikuj(wiadomosc, podpis):
    global klucz_publiczny
    global modul

    wiadomosc_binarna = wiadomosc.encode('utf-8')
    hasz = hashlib.sha1(wiadomosc_binarna).hexdigest()

    podzielony_podpis = podpis.split('0x')
    odszyfrowany_podpis = ''

    for i in range(1, len(podzielony_podpis)): #!!!! od 1
        wynik_mod_pow = pow(int(podzielony_podpis[i], 16), klucz_publiczny, modul)
        if wynik_mod_pow == 0:
            wynik_hasz = '0'
        else:
            wynik_hasz = hex(wynik_mod_pow).lstrip("0x")
        odszyfrowany_podpis += str(wynik_hasz)

    if odszyfrowany_podpis == hasz:
        print('Podpis zweryfikowany')
    else:
        print('Podpis niewazny')

if __name__ == '__main__':
    p = 23
    q = 17
    e = 13

    generuj_klucze(p, q, e)
    podpis = podpisz("Magda ma kota")
    weryfikuj("Magda ma kota", podpis)