Kryptographische Verfahren Zusammenfassung

Mathematische Grundlagen

Teilbarkeit

Eine ganze Zahl \(a\) teilt eine ganze Zahl \(b\) genau dann, wenn eine ganze Zahl \(n\) mit \(a \cdot n = b\) existiert. Man schreibt \(a|b\) und sagt \(a\) teilt \(b\). Wenn \(a\) \(b\) nicht teilt, schreibt man \(a \nmid b\).

Modulo und Rest

Wenn \(a \nmid b\) gilt, bleibt bei der Divison ein Rest. An diesem ist man beim Modulo-Rechnen interessiert:

\(\mod : \mathbb{Z} \times (\mathbb{Z}\setminus\lbrace 0 \rbrace) \rightarrow \mathbb{Z}, (a,m) \mapsto a \mod m := a - \lfloor \dfrac{a}{m} \rfloor \cdot m \)

Größter gemeinsamer Teiler Euklidischer Algorithmus, \(ggT(a,b)\)

Der \(ggT(a,b)\) von zwei ganzen Zahlen \(a,b \in \mathbb{Z} \) ist die größte natürliche Zahl, die sowohl \(a\) als auch \(b\) teilt.

Eingabe: \(a,b \geq 0\), da \(ggT(a,b) = ggT(-a,b) = ggT(b,a)\).

  1. Wenn \(a = 0\) ist, gebe \(b\) aus.
  2. Andernfalls gebe \(ggT(b \mod a, a)\) aus.

Lemma von Bézout Erweiterter euklidischer Algorithmus, \(eggT(a,b)\)

Für zwei ganze Zahlen \(k,l \in \mathbb{Z}\) existieren immer zwei ganze Zahlen \(a,b \in \mathbb{Z}\) mit \(ggT(k,l) = a\cdot k + b\cdot l\).

Eingabe: \(a,b \geq 0\)

Ausgabe: \((p,q,s)\) mit \(a\cdot p + b \cdot q = s = ggT(a,b)\).

  1. Wenn \(a = 0\) ist, gebe \((0,1,b)\) aus.
  2. Andernfalls berechne \((p,q,s) := eggT(b \mod a, a)\) und gebe dann \((q-p \cdot \lfloor \frac{a}{b} \rfloor,p,s)\) aus.

Chinesischer Restsatz

(Nach Sun Zi): Seien \(m_1,\ldots,m_n \in \mathbb{Z}\) paarweise teilerfremd und sei \(m = m_1 \cdot m_2 \cdot \cdots \cdot m_n \). Für alle \(x_1,\ldots,x_n \in \mathbb{Z}\) existiert genau ein \( x \in \lbrace 1,\ldots,m-1 \rbrace \) das simultan folgende Kongruenzen erfüllt:

\begin{eqnarray} x & \equiv & x_1 \mod{m_1} \\ & \vdots & \\ x & \equiv & x_n \mod{m_n} \end{eqnarray}

Die Lösungsmenge ist \( x + m\mathbb{Z} \). Die Lösung kann mit dem erweiterten euklidischen Algorithmus gefunden werden:
Schreibe \(\forall i: 1 = a_i \cdot m_i + b_i \cdot m/m_i\) und verwende die gefundenen \(b_i\) in \(x = \sum_{i=1}^n x_i \cdot b_i \cdot m_i\).

Falls \(m_1,\ldots,m_n \in \mathbb{Z}\) nicht paarweise teilerfremd sind, existiert eine Lösung, wenn \(\forall i \not= j : x_i \equiv x_j \mod ggT(m_i,m_j)\) gilt.

Primzahl

Eine natürliche Zahl \(p \in \mathbb{N} \) ist genau dann eine Primzahl, wenn \(p\) genau zwei verschiedene Teiler \(1|p\) und \(p|p\) hat. Insbesondere ist 1 keine Primzahl.

Fundamentalsatz der Arithmetik

Jede natürliche Zahl \(n\) hat eine eindeutige Primfaktorzerlegung/Darstellung mit Primfaktoren durch \(n = \prod_{p \in \mathbb{P}} p^{n_p} \text{ mit } n_p \not= 0 \Leftrightarrow p|n\). Beispielsweise ist \(75600 = 16 \cdot 27 \cdot 25 \cdot 7 = 2^4 \cdot 3^3 \cdot 5^2 \cdot 7\).

Kleiner fermatscher Satz

Sei \(a\) eine ganze Zahl und \(p\) prim, dann gilt \(a^p \equiv a \mod p\). Falls \(a\) kein Vielfaches von \(p\) ist, dann gilt \(a^{p-1} \equiv 1 \mod p\).

Primitivwurzel

Eine ganze Zahl \(a\) ist eine Primitivwurzel modulo \(m\), wenn die Restklasse \(a + m\mathbb{Z}\) die prime Restklassengruppe \((\mathbb{Z}/m\mathbb{Z})^*\) erzeugt. Das bedeuted, dass sich alle Elemente der primen Restklassengruppe \((\mathbb{Z}/m\mathbb{Z})^*\) als Potenzen von \(a\) darstellen lassen.

Schnelle modulare Exponentation

Ziel ist es die Zahl \(a^n\) mit \(M\) Monoid, \(a \in M\) und \(n \in \mathbb{N}\) zu berechnen.

Das Vorgehen ist, möglichst oft zu quadrieren. Im Fall von \(M = \mathbb{Z}/n\mathbb{Z}\) wird jede Multipliakation \(\mod n\) gerechnet, was die Zahlen durch \(n\) beschränkt lässt.

Geburtstagsparadoxon

Bei einer Zufallsfolge von Elementen aus einer \(n\)-elementigen Menge ist die Wahrscheinlichkeit zwei gleiche Elemente darin zu haben bereits nach \(m=\sqrt{2n \ln 2} \in O(\sqrt{n})\) groß (\(\geq 1/2)\).

Kryptanalyse

Kompromittierungsvarianten

Menge von Vorwissen

Ausgehend davon, dass ein Angreifer mindestens das verwendete Kryptosystem kennt (Kerckhoffs Prinzip), kann das weitere Vorwissen wie folgt klassifiziert werden:

Sicherheitsstufen

Ausgehend von der ausschließlichen Kenntnis des Geheimtextes (COA), kann man Verschlüsselungsverfahren wie folgt charkatisieren:

Verschlüsselungsverfahren

Verschlüsselungsverfahren können in zwei Kategorieren aufgeteilt werden. In Symmetrische Verfahren, bei denen für die Ver- und Entschlüsselung der gleiche Schlüssel verwendet wird und in asymmetrische Verfahren bei denen für die Verschlüsselung ein anderer Schlüssel als für die Entschlüsselung verwendet wird.

Symmetrische Verfahren

Blockchiffren

Größe des Schlüsselraums

  • Personal use
  • Unlimited projects
  • 24/7 support

DES

S-Boxen machen es nicht-linear

  • Personal use
  • Unlimited projects
  • 24/7 support

Vernam-One-Time-Pad

Perfekte Sicherheit

  • Personal use
  • Unlimited projects
  • 24/7 support

Asymmetrische Verfahren

RSA-Kryptosystem

Pragmatische Sicherheit

  • Basiert auf dem Faktorisierungsproblem, könnte aber vielleicht auch anders gebrochen werden.
  • Unlimited projects
  • 24/7 support

Rabin-Kryptosystem

Relative Berechnungssicherheit

  • Ist nachweislich so schwer wie das Faktorisierungsproblem.
  • Entschlüsselung nicht eindeutig.
  • Verschlüsseln durch Quadrieren im Restklassenring modulo \(n\)

ElGamal-Verschlüsselung

Relative Berechnungssicherheit

  • Mindestens so schwer wie Decisional-Diffie-Hellman-Problem und Diskreter-Logarithmus.
  • Verwandt mit Diffie-Hellman-Schlüsselaustausch
  • 24/7 support

McEliece-Kryptosystem

Relative Berechnungssicherheit

  • Basiert auf der Schwierigkeit einen linearen Code zu dekodieren.
  • Unlimited projects
  • 24/7 support

RSA-Kryptosystem

Das RSA-Kryptosystem basiert auf dem Problem große Zahlen schwer in ihre Primfaktoren zerlegen zu können (Faktorisierungsproblem).

In der Praxis werden verschiedene Modifikationen an dem vorgestellten Ablauf vorgenommen:

  • Hinzufügen von einer Anzahl Zufallsbits (Padding) an jede Nachricht, damit häufig auftretende oder vorher in einer Liste gespeicherte Paare von (Nachricht, Verschlüsselte Nachricht) nicht vorberechnet und nachgeschlagen werden können.
Ablauf
  1. (geheim) Alice wählt zwei verschiedenen große Primzahlen \(p,q\) so aus, dass \(n = p \cdot q\) nicht leicht faktorisiert werden kann.
  2. (geheim) Sie berechnet die eulersche Phi-Funktion \(\varphi(n) = (p-1)(q-1)\).
  3. (geheim) Sie wählt eine zu \(\varphi(n)\) teilerfremde Zahl \(e\) mit \(1 < e < \varphi(n)\).
  4. Sie veröffentlicht \((n,e)\) als ihren öffentlichen Schlüssel.
  5. (geheim) Sie berechnet das Inverse Element \(s\) mit \(e \cdot s \equiv 1 \mod \varphi(n)\). Diese kann sie mit dem erweiterten euklidischen Algorithmus leicht finden.
  6. (geheim) Bob kann damit eine Nachricht \(m\) mit \(y = m^e \mod n\) verschlüsseln.
  7. (geheim) Alice entschlüsselt Nachrichten mit \( m = y^s \mod n\).
Beispiel
  1. Wir wählen als Primzahlen \(p = 11, q = 13\)
  2. Weiterhin wählen wir ein \(e\) mit \(ggT(e,120) \wedge 1 < e < 120\). \(e = 23\)
  3. Dann berechnen wir mit Hilfe des erweiterten euklidischen Algorithmus \(s\) mit \(23 \cdot s \equiv 1 \mod 120\): \[ 23 \cdot s + 120 \cdot k = 1 = ggT(23,120) \Rightarrow s = 47 \]
  4. Bob möchte uns die Nachricht \(m = 7\) verschlüsselt schicken. Er führt also \(y \equiv 2 \equiv 7^{23} \mod 143\) aus.
  5. Um die empfangene Nachricht wieder zu entschlüsseln führen wir \(m \equiv 2^{47} \equiv 7 \mod 143\) aus.
Korrektheit

Für eine verschlüsselte Nachricht \(y = m^e \mod n\) gilt beim Entschlüsseln: \[ y^s \equiv (m^e)^s \equiv m^{es} \equiv m \cdot (m^{p-1})^k \equiv m \mod p, ~ es = 1 + (p-1)k \] \[ y^s \equiv (m^e)^s \equiv m^{es} \equiv m \cdot (m^{q-1})^k \equiv m \mod q, ~ es = 1 + (q-1)k \] Mit dem chinesischen Restsatz folgt daraus \(y^s \mod n = m\).

Sicherheit

Rabin-Kryptosystem

Das Rabin-Kryptosystem basiert ähnlich wie das RSA-Kryptosystem auf dem Faktorisierungsproblem. Es ist aber nachweislich genau so schwer wie das Faktorisierungsproblem, sprich würde eine andere Möglichkeit gefunden werden es zu brechen, würde damit auch der geheime Schlüssel faktorisiert.

Was es für die Praxis ungeeignet macht ist die Tatsache, dass die Entschlüsselung nicht eindeutig ist sondern 4 mögliche Lösungen anbietet. Dies kann man zwar durch Markieren der Nachricht beseitigen, aber dann ist es auch nicht mehr genauso schwer wie das Faktorisierungsproblem.

Ablauf
  1. Alice wählt zwei zufällige verschiedene große Primzahlen \(p\) und \(q\) mit \(p \equiv q \equiv 3 \equiv -1 \mod 4\)
  2. Daraus berechnet sie ihren öffentlichen Schlüssel \(n = p \cdot q\) und gibt ihn Bob
  3. Bob verschlüsselt seine Nachricht \(m \in \mathbb{Z}/n\mathbb{Z}\) durch Quadrieren mit \(y = m^2 \mod n\)
  4. Alice entschlüsselt mit ihrem privaten Schlüssel \((p,q)\) wie folgt:
    \[ z_p = y^{\frac{p+1}{4}} \mod p \text{ und } z_q = y^{\frac{q+1}{4}} \mod q \] Hieraus ergeben sich mit dem chinesischen Restsatz bis zu vier verschiedene Werte für \(z \in \mathbb{Z}/n\mathbb{Z}\) mit \(z \equiv \pm z_p \mod p\) und \(z_q \equiv \pm z_q \mod q\). Einer dieser Werte ist die ursprüngliche Nachricht \(m\) von Bob.
Beispiel
  1. Wir wählen \(p = 3\) und \(q=7\). Das erfüllt auch die Kongruenzbedingung \(3 \equiv 7 \equiv 3 \mod 4\).
  2. Als unseren öffentlichen Schlüssel berechnen wir \(n = 3 \cdot 7 = 21\).
  3. Angenommen wir wollen die Nachricht \(m = 4\) an uns verschicken. Diese verschlüsseln wir zu \(y = m^2 = 4^2 = 16 \equiv 16 \mod 21\).
  4. Zum entschlüsseln berechnen wir \(z_p = 16^{\frac{3+1}{4}} \equiv 1 \mod 3\) und \(z_q = 16^{\frac{7+1}{4}} \equiv 2^2 \equiv 4 \mod 7\). Daraus folgt, dass die Nachricht eines der \(z \in \lbrace 4, -4, 1, -1 \rbrace\) sein muss. Dies ist auch der Fall.
Korrektheit

Das Verfahren ist korrekt, wenn einer der 4 Werte tatsächlich immer dem ursprünglichen Klartext entspricht.

Zunächst beobachten wir, dass aus \(m^2 \equiv y \mod n \Rightarrow m^2 \equiv y \mod p \wedge m^2 \equiv y \mod q\) folgt. Des Weiteren sind \(p,q\) Primzahlen. Das bedeuted die beiden Kongruenzen haben jeweils nur höchstens zwei Lösungen \(\pm m_p \in \mathbb{Z}/p\mathbb{Z} \wedge \pm m_q \in \mathbb{Z}/q\mathbb{Z}\). Damit folgt für \(m \equiv \pm m_p \mod p \wedge m \equiv \pm m_q \mod q\).

Mit diesem Wissen reicht es, aus Symmetriegründen, \({z_p}^2 \equiv y \mod p\) zu zeigen. Die beiden Lösungen der Kongruenz sind dann die ersten beiden Lösungen für unsere Nachricht.

Falls \(y \equiv 0 \mod p\) gilt, ist nichts zu zeigen. Sei deshalb \(y \in (\mathbb{Z}/p\mathbb{Z})^*\): \[ {z_p}^2 \equiv (y^{\frac{p+1}{4}})^2 \equiv y^{\frac{p+1}{2}} \equiv y \cdot y^{\frac{p-1}{2}} \equiv_{\text{EK}} y \mod p \]

Sicherheit
Es kann gezeigt werden (TODO), dass mit dem Brechen des Rabin-Kryptosystems automatisch auch der geheime Schlüssel in seine Primfaktoren zerlegt werden würde. Falls es also effizient möglich ist, das Rabin-Kryptosystem zu brechen, ist es auch effizient möglich zu Faktorisieren.

ElGamal-Verschlüsselung

Die ElGamal-Verschlüsselung läuft ähnlich wie das Diffie-Hellman-Schlüsselaustauschverfahren ab. Im folgenden wird als zyklische Gruppe \((\mathbb{Z}/p\mathbb{Z})^* = \mathbb{F}_p^*\) verwendet. Es könnte genauso gut die Menge der \(q\)-rationalen Punkte einer elliptischen Kurve über \(\mathbb{F}_p\) gewählt werden.

ElGamal-Verschlüsselung Ablauf
  1. (öffentlich) Alice wählt eine endliche zyklische Gruppe \(\mathbb{F}_p^*\) und eine Primitivwurzel \(g \mod p \) mit \(g \in \left[ 2,p-2\right]\).
  2. Sie wählt zufällig eine Zahl \(a_{\text{Alice}} \in \lbrace 2, \dots, p-2 \rbrace\).
  3. Sie berechnet ein \(K_{\text{Alice}} = g^{a_{\text{Alice}}} \mod p\) und veröffentlicht \((p,g,K_{\text{Alice}})\).
  4. Bob wählt zufällig eine Zahl \(a_{\text{Bob}} \in \lbrace 2, \dots, p-2 \rbrace\) und berechnet \(K_{\text{Bob}} = g^{a_{\text{Bob}}} \mod p\).
  5. Bob verschlüsselt seine Nachricht \(m\) mit \(y = K_{\text{Alice}}^{a_{\text{Bob}}} \cdot m \mod p\) und sendet öffentlich \((K_{\text{Bob}},y)\) an Alice.
  6. Alice kann die Empfangene Nachricht nun mit \(m = K_{\text{Bob}}^{-a_{\text{Alice}}} \cdot y \mod p\) entschlüsseln.
Korrektheit

Zu zeigen ist \(m = K_{\text{Bob}}^{-a_{\text{Alice}}} \cdot y \mod p\):

\[ K_{\text{Bob}}^{-a_{\text{Alice}}} \cdot y \equiv K_{\text{Bob}}^{-a_{\text{Alice}}} \cdot K_{\text{Alice}}^{a_{\text{Bob}}} \cdot m \equiv \] \[ g^{-a_{\text{Alice}} \cdot a_{\text{Bob}}} \cdot g^{a_{\text{Alice}} \cdot a_{\text{Bob}}} \cdot m \equiv m \mod p \]

Die Nachricht wird also wieder korrekt entschlüsselt.

McEliece-Kryptosystem

Diffie-Hellman Schlüsselaustauschverfahren

Um über einen unsicheren Kanal beispielsweise den Schlüssel für ein symmetrisches Verschlüsselungsverfahren auszutauschen, kann der Diffie-Hellman Schlüsselaustausch benutzt werden.

Dazu befolgen Alice und Bob folgende Schritte:

  1. (öffentlich) Sie einigen sich auf eine Primzahl \(p\) sowie eine Primitivwurzel \(g \mod p \) mit \(g \in \left[ 2,p-2\right]\)
  2. (geheim) Sie erzeugen jeweils eine Zufallszahl \(a_{\text{Alice}}\) und \(a_{\text{Bob}}\) aus \(\lbrace 1, \ldots, p-2 \rbrace\)
  3. (geheim) Nun berechnen Alice \(K_{\text{Alice}} = g^{a_{\text{Alice}}} \mod p\) und Bob \(K_{\text{Bob}} = g^{a_{\text{Bob}}} \mod p\)
  4. und senden es (öffentlich) an den jeweils anderen
  5. Jetzt können Alice und Bob den gemeinsamen Schlüssel jeweils mit \(K = K_{\text{Bob}}^{a_{\text{Alice}}} \mod p\) und \(K = K_{\text{Alice}}^{a_{\text{Bob}}} \mod p\) berechnen
Jemand der den Kanal belauscht bekommt zwar \(p,g,K_{\text{Alice}},K_{\text{Bob}}\) mit, aber diese Daten reichen nicht aus um den geheimen Schlüssel \(K\) zu berechnen. Das zugrunde liegende Problem ist, den diskreten Logarithmus \( a_{\text{Alice}}\) von \(K_{\text{Alice}} \equiv g^{a_{\text{Alice}}} \mod p\) oder \( a_{\text{Bob}}\) von \(K_{\text{Bob}} \equiv g^{a_{\text{Bob}}} \mod p\) zu berechnen. Dies gilt als schwierig. Um einen Man-in-the-middle-Angriff auszuschließen können Digitale Signaturen verwendet werden.

Mathematische Brechungs-/Berechnungsverfahren

Faktorisieren

Das Faktorisierungsproblem besteht darin, zu einer gegebenen Zahl \(n\) einen Teiler \(m|n\) mit \(1\lt m \lt n\) zu finden.

Pollards (p-1)-Methode zur Faktorisierung
  1. Wähle eine Basis(-Menge) \(B\) von Primzahlen bis zu einer gewissen Größe.
  2. Setze \(k = \prod_{q \in B} q^{\lfloor \log_q n \rfloor}\).
  3. Wähle ein zufälliges \(a \in \lbrace 2, \ldots, n-1\rbrace\) und berechne \(ggT(a^k - 1,n)\).
  4. Dies kann einen Teiler von \(n\) liefern, falls nicht, starte mit einem anderen \(a\) oder größeren Basis \(B\).

Basiert auf dem kleinen Satz von Fermat. Funktioniert nur wenn ein Primteiler \(p\) von \(n\) die Eigenschaft hat, dass \(p-1\) nur kleine Primfaktoren hat. Bei einer zu großen Basis wird es auch ineffizient.

Pollards rho-Methode zur Faktorisierung
  1. Wähle eine Funktion \(F(x) = x^2 + a \mod n\).
  2. Wähle einen Startwert \(x_0 \in \lbrace 0, \ldots, n-1\rbrace\) und setze \(y_0 = x_0\).
  3. \(\forall i \geq 1 :\) berechne \((x_i,y_i) = (F(x_{i-1}),F^2(y_{i-1}))\) und überprüfe ob \(ggT(y_i - x_i,n)\) einen nichttrivialen Teiler von \(n\) liefert.
  4. Falls \(ggT(y_i - x_i,n) = n\) breche ab und wähle neuen Startwert \(x_0\) oder neue Funktion \(F\) und beginne von vorn.

Basiert auf dem Geburtstagsparadoxon. Ist nur effizient, wenn \(n\) einen kleinen Primfaktor \(p\) besitzt. Erwartete Laufzeit liegt in \(O(\sqrt{p})\).

Diskreter Logarithmus

Das diskrete Logarithmus Problem besteht darin, zu einem gegebenen \(a = g^x \mod q\) die Zahl \(x\) zu berechnen. Es ist also die Umkehrung der modularen Exponentation, welche sehr effizient durchgeführt werden kann.

Pollards rho-Methode zur Berechnung des diskreten Logarithmus
Babystep-Giantstep-Algorithmus (Daniel Shank)

Eingabe: Endliche zyklische Gruppe \(G\), ein Erzeuger \(g\) und ein Element \(a\) der Gruppe

Ausgabe: \(x := \log_g a\) (Inverse zu \(g^x = a\))

  1. Zunächst berechnen wir \(n = |G|\) und setzen \(m = \lceil \sqrt{n}\rceil\).
  2. (Babysteps) Dann speichern wir in einer Tabelle mit Hashwertbasiertem Zugriff: \(\forall j \in \lbrace 0, \ldots, m-1\rbrace : (j,g^j)\).
  3. (Giantsteps) Danach suchen wir in der zweiten Spalte der Tabelle: \(\forall i \in \lbrace 0, \ldots, m-1\rbrace : a(g^{-m})^i\). Wenn wir das Element finden, geben wir \(im + j\) als Ergebnis aus.

Die Laufzeit des Algorithmus ist, bei angenommener konstanter Zugriffszeit für die Tabelle, in \(O(\frac{n}{m})\), also mit \(m \approx \sqrt{n} \Rightarrow O(\sqrt{n})\). Der Speicherplatz für die Tabelle beträgt genauso \(O(\sqrt{n})\). Beides ist für die Praxis zu lange bzw. zu groß.

Probabilistischer Miller-Rabin Primzahltest

Der Miller-Rabin Primzahltest ist ein rundenbasierter zufallsgesteuerter Algorithmus um zu entscheiden ob eine ungerade natürliche Zahl \(n\) keine Primzahl oder mit Wahrscheinlichkeit (Monte-Carlo-Algorithmus) \(\geq 3/4\) eine Primzahl ist.

Miller-Rabin Primzahltest Algorithmus

Eingabe: \(n > 3\) ungerade natürliche Zahl (und \(k\) Anzahl der Runden)

Ausgabe: Zusammengesetzt oder Wahrscheinlich Primzahl

  1. Schreibe \(n-1 = 2^s \cdot u\) mit \(u\) ungerade
  2. Führe \(k\)-mal aus:
    1. Wähle zufälliges \(a \in \lbrace 2,\ldots,n-1\rbrace\)
    2. Berechne \(b = a^u \mod n\)
    3. Falls \(b = 1\) gebe Wahrscheinlich Primzahl aus
    4. Andernfalls mache \(s\)-mal:
      1. Quadriere \(b = b^2 \mod n\)
      2. Falls \(b = n-1 \equiv -1\) gebe Wahrscheinlich Primzahl aus
    5. Gebe Zusammengesetzt aus
Beispiel
oder einen Bit Wert

Ausgabe

Beweis (\(n\) ist Primzahl)

Nach dem kleinen Satz von Fermat gilt damit \(a^{n-1} \equiv 1 \mod n\). Falls \(b \equiv 1 \mod n\) ist, wird Wahrscheinlich Primzahl ausgegeben, was korrekt ist.

Ist nun \(b \not\equiv 1 \mod n\) wird vom Algorithmus die Folge \[ (b^2, b^4, \ldots, b^{2^{s-1}}, b^{2^{s}}) \equiv (a^{u^2}, a^{u^4}, \ldots, a^{u^{2^{s-1}}}, a^{u^{2^{s}}}) \equiv \] \[ (a^{2u}, a^{4u}, \ldots, a^{2^{s-1} u}, a^{2^s u}) \equiv (,a^{2u}, a^{4u}, \ldots, a^{2^{s-1} u}, a^{n-1}) \equiv \] \[ (a^{2u}, a^{4u}, \ldots, a^{2^{s-1} u}, 1) \] berechnet. Der letzte Eintrag ist nach dem kleinen Satz von Fermat also kongruent 1. Jedes Element der Folge ist das Quadrat des Vorgängers. Damit am Ende eine 1 herauskommt, muss zwischendurch eine Zahl \(c\) vorhanden sein, die quadriert kongruent 1 ist. Dies kann nur \(-1\) oder \(1\) selbst sein, was sich wie folgt einsehen lässt: \[ x^2 \equiv 1 \mod n \Leftrightarrow x^2 -1 \equiv 0 \mod n \] \[ \Leftrightarrow n|x^2-1 \Leftrightarrow n|(x-1)(x+1) \Leftrightarrow n|(x-1) \text{ oder } n|(x+1) \] \[ \Leftrightarrow x - 1 \equiv 0 \mod n \text{ oder } x+1 \equiv 0 \mod n \] \[ \Leftrightarrow x \equiv 1 \mod n \text{ oder } x \equiv -1 \mod n \]

Beweis (\(n\) ist keine Primzahl)

Fängt die Folge nicht mit \(1\) an oder enthält keine \(-1\) so kann \(n\) keine Primzahl sein.

Angenommen \(n \geq 3\) sei ungerade und nicht prim. Dann enthält die Menge \(\lbrace 2,\ldots,n-1\rbrace\), aus der wir zufällig auswählen, höchstens \(\dfrac{n-2}{4}\) zu \(n\) teilerfremde Elemente \(a\) (\(ggT(a,n)=1\)) die keine Zeugen für die Zusammengesetztheit sind.

Damit ist die Wahrscheinlichkeit keinen Zeugen für eine zusammengesetzte Zahl zu treffen kleiner als \(1/4\). Bei \(k\)-facher Anwendung folgt daraus, dass die Wahrscheinlichkeit eine zusammengesetzte Zahl für eine Primzahl zu halten kleiner als \(4^{-k}\) ist. Zusammengesetzte Zahlen die den Test bestehen sind starke Pseudoprimzahlen.

Kryptographische Hashfunktionen

Eine Hashfunktion bildet eine Zeichenfolge beliebiger Länge auf eine Zeichenfolge mit fester Länge ab. Hieraus resultiert zwangsläufig (nach dem Schubfachprinzip), dass mehrere unterschiedliche Eingabefolgen auf den gleichen Hashwert abgebildet werden.

Verwendung

Kryptograpische Hashfunktionen sind weit verbreitet. Verwendet werden sie hauptsächlich für:

Anforderungen

Für eine Kryptographische Hashfunktion werden folgende Anforderungen gestellt:

Konstruktion

Eine Hashfunktion wird üblicherweise nach dem Merkle–Damgård oder dem Wide-pipe (doppelt so großer interner Zustand) Schema konstruiert. Dabei wird auf kollisionsresistente Einwegkompressionsfunktionen \(f(a,b) = c\) mit \(|c| = |a|\) zurückgegriffen. Diese Kompressionsfunktionen sollten den sogenannten Lawineneffekt haben, bei dem sich bei einer kleinen Änderung der Eingabe eine große Änderung in der Ausgabe ergibt.

Merkle–Damgård Hash Konstruktionsschema

Davidgothberg, 2007, Wikimedia Commons (Public Domain)

Wide-pipe Hash Konstruktionsschema

Watchdog9, 2011, Wikimedia Commons (Creative Commons Attribution-Share Alike 2.5 Generic)

Digitale Signaturen

Um digitale Nachrichten authentifizieren zu können kann man auf Digitale Unterschriften zurückgreifen. Zum Digital Signature Algorithm (DSA) Standard der auf dem ElGamal-Verfahren aufbaut, gehören auch noch die RSA-Signatur und der Elliptic Curve Digital Signature Algorithm (ECDSA).

Teilen von Geheimnissen

Angenommen ein Geheimnis soll auf mehrere Mitwisser aufgeteilt werden, so dass zur Rekonstruktion des Geheimnisses immer eine bestimmte Anzahl an Mitwissern benötigt wird.

Dies kann für eine natürliche Zahl \(s\) als Geheimnis wie folgt realisiert werden:

Shamir's Teilen von Geheimnissen

Eingabe: Geheimnis \(s\), Anzahl der Mitwisser \(n\) und Mindestanzahl benötigter Mitwisser \( m < n\).

  1. (öffentlich) Wahl einer Primzahl \(p\) die viel größer als \(n\) und \(s\) ist.
  2. (geheim) Generierung eines Polynoms durch zufällige und gleichverteilte Wahl von Koeffizienten \(a_1, \ldots, a_{m-1} \in \mathbb{F}_p\).
  3. (geheim) Das Polynom ergibt sich damit wie folgt \(f(x) = s + \sum_{i=1}^{m-1} a_i x^i \in \mathbb{F}_p[x]\) mit Grad kleiner \(m\) und \(f(0) = s\).
  4. (geheim für jeden Mitwisser) Ausgabe von aus dem Polynom erzeugten Wertepaaren \((x_i,f(x_i))\) an den i-ten Mitwisser.

Rekonstruktion des Geheimnisses mit Lagrange-Interpolation an der Stelle \(x=0\):

\[s = f(0) = \sum_{i} \left( f(x_i) \cdot \prod_{1\leq j\leq m, j \not=i} \dfrac{-x_j}{x_j-x_i} \mod p\right)\]
Sicherheit

Nach dem Fundamentalsatz der Algebra werden \(m\) Wertepaare benötigt um ein Polynom \(m-1\)-ten Grades eindeutig bestimmen zu können. Es können also \(m\) oder mehr Personen das Polynom wieder bestimmen und an das Geheimnis gelangen.

Angenommen \(m-1\) Personen wollen mit ihren Stützstellen \(((x_1,f(x_1)), \ldots, (x_{m-1},f(x_{m-1})))\) an das Geheimnis kommen. Dann folgt mit der Lagrange-Interpolation, dass es genau \(p\) Polynome in \(\mathbb{F}_p[x]\) mit Grad kleiner \(m\) für diese Stützstellen gibt. Jedes dieser Polynome ist gleich wahrscheinlich und somit auch jedes dazugehörige Geheimnis. Somit können \(m-1\) Personen das Geheimnis nicht lüften.

Elektronische Verpflichtung

Wenn sich Alice gegenüber Bob auf eine bestimmte Information so festlegen möchte, dass sie die Information selbst zunächst nicht bekannt geben muss, aber später überprüft werden kann, dass sie sich tatsächlich auf die Information festgelegt hat, kann sie das wie folgt mit einer öffentlichen kollisionsresistenten Hashfunktion machen:

Ablauf
  1. (geheim) Alice wählt zwei verschiedene, lange und zufällige Zeichenfolgen \(r_1,r_2\) und ihre Informations-Zeichenfolge \(m\).
  2. (öffentlich) Alice schickt den Hashwert \(h(r_1 r_2 m)\) und \(r_1\) an Bob.
  3. (öffentlich) Wenn sie die Information veröffentlichen möchte, schickt sie noch die zweite Zufallsfolge \(r_2\) und ihre Information \(m\) an Bob.
  4. Bob kann damit später überprüfen, ob der am Anfang gesendete Hashwert korrekt war.
Sicherheit

Dabei kann Bob die Information nicht erraten, da die Hashfunktion schwierig zu invertieren ist und es auch mehrere Eingabefolgen mit \(r_1\) am Anfang für diesen Hashwert gibt.

Genauso ist es für Alice nicht möglich, sich später für eine andere Information zu entscheiden. Da sie einen Teil der Zufallsfolgen veröffentlicht, ist es für sie nicht möglich spezielle Folgen zu wählen für die Kollisionen wahrscheinlicher währen.