def stringToByteList(s):
    """
    wandelt ein Zeichenkette in eine Byteliste um;
    die Codierung erfolgt mit UTF-8

    >>> stringToByteList('Schlüsselpaar')
    [83, 99, 104, 108, 195, 188, 115, 115, 101, 108, 112, 97, 97, 114]


    """
    return list(bytes(s, 'utf8'))

def byteListToString(byteListe):
    """
    wandelt ein Byteliste in eine Zeichenkette um;
    die Codierung erfolgt mit UTF-8

    >>> byteListToString([83, 99, 104, 108, 195, 188, 115, 115, 101, 108, 112, 97, 97, 114])
    'Schlüsselpaar'


    """
    return str(bytes(byteListe), 'utf8')

def blocklaenge(n):
    """
    bestimmt die maximale Blocklänge bei vorgebenem n

    >>> blocklaenge(3001122295343)
    5
    
    """
    if n < 256:
        return 0
    else:
        if n == 256:
            return 1
        else:
            return blocklaenge(n//256)+1


def byteListToNat(byteListe):
    """
    erzeugt aus einer Liste von Bytes eine natürliche Zahl 

    >>> byteListToNat([83, 99, 104, 108, 195])
    358150073539
    
    """    
    if len(byteListe) == 1:
        return byteListe[0]
    else:
        return byteListe[-1] + 256*byteListToNat(byteListe[:-1])


def byteListToNatList(byteListe, blocklaenge):
    """
    wandelt ein Liste von Bytes in eine Liste mit Zahlen um;
    berücksicht dabei eine vorgegebene Blocklänge

    >>> byteListToNatList([83, 99, 104, 108, 195, 188, 115, 115, 101, 108, 112, 97, 97, 114], 5)
    [358150073539, 809390794092, 1885430130]


    """
    if len(byteListe) <= blocklaenge:
        return [byteListToNat(byteListe)]
    else:
        return [byteListToNat(byteListe[0:blocklaenge])] + byteListToNatList(byteListe[blocklaenge:], blocklaenge)

def natToByteList(zahl):
    """
    wandelt eine natürliche Zahl in eine Liste mit Bytes um;
    
    >>> natToByteList(358150073539)
    [83, 99, 104, 108, 195]

    """
    if zahl < 256:
        return [zahl]
    else:
        return natToByteList(zahl//256) + [zahl%256]
    
def natListToByteList(natListe):
    """
    wandelt eine Liste mit natürlichen Zahl in eine Liste mit Bytes um;
    
    >>> natListToByteList([358150073539, 809390794092, 1885430130])
    [83, 99, 104, 108, 195, 188, 115, 115, 101, 108, 112, 97, 97, 114]

    """
    if natListe == []:
        return []
    else:
        return natToByteList(natListe[0]) + natListToByteList(natListe[1:])
    
def modpot(x, y, m):
    """
    berechnet (schnell) die modulare Potenz

    >>> modpot(52, 37, 77)
    24
    
    """
    if y == 0:
        return 1
    else:
        if y%2 == 1:
            return (x*modpot((x*x)%m, y//2, m))%m
        else:
            return (modpot((x*x)%m, y//2, m))%m


def verschluesselnRSA(zahl, schluessel):
    """
    verschluesselt durch modulare Potenzbildung

    >>> verschluesselnRSA(358150073539, (65537, 3001122295343))
    2465016304633
    >>> verschluesselnRSA(2465016304633, (2384015708753, 3001122295343))
    358150073539
    
    """
    return modpot(zahl, schluessel[0], schluessel[1])

def myMap(liste, f):
    if liste == []:
        return liste
    else:
        return [f(liste[0])] + myMap(liste[1:], f)


def verschluesselnListeRSA(zahlenListe, schluessel):
    """
    verschluesselt eine Zahlenliste durch modulare Potenzbildung

    >>> verschluesselnListeRSA([358150073539, 809390794092, 1885430130], (65537, 3001122295343))
    [2465016304633, 2630297697622, 381401817373]
    >>> verschluesselnListeRSA([2465016304633, 2630297697622, 381401817373], (2384015708753, 3001122295343))
    [358150073539, 809390794092, 1885430130]

    """
    h = lambda zahl: verschluesselnRSA(zahl, schluessel) 
    return myMap(zahlenListe, h)

def codierenZeichenketteZahlenliste(zeichenkette, schluessel):
    """
    erzeugt aus einer Zeichenkette eine Folge natürlicher Zahlen

    >>> codierenZeichenketteZahlenliste('öffentlicher Schlüssel', 5)
    [840578786917, 474399664483, 448378576979, 426953720764, 1936942444]

    """
    n = schluessel[1]
    b = blocklaenge(n)
    byteListe = stringToByteList(zeichenkette)
    #print('Byteliste:', byteListe)
    natListe = byteListToNatList(byteListe, b)
    return natListe

def decodierenZahlenlisteZeichenkette(zahlenListe):
    """
    erzeugt aus einer Zeichenkette eine Folge natürlicher Zahlen

    >>> decodierenZahlenlisteZeichenkette([840578786917, 474399664483, 448378576979, 426953720764, 1936942444])
    'öffentlicher Schlüssel'

    """
    #print('Byteliste:', byteListe)
    byteListe = natListToByteList(zahlenListe)
    #print('Byteliste:', byteListe)
    zeichenkette = byteListToString(byteListe)
    return zeichenkette


def verschluesseln(zeichenkette, schluessel, codierFunktion):
    """
    erzeugt aus einer zu einer Zeichenkette eine Bytefolge 

    >>> verschluesseln('öffentlicher Schlüssel', (65537, 3001122295343), codierenZeichenketteZahlenliste)
    [840578786917, 474399664483, 448378576979, 426953720764, 1936942444]

    """
    #print('Zeichenkette:', zeichenkette)
    natListe = codierFunktion(zeichenkette, schluessel)
    #print('Zahlenliste:', natListe)
    natListeVerschluesselt = verschluesselnListeRSA(natListe, schluessel)
    #print('Zahlenliste:', natListeVerschluesselt)
    return natListeVerschluesselt


def entschluesseln(natListe, schluessel, decodierFunktion):
    """
    erzeugt aus einer Bytefolge eine Byteliste

    >>> entschluesseln([840578786917, 474399664483, 448378576979, 426953720764, 1936942444], (2384015708753, 3001122295343), decodierenZahlenlisteZeichenkette)
    'öffentlicher Schlüssel'

    """
    #print('Zahlenliste:', natListe)
    natListeEntschluesselt = verschluesselnListeRSA(natListe, schluessel)
    #print('Zahlenliste:', natListeEntschluesselt)
    zeichenkette = decodierFunktion(natListeEntschluesselt) 
    #print('Zeichenkette:', zeichenkette)
    return zeichenkette

# Test
n = 116063
e = 4097
d = 51137
oeffentlicherSchluessel = (e, n)
privaterSchluessel = (d, n)

s0 = 'Köln'
print(s0)
s1 = verschluesseln(s0, oeffentlicherSchluessel, codierenZeichenketteZahlenliste)
print(s1)
s2 = entschluesseln(s1, privaterSchluessel, decodierenZahlenlisteZeichenkette)
print(s2)