So, dann wunderschönen guten Morgen und willkommen zur letzten
Veranstaltung bei GWE in diesem Jahr, zur letzten Übung Grundbegriffe
der Informatik, diesmal hauptsächlich zum vierten Übungsblatt.
Und Sie hatten schon gesehen, beim vierten Übungsblatt ging es viel um
die MIMA und was man mit der MIMA machen kann.
Unter anderem waren so ein paar Aufgaben dafür da, dass man
programmieren sollte in der MIMA.
Und wenn man jetzt etwas in der MIMA programmieren muss, dann muss man
halt wirklich das Problem, das man jetzt da angehen möchte, in
Babyschritte zerlegen, weil man halt nur sehr elementare Operationen
überhaupt zur Verfügung hat.
Und das ist somit eine dieser Herausforderungen, dass man jetzt halt
sich anschaut, was können diese Operatoren, was können sie nicht.
Manchmal können sie mehr, als man denkt.
Manchmal können sie weniger, als man denkt.
Und dass man dann diese etwas komplizierteren Probleme wirklich
möglichst klein zerteilt.
Also bei der ersten Aufgabe ging es darum, als erstes sich zu
überlegen, was ist die größtmögliche Zahl, die ich mit dem MIMA-Befehl
loadconstant laden kann.
Und damit man das richtig beantworten kann, muss man sich halt noch
mal klar machen, wie funktioniert das, was für Zahlen werden da
geladen und wie sind die kodiert.
Und wir hatten gelernt, in der MIMA ist die Kodierung, die wir
verwenden, eine Zweier-Kompliment-Kodierung.
Und eine Zweier-Kompliment-Kodierung sagt Ihnen nur dann etwas.
Wissen Sie nur dann, was das bedeutet, Zweier-Kompliment, wenn Sie
auch wissen, wie lang die Kodierung in Bits ist.
Bit hier als ein Zeichen aus dem Alphabet 01.
Und die Speicherzellen in der MIMA, die haben halt Länge 24.
Das heißt, das, was Sie in der MIMA kodieren, ist im Zweier-Kompliment
der Länge 24 Wörter, der Länge 24 im Zweier-Kompliment kodiert.
Jetzt ist so ein Befehl, den man lädt, halt auch 24 Bit lang und der
enthält dann sowohl die Kodierung darüber, um welchen Befehl handelt
es sich, als auch die Kodierung darüber, über welche Parameter
sprechen wir hier.
Beispielsweise ist einer der Parameter die Adresse.
Wenn man sowas hat wie Load-Value, Store-Value, Adressen sind 20 Bit
lang, also sind die letzten 20 Bits sowas wie Adressen.
Oder halt bei Load-Constant gibt man halt auch eine Konstante an.
Und da ist halt das Problem, die Konstante kann halt nicht 24 Bit lang
sein, die ich lade.
Die kann weniger sein.
Und wir hatten gelernt, die Konstante, die ich lade, die ist halt 20
Bit lang und die vier Bit, die ersten vier Bit sind reserviert für die
Kodierung des Befehles Load-Constant.
Und was passiert also mit den vier Bit, die ganze links stehen, die
halt nicht drin stehen, die werden mit 0 aufgefüllt.
Das heißt, insbesondere wenn man bedenkt, dass im Zweierkomplement
eine negative Zahl immer das ganz links stehende, das höchstwertige
Bit auf 1 stehen hat, können wir schon mal keine negativen Zahlen
laden.
Was ist jetzt mit den positiven Zahlen?
Naja gut, ich kann halt was laden, was 20 Bit lang die 1 enthält und
mehr halt nicht.
Aber das ist nach wie vor eine positive Zahl.
Da wird links mit 0 aufgefüllt.
Das heißt, das ist eine positive Zahl.
Also ist die größtmögliche Zahl, die ich laden kann, diejenige Zahl,
die 20 Bit hat, die auf 1 stehen.
Und dann kommen links davon nochmal vier Bit, die auf 0 stehen.
Und das ist eben gerade die Zahl 2 hoch 20 minus 1.
Oder wenn es einen interessiert, das ist 1.048.875.
Dann die nächste Aufgabe, da ging es darum, dass man ein MIMA-Programm
schreiben soll, das halt so zwei Zahlen, 2 hoch 20 und 2 hoch 19
addiert und in eine Speicherzelle Y schreibt.
Und jetzt kriegen wir schon das Problem, da steht nichts davon, dass
diese Zahlen, die ich addieren will, schon irgendwo im Speicher
liegen, sondern die Zahlen muss ich erstmal irgendwie in den Speicher
bekommen.
Und die größte Zahl, die ich halt mit loadConstant laden kann, ist 2
hoch 20 minus 1.
Das heißt, 2 hoch 20 in den Speicher zu bekommen, ist jetzt erstmal
eine kleine... muss man sich halt ein bisschen darum kümmern, kann man
nicht einfach hinschreiben loadConstant 2 hoch 20, das geht nicht,
sondern ich kann maximal 2 hoch 20 minus 1 laden.
Das heißt, damit ich das jetzt korrekt machen kann, lade ich mir halt
2 hoch 20 minus 1 und muss zumindest als nächstes erstmal eine 1 drauf
agieren.
Vorlage 3.
Also mit anderen Worten, wenn ich das jetzt machen möchte, der erste
Schritt ist, dass ich halt 2 hoch 20 minus 1 laden kann,
dann speichere ich mir die erstmal ab, zum Beispiel an der
Speicheradresse y, von der ich weiß, dass sie existiert, da ja die ist
angegeben, und dann muss ich halt 1 drauf agieren.
Lade mir also die 1 in den Akku und dann addiere ich entsprechend y
drauf.
Und an der Stelle...
Das heißt, an der Stelle steht also jetzt im Akku 2 hoch 20.
Das merke ich mir wieder.
Jetzt müssen noch 2 hoch 19 drauf agiert werden.
2 hoch 19 ist kleiner als 2 hoch 20 minus 1, kann ich also mit
loadConstant laden.
Und addiere jetzt die 2 hoch 20 drauf und muss das Ganze halt noch
wieder an der Speicherstelle y abspeichern.
Und an dieser Stelle ist halt y genau 2 hoch 20 bis 2 hoch 19.
Ist also jetzt keine schwierige Aufgabe in dem Sinne.
Man muss halt den Fallstrick beachten, dass es manchmal schwierig sein
kann, die Konstanten, die ich gerne hätte, auch mithilfe von
loadConstant laden zu können.
Und damit zusammenhängt halt auch noch mal die Frage der Kodierung der
Befehle.
Wir hatten in der Vorlesung kennengelernt, dass es generell Befehle
gibt, die werden mit den 4 höchstwertigen Bits kodiert und es gibt
Befehle, die werden mit den 8 höchstwertigen Bits kodiert.
Das heißt, wenn ich jetzt erstmal irgendeinen Wert mir aus dem
Speicher raushole und sage, dass da ein Befehl, dann kann ich nicht
einfach erstmal a priori wissen, ohne dass ich die Bitfolge angucke,
ist das jetzt ein Befehl, der mit 4 Bit oder der mit 8 Bit kodiert
wurde.
Das muss sozusagen in der Kodierung der ersten 8 Bit irgendwie
drinstehen und dann kann ich halt, wenn ich das dann weiß, dann kann
ich halt mir entweder die ersten 4 oder 8 Bit hernehmen, das
Steuerwerk interpretiert die und interpretiert dann gegebenenfalls die
restlichen 20 Bit für die Verwendung des Befehles, beziehungsweise
wenn der Befehl mit 8 Bit kodiert wurde, dann ist es so, dass die
restlichen 12 Bit, die dann noch kommen, keinerlei Bedeutung haben für
die Ausführung des Befehls, nicht relevant sind.
Hier sind die Befehle, die Sie kennen, vorgegeben.
Die Aufgabe war es halt jetzt vorzuschlagen, was wäre eine sinnvolle
Kodierung dieser Befehle und wann immer es möglich sein sollte, sollte
man 8 Bit Kodierung verwenden und wenn es halt nicht möglich ist, dann
halt nur dann auf die 4 Bit Kodierung zurückfallen.
Gut, wann ist es möglich, die 8 Bit zu verwenden?
Möglich ist es, die 8 Bit zu verwenden, wenn ich halt nicht hinterher
die nächsten 20 Bit, die niederwertigen 20 Bit als Argument haben
will.
Das heißt, LoadConstant ist einer der Befehle, die kann ich nur mit 4
Bits machen.
LoadValue, StoreValue, LoadIndirectValue, StoreIndirectValue kann ich
auch nur mit 4 Bits kodieren, weil die brauchen halt alle diese 20 Bit
Adresse.
Genauso ist es bei Add.
AND, OR, XOR, NOT, EQUAL operieren alle nur auf dem Akku und brauchen
keine zusätzlichen
zusätzlichen Parameter wie Adressen oder sowas.
Das heißt, die kann ich mit 8 Bit kodieren.
JUMP und JUMP NOT EQUAL, die brauchen wieder, ja stimmt, Ent, OR und
XOR brauchen natürlich auch, und EQUAL auch, braucht auch eine
Adresse, stimmt.
Also Ent, OR, XOR brauchen alle Adressen, EQUAL braucht eine Adresse,
JUMP braucht eine Adresse, JUMP NOT EQUAL und erst VOTATE WHITE und
NOT sind die einzigen, die rein auf dem Akku operieren.
Die brauchen also keine Parameter und HOLD als Befehl, den wir so
halber kennengelernt haben, der braucht auch keine Parameter.
Das heißt, also die meisten muss man tatsächlich mit 4 Bit kodieren
und nur sehr wenige kann man überhaupt mit 8 Bit kodieren.
Und dann muss man halt aufpassen, dass das Ganze präfixfrei ist, dass
also die 4 Bit und die 8 Bit Befehle präfixfrei sind.
Das heißt also, es darf keine 4 Bit Sequenz geben, die ein 4 Bit
Befehl ist und gleichzeitig ein Präfix für eines dieser 8 Bit Befehle
ist.
Und da kann man halt entsprechend einen Vorschlag machen.
Eine in der Musterlösung, die Idee ist halt, dass man so ein 8 Bit
Befehl immer anfangen lässt mit der Sequenz 1 1 0 0 und wenn man dann
schaut, man hat insgesamt dahinter, was sind das?
1 2 3 4 5 6 7 8 9 10 11 12 Befehle, die man mit 4 Bit kodieren muss
und dann halt 3 Befehle, die man mit 8 Bit kodieren kann.
Wenn man das Präfix 1 1 reserviert, um anzuzeigen, dass jetzt ein 8
Bit Befehl kommt, dann kann man die alle anderen 4 Bit Befehle so
kodieren, dass man dafür nie das Präfix 1 1 braucht.
Man kann die also einfach von 0 beginnend hochzählen lassen und landet
dann hinterher beim höchsten Befehl hier bei dem 1 0 1 1 und das lässt
einem halt das Präfix 1 1 noch übrig, mit dem man dann anzeigen kann,
dass jetzt ein 8 Bit Befehl kommt.
Und dann kann man halt mit 1 1 anfangen und dann halt auch
entsprechend wieder die Befehle der Reihe nach hochzählen.
Und man hat auf diese Art und Weise eine mögliche Art der Kodierung.
Kann man natürlich auch umgekehrt machen.
Gibt halt auch noch andere Möglichkeiten, wie man das hinbekommen
kann.
Also so viel dazu.
Dann die nächste Aufgabe war wieder eine Programmieraufgabe.
Da ging es darum, jetzt Ganzzahldivision durchzuführen und das ganze
halt im Zweierkomplement.
Und wir hatten die Ganzzahldivision eigentlich nur auf positiven
Zahlen definiert.
Deswegen braucht man hier an dieser Stelle noch eine zusätzliche
Definition.
Was ist, wenn wir denn eine negative Zahl haben?
Und was berechnet werden soll, soll halt die Ganzzahldivision durch 4
und wenn ich halt eine negative Zahl habe, die ich durch 4 ganzzahlig
dividieren soll, dann soll ich erst mal den Betrag nehmen der Zahl,
also den positiven Wert der Zahl.
Den dividiere ich durch 4 und dann das Ergebnis legiere ich wieder.
Das wäre so eine Möglichkeit mit der Operation DIV, die wir nur auf N0
kennengelernt haben, geht zu einer DIV-Operation auf den ganzen Zahlen
zu definieren.
Das Ganze muss man jetzt also irgendwie in ein Programm gießen und die
erste Idee dabei war, wir hatten schon in der Vorlesung gesagt, wenn
man so durch Zweierpotenzen dividieren möchte, eine positive ganze
Zahl im Zweierkomplement zum Beispiel, wenn ich die mithilfe von
Zweierpotenzen dividieren will, dann ist das einfach ein
rechtsverschiebender Bits und man lässt rechts halt die
niederwertigsten Bits rausfallen und muss halt gucken, dass links von
links 0 Bits nachrutschen.
Das ist, wenn ich das einmal um 1 nach rechts verschiebe, das Bit, das
rechts rausfällt, wegwerfe, links mit 0 auffülle, dann habe ich halt
durch 2 dividiert und wenn ich das zweimal mache, habe ich halt durch
4 dividiert.
Das ist jetzt die Grundidee, das Ganze algorithmisch umzusetzen.
Da muss man halt jetzt auf ein paar Kleinigkeiten achten.
Das erste ist, wir haben zwar einen Befehl, der rotiert nach rechts,
aber der füllt links nicht mit 0 auf, sondern der geht im Kreis.
Das heißt, wenn ich rechts eine 1 rausschiebe beim Rotate Right auf
dem Akku, dann erscheint die wieder ganz links vorne.
Und wenn ich das zweimal mache, dann kann es halt sein, dass zwei
Einsen, die ich rechts rausschiebe, vorne links erscheinen.
Die muss ich also hinterher per Hand auf 0 setzen.
Das muss ich im Kopf behalten.
Und das andere, was ich in der Lage sein muss zu tun, ist hier
offensichtlich Zahlen zu legieren.
Ich muss also in der Lage sein, dass wenn ich eine negative Zahl habe,
die ich jetzt dividieren möchte, dass ich daraus erstmal eine positive
Zahl mache.
Und ein zweier Kompliment hatten wir auch in der Vorlesung kurz
angesprochen.
Wenn ich da eine Zahl legieren möchte, dann kann ich das machen, indem
ich erstmal ein bit-weises NOT rechne auf der Kodierung der Zahl und
dann noch 1 drauf addiere.
Beispielsweise, wenn ich halt die Zahl 1 habe und möchte daraus die
Zahl minus 1 machen.
Die Zahl 1 ist kodiert mit 0 und 0 und eine 1.
Mache ich daraus ein NOT, bekomme ich ganz viele 1, 1, 1, 1 und am
Ende eine 0.
Daraus kommen muss aber komplett 1.
Das heißt, ich muss hinten nochmal 1 drauf addieren, damit hinten die
1 draufkommt.
Wir haben eine Speicherzelle T1 gegeben.
In der speichern wir erstmal den ursprünglichen Wert, den wir im Akku
vorliegen haben, den wir dividieren wollen.
Warum?
Wir müssen uns für später merken, muss ich das Ergebnis denn nochmal
wieder negieren.
Wenn ich am Anfang eine negative Zahl habe, dann muss ich ganz am Ende
das Ergebnis, das nach dem Rotieren kommt, nochmal negieren.
Also muss ich mir zumindest merken, ob ich am Anfang eine negative
Zahl hatte.
Und das kann ich einfach dadurch machen, dass ich die ursprüngliche
Zahl abspeichere.
Denn die ganzen bedingten Befehle, die ich habe, um meinen
Kontrollfluss durchzuführen, meine Reihenfolge der Befehle zu ändern,
die prüfen immer ab, ob eine negative Zahl im Akku steht.
Und da ich halt hier hinterher auch abprüfen muss, ob die
ursprüngliche Zahl negativ war, muss ich jetzt nicht groß mehr
irgendwie bestimmtes Flex setzen.
Ich kann einfach die ursprüngliche Zahl abspeichern und dann hinterher
darauf testen, ob die negativ war.
Jetzt kann es sein, dass diese Zahl, die ursprünglich im Akku steht,
negativ ist.
Bevor ich jetzt also anfange zu rotieren, muss ich aus einer negativen
Zahl erstmal eine positive Zahl machen.
Das heißt, als erstes muss ich einen JumpNotEqual machen, zu einer
Adresse, wo ich diese Negierung erstmal durchführe.
Jetzt, wenn ich das so linear runterschreibe, weiß ich meistens noch
nicht, wie viele Zellen ich brauche.
Deswegen lasse ich mir das erstmal übrig und gucke, wo ich hinterher
Platz habe, das hinzuschreiben.
Und gucke mir jetzt mal den Fall an, was ist, wenn das Ganze eine
positive Zahl war.
Dann muss ich also erstmal die Division durchführen.
Einmal RotateWide wird nach rechts verschoben, zweimal RotateWide wird
nach rechts verschoben.
Das ist dann schon fast die Division durch 4, nur dass ich jetzt halt
auf die beiden höchstwertigen Bits noch achten muss.
Die beiden höchstwertigen Bits müssen halt noch auf 0 gesetzt werden.
Damit ich die auf 0 setzen kann, muss ich so ein bisschen
Vorbereitungsarbeit machen.
Also speichere ich mir jetzt erstmal das Zwischenergebnis ab.
Was ich jetzt brauche ist, damit ich die beiden höchstwertigen Bits
auf 0 setzen kann.
Zum Beispiel ein Bitmuster, das halt aussieht wie 1,1 und dann ganz
viele Nullen und wenn ich das... Entschuldigung, zwei Nullen und ganz
viele Einsen und wenn ich dann ein End ausführe, dann werden die
beiden höchstwertigen Bits garantiert auf 0 gesetzt.
Also muss ich jetzt irgendwie diese Bitfolge 0,0,1,1 reinbekommen in
den Akku.
Jetzt ist das eine Konstante, nur die Konstante ist zu groß, als dass
ich sie laden könnte, weil ich brauche halt da zwar zwei Nullen, aber
dann kann ich das mit Load konstant nicht laden, also muss ich ein
bisschen turnen, damit ich das machen kann.
Eine Möglichkeit ist, dass ich mir halt die Bitfolge 1,1 lade, erstmal
in den Akku.
Das wäre Konstante 3.
Dann rotiere ich das Ganze zweimal nach rechts.
Jetzt stehen diese beiden Einsen an den höchstwertigen Stellen des
Akkus und der Rest ist 0.
Das ist schon fast, was ich haben möchte, nur genau das Umgekehrte.
Dann mache ich daraus noch einen Not und jetzt sieht mein Akku halt so
aus, dass ich da 0 und ganz viele Einsen drin habe.
Und jetzt kann ich die Endoperation ausführen auf diesem Zwischenwert,
den ich hier oben ja abgelegt hatte.
Und jetzt habe ich die positive Zahl um 4 durch 4 geteilt und auch
dafür gesorgt, dass nicht irgendwelche Einsen rechts rausgerutscht
sind und vorne wieder reingerutscht sind.
Das heißt, den Wert können wir uns jetzt erstmal abspeichern.
Also man könnte auch, ja man kann sich auch die Konstante 3 laden,
noten und dann mit dem ursprünglichen Wert im Akku endmachen, ist auch
möglich.
Würde auch funktionieren.
Ich überlege gerade, das was man sich spart, sind halt dann diese
beiden Rotate Wide Befehle.
Um die kommt man dann halt weniger rum.
Gut, jetzt habe ich also diese positive Zahl, die früher mal irgendwo
im Akku stand, durch 4 geteilt und mir abgespeichert.
Jetzt muss ich mich noch darum kümmern, was war, wenn die
ursprüngliche Zahl eine negative Zahl war.
Angenommen, ich hatte halt irgendwo hier oben so eine Magie, die mir
aus der positiven Zahl eine negative Zahl gemacht hat.
Jetzt muss ich mir wieder das T1 herholen und jetzt hängt es davon ab,
ob das Ding negativ war oder nicht.
Wenn das Ding negativ war, wenn das Ding nicht negativ war, dann bin
ich an der Stelle fertig.
Dann steht jetzt, Moment, dann muss ich mir den ursprünglichen Wert
herholen und danach bin ich fertig.
Das Ergebnis, das ich haben wollte, steht dann im Akku.
Wenn das Ding nicht negativ war, dann machen wir hier hinten
bei 15 weiter.
Was ich jetzt mache ist, ich muss jetzt das, was im T2 steht, erstmal
noch negieren, bevor ich daraus dann das richtige Ergebnis habe.
Ich muss daraus dann nochmal eine negative Zahl machen.
Das kann ich einfach machen, indem ich mir das Ding lade,
negiere.
Negieren ist halt bitwise das Notmachen und dann eine 1 entsprechend
draufladen.
Und wenn ich das gemacht habe, steht jetzt ein Wert im Akku, der
negativ ist.
Ich habe vorher abgeprüft, dass der Wert,
das ist der ursprüngliche Wert, den ich hatte, negativ war.
Ich hatte den irgendwann invertiert, ich hatte dividiert, ich hatte
auf alle Fälle eine positive Zahl in dem T2 drin stehen.
Diese positive Zahl habe ich jetzt negiert.
Die ist auf alle Fälle negativ.
Wenn sie negativ ist, bin ich fertig.
Kann ich zu dem Halt springen.
Warum mache ich das so umstränglich?
Ich kann jetzt dieses Stück Code, was ich hier für die Negierung
verwende, kann ich jetzt dafür verwenden, dass ich das Ganze verwende
für die ursprüngliche Negation.
Weil ich habe hier oben ja immer noch die Sache zu verstehen, wenn das
T1 negativ ist, dann muss ich das T1 negieren.
Weil der Kollege hatte hier was vergessen.
An dieser Stelle hier, das wäre Speicherzelle 16, fange ich ja an, den
Wert im Akku zu negieren.
Das heißt,
hier an der Stelle speichere ich mir das Ergebnis noch in T2
sicherheitshalber ab.
Und dann kann ich hier eben an diese Stelle 16 springen.
Und was dann passiert ist, dass der Wert im Akku negiert wird und an
die Stelle 2 geschrieben wird.
Dieses an der Stelle 2 kann ich mir streng genommen auch sparen, weil
ich hier danach auf dem Akku weitermache.
Können wir also, wenn wir wollen, sparen und dann hier tatsächlich an
die Stelle 14 springen.
Das heißt, was man also hier macht, ist, dass man diesen Code für das
Negieren doppelt verwendet und halt sich zunutze macht, wenn da was im
Akku steht an der Stelle, das negativ ist nach dem Negieren, dann muss
es das zweite Negieren, das ich machen muss, gewesen sein und dann bin
ich fertig.
Und wenn danach im Akku was Positives steht, dann war das
offensichtlich das erste Negieren, was ich machen musste und dann muss
ich da an der Stelle 2 entsprechend weitermachen.
Mit der eigentlichen Division durchführen.
Mit der eigentlichen Division weitermachen.
Das ist so die Idee dahinter, das zu machen.
Ist das so im Großen und Ganzen die Idee dahinter klar?
Okay, dann machen wir weiter.
Das war es zu Aufgabe 4.2.
Mit der Aufgabe 4.3.
Wieder etwas zum Programmieren.
Sollte man ein bisschen mit Strings arbeiten und so eine formale
Sprachenoperation, eine simple formale Sprachenoperation mit Hilfe der
MIMA durchführen.
Die Konkatenation zweier Wörter.
Wörter werden halt in Programmiersprachen in der Regel als Strings
dargestellt und da ist halt immer die Sache, wenn ich einen String
beliebiger Länge, ein Wort beliebiger Länge irgendwie in einem
Speicher darstellen will, dann brauche ich paar Metainformationen.
Unter anderem zum Beispiel, wie lang ist das Wort.
Also kann beliebige Zeichenlänge haben.
Ich muss also in irgendeiner Form wissen, wie lang ist das Wort, damit
ich weiß, welcher Speicher gehört überhaupt zu dem Wort.
Wo hört das Wort irgendwo auf.
Das kann man unterschiedlich machen.
Zum Beispiel in objektorientiertem Programmieren könnte man häufig
sagen, ich habe halt ein Objekt, das repräsentiert einen String.
Das hat einmal einen Array, das enthält die ganzen Zeichen und dann
habe ich noch eine zweite Information, die sagt mir, wie viele Zeichen
denn überhaupt aus diesem Wort, dieses Wort besteht und dann weiß ich,
wie ich die einzelnen Zeichen aus dem Array rausholen kann.
Das ist natürlich, sagen wir mal, relativ großer Aufwand.
Eine andere Möglichkeit, das zu machen ist, dass ich mir halt ein
spezielles Zeichen reserviere, das mir sagt, hier Ende des Strings.
Und das ist halt in C so gelöst, dass das dieses Zeichen 0 eben als
besonderes Zeichen reserviert ist, das halt eigentlich in einem
normalen String nicht vorkommen darf.
Und wenn immer ich irgendwo durch eine Zeichenkette durchgehe, wenn
ich auf den Wert 0 stoße, auf das Zeichen 0 stoße, dann weiß ich, dass
hier ist das Ende des Strings.
Und jetzt geht man halt davon aus, dass man irgendwo zwei Strings im
Speicher stehen hat und will die jetzt halt entsprechend
konkatenieren.
Gut, was ist da die Idee dahinter?
Von der Ausführung her ist das relativ einfach.
Wir haben zwei Variablen, die nehmen wir zum Laden des Wertes,
beziehungsweise zum Schreiben des Wertes.
Das heißt, wir haben Speicherzellen, in denen merken wir uns immer,
was ist die Adresse des nächsten Wertes, das ich laden muss, und was
ist die Adresse, an die ich jetzt bei der Konkatenationsoperation
diesen Wert entsprechend als nächstes hinschreiben muss.
Und dann muss ich sozusagen von der Idee her halt durch den String
durchgehen, immer die Adresse auf das nächste Zeichen setzen, bei uns
stehen die hintereinander, muss ich also einfach mal um 1 erhöhen,
solange bis ich das erste Mal 0 bekomme im ersten String.
Dann muss ich bei der Anfangsadresse des zweiten Strings weitermachen
und da so lange durchgehen, bis ich halt die 0 sehe.
Und die einzige Unterscheidung, die ich machen muss, wenn ich den
ersten String rüber kopiere an die neuen Adressen, dann darf ich halt
die 0 nicht mit rüber kopieren.
Und wenn ich den zweiten String rüber kopiere, wenn ich da auf die 0
stoße, muss ich halt die 0 mit rüber kopieren, damit der String, der
finale konkatenierte String, auch ordentlich terminiert ist.
Dann nehme ich mir noch zwei weitere temporäre Variablen.
Die eine ist halt, dass ich halt irgendwas zum Zwischenspeichern
brauche, um halt immer abgleichen zu können, ist das Ganze jetzt 0
oder nicht.
Und dann brauche ich halt noch eine temporäre Variable für die ganzen
Additionsoperationen, die ich mache, wenn ich halt jeweils die
Adressen erhöhen möchte.
Und an der Stelle, wenn ich das halt so konzipiere, kommt halt diese
schöne zusätzliche Befehl, diese indirect load und weitgehende Befehle
mir schön zu nutzen.
Wenn ich also ein Load Value indirect mache, dann brauche ich dem halt
nur die Adresse zu geben t1, dann guckt er halt in t1 nach, was ist
denn die Adresse, von der ich jetzt laden will.
Und genauso dieses Store Value indirect, dem gebe ich dann halt immer
das t2, übergebe ich immer das t2.
Der guckt dann nach an der Stelle t2, wo muss ich als nächstes
hinschreiben und schreibt da halt entsprechend das Zeichen hin.
Wenn man jetzt so ein Programm aufschreibt, dann ist es halt das
erste, dass man sich die Variablen, die Hilfsvariablen, die man da
braucht, entsprechend initialisiert.
Ich hole mir halt als erste die Speicherstelle, an der der erste
String anfängt, rein.
Das ist halt die Speicherzelle x, die speichere ich mir in der
temporären Variable t1 ab.
Dann hole ich mir das Z, was war nochmal das Z?
Wo hole ich mir ein Z?
Das ist die Speicheradresse, wo es hin soll, oder?
Ah ja, hier stimmt es.
Genau, das ist die Speicheradresse, wo es hin soll.
Die kommt halt nach t2 rein, da wird das erste Zeichen hingeschrieben
und dann fangen wir halt an.
Wir holen uns das erste Zeichen von dem ersten String, speichern das
halt immer ab, gucken... also speichern das noch nicht ab, sondern
gucken erstmal als erstes, ist das Zeichen der Null String?
Wenn ja, dann Wort vollständig kopiert und wir machen bei dem Kopieren
des zweiten Wortes weiter.
Wenn nein, dann können wir das Zeichen halt in den Zielbereichen, in
die neue Zieladresse reinschreiben, müssen halt die Zieladresse um 1
erhöhen, müssen die Adresse, von der wir das nächste Zeichen um 1
erhöhen und dann geht die Schleife wieder los.
Und dann habe ich halt irgendwann hier an der Stelle das Zeichen Null
irgendwo hier geladen, merke das hier an dieser Stelle und mache dann
das ganze Spielchen wieder für den zweiten String und muss hier halt
dann aufpassen, dass ich dieses Checken, ob ich jetzt den Null String
hole, dass ich das hinter das Schreiben lege.
Dass ich also auch garantiert das Null Zeichen immer noch reinschreibe
und erst dann springe und nicht wie beim ersten Mal umgekehrt.
Und ansonsten ist das wieder genau die gleiche Schleife.
Das ist halt ein bisschen umfangreich hinzuschreiben, aber durch diese
load indirect value store, indirect value, spart man sich da halt
einiges und kann damit schön arbeiten.
Das ist sozusagen mit das simpelst mögliche Beispiel, das sie für eine
Technik verwenden können, die sich da Zeiger Arithmetik heißt oder
auch Pointer Arithmetik.
Wenn sie schon mal in C programmiert haben oder irgendwann mal in C
programmieren werden, ist das immer eine beliebte Technik, um halt
Speicher schnell zu, mit Speicher schnell manipulieren zu können.
Ist aber auch immer eine beliebte Federquelle, dass man bei Zeiger
Arithmetik irgendwas falsch macht und plötzlich irgendwo hin und
bringt, wo man gar nichts zu suchen hat.
Dass man also irgendwelchen Speicher überschreibt, die man eigentlich
gar nicht überschreiben sollte.
Und das ist dann meistens immer irgendein Einfallstor, wenn sie
irgendwelche Hackerangriffe haben, ist das mit eines der
wahrscheinlich am häufigsten ausgenutzten Feder, die beim
Programmieren passieren, dass man eben irgendwo über das Ende eines
Speichers hinausschreibt.
Irgendwann dafür sorgt, dass der Zeiger, an dem man jetzt, der auf die
Adresse zeigt, an die man als nächstes schreibt oder vor allem auch an
die man als nächstes lesen möchte, irgendwo zu einem Speicher gehört,
wo man eigentlich gar nichts zu suchen hat.
Und dann fängt man halt an von außen da Code einzuschleusen, der dann
das Programm aus der Bahn wirft und dann das macht, was ich möchte,
das jetzt auf diesem Rechner gemacht wird und nicht mehr das, dass
der, dem der Rechner gehört, das macht, was er machen möchte.
Deswegen gibt es inzwischen solche Speicherverwaltungsmechanismen,
Speicherschutzmechanismen, die halt versuchen, diese Programmierfeder
zu unterbinden, haben halt den Nachteil, dass das entsprechend
Overhead produziert, der die Programme halt langsamer macht, dass ich
also da jetzt mit dem Programm dadurch deutlich langsamer werde.
Und gerade wenn es so Anwendungen sind, wo es schnell gehen muss, dann
wird es halt problematisch.
Irgendwas unklar.
Meine Übungen sind dafür bekannt, dass ich da Fehler drin mache.
Insofern, wenn irgendwas fehlerhaft scheint, ruhig sagen.
Das wäre nicht ungewöhnlich.
Gut.
Also deswegen, das ist einfach nur etwas, wenn sie hinterher mal was
Schnelles Hardware nachprogrammieren müssen, werden sie mit dieser
Zeigearithmetik unter Umständen viel in Kontakt kommen.
Deswegen ist es ganz gut, wenn man sowas Einfaches mal übt.
Es ist halt nicht immer alles nur Java.
Java ist schon eine sehr hohe und abstrakte Programmiersprache, die
einem manchmal einige Sorgen abnimmt, die man dann aber eintauscht
gegen Geschwindigkeit.
Dann hatten wir noch was gemacht, ein bisschen zum Thema Grammatik.
Es war eine Grammatik angegeben mit Menge von Terminalen, Nicht
-Terminalen, Produktionen und einem Startsymbol.
Und dann sollte man ein bisschen mit dieser Grammatik so ein paar
kleine Fingerübungen machen.
Man sollte halt schauen, welche Wörter kann ich ableiten.
Das tastet man sich halt heran, indem man erstmal guckt, okay, wird
ein Wort vorgegeben, wie leite ich das denn ab?
Was passiert denn da?
Man kann das machen durch solche Ableitungsfolgen, man kann das machen
durch solche Ableitungsbäume.
Und dann irgendwann will man halt den Schritt hin machen, dass man
sich überlegt, okay, im Allgemeinen, welche Sprache erzeugt diese
Grammatik denn im Allgemeinen?
Und die einzig vernünftige Art und Weise, das herauszufinden, ist
halt, indem man irgendwie versucht, eine Art Logik, eine Art System,
eine Art Schema hinter diesen Produktionsregeln zu erkennen, die einem
dann zeigen, irgendwelche Bedeutungen müssen diese Nicht-Terminal
-Symbole in der Regel bei kontextfreien Grammatiken haben.
Die stehen immer für irgendwas.
Manchmal versucht man, das so ein bisschen zu verstecken, indem man da
so kleine Zirkel oder was einbaut.
Aber irgendwie, wenn man halt mal durchguckt und das so ein bisschen,
wie bei den, was wir als Kind gemacht haben, finden Sie, welcher Fisch
kommt in die Koralle rein.
Und dann haben Sie da drei Linien und müssen immer der Linie
nachfolgen, bis Sie herausgefunden haben, ob der jetzt sein Ziel
erreicht, die Schatzkuh erreicht oder nicht.
Und genauso hier muss man halt mal so ein bisschen diesen
Produktionsketten folgen, um zu verstehen, was passiert da, was wird
da, wo werden mal Terminal-Symbole eingezeugt, eingefügt und welches
Schema steckt da dahinter, welche Systematik steckt da dahinter.
Und dann, um es noch ein klein bisschen verwirrender zu machen,
Produktionen sind eine Menge.
Die Menge der Produktionen, das heißt die Reihenfolge der
Produktionen, ist darin beliebig.
Wir machen es halt in der Vorlesung immer, dass die erste Produktion
diejenige ist, die aus dem Startsymbol abgeleitet wird oder die ersten
Endproduktionen sind immer die, die aus dem Startsymbol kommen.
Das muss aber nicht sein.
Die Reihenfolge ist beliebig.
Deswegen beliebter Flüchtigkeitsfehler ist halt, dass man hier guckt,
nicht richtig guckt, was überhaupt der Startsymbol ist.
Und das Startsymbol ist halt hier Y und da muss man halt aufpassen,
dass das in diesem Fall ganz am Ende der Produktion steht.
Und dann kann man halt leicht anfangen.
Man soll halt erst mal das Wort 01 ableiten und fangen halt beim
Startsymbol Y an.
Gibt es nur eine Regel, das ist 0.
Und jetzt muss ich irgendwie noch zu der 1 kommen.
Hier komme ich zur 0A.
Eine Möglichkeit zur 1 zu kommen, wäre jetzt zum Beispiel über 1B zu
gehen.
Dann habe ich da eine 1 stehen.
Nur dann muss ich mir schauen, was dieses B produziert.
Und das B produziert immer mindestens ein zusätzliches Terminalsymbol.
Das heißt, wenn ich jetzt will, dass nur noch ein zusätzliches
Zeichen, also produziert immer ein, wenn ich hier zu dem BC gehe, das
B produziert immer mindestens noch ein zusätzliches Terminalsymbol.
Und die einzige Möglichkeit dann aufzuhören ist hier, wenn man in das
C geht und da die Epsilon macht.
Das heißt, wenn ich jetzt hier anfange, 0A habe und jetzt bin ich nur
noch die 1.
Und wenn ich die 1, die Regel habe, die lautet A1B oder ABC.
Die Regel 1B bringt mir halt nichts, weil dann nach der 1 noch
mindestens ein weiteres Terminalsymbol folgen muss, das halt nicht
Epsilon ist.
Und mein Wort soll nur noch 1 sein.
Das heißt, ich kann also nur über das BC gehen.
Und bei dem BC habe ich halt die Möglichkeit, jetzt hier das 1 zu
erzeugen und dann hinterher in dem C zu sein.
Und da komme ich dann über das C endlich in das Epsilon rein.
Das heißt, das ist so die eine Möglichkeit, wie man halt gehen kann,
dass man halt geht.
0A, A dann auf BC.
Und dann kann man bei BC halt das B auf das 1C ableiten und dann das
eine C auf das Epsilon und dann das andere C auf das Epsilon ableiten.
Dann, wenn man jetzt ein bisschen kompliziertere... wenn man ein
bisschen kompliziertere Wort hat, dann muss man sich halt auch
anschauen, wie komme ich jetzt da zu dem Ergebnis.
Und dann sieht man schon, dahinter ist irgendwie so eine Logik, dass
ich Wörter habe, die müssen alle irgendwie mit 0 anfangen.
Und dann habe ich hier verschiedene Möglichkeiten, entweder eine 1
oder eine 0 dahin zu zaubern und dann am Ende aufzuhören.
Und da ist es halt so, dass ich halt, wenn ich eine 0 hinzaubern will,
muss ich irgendwie gucken, dass ich über diesen 0C2 komme.
Das heißt, das ist das, was mir das BC angibt.
Und wenn ich dann irgendwie eine 1 hinzaubern will und es soll noch
weiter gehen, dann kann ich über den 1B-Pfeil gehen.
Und wenn ich eine 1 hinzaubern will und es soll aufhören, dann muss
ich auch entsprechend wieder über den BC-Pfeil gehen.
Und dann kann ich halt wirklich, also so...
Der Baum ist falsch.
Den hat irgendeiner, den alten Baum hingeschoben.
Das heißt also, auf die Art und Weise kann ich mir dann hier nach
diesen Regeln, dass dieses Wort 011010 entsprechend zusammenbauen.
Und je nachdem kann ich dann das Ganze entweder auf einem langen Weg
machen, indem ich halt immer über diese 1C0C bzw.
über diese 1B0C und dann mit dem BC-Regel gehe oder manchmal kann ich
halt auch so Abkürzungen einbauen.
Genau,
ich sage ja, der Baum ist falsch.
Das gucken wir uns gleich an.
Also jetzt bei der B sind wir erstmal bei der 01101.
Jetzt schauen wir uns halt den C an, den Baum 0110.
Und ich vermute mal, dass der Kollege, bevor er in den
Weihnachtsurlaub gefahren ist, dann noch schnell den alten Baum
reingemacht hat, weil ein Startsymbol S gibt es bei uns gar nicht.
Gut, was können wir machen?
Bei Y können wir überhaupt nur 0A ableiten.
Und dann brauchen wir 0110.
Gut, A kann man auf 1B machen, B kann man auf 1B machen und dann
brauche ich halt noch, dann habe ich das 011, dann brauche ich halt
noch die 0 und da muss ich halt wieder diesen BC-Zweig nehmen, kann
dann das 0, den BC-Zweig nehmen, kann dann hier, also den, also Y, den
0A -Zweig, den A-Zweig, der macht halt hier das 1B, 1B und dann an der
Stelle brauche ich halt, achso ja, kann ich die 0C nehmen und das C
dann entsprechend auf Y abbilden, so dass ich dann das Wort 0110 am
Ende da stehen habe als Ableitungsbaum.
Jetzt sollte man den zweiten Ableitungsbaum malen, der das gleiche
entsprechend macht.
Ich fange halt wieder genauso an mit meinem 0A, 1B, 1C und jetzt an
der Stelle unterscheide ich mich halt, dass ich halt hier aus dem B
halt entsprechend ein 1C ableite und dann aus dem C kann ich das B
entsprechend ableiten und aus dem B mache ich wieder ein 0C und aus
dem C mache ich halt entsprechend ein Y.
Und wenn man das jetzt alles zusammenzieht, was man also jetzt mit
dieser Grammatik machen kann, dann sieht das am Ende so aus, das Wort
muss also immer mit einer 0 anfangen.
Das heißt, die Sprache, die nur aus dem Wort 0 steht, ist das, wo
hinten dann irgendwelche anderen Wörter dran multipliziert werden und
wenn man dann schaut, welche anderen Worte man dann hinterher aus dem
eigentlichen A ableiten kann, dann sieht man, dass man halt aus dem A
entsprechend dann beliebige Worte über dem Alphabet 0, 1 entsprechend
ableiten kann.
Weil ich kann zum Beispiel sowas machen.
A geht nach B,
das...
ah, ne, Entschuldigung, stimmt, Sie haben recht.
Ja, das muss ein Plus sein, weil aus diesem B komme ich nicht heraus,
ohne dass ich, also aus dem A komme ich nicht heraus, ohne dass ich
irgendwas erzeuge.
Stimmt, ja, das muss ein Plus sein.
Dankeschön.
Gut.
Nächste Aufgabe.
Da ging es um eine prädikatenlogische Formel und den Zusammenhang der
aussagenlogischen Formel und der prädikatenlogischen Formel.
Und manchmal hört man so salopp die Aussage, die aussagenlogischen
Formeln sind ja nur eine Untermenge der prädikatenlogischen Formel.
Und das stimmt leider nur bedingt.
Es stimmt nicht so hundertprozentig ganz.
Wenn man sich die Grammatik anschaut, mit der so prädikatenlogische
Formeln erzeugt werden, dann hatten wir schon gesagt, so eine
prädikatenlogische Formel braucht mindestens ein Relationssymbol,
sonst ist es keine prädikatenlogische Formel.
Das heißt, eine beliebige aussagenlogische Formel G kann keine
prädikatenlogische Formel sein, weil sie halt dieses Relationssymbol
nicht enthält.
Natürlich ist dann Zusammenhang zwischen prädikatenlogisch und
aussagenlogisch.
Eine prädikatenlogische Formel wertet sich immer zu wahr oder falsch
aus und eine aussagenlogische Formel wertet sich immer zu wahr oder
falsch aus.
Aber diese Auswertung von Aussagenlogik und von Prädikatenlogik
funktioniert inhärent schon ein bisschen anders.
Bei der Prädikatenlogik ist das schon mal nochmal deutlich
komplizierter.
Und man muss aufpassen, dass man auch mit den Begriffen richtig
arbeitet, weil schon die Begriffe in der Prädikatenlogik und der
Aussagenlogik sich unterscheiden.
Wenn wir uns erinnern, eine Interpretation in der Aussagenlogik war
letztendlich nichts anderes als eine Variablenbelegung.
Eine Interpretation einer aussagenlogischen Formel ist die Zuweisung
der Variablen in der aussagenlogischen Formel mit den Begriffen wahr
oder falsch.
Bei der prädikatenlogischen Formel hat da eine Interpretation erstmal
noch nichts mit der Variablenbelegung zu tun.
Die Variablenbelegung war etwas Separates bei der aussagenlogischen
Formel.
Die Variablenbelegung ist separat und die Interpretation bestand aus
zwei Dingen.
Man hatte so ein Universum, so eine Domäne D und man hatte dann die
Interpretation der Konstantensymbole und der Funktionen.
Das heißt also, die Funktionssymbole standen nicht per se für sich
etwas, sondern das waren erstmal nur Symbole und denen musste eine
Interpretation zugeordnet werden.
Und genauso standen die Konstanten nicht direkt für etwas, sondern die
Konstanten, denen musste etwas zugeordnet werden, was halt auch
entsprechend aus diesem ursprünglichen Universum D kam.
Deswegen ist schon die Formulierung der Aufgabe als solches erstmal
ein bisschen aufwendiger, damit man hinterher diese beiden Value
-Funktionen überhaupt zusammen bekommt.
Die Value-Funktion der Aussagenformel braucht halt diese
Variablenbelegung.
Eine Interpretation die bei uns halt eine Variablenbelegung ist und
wenn man sich jetzt halt dieses Beta anschaut, dann kann die halt als
Interpretation dienen für eine aussagenlogische Variable.
Nämlich dann, wenn sie von den Variablen immer in die Domäne der
bool'schen Werte abbildet.
Das hatten wir hier allerdings gefordert, dadurch dass wir die Domäne
der Prädikantenlogik halt auf die entsprechenden bool'schen Werte
festgelegt haben.
Deswegen können wir das Beta überhaupt bei der Value-Funktion für die
Aussagenlogik einsetzen.
Und jetzt bei der Value-Funktion für die Prädikatenlogik haben wir
halt das D, die Interpretation und die Beta.
An der Beta können wir nichts drehen.
Die Beta sollen alle möglichen Variablenbelegungen sein.
Die ist dadurch bestimmt, dass wir sagen, es ist irgendeine
Variablenbelegung, die halt die bool'schen Werte abbildet.
Und jetzt hätten wir gerne, dass für jede Variablenbelegung halt der
Wahrheitswert dieser prädikatenlogischen Formel P der gleiche sein
soll, wie der gegebenen Wert der prädikatenlogischen Formel G.
Und die prädikatenlogische Formel G, die wertet sich zu irgendwas aus,
zu wahr oder falsch.
Und jetzt hätte ich gerne eine prädikatenlogische Formel, die wahr
ist, wenn G wahr ist und die falsch ist, wenn G falsch ist.
Und ein Relationssymbol, das wir halt immer haben in der
Prädikatenlogik, ist dieses Gleich-Gleich.
Das Gleich mit dem Punkt rüber.
Und dann kann man halt sagen, ja, die prädikatenlogische Formel, die
da lautet G Gleich-Gleich C mit der Interpretation C gleich wahr, die
ist halt immer dann wahr, wenn die aussagenlogische Formel sich in
ihrer eigenen Value-Funktion zu wahr auswertet und zu falsch noch.
Das heißt, man muss also hier, wenn man das hinschreibt, aufpassen.
Man braucht mindestens dieses eine Relationssymbol, sonst habe ich
keine prädikatenlogische Formel.
Plus, ich kann da nicht einfach W hinschreiben, sondern ich muss immer
mit Konstanten arbeiten und dann muss ich den Konstanten halt eine
Interpretation zuordnen, die dann halt dem entsprechenden Gewünschten
entspricht.
Nur auf diese Art und Weise kann ich zu einer güntigen
prädikatenlogischen Formel kommen, die auch wirklich das Richtige
macht.
Gibt auch andere Möglichkeiten, das zu machen.
Das ist so die kürzeste, die uns eingefallen ist.
Man kann auch zum Beispiel das von innen nach außen
rumreißen.
Man kann zum Beispiel anfangen, die Variablen in der aussagenlogischen
Formel durch Relationen zu ersetzen und dann halt auf unterster
Variablen -Ebene halt immer mit den Gleich-Gleich- Relationen zu
arbeiten und sich dann von unten nach oben zu einer gültigen
prädikatenlogischen Formel vorzuarbeiten.
Die Möglichkeit besteht gegebenenfalls auch.
Aber das ist halt, denke ich, kürzer und eleganter.
Wir schauen mal in den reinreichenden, ob es irgendwas gibt, was
vielleicht auch noch möglich und interessant ist, woran wir jetzt so
an der Stelle nicht gedacht haben.
Dann nächste Aufgabe.
Aufgabe 4.6.
Viel Text, wenig Inhalt.
Es geht darum, eine Cäsar-Chiffre zu knacken.
Wie funktioniert eine Cäsar-Chiffre?
Eine Cäsar-Chiffre ist eigentlich was relativ Einfaches.
War halt damals zu Zeiten von Julius Cäsar Stand der Dinge.
Heutzutage überrascht uns das nicht mehr so sehr.
Die Idee ist eigentlich einfach, dass wenn ich ein Alphabet habe, über
den meine Nachrichten geschrieben sind, dann erschiebe ich das
einfach, mache ich einen Rotate Right, so wie ich das in der MIMA
habe, halt drumherum und ersetze dann einfach die Buchstaben durch das
Zeichen, das N-Symbole weiter hinten im Alphabet kommt und wenn ich
halt über die Grenze des Alphabetes hinaus trage, dann bin ich halt in
dem Ring, in dem geschlossenen Ring und fange wieder vorne an.
Das heißt, ich mache sozusagen eine Addition und dann mache ich ein
Modulo, addiere ein Offset auf den Index des aktuellen Zeichens im
Alphabet, mache ein Modulo über die Größe des Alphabetes und das, was
herauskommt, ist dann der Index des Zeichens, mit dem ich das alte
Zeichen kodiere.
Wenn man sich überlegt, ich habe 26 Buchstaben jetzt mal im
lateinischen Alphabet der Großbuchstaben.
Ich habe also insgesamt nur 26 unterschiedliche mögliche Schlüssel,
wobei ein Schlüssel relativ problematisch ist, weil da nämlich genau
wieder die ursprüngliche Nachricht herauskommt.
Das ist der Schlüssel, den ich wahrscheinlich nicht verwenden möchte,
sodass ich also effektiv 25 Schlüssel zur Verfügung habe, um meine
Nachricht zu verschlüsseln.
Und wenn ich jetzt also herausfinden will, was ist denn die
ursprüngliche Nachricht und ich kenne den Schlüssel nicht, dann sieht
es mal dann gut aus, wenn folgendes gegeben ist.
Erstens, diese Funktion, mit der verschlüsselt ist, die muss
invertierbar sein und ich muss das Inverse berechnen.
Das ist in diesem Fall relativ einfach, also ohne großes besonderes
Wissen.
Wenn ich den Schlüssel habe, kann ich die Inversefunktion problemlos
berechnen.
Ich weiß, wie ich die Inversefunktion berechnen muss.
Alles ist gut.
Die andere Sache ist, wie viele verschiedene Schlüssel gibt es denn?
Und wenn die Anzahl der verschiedenen Schlüssel halt relativ klein
ist, dann probiere ich halt einfach alle Schlüssel mal durch und gucke
am Ende, was scheint denn die Nachricht zu sein, die das gewesen ist.
Das basiert halt auf dem Phänomen, dass ich nicht so viele
syntaktisch, semantisch, sinnvolle, korrekte Nachrichten über dem
Alphabet der lateinischen Großbuchstaben in einer bestimmten Sprache
habe.
Deswegen auch viel dieser Text, tralala, ein Kollege aus Deutschland
und so weiter, tralala, hat geschrieben.
Das ist einfach subtiler Hinweis, wenn es ein Kollege aus Deutschland
war, der mir schreibt, dann wird er vermutlich auf Deutsch schreiben.
Das heißt, wenn ich also einfach alles durchprobiere, dann gucke ich
halt unter den 25 möglichen Schlüsseln, bei welchen kommt denn eine
Nachricht raus, die irgendwie eine offensichtlich sinnvolle Nachricht
auf Deutsch ist und dann wird es wahrscheinlich die gewesen sein.
Ich kann nicht beweisen, dass es die Nachricht war.
Ich kann es nur erraten.
Aber die Wahrscheinlichkeit, dass ich richtig rate, wird relativ groß
sein.
Wenn ich Pech habe, kann halt sein, dass es irgendwas ganz anderes war
und vielleicht gibt es zum Beispiel zwei Schlüssel, wenn ich die
anwende und zurückrechne, dann kommt beidesmal eine sinnvolle
Nachricht raus und da muss ich halt aus dem Kontext raten, was war
denn die Ursprünge.
Aber das ist beim Dechiffrieren und beim Codeknacken halt immer so,
dass man halt viel Raten und Weltwissen einbringen muss.
Jetzt kann man sagen, naja, dieses Durchprobieren, das ist ja keine
Methode, die jetzt in der Praxis heutzutage noch Anwendung finden
wird.
Das ist nur bedingt richtig.
Man muss gar nicht so weit in der Geschichte zurückgehen, um auf
wirklich sehr wichtige erfolgreiche Dechiffrierversuche zu stoßen von
relativ komplizierten Chiffrierverfahren, wo aber so eine Brutforce
-Attacke zum Erfolg geführt hat.
Und wenn wir da hingehen, dann kommen wir halt relativ schnell wieder
bei Alan Turing an.
Und das ist, wenn man alles an Mathematik und drumherum wegschneidet
und sonst irgendwas, das ist genau das, was er gemacht hat, um die
Enigma zu knacken.
Das Verfahren zur Knacken der Enigma in seinem innersten Kern beruht
darauf, ich probiere so lange alle möglichen Schlüssel durch, bis eine
Nachricht rauskommt, die offensichtlich sinnvoll war.
Und dann kenne ich den Schlüssel und kann alle anderen Nachrichten,
die mit diesem Schlüssel chiffriert wurden, halt wieder dechiffrieren.
Nichts anderes hat Colossus gemacht.
Und was da zum Beispiel zum Tragen gekommen ist, ist, man hatte dieses
relativ komplizierte Verfahren mit mehreren Walzen, damit also nicht
wie so meiner simplen Caesar-Schrift, wo ich halt nur 26 Schlüssel
habe, sondern dass ich möglichst viele Schlüssel habe, dass also nicht
immer in der Nachricht jedes Zeichen auf dasselbe Zeichen abgebildet
wird, sondern abhängig davon, in welcher Position in der Nachricht
steht das Zeichen, wird es halt auf ein anderes Zeichen abgebildet.
Und dann waren die Konstrukteure der Enigma so schlau, genau das
Gleiche zu machen, was sie heutzutage an vielen Stellen finden, wenn
sie irgendwo ein Passwort eingeben müssen.
Wenn sie beim SCC sich ein Passwort anlegen müssen, dann steht da
drin, das Passwort muss zwischen mindestens sechs Zeichen lang sein,
es muss mindestens ein Sonderzeichen blablabla enthalten, muss
mindestens ein Großbuchstaben, mindestens ein Kleinbuchstaben und so
weiter und so fort.
Warum?
Ja gut, damit will man verhindern, dass man Passwörter nimmt, die
leicht zu raten sind.
Der Standard-Informatiker-Witz ist immer, my password is incorrect.
Why?
Because whenever I forget my password, the system will tell me your
password is incorrect.
Das will man halt verhindern und die Menschen sind dumm, die machen
das.
Also wenn man sich anguckt, die am meisten verwendeten Passwörter ist
irgendwie 1, 2, 3, 4, 5, 6 ist das am meisten verwendete und 1, 2, 3,
4, 5, 6, 7, 8 ist irgendwie das zweitmeist verwendete Passwort.
Gefolgt von solchen genialen Dingern wie Passwort und Secret und so
weiter und so fort.
Da ist man natürlich relativ schnell drauf gekommen und wenn man halt
in großem Maße durchprobieren will, irgendwie so Passwörter zu
knacken, dann gibt es halt Listen, da guckt man nach, was sind so die
meistverwendeten Passwörter und die probiert man mal durch.
Rechenzeit kostet ja nichts mehr.
Internet kostet ja nichts mehr.
Und für viele Anwendungen ist es halt nicht möglich zu sagen, naja,
wenn der dreimal falsch geraten hat, dann mache ich mal dicht, dann
kann ich nämlich die Konten von Leuten dichtlegen, indem ich einfach
Schrott hinziehe, hinschicke und dann können die Leute sich nicht
einloggen, weil halt der Login gesperrt ist.
Deswegen gibt es diese Sonderregel.
Und bei der Enigma gab es auch eine Sonderregel, von der die dachten,
das ist ganz schlau.
Und die Sonderregel lautete, ein Zeichen durfte nie auf sich selber
abgebildet werden.
Und das war tödlich.
Denn diese Sonderregel sorgte dafür, dass die Anzahl der möglichen
Schlüssel deutlich eingeschränkt wurde.
Und das Genie von Alan Turing war halt, dass er halt bei der Analyse
einer Enigma, die er halt, die wir von dem U-Boot erbeutet haben, halt
gesehen hat, dass das eben nicht passieren durfte.
Dass sie halt gesagt haben, okay, ein Zeichen darf nicht auf sich
selber abgebildet werden.
Das ist eigentlich völlig egal, weil ja die Abbildung war
positionsabhängig.
Den einzigen Sonderfall, den man auf die Art und Weise ausgeschlossen
hat, ist, dass man den Schlüssel, alles wird immer auf sich selber
abgebildet, den hat man damit natürlich auch ausgeschlossen.
Nur das wäre eigentlich das richtige Ausschlusskriterium gewesen.
Also das richtige Ausschlusskriterium wäre gewesen, ich schließe den
Schlüssel aus, der komplett in der gesamten Nachricht immer jedes
Zeichen auf sich selber abgebildet.
Und nicht der mal irgendwann an einer beliebigen Stelle ein Zeichen
auf sich selber abgebildet.
Und das hat halt entsprechend die Menge der möglichen Schlüssel stark
eingeschränkt.
Und dadurch hatte man eine größere Chance, durch einfaches Raten, den
richtigen Schlüssel zu finden.
Jetzt ist natürlich das immer noch zu langsam, zu sagen, Schlüssel 1
anwenden, Mensch guckt drauf, ist das sinnvoll oder nicht?
Schlüssel 2 anwenden, Mensch guckt drauf, ist das sinnvoll oder nicht?
Das wäre natürlich noch zu langsam, das muss man automatisieren.
Jetzt ist es natürlich, selbst nach heutigen, aber nach damaligen
Methoden, völlig aussichtslos, eine Maschine beizubringen, hier ist
eine Nachricht, sagt mir mal, ob das eine sinnvolle Nachricht ist oder
nicht.
Aber dann haben sie wieder sich angeguckt, was funkt denn die
Deutschen da so überhaupt durch die Gegend?
Und das eine, was sie durch die Gegend gefunkt haben, ist immer
Wetterbericht.
Und jede Nachricht fing irgendwie an, der Wetterbericht für heute
lautet, so sinngemäß.
Das heißt, er hat einfach Schlüssel durchprobiert, so lange, bis eine
Nachricht rauskam, die anfing, der Wetterbericht für heute lautet.
Und dann hat er gewusst, okay, Treffer, das ist der Schlüssel.
Und sobald die Maschine mal schnell genug war, das durchzuprobieren,
konnte der Schlüssel, konnte ein Schlüssel geknackt werden und alle
Funksprüche des Tages konnten halt entsprechend bis zum nächsten
Schlüsselwechsel gelesen werden.
Und dann haben die Deutschen noch einen anderen, sehr tödlichen Fehler
gemacht.
Das Problem ist ja, also es ist sinnvoll, den Schlüssel regelmäßig zu
wechseln.
Nur wenn ich jetzt halt mit Stationen funke, die irgendwo physikalisch
über die Welt verteilt sind, dann habe ich das Problem, wie lege ich
denn fest, was jetzt der nächste Schlüssel ist.
Eine Möglichkeit ist halt, bevor die mit ihrem Funkgerät losdüsen,
kriegen die halt ein Buch in die Hand und da steht für jeden Tag drin,
was der Schlüssel ist.
Das ist gefährlich, weil ich brauche mir nur einen zu catchen, der so
ein Buch in der Tasche hat.
Und dann ist die ganze Scheiße vorbei.
Dann kann jeder mitlesen, der dieses Buch gefunden hat.
Also haben wir eine ganz geniale Idee gehabt.
Wir haben eine verschlüsselte Funkverbindung.
Wir schicken einfach als Funkspruch den Schlüssel für den nächsten Tag
mit.
Natürlich doof, weil wenn ich einmal irgendwann in der Vergangenheit
eine Nachricht entschlüsselt habe, dann brauche ich mich halt nur
durch die Tage so lange durchzuhangeln und kriege immer wieder den
nächsten Schlüssel mit.
Und das ist halt eine der anderen Sachen, die sie gemacht haben.
Jetzt gibt es diesen schönen Film dazu, wo halt auch erzählt wird, da
ist es natürlich Hollywood.
Ich bin jetzt kein Kryptologie-Historiker.
Da hat es immer geheißen, sie haben erkannt die, der Funknachricht,
weil die angeblich immer mit Heil Hitler aufgehört hat.
Das ist nicht das, was ich weiß.
Also was ich weiß, ist wirklich, dass sie immer gewusst haben, um die
Uhrzeit wird der Wetterbericht übertragen und der Wetterbericht fängt
immer mit an, das Wetter für heute ist, die Wettervorhersage für die
nächsten 24 Stunden lautet.
Und daran haben sie das halt erkannt.
Aber auch so, sobald ich weiß, garantiert weiß, eine dieser Phrasen
muss vorkommen, dann kann ich halt danach suchen und gucken.
Und jetzt an der Stelle war es halt relativ einfach.
Als Mensch ist man nicht überfordert, sich 25 kleine Texte anzugucken
und dann zu entscheiden, was ist der richtige Text.
Und der richtige Text war halt jahreszeitabhängig entsprechend
gewählt.
Mein Interesse halber, wer hat das gemacht?
Wer hat das Ding entsprechend dekodiert hier im Hörsaal?
Doch die meisten.
Also okay, das ist schon, also offensichtlich was.
Das war nicht so aufwendig.
Das heißt, wir können alle im Chor lesen, es begab sich zu der Zeit,
dass vom Kaiser Augustus ein Gebot ausging, dass alle Welt sich zählen
ließe.
Und dieses war die erste Zählung ihrer Art und geschah zu der Zeit,
als, ich weiß schon nicht mehr, Stadthalter in Syrien war und so
weiter und so fort.
Jetzt wäre natürlich die erste Frage, die Sie stellen sollen, was will
der hier mit dem Weihnachtskitsch?
Wir machen Informatik.
Und jetzt kommt er da mit so einer Nachricht, die wir dekodieren
müssen, die da irgendwie so einen religiösen Weihnachtskitsch enthält.
Das ist nur die erste Betrachtung.
Wenn man sich das Ding durchliest, ist das doch etwas, was für
Informatiker eine ganz besondere Bedeutung hat.
Abgesehen davon, also der religiöse Inhalt, die Engel auf dem Felde
verkünden und dann, dass der Sohn Gottes geboren wurde und so weiter.
Aber der historische Kontext, der ist interessant.
Es begab sich zu der Zeit, dass vom Kaiser Augustus ein Gebot ausgeht,
dass alle Welt sich zählen ließe.
Und das war die erste Zählung ihrer Art und so weiter und so fort.
In anderen Worten, da wird eine Volkszählung durchgeführt.
Und das ist etwas, was auch noch heute die Gemüter erhitzt und zu
heftigen Diskussionen führt, ist sowas überhaupt zulässig.
Ist eine Volkszählung etwas, was man machen darf?
Als ich in der Schule war, da wurden große ideologische Grabenkämpfe
durchgeführt, weil Deutschland wollte eine Volkszählung durchführen
und darf die überhaupt eine Volkszählung durchführen.
Und jetzt erst vor, ich glaube, drei Jahren war die letzte
Volkszählung, die durchgeführt wurde, wo die meisten von ihnen gar
nichts von mitbekommen haben, weil die halt nicht dieses alle Welt
wird gezählt, also bei jedem kommt einer vorbei und zählt, wie viele
Leute sind das denn und wie alt und wie viel Männlein und Weiblein und
was arbeiten sie denn so und wo fahren sie hin.
Sondern es wurden nur Stichproben genommen und daraus wurde dann
interpoliert.
Was zum Beispiel dafür gesorgt hat, dass Karlsruhe neuerdings die
zweitgrößte Stadt im Lande Baden-Württemberg ist und die Mannheimer
angefressen bis zum Gehtnichtmehr, weil sie plötzlich die drittgrößte
Stadt sind.
Die klagen bis heute dagegen.
Nicht, weil ihr Stolz verletzt ist, sondern weil sie glauben, dass sie
mehr Einwohner haben, als nach dieser extrapolierten Volkszählung
rausgekommen ist und sie bitteschön mehr Steuergelder kriegen sollen,
als sie im Augenblick kriegen.
Nichtsdestotrotz, also und wenn man sich jetzt anschaut,
unterschiedliche Länder handhaben das unterschiedlich.
In den USA steht in der Verfassung drin, dass gefälligst gezählt wird
und dass bitteschön alle zehn Jahre gezählt wird.
Und das ist für die Informatik auch ganz interessant.
Das hatten wir schon erwähnt.
Das ist letztendlich einer der wichtigen Trittsteine, der zum Erfolg
der Firma IBM geführt hat.
IBM hat halt so Rechenmaschinen gemacht und die USA haben halt alle
zehn Jahre ihre Bevölkerung durchgezählt und wie das so ist, im Laufe
der Zeit ist die Bevölkerung halt gewachsen und irgendwann waren die
USA an einem Zeitpunkt, da hatten sie die letzte Volkszählung noch
nicht ausgewertet, also die hatten die ganzen Tabellen, die da
zusammenkamen, noch nicht zusammengezählt.
Sie wussten noch gar nicht, wie viele Leute denn jetzt da vor zehn
Jahren gelebt haben und mussten schon die nächste Volkszählung
durchführen.
Und das war irgendwie der Zeitpunkt, wo denen aufging, das geht so
nicht weiter, da müssen wir was machen.
Und dann hat IBM denen halt schöne Maschinen gebastelt und
hingestellt, mit denen sie halt schneller automatisch die Volkszählung
entsprechend auswerten konnten.
Und dann ist halt der andere Aspekt.
Ist das legal oder ist das nicht legal?
Darf man das oder darf man das nicht?
Und Deutschland hatte halt in den 80er Jahren angefangen, Volkszählung
durchzuführen mit der Begründung, naja, das ist halt sinnvoll, wenn
ich solche Statistiken weiß, dann kann ich besser planen.
Da hängt relativ viel dran, wie viele Schulen brauche ich.
Weil so, wenn ich jetzt feststelle, nächstes Jahr habe ich plötzlich
50 Prozent mehr Schüler, dann habe ich nicht nächstes Jahr plötzlich
auch 50 Prozent mehr Lehrer da stehen und erst recht nicht 50 Prozent
mehr Klassenräume und so weiter.
Wenn plötzlich rauskommt, mehr Leute pendeln zur Arbeit, dann habe ich
nicht plötzlich mehr Eisenbahnen und mehr Straßen und mehr Brücken und
so weiter zur Verfügung.
Wenn rauskommt, morgen habe ich 50 Prozent mehr Leute, dann habe ich
aber nicht, wenn ich das heute feststelle, morgen dann auch 50 Prozent
mehr Krankenhäuser und Ärzte und sonst was da stehen.
Das heißt, ich habe auch nicht genügend Universitäten dann und so
weiter und so fort.
Das heißt, die Idee war dahinter, wir zählen halt sehr genau, wir
erheben sehr genau detaillierte Informationen, damit wir extrapolieren
können, was wir denn in der Zukunft so an Infrastruktur brauchen und
wo wir das Steuergeld dann bitteschön hinkanalisieren, was wir machen
können.
Und dann sind die halt hingegangen und haben halt gesagt, naja, je
genauer wir das wissen von den einzelnen Leuten, desto genauer können
wir halt entsprechend das vorhersagen und desto besser können wir die
Steuergelder anführen.
Und dann haben die halt eine Volkszählung per Gesetz beschlossen, wo
extrem detaillierte Informationen herum, also was arbeiten sie, wie
viel Geld verdienen sie, wie viele Kilometer fahren sie zur Arbeit,
wie viele Kilometer wohnen sie von dem und dem weg und so weiter und
so fort, was ist ihre Schulgröße.
Also es war so sinngemäß, es war extrem detailliert.
Und das hat einigen Leuten nicht gefallen, weil sie halt gesagt haben,
das geht den Staat rein gar nichts an.
Es kann nicht sein, dass der Staat so ein Register aufstellt, wo
extrem detaillierte Informationen über mich irgendwo zentral gesammelt
sind und haben dagegen geklagt.
Und das ging halt durch die Instanzen durch und landete irgendwann
dann entsprechend vom Bundesverfassungsgericht.
Und damit sind wir dann entsprechend bei der nächsten Aufgabe, bei der
Aufgabe 4.7.
Die hat jetzt erstmal den ersten Aspekt, dass ich da ein anderes
Verschlüsseungsverfahren habe.
Und dieses Verschlüsseungsverfahren ist auch schon lange bekannt und
nennt sich das One-Time-Pet.
Und jetzt ist da auch wieder ein bisschen blubbi blubbi und einer der
blubbi blubbi sagte, hier ist der Hinweis, schauen Sie mal bei
Wikipedia nach, was da so über One-Time-Pet steht.
Und das erste, was man nachliest, wenn man bei Wikipedia schaut bei
One -Time-Pet, ist dieser interessante Satz, das One-Time-Pet ist ein
beweisbar sicheres Verschlüsselungsverfahren.
Das heißt, ich kann beweisen, dass ich diesen Code nicht knacken kann.
Dementsprechend 120 Punkte, also wer es schafft, den Code zu knacken
und mir zu beweisen, dass das die Nachricht ist, die ich da bitteschön
verschlüsselt habe, der kann von mir erst die 120 Punkte liebend gerne
haben.
Dem gebe ich auch eine 1-0 in der Klausur, ohne dass ich mir die
Klausur anschaue, weil es nicht geht.
Und die Idee dahinter ist halt, ich mache halt wirklich, ich nehme
meine Nachricht, kann die zum Beispiel als Bitstream auffassen, dann
mache ich mir einen zufälligen Bitstream, der genauso lang ist wie die
Nachricht und berechne immer ein exklusives Oder und das Ergebnis
schreibe ich raus und zurückrechnen kann ich halt nur, wenn ich den
Schlüssel kenne.
Das Ding kann man nicht knacken.
Solche Sachen, die damit verschlüsselt sind, sind absolut 100 Prozent
sicher mit einem großen K-Wert und das ist, der Schlüssel muss sicher
sein.
Und damit der Schlüssel sicher ist, muss er zum einen zufällig erzeugt
sein, weil ansonsten habe ich unter Umständen eine Chance, wenn ich
sozusagen den Mechanismus hinter dem Erzeugen des Schlüssels
rauskriegen kann, dass ich dann die Schlüssel ausrechne, ohne dass ich
den Schlüssel kenne.
Die andere Möglichkeit ist, ich catch mir einen, der den Schlüssel hat
und wirk den so lange, bis er mir den Schlüssel gibt.
Oder ich schnappe mir halt sein Kind und schicke dann dem so lange
Finger von dem Kind, bis er mir den Schlüssel gibt.
Sie lachen, das wird gemacht.
Das wird gemacht.
Also das ist eine reale Bedrohung bei solchen Schlüsseln.
Das ist genauso wie dem Bankdirektor, der den Schlüssel zum Tresor
hat.
Das ist eine reale Bedrohung, dass dessen Kinder gecatcht werden und
dann Kind gegen Schlüssel.
Oder halt Kind in Stücken zurück.
Dann wird er sich meistens dafür entscheiden, dass vielleicht das Geld
doch nicht so viel wert ist, wie sein Kind und den Schlüssel
rauskriegt.
Das passiert relativ häufig.
Das heißt also, dass die Sicherheit des Verfahrens hängt davon ab, wie
sicher ist der Schlüssel.
Und es hat natürlich den Haken, ich brauche den Schlüssel sowohl auf
Empfänger - als auch auf Senderseite.
Beide müssen diesen Schlüssel kennen.
Und viele kryptographische Verfahren, die man heutzutage ausverwendet,
die sie so in der Regel verwenden, die haben das eben nicht mehr.
Die sind von der Gestalt, dass ich nicht den Schlüssel kennen muss,
mit dem verschlüsselt wurde, damit ich entschlüsseln kann.
Sondern das sind dann diese asymmetrischen Verfahren, da gebe ich
einen Schlüssel raus, kann sagen, das ist der Schlüssel, mit dem Sie
bitte verschlüsseln, aber danach kann man das Ganze nicht mehr so
leicht zurückrechnen.
Weil die Funktion ist zwar invertierbar, man kann es ja sonst schlecht
entschlüsseln, nur das Berechnen der invertierten Funktion ist so
fürchterlich aufwendig teuer, dass ich halt ein paar hundert Jahre
rechnen muss, bevor ich die Schlagricht dekodiert habe.
Wenn ich nicht irgendwelche Zusatzinformationen habe, und diese
Zusatzinformationen, wie die Primfaktorzerlegung der Schlüssel, die
bleibt halt beim Empfänger nur liegen.
Aber die Sachen sind offensichtlich unsicher, weil wenn man nur
genügend Rechenzeit reinsteckt, kann ich das entsprechend erknacken.
Das heißt also, bei dem Schlüssel kommt es darauf an, ich brauche sehr
guten Zufall, sonst kann ich bei sehr hohem Datenvolumen mit
geschickten Analysen unter Umständen zurückrechnen, und ich muss halt
dafür sorgen, dass der Schlüssel auch selber geheim bleibt.
Und das ist natürlich teuer, deswegen, wenn wird sowas angewendet für
Verfahren, da kommt es wirklich darauf an, die Nachricht, das Geld,
die Nachricht muss es wert sein, das muss eine teure Nachricht sein.
Das sind meistens so Regierungsdingen, wo ich nicht möchte, dass
irgendein anderer Staat mit liest, und die werden dann per
Telekommunikation übertragen, und man sagt halt, das ist ich, one time
per index, da geht's los, und dann muss man wieder bei sich
nachgucken, der eine verschlüsselt, der andere entschlüsselt, und
zwischendurch fahren dann halt da solche Booten durch die Gegend, dann
kommt der Queen's Messenger, ehemaliger Elite-Soldat mit Köfferchen,
das per Handschelle an sein Handgelenk gekettet wurde, und wenn einer
zu nahe kommt, passiert was, und der überträgt halt das Köfferchen zur
Botschaft, die dann demnächst Nachrichten entschlüsseln soll, die mit
dem One-Time-Pad, die in dem Köfferchen drin sind, verschlüsselt sind.
Und wie gesagt, Zufall herzustellen, ist extrem schwierig.
Der Rechner ist eine deterministische Maschine, das hatten wir schon
ein bisschen diskutiert.
Es gibt keinen Zufallszahlengenerator in dem Sinne, der durch
algorithmisches Rechnen funktioniert.
Das gibt es nicht.
Sowas wie Würfeln kann man ungefähr als Zufallszahlengenerator
ansehen, aber das ist was Analoges.
Digitaler Zufallszahlengenerator gibt es nicht, es gibt nur Pseudo
-Zufallszahlengenerator.
Das sind so mathematische Berechnungsvorschriften, da wird halt eine
initiale Zahl reingeworfen und danach kommen immer wieder neue Zahlen
raus, die halt zufällig aussehen, aber wenn ich wieder von vorne
anfange, kommt wieder die gleiche Zahlenfolge raus.
Das ist deterministisch, welche Zahlen da so im Laufe der Zeit
rauskommen, wenn ich mal den gleichen ziehe.
Dann versucht man halt den Seed, mit dem ich das initialisiere,
zufällig zu machen.
Außentemperatur, Tageszeit, Auslastung des Drehzahl, des aktuelle
Drehzahl des Lüfters und was es da alles so gibt.
Aber das sind alles, wenn es, wenn man es darauf anlegt und wenn man
genügend Daten hat, sind das alles Verfahren, die angreifbar sind.
Das heißt, wenn man jetzt so ein One-Time-Pad erzeugt, im schlimmsten
Fall, wenn es wirklich, also hier, nukleare Startpods und sowas von
der Größenordnung geht, dann geht man darüber, dass man zum Teil sowas
wie nukleare Zerfallsprozesse beobachtet.
Dann habe ich da halt irgendwo ein Cesiumatom stehen und dann gucke
ich, was ist denn das Intervall zwischen den einzelnen
Zerfallsprozessen, die da stattfinden, zu welchem Zeitpunkt finden die
denn statt und sieht das als ungefähr zufällig an.
Weil man halt als nukleare Zerfallsprozesse als in irgendeiner Art und
Weise zufällig verteilt ansieht.
Und dann kann ich halt zurückrechnen auf eine gleichmäßige
Zufallsverteilung.
Zurück zu der Frage, was ist das jetzt für eine Nachricht.
Da ich ein fieser Möpp bin, habe ich mir einen schlanken Fuß gemacht.
Eine Möglichkeit, eine Nachricht zu entschlüsseln, ist, Sie brechen
bei mir in mein Konto ein und gucken, ob Sie den Schlüssel finden.
Und wenn Sie dann den Schlüssel gefunden haben, dann können Sie
dekodieren.
Da müssen Sie nur die Sicherheitsmechanismen umgehen, die sozusagen
mein Dateisystem, meines Rechners, wo ich das halt gemacht habe,
umgehen.
Und die sind halt nicht mit One-Time-Pet oder irgendwas Besonderem
abgesichert.
Wenn man will, kommt man da rein.
Passiert häufig genug, dass irgendwelche Computerkonten bekommen.
Also habe ich mir nicht die Gemühe gemacht, einen Schlüssel zu
erzeugen und zu verschlüsseln, weil dann besteht die Gefahr, dass Sie
sich den Schlüssel krallen können, sondern ich habe das Ganze
simuliert.
Ich habe meine Nachricht, die ich verschlüsseln wollte, genommen, habe
geguckt, wie viel Byte hat die denn.
Okay, dann brauche ich jetzt also irgendwie eine zufällige Bytefolge,
die genauso lang ist.
Und wenn Sie unbedingt einen Schlüssel von mir haben wollen, ist das
kein Problem.
Dann setze ich mich nachher an den Rechner und gebe Ihnen den
Schlüssel, weil ich ja jederzeit zurückrechne.
Ich weiß ja, was die Verschlüsselung ist, ich weiß, was die originale
Nachricht ist.
Es gibt diesen Schlüssel.
Ich habe ihn halt nur nicht explizit hingeschrieben.
Und um mal ein bisschen zu verwirren, jetzt brauche ich irgendwie, das
waren 192.000 irgendwas Bytes, die ich brauchte.
Wo nehme ich die her?
Zufallszahlengenerator wollte ich nicht annehmen, also habe ich
einfach den Anfang des Linux-Körners bei mir auf der Maschine gemacht.
War sofort da.
Was hat das zu bedeuten?
Das ist der Anfang des Linux-Körners.
Das muss irgendwas bedeuten.
Das bedeutet nichts.
Es ist einfach eine Nachricht, die ist 192.000 Bytes lang, genauso
lang wie die ursprüngliche Nachricht.
Und dann kam, ja, aber das kann nicht rauskommen.
Es kann keine Klartextnachricht rauskommen, wenn ich verschlüssele.
Natürlich kann das.
Der Schlüssel ist zufällig erzeugt worden.
Es ist zufällig.
Es kann alles rauskommen.
Ja, aber es ist extrem unwahrscheinlich, dass ausgerechnet das.
Nee.
Ich kann zwei Nachrichten nehmen.
Ich kann ihnen einen Zufall nehmen.
Ich kann die Nachricht nehmen, die ich genommen habe.
Die Wahrscheinlichkeit, dass jetzt die ersten paar, die ersten Bytes
des Linux-Körners bei rauskommen, diese Nachricht, hat genau die
gleiche Wahrscheinlichkeit, als dass jede beliebige andere Nachricht
bei rauskommt.
Das sind statistisch unabhängige Ereignisse.
Die sind komplett unabhängig.
Das ist genauso, wie bei den Lottozahlen.
Es ist genauso unsinnig zu sagen, dass die Lottozahlen jetzt gerade
die Zahlen, was ist es, 6 aus 49, 1, 2, 3, 4, 5, 6 sind.
Das ist extrem unwahrscheinlich.
Das kann gar nicht sein.
Das muss irgendeine andere sein, dass ich also, sagen wir mal, das
ausschlüssele.
Nee.
Es ist genauso, Sie können 1, 2, 3, 4, 5, 6.
Das ist genauso wahrscheinlich und unwahrscheinlich wie jede andere
beliebige Methode, 6 aus 49 zu ziehen.
Das ist bei Zufall so.
Das kann halt bei rauskommen.
Wenn ich Ihnen jetzt eine Million Nachrichten gebe, dann ist die
Wahrscheinlichkeit, dass eine Million mal hintereinander der Linux
-Körner rauskommt, wenn Sie also das Ereignis nehmen, das ist dann,
sagen wir mal, unwahrscheinlicher als ein Ereignis, dass irgendwelche
Ereignisse rauskommen, die halt nicht eine Million mal hintereinander
der Linux-Körner sind.
Und das hilft Ihnen beim Entschlüsselen überhaupt nichts, weil Sie
brauchen das eine Ereignis und müssen jetzt zurückrechnen.
Und Sie können es nicht.
Es ist halt gerade zufällig so rausgekommen.
Bleibt also noch die einzige spannende Frage, was ist denn das, die
Datei?
Ich lege Ihnen die nachher auf die, aufs Ilias.
Ich lese die Ihnen jetzt aber kurz vor, weil das eine Datei ist, die
sollte jeder verantwortungsbewusste Informatiker kennen.
Nein, ich lese.
Ich habe jetzt keine Lust anzuhören.
Ich lese und Sie hören.
Ich lege es Ihnen nachher ins Ilias, aber das ist etwas, das sollten
Sie kennen.
Ich hatte gehofft, als ich die Aufgabe konstruiert habe, dass ich so
eine schöne Fassung finde, die so schön klischeehaft anfängt.
Sie gibt es leider nicht.
Ich wollte die Fassung haben, die anfängt mit im Namen des Volkes
ergeht folgendes Urteil.
Gibt es nicht.
Das ist die offizielle Version.
Fängt an mit Urteil Aktenzeichen 1 BVR 209 Schräger 83 1 BVR 484
Schräger 83 1 BVR 420 Schräger 83 1 BVR 362 Schräger 83 1 BVR 269
Schräger 83 1 BVR 440 Schräger 83 Sternchen.
Solange erst mal noch blöd, langweilig, interessiert sein.
Jetzt wird es schon ein interessanter Bundesverfassungsgericht.
15.
Dezember 1983.
Erstens, unter den Bedingungen der modernen Datenverarbeitung wird der
Schutz des Einzelnen gegen unbegrenzte Erhebung, Speicherung,
Verwendung und Weitergabe seiner persönlichen Daten von dem
allgemeinen Persönlichkeitsrechts des Artikels 2 Absatz 1 Grundgesetz
in Verbindung mit Artikel 1 Absatz 1 Grundgesetz umfasst.
Jetzt muss man wissen, was besagt Artikel 1 Absatz 1 des
Grundgesetzes?
Die Würde des Menschen ist unanpassbar.
Sie zu achten und zu schützen ist Aufgabe jeder staatlichen Gewalt.
Was sagt Artikel 2 Absatz 1?
Artikel 2 Absatz 1, was besagt der?
Jetzt wird es schon dumm.
Extrem wichtig.
Artikel 2 Absatz 1.
Jeder hat das Recht auf die freie Entfaltung seiner Persönlichkeit,
solange er nicht gegen die Recht eines anderen verstößt.
Artikel 2 Absatz 2 sollten Sie auch noch kennen.
Jeder hat das Recht auf körperliche Unversehrtheit und so weiter und
so fort.
Okay, also die beiden Artikel sagen, dass man ihre Daten nicht so
einfach nach Belieben speichern, auswerten und von ihnen abfragen darf
oder auch weitergeben darf.
Und dann Einschränkung dieses Rechts auf informationelle
Selbstbestimmung.
Und das ist jetzt, das ist revolutionär.
Da wird ein Recht, ein Grundrecht abgeleitet, das so nicht direkt im
Grundgesetz steht.
Und das war in der Geschichte der Rechtsprechung etwas extrem
Seltenes, dass man sagt, da existiert ein Grundrecht, das so nicht
explizit im Grundgesetz niedergeschrieben ist.
Und das ist dieses Grundrecht auf informationelle Selbstbestimmung,
das jeder kennen sollte, sind nur in überwiegendem allgemeinen
Interesse zulässig.
Bedürfen einer verfassungsgemäßen gesetzlichen Grundlage, die dem
rechtsstaatlichen Gebot der Normenklarheit entsprechen muss.
Bei seinen Regelungen hat der Gesetzgeber ferner den Grundsatz der
Verhältnismäßigkeit zu beachten, auch hat er organisatorische und
verfahrensrechtliche Vorkehrungen zu treffen, welche der Gefahr einer
Verletzung des Persönlichkeitsrechts entgegenwirken.
Mit anderen Worten, wenn der Staat Daten von Ihnen erhebt und
abspeichert, dann muss er dafür einen verdammt guten Grund haben.
Er darf es nur verhältnismäßig machen, das heißt, das, was gemacht
werden sollte, mit den sämtlichen kleinsten Details, alles über mich
abfragen in der Volkszählung, das darf man eben nicht, sondern man
muss sich auf das Verhältnismäßige beschränken.
Und, dass man das Ganze dann einfach so in der Excel-Datei beim
Kollegen auf dem Rechner hat, das darf auch nicht sein.
Sondern die Daten müssen geschützt sein.
Sie müssen geschützt sein gegen unbefugten Zugriff und so weiter und
so fort.
Bei den verfassungsrechtlichen Anforderungen an derartige
Einschränkungen ist unter uns zu unterscheiden zwischen
personenbezogenen Daten, die an individualisierte, nicht anonymer Form
erhoben und verarbeitet werden, und solchen, die für statistische
Zwecke bestimmt sind.
Das heißt, statistische Daten, bei denen ich nicht auf personalisierte
Daten zurückschließen kann, darf ich mehr als bei personalisierten
Daten.
Und da wird es interessant, weil da kommen Sie nämlich als
Informatiker ins Spiel.
Es gibt viele Daten, da guckt man drauf und denkt, ja, das sind nur
statistische Daten.
Und dann guckt ein Informatiker drauf und dann fängt er mal an, ein
bisschen zu rechnen.
Und dann kann der ganz ratzifatzi aus solchen auf den ersten Blick
statistischen Daten ganz schnell jede Menge personalisierte,
individualisierte Daten ableiten.
Und da wird es dann halt wichtig, dass man dann auch darauf hinweist
und weiß, dass das nicht unbedingt immer offensichtlich ist, was jetzt
statistisch ist und was nicht.
Und dann, es geht ein bisschen weiter und so weiter.
Und am Ende, das Wichtigste ist, das Erhebungsprogramm des
Volkszählungsgesetzes 1983 führt nicht zu einer mit der Mürde des
Menschen unvereinbaren Registrierung und Katalysierung der
Persönlichkeiten.
Es entspricht auch den Geboten der Normenklarheit und
Verhältnismäßigkeit.
Das heißt also, die Volkszählung, so wie sie gemacht wurde, wurde als
verhältnismäßig angesehen.
Das Gesetz war ordentlich ausformuliert, aber indessen bedarf es zur
Sicherung des Rechts auf informationelle Selbstbestimmung ergänzender
verfahrensrechtlicher Vorkehrungen für Durchführung und Organisation
der Datenerhebung.
Das heißt also, die Daten, die erheben werden sollten, waren in
Ordnung.
Nur die Art und Weise, wie sie erhoben und verarbeitet werden sollten,
war nicht in Ordnung.
Und das ist dann, wo die Informatiker halt entsprechend dafür sorgen
müssen, dass Mechanismen bereitstehen, um die Daten gesetzeskonform in
Übereinstimmung mit dem Grundrecht auf persönliche Selbstbestimmung,
informationelle Selbstbestimmung in Einklang zu bringen.
Und das war halt, das im Großen und Ganzen das Volkszählungsgesetz aus
dem Jahre 1983, das mit zum ersten Mal in der Geschichte der
Bundesrepublik Deutschland das, was wir als Informatiker machen, das
Verarbeiten von Informationen einer breiten Öffentlichkeit vor Augen
geführt hat, dass es sehr mächtig ist, dass man da sehr viele Dinge
mitmachen kann, dass man damit gute Dinge machen kann und dass man
damit böse Dinge machen kann.
Und dass das Achten auf die eigenen persönlichen Daten etwas ist, was
ein Mensch im Auge haben sollte.
Und der generelle Tenor ist halt, dass gerade in ihrer Generation und
den ihnen folgenden Generationen so ein bisschen dieses Bewusstsein
darüber, dass man vielleicht auf seine eigenen persönlichen Daten auch
ein bisschen mehr Acht geben müsste, abhandengekommen ist.
Es gibt durchaus auch Stimmen, die fordern, sowas wie persönliche
Datensicherheit gibt es nicht mehr.
Man muss alles öffentlich machen, weil man halt aus vielen Sachen zum
Beispiel eh zurückrechnen kann.
Deswegen pfeift was drauf, macht eh alles öffentlich.
Wenn von jedem die kleinste Peinlichkeit öffentlich ist, dann ist es
eh nicht mehr peinlich und dann ist es nicht mehr relevant.
Das ist durchaus Argumentation, die man hin und wieder hört und ich
möchte einfach hiermit, dass Sie sich ein bisschen noch mal darüber
Gedanken machen.
Was heißt das?
Was heißt es, so ein Grundrecht, das hier durch das Verfassungsgericht
festgestellt wurde, auf diese Art und Weise einfach so nonchalant
aufzugeben?
Ist das eine weise Entscheidung oder ist das etwas, was man vielleicht
noch mal überdenken sollte?
Und wenn Sie überall Ihre Daten, so wie ich das auch mache, in
sämtlichen sozialen Netzwerken hin und her schicken, dann ist das die
eine Sache und die andere Sache ist, vertrauen Sie den Firmen, die
dahinterstecken.
Das Bundesverfassungsgericht hatte sich beschäftigt mit, was darf der
Staat und hat dem Staat sehr enge Grenzen gesetzt.
Der Industrie hat das Bundesverfassungsgericht diese Grenzen nicht
gesetzt.
Es ging hier um die Daten, die der Staat erhebt.
Warum?
Da habe ich jetzt was Interessantes gehört.
Das ist eine relativ radikale Meinung, aber am Ende ist es wahr.
Wenn man es bis zur letzten Konsequenz und also wirklich bis zur
allerletzten Konsequenz runterdrillt, wenn der Staat Daten erhebt,
wenn er so ein Volkszählungsgesetz verabschiedet, dann heißt das
nichts anderes, dass wenn man es bis zum Ende durchgibt, er nimmt sie,
hält ihnen die Knarre an den Kopf und sagt, du gibst mir jetzt die
Daten oder.
Weil, wenn man halt die Daten nicht abgibt, dann gibt es eine Strafe.
Das kann erstmal nur eine Geldstrafe sein.
Wenn ich die nicht bezahle, dann gibt es eine zweite Geldstrafe.
Und wenn es keine zweite Geldstrafe gibt, dann gibt es irgendwann eine
Gefängnisstrafe.
Dann kriegt man einen Brief und sagt, Sie gehen jetzt ins Gefängnis.
Dann sage ich, nö, ich gehe nicht ins Gefängnis.
Und dann kommt irgendwann ein Polizist vorbei und nimmt sie.
Oder sagt ihm erstmal, okay, wir gehen jetzt ins Gefängnis.
Dann sagen sie, nee, ich gehe nicht mit.
Dann nimmt der Polizist sie und schleift sie ins Gefängnis.
Und wenn sie sich dann dagegen wehren, dann müssen sie sich mit Gewalt
dagegen wehren und dann wird halt der Staat auch Gewalt anwenden, um
das Gesetz durchzusetzen.
Und irgendwann eskaliert die Gewalt.
Die Gewalt wird immer entsprechend, es muss immer verhältnismäßig sein
zu der Gewalt, die sie entgegengesetzen, um sich dem Gesetz zu
entziehen.
Nur irgendwann, der Staat lässt mich locker.
Irgendwann nimmt er sie und im schlimmsten Fall, wenn sie halt dann
versuchen, ach sei es wie übrig bleibt, sozusagen den Polizisten zu
erschießen, der sie ins Gefängnis nimmt, dann wird der sie erschießen.
Das heißt, ganz am Ende, wenn man so ein Gesetz sieht, heißt das
immer, der Staat hält ihm letztendlich in letzter Konsequenz die
Pistole an den Kopf und sagt, Daten her oder.
Bei der Industrie ist das nicht.
Die Industrie hält ihm nicht die Knarre an den Kopf.
Die Industrie sagt, dürfte ich bitte die Daten haben, wir schließen
den Vertrag, du gibst mir meine Daten und ich gebe dir das dafür.
Und dann können sie sagen, ja mache ich oder mache ich nicht.
Und heutzutage sagt man immer, ja, ja mache ich, klick, klick, klick.
Allgemeine, ja passt schon.
Allgemeine geschäftsführende Datenschutz-Erklärung, ja, ja ist schon
in Ordnung, machbar.
Und der Gesetzgeber sagt, ja, selber Schuld.
Es gibt in Deutschland sowas wie Vertragsfreiheit.
Wenn sie das unbedingt wollen, dann darf man das erstmal.
Und dann hat man halt festgestellt, dass die Leute halt zu viel klick,
klick, klick machen.
Und dann fängt man halt an, okay, es muss halt, darf nicht wieder die
guten Sitten sein und so weiter und so fort.
Und dann kommt man in sehr schwammige Bereiche, wo man halt
regulatorisch versucht, tätig zu werden.
Und dann gibt es halt sowas zumindest wie jetzt ganz neu, das jetzt im
Mai wirklich in Kraft treten wird, die neueste europarechtliche
Datenschutzverordnung, die halt versucht da in dieses Potenziell, man
darf machen, was man will und am Ende weiß man gar nicht, was man sich
selber für einen Schaden zuzufügen, versucht da regulatorisch
einzugreifen.
Aber das meiste liegt immer noch an ihrer Hand, wenn sie sagen, klick,
ja, mach mit meinen Daten, was du willst.
Kann ja nicht so schlimm sein, ich habe ja nichts zu verbergen.
Und das ist gefährlich, weil da kann man wirklich extrem viel
mitmachen und auch extrem viel, was gegebenenfalls zu ihrem Schaden
sein kann.
Deswegen wägen sie da immer gut ab, ob sie ihre Daten rausgeben oder
nicht, ob ihnen die Sache das wirklich wert ist.
Und sie sind Informatiker.
Wenn einer das durchdenken kann bis zum Ende, dann sollten sie das
sagen.
Damit frohe Festtage, frohe für die, die feiern, frohe Weihnachten.
Kommen Sie gut ins neue Jahr.
Wir sehen uns dann mit der Probeklausur im Januar, am 10.
Januar wieder.
Bis dann.