Einführung in die Kryptographie

In diesem Exposé geht es um eine kleine Einführung in die Grundlagen der praxisnahen Kryptographie. Hierzu werden keine Verschlüsselungsalgorithmen beschrieben oder mathematisch aufbereitet. Dazu gibt es schon hunderte und tausende Papers/Artikel/Skripte im Internet zum Durchlesen. Es gibt höchstens mal Verweise auf andere Verfahren. Vielmehr soll ein Gefühl entwickelt werden, sich mit den Hintergründen von Verschlüsselungen auseinanderzusetzen und verschiedene Algorithmen zu bewerten.

Dazu schauen wir uns drei fiktive Kommunikationswege mit verschiedenen einfachen Verschlüsselungsverfahren an. Alle drei Verschlüsselungsverfahren in diesen Beispielen funktionieren nach dem Prinzip des mehrfachen Schlosssystems. Was damit gemeint ist, wird am Beispiel besser erkennbar.

Angenommen wir haben einen Sender und einen Empfänger, die miteinander kommunizieren wollen. Diese Mehrfachschlossverfahren funktionieren nach dem Three-Way-Handshake-Prinzip. Im Prinzip legt der Sender eine Nachricht in einen Tresor und hängt ein Vorhängeschloss davor. Dann schickt er diesen Tresor an den Empfänger. Dieser hängt ein weiteres Schloss an den Tresor und schickt ihn zurück an den Sender. Dieser entfernt dann sein eigenes Schloss wieder vom Tresor und schickt es zurück an den Empfänger, welcher dann ebenfalls sein eigenes Schloss entfernt und die Nachricht herausnehmen kann. Während der Übertragungen ist zu jeder Zeit sichergestellt, dass der Tresor verschlossen ist.

Verfahren-Nummer 1:

Bei diesem Verfahren verschlüsselt der Sender seine Nachricht m durch Multiplikation seines geheimen Schlüssels k1, den außer ihm niemand kennt. Dann schickt dieser verschlüsselte Nachricht d1 an den Empfänger. Der Empfänger versucht gar nicht erst das Empfängnis zu lesen und multipliziert d1 mit seinem eigenen privaten Schlüssel k2. Das Ergebnis d2 schickt der Empfänger wieder an den Sender zurück. Dieser nimmt die Nachricht d2 und multipliziert mit dem Kehrwert seines Schlüssels k1. Danach schickt der Sender das Ergebnis d3 an den Empfänger zurück. Dieser muss nun nur noch d3 mit dem Kehrwert seines eigenen Schlüssels k2 multiplizieren und erhält somit die Nachricht.

Bei all diesen Größen (m,k1,k2) handelt es sich um natürliche Zahlen. Also muss man seine Textnachricht entsprechend kodieren (z.B. A=0, B=1, C=2, …), damit dieses Protokoll/Verfahren funktioniert. Eine weitere Voraussetzung ist, dass beide Kommunikationspartner das Protkoll kennen (logisch, sonst funktioniert es nicht). Aber für dieses Verfahren müssen keine Schlüssel/Passwörter vorher ausgetauscht werden. Es kann einfach drauflos gesendet werden. Klingt doch erst einmal toll. Doch, wo ist der Haken?

Ich nehme an, bei diesem Verfahren ist für jeden Leser mit ein zwei Proben leicht zu erkennen, dass dieses Verfahren äußerst unsicher ist. Stellen wir uns einmal eine weitere Person vor, die alle drei Nachrichten d1,d2,d3 abfängt, aber weder k1,k2 noch m kennt. Diese Person hat also eine passive Attacke durchgeführt (Lauschangriff). Kann sie mithilfe dieser drei abgefangenen Daten auf die Nachricht m schließen?

Empfehlung: Wer etwas rätseln möchte, sollte hier kurz aufhören weiterzulesen. Sonst erfolgt als nächstes die Auflösung.

Thinking Level 20%

Auflösung zu 1

In diesem Fall hat die lauschende Person Glück. Aus der Kombination der drei Daten d_{1},d_{2},d_{3} lassen sich die Nachricht und sogar die Schlüssel $k_{1}$ und $k_{2}$ errechnen. Denn es gilt $k_{1} = \frac{d_{2}}{d_{3}}$ und $k_{2} = \frac{d_{2}}{d_{1}}$ und damit $m = \frac{d_{1}*d_{3}}{d_{2}}$ .

Dieses Verfahren ist somit leider absolut ungeeignet für eine sichere Kommunikation zwischen zwei Partnern.

Verfahren-Nummer 2:

Dieses Verfahren funktioniert sehr ähnlich zu dem ersten Verfahren mit dem Unterschied, dass jede übertragene Zahl nun noch mit einem Modulo-Operator reduziert wird. Für alle, die nicht mehr ganz mit dem Modulo Operator vertraut sind folgt eine kurze Wiederholung. Für alle anderen gilt es, diesen Abschnitt zu überspringen.

Thinking Level 60%

Exkurs Modulo

Der Modul ist ganz einfach ausgedrückt ein Operator, der den Rest einer Division von zwei Zahlen ausgibt.

Beispiel: $10 : 3 = 3 \:Rest \:1$ .

Also ist $10 \% 3 = 1 \iff 10 \:mod \:3 = 1$ (% ist der Modulo-Operator in der Informaik).

Damit ist am Moduloperator so besonders, da er im Gegensatz zu herkömmlichen Operationen wie Addition und Multiplikation mehrere Lösungen für eine Gleichung liefern kann.

Beispiel:

$10+3=13$ . Das gilt immer und die erste Zahl kann nicht anders als $10$ sein, sodass die Gleichung immer noch gelten würde.

$10 \% 3 = 1$ , aber auch $1 \% 3 = 1$ oder $4 \% 3 = 1$ . Es gibt also mehrere Zahlen für die, diese Gleichung gilt (alle diese Zahlen, für die diese Gleichung gilt vereinigt man in einer Menge $\mathbb{Z}_{3}$ , aber das nur als Zusatzinfo).

Für den Moduloperator gelten genauso Rechengesetze wir für Additionen, Subtraktion etc. Genaueres kann in der entsprechenden Literatur darüber gelesen werden. Wichtig ist nur, dass die Notation dazu verständlich ist.

Die erste Schreibweise ist: $10 \:mod \:3 = 1$ , wobei „mod“ als Operator fungiert. Eine alternative Schreibweise ist: $10 \equiv 1 \:(mod \:3)$ . Gelesen wird das ganze: Eins kongruent zehn bezüglich des Moduls drei. Dabei ist die Kongruenz kein Operator, sondern eine Relation bezüglich des Moduls, welches gekennzeichnet wird durch einen geklammerten Ausdruck am Ende der Zeile.

Für die Addition existiert unter den natürlichen Zahlen das neutrale Element 0. Das bedeutet, egal welche Zahl mit dem neutralen Element addiert wird, es kommt wieder genau diese Zahl wieder heraus. Für Multiplikation existiert auch ein neutralen Element, nämlich die 1. Zudem gibt es bei der Addition zu jeder natürlichen Zahl eine Inverszahl aus der Menge der ganzen Zahlen, sodass ihre Addition das neutrale Element 0 ergibt. Genauso gibt es bezüglich der Multiplikation für jede natürliche Zahl eine Inverszahl aus den rationalen Zahlen, sodass ihre Multiplikation das neutrale Element 1 ergibt.

Beispiele:

$3 - 3 = 0$ . Demnach ist $-3$ die Inverszahl zu $3$ bezüglich des Additionsoperators.

$3 * \frac{1}{3} = 1$ . Demnach ist $\frac{1}{3}$ die Inverszahl zu $3$ bezüglich des Multiplikationsoperators.

Beim Modul-Operator gibt es zu jeder natürlichen Zahl eine Inverszahl bezüglich Addition zu einem beliebigen Modul m. Es gibt jedoch nicht immer eine Inverszahl bezüglich Multiplikation zu einem beliebigen Modul m.

Beispiele:

Finde die Inverszahl $x$ zum Ausdruck $1+x \equiv 0 \:(mod\:7)$ . $x = 6$ , da die Addition aus den beiden Zahlen das neutrale Element 0 bezüglich des Moduls 7 ergeben muss. Ein weiteres Beispiel ist $5+x \equiv 0 \:(mod\:21)$ . Hierfür ist $x=17$ mit der gleichen Begründung.

Für die Multiplikation im Bezug auf eine Modulkongruenz gibt es leider nicht für jede Zahl eine Inverszahl. Es existiert für die Multiplikation nur unter bestimmten Voraussetzungen eine Inverszahl $p^{-1}$ mit $p^{-1}*p \equiv 1 \:(mod \:n)$ .

Die Voraussetzung ist, dass die Zahl $p$ zu der Zahl $n$ teilerfremd sein muss, sodass es keinen größten gemeinsamen Teiler geben kann ( $ggT(p,n) = 1$ ). Wenn das der Fall ist, dann existiert auch ein Multiplikatives Inverses $p^{-1}$ .

Beispiel:

$3 * x \equiv 1 \:(mod \:5)$ . Der größte gemeinsame Teiler für $3$ und $5$ ist $1$ ( $ggT(3,5) = 1$ ), da es keinen Divisor über 1 gibt, sodass $3$ und $5$ geteilt würden und eine natürliche Zahl dabei herauskäme. Also lässt sich ein multiplikatives Inverses für $3$ berechnen (zur Info: $x = 2$ ).

Aber bei $10 * x \equiv 1 \:(mod \:5)$ , kann es kein x geben, sodass diese Kongruenz gültig wird, da gilt: $ggT(5,10)=5>1$ . Sollte der Modul eine Primzahl sein, so gibt es immer für jede Zahl ein multiplikatives Inverses. Sie dürfen darüber nachgrübeln, wieso 😀

Das additive und multiplikative Inverse kann dazu verwendet werden bei Gleichungen einzelne Summanden oder Faktoren auf die andere Seite zu bringen. Rechnet man beispielsweise bei den „normalen“ Gleichungen $3+x = 5$ , benutzt man das additive Inverse von $x$ , nämlich $-x$ um das $x$ auf die andere Seite zu bekommen, also: $3=5-x$ . Analog dazu bei Faktoren und der Multiplikation: $3*x=5 \Rightarrow x=5*\frac{1}{3}$ . Die Inversen werden allgemein mit dem Exponenten $n^{-1}$ , also $-1$ gekennzeichnet, das bedeutet also hierbei nicht, dass die Zahl hoch $-1$ gerechnet werden soll. Diesen Sachverhalt also nicht verwechseln.

$3+x=5 \Rightarrow 3=5+x^{-1}$ und $3*x=5 \Rightarrow 3=5*x^{-1}$ .

Das Berechnen des additiven Inversen beim Modul-Operator

Das Berechnen des additiven Inversen ist einfach, da man sich nur eine Zahl überlegen muss, die addiert mit der ersten Zahl kongruent 0 ist bezüglich des Moduls m.

Beispiel:

$3+x \equiv 0 \:(mod \:21)$ . Dann gilt: $x = -3$ . Aber da man bei der Modulorechnung lieber mit positiven ganzen Zahlen rechnet, nimmt man einfach den Modul und subtrahiert diesen mit der ersten Zahl und erhält automatisch das positive additve Inverse: $x=21-3=18$ .

Das Berechnen des multiplikativen Inversen beim Modul-Operator

Das Berechnen des multiplikativen Inversen zu einer Zahl und einem bestimmten Modul, sofern es denn existiert, lässt sich mit dem erweiterten euklidschen Algorithmus in effektiver Zeit berechnen. Dazu gibt es genug Quellen im Internet oder Literatur.

Auflösung zu 2

Auch in diesem Fall hat die lauschende Person Glück. Aus der Kombination der drei Daten $d_{1}, d_{2}, d_{3}$ lassen sich wieder die Nachricht und sogar die Schlüssel $k_{1}$ und $k_{2}$ errechnen. Denn es gilt:

$k_{1} = d_{1} * m^{-1} \:mod \:B$

$k_{2} = d_{3} * m^{-1} \:mod \:B$

Hier wurden einfach das $m$ auf die andere Seite gebracht mithilfe des multiplikativen Inversen vom $m$ . Danach noch $k_{1}$ und $k_{2}$ in $d_{3}$ einsetzen und nach $m$ umstellen.

$d_{2} = d_{1} * m^{-1} * d_{3} * m^{-1} * m \:mod \:B$

$d_{2} = d_{1} * m^{-1} * d_{3} * \cancel{m^{-1} * m} \:mod \:B$

$m = d_{1} * d_{3} * d_{2}^{-1} \:mod \:B$

Dieses Verfahren ist somit leider auch absolut ungeeignet für eine sichere Kommunikation zwischen zwei Partnern. Und sollte es kein multiplikatives Inverses für den Modul $B$ geben, so kann die Nachricht nicht entschlüsselt werden, aber dann kann auch der Empfänger die Nachricht nicht entschlüsseln.

Verfahren-Nummer 3:

Dieses Verfahren funktioniert sehr ähnlich zu dem zweiten Verfahren mit dem Unterschied, dass die übertragenen Nachrichten jetzt nicht nur mit den Schlüssel multipliziert sondern potentiert werden. Da man bei der Grafik mit der Interpretationsfähigkeit der mathematischen Zeichen an die Grenzen kommt, werden hier nochmals alle drei Werte sauber aufgeschrieben.

$d_{1} = m^{k_{1}} \:mod \:B$

$d_{2} = (m^{k_{1}})^{k_{2}} \:mod \:B$

$d_{3} = ((m^{k_{1}})^{k_{2}})^{k_{1}^{-1}} \:mod \:B = m^{k_{2}} \:mod \:B$

Zudem nehmen wir jetzt einmal an, dass dem Angreifer sogar die Schlüssel $k_{1}$ und $k_{2}$ bekannt sind. Kann er mit diesen Informationen an die Nachricht $m$ gelangen? Und wenn ja, ist es dabei egal, wie groß der Modul $B$ wird?

Thinking Level 90%

Auflösung zu 3

In diesem Fall hat die lauschende Person leider Pech gehabt, wenn der Modul groß wird. Selbst mit den bekannten Schlüsseln wird es uns nicht gelingen die Nachricht in effektiver Zeit zu berechnen. Aber warum ist das so?

Dadurch, dass $k_{1}$ und $k_{2}$ bekannt sind, kann man immerhin folgende Gleichung betrachten:

$d_{1} \equiv m^{k_{1}} \:(mod \:B)$

Also errinern wir uns an einen Satz beim RSA-Verfahren. Das bedeutet, dass wir das Problem der unbekannten Basis $m$ auf das Problem des multiplikativen Inversen aus dem zweiten Verfahren umwandeln können, wenn wir das Ergebnis der Phi-Funktion des Moduls $B$ in effektiver Zeit berechnen können.

$d*e \equiv 1 \:(mod \:\varphi{(B)})$

Diese Idee können wir adaptieren auf unsere Kongruenz mit d_{1}.

$k_{1}^{-1} * k_{1} \equiv 1 \:(mod \:\varphi{(B)})$

Demnach muss für k_{1} nur das multiplikative Inverse zum Modul $\varphi (B)$ berechnet werden. Wenn $B$ keine Primzahl ist, ist das Berechnen von $\varphi (B)$ nicht einfach. Generell ist bisher kein effizientes Faktorisierungsverfahren bekannt. Daher wird dieser Angriff für große, zusammengesetzte Zahlen tatsächlich auch bei bekannten Schlüsseln $k_{1}$ und $k_{2}$ schwierig bis laufzeittechnisch unpraktikabel (auch für Primzahlen, da auch nur ein bekannter Algorithmus existiert, der in effektiver Zeit prüft, ob eine natürliche Zahl eine Primzahl ist oder nicht, aber mit einer polynomialen Komplexität und einer sehr großen Konstante). Bei kleinen Zahlen ist aber eine Berechnung kein Problem, das hängt dann von der Rechenleistung der Maschine ab. Ist der Modul eine Primzahl, ist das ganze einfach, da für Primzahlen gilt: $\varphi (p) = p-1$ .

Dieses Verfahren ist also bei richtiger Wahl des Moduls durchaus sicher und das gilt auch noch, solange kein effektiver Faktorisierungsalgorithmus existiert, der auch auf die Phi-Funktion übertragbar ist.

Einführung in die Kryptographie

Einführung in die Kryptographie