inf-schule | Deklarative Programmierung » Station

Station - Prototyping

Prototypen

Bei der Entwicklung neuer Produkte wird zunächst oft ein Prototyp erstellt. Dabei handelt es sich um ein funktionsfähiges Modell, das dem geplanten Produkt in vielen Bereichen entspricht, meist aber auch eine Reihe von Vereinfachungen aufweist.

Prototyp

Prototypen werden - insbesondere bei komplexen technischen Systemen - zunächst einmal erstellt, um Erfahrungen mit dem neuen System und seiner Entwicklung zu sammeln.

Prototypen kommen entsprechend auch bei der Entwicklung komplexer Software zum Einsatz. Wir skizzieren im Folgenden, wie ein Prototyp zu einem RSA-Kryptosystem mit Hilfe der funktionalen Programmierung erstellt werden kann.

Weitere Informationen zum RSA-Verfahren findest du im Abschnitt Das RSA-Verfahren.

Funktionen zum RSA-Verfahren

Beim RSA-Verfahren werden natürliche Zahlen mit Hilfe eines (öffentlichen bzw. privaten) Schlüssels in neue Zahlen umwandelt.

Black-Box

Dabei wird folgende Berechnungsvorschrift benutzt.

FUNKTION verschluesselnRSA:
verschluesselnRSA(zahl, schluessel) -> (zahl ** schluessel[0]) % schluessel[1]

Anstatt Potenzbildung und Modulo-Operation nacheinander auszuführen, ist es günstiger, eine geeignete Hilfsfunktion zur effektiven Berechnung der modularen Potenz zu benutzen:

Black-Box

Diese Hilfsfunktion lässt sich folgendermaßen festlegen:

FUNKTION modpot:
{Fall 1:}
y == 0: modpot(x, y, m) -> 1
{Fall 2:}
y != 0:
    {Fall 2.1:}
    y%2 == 1: modpot(x, y, n) -> (x*modpot((x*x)%m, y//2, m))%m
    {Fall 2.2:}
    y%2 != 1: modpot(x, y, n) -> (modpot((x*x)%m, y//2, m))%m

Die Korrektheit dieser Regeln uberprüft man am besten anhand konkreter Zahlenwerte:

FUNKTION modpot:
{Fall 1:}
modpot(2, 0, 5) -> 1
{Fall 2:}
    {Fall 2.1:}
    modpot(2, 7, 5) -> (2*modpot(4%5, 3, 5))%5
    {Fall 2.2:}
    modpot(2, 6, 5) -> (modpot(4%5, 3, 5))%5

Mit der Hilfsfunktion lässt sich die RSA-Verschlüsselung aus so festlegen:

FUNKTION verschluesselnRSA:
verschluesselnRSA(zahl, schluessel) -> modpot(zahl, schluessel[0], schluessel[1])

Wenn mehrere Zahlen zur Verschlüsselung vorliegen, benutzen wir die folgende Funktion:

Black-Box

Diese Funktion kann mit dem Map-Operator (siehe ...) oder direkt mit Regeln festgelegt werden:

FUNKTION verschluesselnListeRSA:
{Fall 1:}
zahlenListe == []: verschluesselnListeRSA(zahlenListe, schluessel) -> []
{Fall 2:}
zahlenListe != []: verschluesselnListeRSA(zahlenListe, schluessel) -> 
                       [verschluesselnRSA(zahlenListe[0], schluessel)] +
                       verschluesselnListeRSA(zahlenListe[1:], schluessel)

Funktionen zur Codierung und Decodierung

Das RSA-Verfahren wandelt natürliche Zahlen in natürliche Zahlen um. Wenn man eine Nachricht mit dem RSA-Verfahren verschlüsseln möchte, muss man diese zunächst in geeigneter Weise mit natürlichen zahlen codieren. Wir gehen dabei wie folgt vor.

'Köln'

[75, 195, 182, 108, 110]
 K      ö       l    n

[19395,                    46700,                     110]
 75*(256**1)+195*(256**0)  182*(256**1)+108*(256**0)  110*(256**0)

In einem ersten Schritt werden die Zeichen der Zeichenfolge in Bytes umgewandelt. Wir benutzen dabei die Standardcodierung "UTF-8" (siehe ...). Beachte, dass bei dieser Codierung Umlaute und Sonderzeichen ggf. mit mehreren Bytes dargestellt werden.

In einem zweiten Schritt werden aus Bytes Zahlen erzeugt. Die Bytezahlen werden hierbei als Ziffern im 256-er-System angesehen. Hierbei muss allerdings beachtet werden, dass die erzeugten Zahlen kleiner als die Zahl n eines Schlüsselpaares (e, n) oder (d, n) sind. Es dürfen daher nur eine begrenzte Anzahl von Bytes zusammengefasst werden. Die Anzahl der Bytes, die in Abhängigkeit des verwendeten Schlüssels zusammengefasst werden, nennen wir Blocklänge.

Beim Decodieren gehen wir den umgekehrten Weg:

[19395,                    46700,                     110]
 75*(256**1)+195*(256**0)  182*(256**1)+108*(256**0)  110*(256**0)

[75, 195, 182, 108, 110]
 K      ö       l    n

'Köln'

Zur Durchführung dieser Umwandlungen werden eine Funktion zur Codierung

Black-Box

sowie eine Funktion zur Decodierung konzipiert.

Black-Box

Für die einzelnen Umwandlungsschritte werden ebenfalls Funktionen eingeführt.

Die Funktion stringToByteList wandelt gemäß UTF-8 eine Zeichenkette in eine Liste aus Bytes um.

Black-Box

FUNKTION stringToByteList:
zeichenkette -> list(bytes(s, 'utf8'))

Die Funktion byteListToNat wandelt eine Liste aus Bytes in eine natürliche Zahl um.

Black-Box

FUNKTION byteListToNat:
{Fall 1:}
len(byteListe) == 1: byteListToNat(byteListe) -> byteListe[0]
{Fall 2:}
len(byteListe) != 1: byteListToNat(byteListe) -> byteListe[-1] + 256*byteListToNat(byteListe[:-1])

Mit byteListe[-1] wird hier das letzte Element von byteListe beschrieben, mit byteListe[:-1] die Restliste von byteListe, wenn man das letzte Element weglässt.

Die Funktion byteListToNatList wandelt eine Liste aus Bytes gemäß der Blocklänge in eine Liste aus natürlichen Zahlen um.

Black-Box

FUNKTION byteListToNatList:
{Fall 1:}
len(byteListe) <= blocklaenge: byteListToNatList(byteListe, blocklaenge) -> 
                                   [byteListToNat(byteListe)]
{Fall 2:}
len(byteListe) > blocklaenge:  byteListToNatList(byteListe, blocklaenge) ->
                                   [byteListToNat(byteListe[0:blocklaenge])] + 
                                   byteListToNatList(byteListe[blocklaenge:], blocklaenge)

Mit diesen Umwandlungsfunktionen kann jetzt die Funktion zur Codierung definiert werden.

Black-Box

FUNKTION codierenZeichenketteZahlenliste:
codierenZeichenketteZahlenliste(zeichenkette, blocklaenge) ->
    byteListToNatList(stringToByteList(zeichenkette), blocklaenge))

Für die Umwandlungsschritte beim Decodieren werden ebenfalls weitere Funktionen eingeführt.

Die Funktion natListToByteList wandelt eine Liste aus natürlichen Zahlen in eine Liste aus Bytes um.

Black-Box

FUNKTION natListToByteList:
{Fall 1:}
natListe == []: natListToByteList(natListe) -> []
{Fall 2:}
natListe != []: natListToByteList(natListe) ->
                    natToByteList(natListe[0]) + natListToByteList(natListe[1:])

Die Funktion byteListToString wandelt eine Liste aus Bytes in eine Zeichenkette um.

Black-Box

FUNKTION byteListToString:
byteListe -> str(bytes(byteListe), 'utf8')

Mit diesen Hilfsfunktionen kann jetzt die Funktion zur Decodierung definiert werden.

Black-Box

FUNKTION decodierenZahlenlisteZeichenkette:
decodierenZahlenlisteZeichenkette(zahlenListe) ->
    byteListToString(natListToByteList(zahlenListe))

Zur Bestimmung der Blocklänge wird eine weitere Funktion benötigt.

Black-Box

FUNKTION blocklaenge:
{Fall 1:}
n < 256:  blocklaenge(n) -> 0
{Fall 2:}
n == 256: blocklaenge(n) -> 1
{Fall 2:}
n > 256:  blocklaenge(n) -> blocklaenge(n//256)+1

Funktionen zur Kombination aus RSA-Verfahren und (De-)Codierung

Jetzt können wir die bereits entwickelten Funktionen zum RSA-Verfahren und zur (De-)Codierung kombinieren.

Die Funktion verschluesseln codiert eine Zeichenkette durch eine Zahlenliste und verarbeitet diese mit dem RSA-Verfahren. Die Funktion wird so konzipiert, dass sie eine beliebige Codierungsfunktion benutzen kann.

Black-Box

Dabei wird folgende Berechnungsvorschrift benutzt.

FUNKTION verschluesseln:
verschluesseln(zeichenkette, schluessel, codierFunktion) -> 
    verschluesselnListeRSA(codierFunktion(zeichenkette, schluessel), schluessel)

Entsprechend wird die Funktion entschluesseln konzipiert. Sie verarbeitet eine Zahlenliste mit dem RSA-Verfahren und decodiert sie anschließend, indem sie aus der Zahlenliste eine Zeichenkette erzeugt. Die Funktion wird ebenfalls so konzipiert, dass sie eine beliebige Decodierungsfunktion benutzen kann.

Black-Box

Dabei wird folgende Berechnungsvorschrift benutzt.

FUNKTION entschluesseln:
entschluesseln(zeichenkette, schluessel, decodierFunktion) -> 
    decodierFunktion(verschluesselnListeRSA(natListe, schluessel))

Implementierung der Funktionen

Die Datei kryptosystem_rsa.txt enthält eine Python-Implementierung der entwickelten Funktionen.

Mit diesen Funktionen können jetzt Experimente mit dem RSA-Verfahren im Sinne eines Prototypen gemacht werden:

from kryptosystem_rsa import *
# Testprogramm
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)

Einzelne Funktionen können jetzt variiert werden, oder weitere Funktionen können ergänzt werden.