Wissen: Kryptologie (Überblick)

Autor: André Dalwigk

Umfassende Übersicht zur Kryptologie

Definition: Teilbarkeit

\(a\in\mathbb{Z}\) teilt \(n\in\mathbb{Z}\), wenn es ein \(b\in\mathbb{Z}\) mit \(n=a\cdot b\) gibt, also: \(\forall a,n\in\mathbb{Z}:a\mid b\Leftrightarrow\exists b\in \mathbb{Z}:n=a\cdot b\)

Definition: g-adische Darstellung einer natürlichen Zahl \(\mathbb{N}\)

Die g-adische Darstellung von \(n\in\mathbb{N}\) ist gegeben durch: \(\sum_{i=0}^{n}{a_{i}\cdot g^{i}}=a_{0}\cdot \underbrace{g^{0}}_{=1} + a_{1}\cdot g^{1} + a_{2}\cdot g^{2} + ... + a_{n}\cdot g^{n}\) mit \(a_i\in\{0,1,2,...,g-1\}\)

Definition: Größter gemeinsamer Teiler \(ggT(a,b)\)

Ein gemeinsamer Teiler von \(a,b\in\mathbb{Z}\) ist eine Zahl \(c\in \mathbb{Z}\), die \(a\) und \(b\) teilt, also: \(c\text{ ist ein gemeinsamer Teiler von }a,b\Leftrightarrow c\mid a \wedge c\mid b\). Der größte gemeinsame Teiler \(ggT(a,b)\) von \(a\) und \(b\) ist der größte aller gemeinsamen Teiler von \(a\) und \(b\).

Satz: Zusammenhang ganzzahlige Linearkombinationen und \(ggT\)

Die Menge der ganzzahligen Linearkombinationen von \(a,b\in\mathbb{Z}\) ist die Menge der ganzzahligen Vielfachen von \(ggT(a,b)\).

Beispiel: Welche Zahlen kann man aus \(26\) und \(18\) kombinieren? Nach Satz 1 sind das alle Vielfachen von \(ggT(26,18)=6\), also \(6\mathbb{Z}=\{0,\pm6, \pm12, \pm18, ...\}\).

Satz: Teilbarkeit des \(ggT\)

Seien \(a,b\in\mathbb{Z}\). Alle gemeinsamen Teiler von \(a\) und \(b\) teilen \(ggT(a,b)\). Sei \(t\in\mathbb{Z}\): \(t\mid a\wedge t\mid b\Rightarrow t\mid ggT(a,b)\)

Bemerkung: \(ggT\) für drei Zahlen

Seien \(a,b,c,t,t'\in\mathbb{Z}\), \(ggT(a,b,c)=x\) und \(ggT(a,b)=g\). Dann gilt: \(t\mid a\wedge t\mid b \wedge t\mid c\Rightarrow t\mid g,c\) und \(t'\mid g\wedge t\mid c \Rightarrow t'\mid a,b,c\). Also haben \(a,b,c\) und \(g,c\) dieselben gemeinsamen Teiler \(\Rightarrow ggT(a,b,c)=ggT(c,g)\).

Bemerkung: Kombinationen aus \(a,b,c\in\mathbb{Z}\)

Seien \(a,b,c\in\mathbb{Z}\). Um die Zahlen herauszufinden, die man aus \(a,b,c\) kombinieren kann, berechnet man \(ggT(a,b,c)\) und bildet alle ganzzahligen Vielfache daraus.

Satz: Teilen mit Rest

Seien \(a,b\in\mathbb{N}\) und \(a>b\). Dann ist Teilen mit Rest definiert durch: \(a=q\cdot b+r\) mit \(0\leq r<b\).

Bemerkung: Reduktionseigenschaft des \(ggT\)

Seien \(a,b,r\in\mathbb{N}\) und \(0\leq r<b\). Dann gilt: \(ggT(a,b)= ggT(b,r)\).

Definition: Primzahlen

\(p\in\mathbb{N}\) heißt Primzahl, wenn sie nur durch \(p\) und \(1\) teilbar ist.

Satz: Existenz von Primteilern in \(\mathbb{N}\)

\(\forall a\in\mathbb{N}:a\text{ hat (mindestens) einen Primteiler }p\).

Satz: Primteiler von Produkten

Sei \(p\) eine Primzahl und \(a,b\in\mathbb{Z}\): \(p\mid ab\Rightarrow p\mid a \vee p\mid b\).

Bemerkung: Primzahl teilt das Produkt von Primzahlen

Seien \(q_{1},q_{2},...,q_{n},p\) Primzahlen: \(p\mid q_{1}\cdot q_{2} \cdot ...\cdot q_{n}\Rightarrow p=q\), wobei \(q=q_{1}\cdot q_{2} \cdot ...\cdot q_{n}\).

Satz: Existenz und Eindeutigkeit der Primfaktorzerlegung

Alle \(a\in\mathbb{N}_{>1}\) können eindeutig als Produkt von Primzahlen geschrieben werden.

Satz: Primzahlentest

Ist \(a\) keine Primzahl, so hat sie einen Primteiler \(\leq \sqrt{a}\).

Satz: Anzahl der Primzahlen \(\leq x\)

Sei \(\pi(x)\) die Anzahl der Primzahlen \(\leq x\). Dann gilt:

\(1,26\cdot\frac{x}{\ln(x)}\geq\pi(x)\geq\frac{x}{\ln(x)}\)

Beispiel: \(\pi(113)=30\), denn \(1,26\cdot\frac{113}{\ln(113)} \geq\pi(113)\geq\frac{113}{\ln(113)}\\\Leftrightarrow 30,118\geq\pi(113) \geq23,903\\\Leftrightarrow30\geq\pi(113)\geq24\)

Beispiel: Wie viele Primzahlen gibt es zwischen \(5000000\) und \(90000000\)? \(\pi(9000000)-\pi(5000000)\geq\frac{9000000}{\ln(9000000)}-1,26\cdot \frac{5000000}{\ln(5000000)}=153623\)

Satz: Fermat-Test

Ist \(n\) eine Primzahl und \(a\in\mathbb{N}\) kein Vielfaches von \(n\), so gilt: $$a^{n-1}\equiv1\mod n$$

  1. Rate \(n\).
  2. Wähle \(a\) (kein Vielfaches von \(n\)).
  3. Berechne \(a^{n-1}\mod n\).
  4. Ist das Ergebnis aus 4. nicht \(1\), so ist \(n\) keine Primzahl. Ist der Wert aus 4. eins, so wiederhole den Test mit anderem \(a\) (einige Male).

Bemerkung: Zusammenhang zwischen Primzahlen und \(ggT\)

Der \(ggT\) von zwei Zahlen besteht aus den gemeinsamen Primzahlen.

Definition: Relation

Sei \(M\) eine Menge. Die Teilmenge \(\sim\) von \(M\times M =\{(a,b):a,b\in M\}\) nennen wir Relation. Für \((x,y)\in\sim\) schreiben wir \(x\sim y\).

Definition: Äquivalenzrelation

Sei \(\sim\) eine Relation. \(\sim\) nennen wir Äquivalenzrelation, wenn gilt:

  1. \(\forall x\in M: x\sim x\) (Reflexivität)
  2. \(x\sim y\Rightarrow y\sim x\) (Symmetrie)
  3. \(x\sim y\wedge y\sim z\Rightarrow x\sim z\) (Transitivität)

Beispiel: \(M=\mathbb{Z}\) und \(n\in\mathbb{N}_{\geq 2}\). \(a\sim b\): \(a\) und \(b\) unterscheiden sich durch ein Vielfaches von \(n\), d.h. \(a-b\in n\cdot \mathbb{Z}\). Reflexivität: \(a-a=0\) Symmetrie: \(a-b\in n\cdot \mathbb{Z}\Rightarrow b-a\in n\cdot \mathbb{Z}\) Transitivität: \(a-b\in n\cdot \mathbb{Z}\Leftrightarrow a=b+s\cdot n\wedge b-c\in n\cdot\mathbb{Z}\Leftrightarrow c=b+t\cdot n\\\Rightarrow a-c=b+s\cdot n-b-t\cdot n\in n\cdot\mathbb{Z} \\\Rightarrow a\sim c\)

Definition: Äquivalenzklasse

Sei \(M\) eine Menge und \(\sim\) eine Äquivalenzrelation auf \(M\). Die Menge \([x]=\{y\in M\mid x\sim y\}\) nennen wir Äquivalenzklasse von x. Die Äquivalenzklassen bilden eine Zerlegung (Aufteilung in disjunkte Teilmengen) von \(M\).

Beispiel: Die Klasse von \(a\) ist: \([a]=a+n\cdot \mathbb{Z}\). Für \(n=4\) gilt: \([0]=\{...,-8,-4,0,4,8,...\}\) \([1]=\{...,-7,-3,1,5,9,...\}\) \([2]=\{...,-6,-2,2,6,10,...\}\) \([3]=\{...,-5,-1,3,7,11,...\}\)

Bemerkung: Die Äquivalenzklasse \(a\sim b\)

\(a\sim b\Leftrightarrow a\) und \(b\) haben beim Teilen durch \(n\) denselben Rest.

Definition: Halbgruppe

Eine Menge \(X\) mit einer assoziativen Verknüpfung heißt Halbgruppe \(H\): \(\forall a,b,c\in H:a\cdot(b\cdot c)=(a\cdot b)\cdot c\)

Beispiel: \((\mathbb{Z},+), (\mathbb{Z},\cdot), (\mathbb{Z}_{m},+), (\mathbb{Z}_{m},\cdot)\)

Definition: Neutrales Element

Sei \(H\) eine Halbgruppe und \(e\in H\). \(e\) heißt neutrales Element, wenn \(\forall a\in H:e\cdot a=a\cdot e=a\).

Beispiel: \((\mathbb{Z}_{m},+)\) - neutrales Element \([0]\) \((\mathbb{Z}_{m},\cdot)\) - neutrales Element \([1]\)

Definition: Inverses Element

Sei \((X,\cdot)\) eine Halbgruppe mit neutralem Element \(e\in (X,\cdot)\). \(b\in (X,\cdot)\) heißt Inverses von \(a\), wenn \(ba=ab=e\). Das Inverse von \(a\) bezeichnen wir mit \(a^{-1}\) (bei \(+:-a\)).

Satz: Anzahl an Inversen

Ein Element hat höchstens ein Inverses.

Definition: Gruppe

Sei \(X\) eine Halbgruppe mit neutralem Element \(e\in X\). Wenn jedes Element \(a\in X\) ein Inverses hat, dann nennen \(X\) eine Gruppe.

Bemerkung: Inverse in Verknüpfungstabelle

Zwei Elemente \(x\) und \(y\) in einer Verknüpfungstabelle sind genau dann zueinander invers, wenn an der Stelle \((x,y)\) eine \(1\) (für \(\cdot\), bei \(+:0\)) steht.

Beispiel:

Gruppe: \((\mathbb{Z},+), (\mathbb{Z}_{m},+)\)
keine Gruppe: \((\mathbb{Z},\cdot), (\mathbb{Z},-)\)

Satz: Lösbarkeit von Gleichungen in Gruppen

Sei \(X\) eine Gruppe, \(a,b\in X\) fest und \(x,y\in X\) Variablen. Dann sind Gleichungen der Form \(a\cdot x = b\) und \(y\cdot a = b\) eindeutig lösbar.

Bemerkung: Eigenschaft in Gruppen

Sei \(X\) eine Gruppe und \(a,b,c\in X\). Dann gilt: \(c\cdot a=c\cdot b\Rightarrow a=b\).

Satz: Rechenregeln für Gruppen

Sei \(X\) eine Gruppe, \(a,b,e\in X\) und \(m,n\in \mathbb{Z}\). Dann gilt:

  1. \(a^{0}=e\)
  2. \(a^{m}=\underbrace{a\cdot a\cdot ... \cdot a}_{m \text{ Mal}}\)
  3. \(a^{m}\cdot a^{n}=a^{m+n}\)
  4. \((a^{m})^{n}=a^{m\cdot n}\)
  5. \((a\cdot b)^{-1}=b^{-1}\cdot a^{-1}\), denn \(b^{-1}\cdot a^{-1} \cdot a\cdot b =e\)

Definition: Einheiten

Sei \((X,\cdot)\) eine Halbgruppe mit neutralem Element \(e\in(X,\cdot)\). Die invertierbaren Elemente \(X^{*}\in(X,\cdot)\) heißen Einheiten und bilden die Einheitengruppe \((X^{*},\cdot)\).

Beispiel: Die Einheitengruppe von \((\mathbb{Z}_{6},\cdot)\) ist \(\mathbb{Z}^{*}=\{1,5\}\).

Definition: Ring

\((R,+,\cdot)\) heißt Ring, wenn folgende Eigenschaften erfüllt sind:

  1. \((R,+)\) ist eine kommutative Gruppe ist \((e\hat{=}0)\).
  2. \((R,\cdot)\) ist assoziativ.
  3. \(a\cdot(b+c)=a\cdot b+a\cdot c\) und \((b+c)\cdot a = b \cdot a + c\cdot a\).

Definition: Nullteiler

Sei \((R,+,\cdot)\) ein Ring. \(a,b\in(R,+,\cdot)\) heißen Nullteiler, wenn \(a,b\neq0\) und \(a\cdot b=0\).

Bemerkung: Nullteiler in Verknüpfungstabellen

Nullteiler sind in einer Verknüpfungstabelle an den Nulleinträgen, wo keiner der dazugehörigen Randwerte 0 ist, zu finden.

Satz: Beziehung zwischen Nullteilern und Einheiten

Sei \((R,+,\cdot)\) ein Ring mit neutralem Element \(1\). Ein Nullteiler in \((R,+,\cdot)\) kann keine Einheit sein.

Definition: Teilerfremd

Seien \(a,b\in \mathbb{Z}\). Wir nennen \(a\) und \(b\) teilerfremd, wenn \(ggT(a,b)=1\).

Satz: Hilfssatz zur Teilerfremdheit

\(a,b,m\in\mathbb{N} \wedge ggT(a,m)=1 \wedge m\mid (a\cdot b) \Rightarrow m\mid b\).

Satz: Nullteilerkriterium

Sei \((\mathbb{Z}_{m},+,\cdot)\) ein Restklassenring. Ein Element \([a]\neq [0]\) ist genau dann ein Nullteiler, wenn \(ggT(a,m)>1\).

Satz: Multiplikative Inverse

Sei \((\mathbb{Z}_{m},+,\cdot)\) ein Restklassenring modulo \(m\). \([a]\neq[0]\) hat genau dann ein multiplikatives Inverses, wenn \(ggT(a,m)=1\). Daraus folgt: \((\mathbb{Z}_{m},+\cdot)\) zerfällt in \([0]\), Nullteiler und Einheiten.

Algorithmus: Berechnung von multiplikativen Inversen

Die Berechnung des multiplikativen Inversen \(a^{-1}\) von \(a\in(\mathbb{Z}_{m},\cdot)\) erfolgt durch den erweiterten Euklidischen Algorithmus mit \(ggT(a,m)\). Ist \(ggT(a,m)\neq 1\), dann besitzt \(a\) kein Inverses in \((\mathbb{Z}_{m},\cdot)\).

Algorithmus: Berechnung von Nullteilern

Die Berechnung von Nullteilern \(a\in(\mathbb{Z}_{m},\cdot)\) erfolgt durch den erweiterten Euklidischen Algorithmus mit \(ggT(a,m)\). Das Backtracking beginnt bei \(0\).

Definition: Körper (Definition 1)

Sei \((R,+,\cdot)\) ein kommutativer Ring mit neutralem Element \(1\). \(R\) heißt Körper, wenn jedes \(a\neq0\) ein multiplikatives besitzt.

Definition: Körper (Definition 2)

\((K,+,\cdot)\) heißt Körper, wenn folgende Eigenschaften gelten:

  1. \((K,+)\) ist eine kommutative Gruppe mit neutralem Element \(0\).
  2. \((K\setminus\{0\},\cdot)\) ist eine kommutative Gruppe mit neutralem Element \(1\).
  3. \(a,b,c\in(K,+,\cdot)\Rightarrow a\cdot(b+c)=a\cdot b+a\cdot c\).

Für jede Primzahl \(p\) gibt es einen endlichen Körper mit \(p\) Elementen, nämlich \((\mathbb{Z}_{p},+\cdot)\).

Satz: Multiplikative Inverse

\((\mathbb{Z}_{m},+,\cdot)\) ist genau dann ein Körper, wenn \(m\) eine Primzahl ist.

Definition: Prime Restklassengruppe modulo \(m\)

Sei \((\mathbb{Z}_{m},+,\cdot)\) ein Körper. Die Einheitengruppe \((\mathbb{Z}^{*}_{m},\cdot)\) heißt prime Restklassengruppe modulo \(m\).

Definition: Eulersche \(\varphi\)-Funktion

\(\varphi(m)=|\{a\mid1\leq a\leq m\wedge ggT(a,m)=1\}|= |\mathbb{Z}^{*}_{m}|\) heißt Eulersche \(\varphi\)-Funktion. Insbesondere sind \(\varphi(1)=1\) und \(\varphi(0)=0\).

Satz: \(\varphi\)-Funktion für Primzahlen

Sei \(p\) eine Primzahl. Dann gilt: \(\varphi(p)=p-1\).

Satz: Summenformel der Eulerschen \(\varphi\)-Funktion

Sei \(m\in\mathbb{N}\). Dann gilt: \(m=\sum_{d\mid m, d>0}{\varphi(d)}\).

Definition: Ordnung von Gruppenelementen

Sei \((G,\cdot)\) eine Gruppe mit neutralem Element \(1\). Sei weiterhin \(g\in G\). Die kleinste natürliche Zahl \(n\in\mathbb{N}\) mit \(g^{n}=1\) heißt Ordnung von \(g\). Falls \(g^{n}\neq 1\) für alle \(n\), dann ist die Ordnung unendlich groß und wir schreiben \(ord(g)=\infty\).

Bemerkung: Inverse für Gruppen unendlicher Ordnung

Sei \(G\) eine Gruppe und \(g\in G\). Dann gilt: \(\forall n\in \mathbb{N}:ord(g)=\infty\Rightarrow g^{-n}\neq1\).

Satz: Beziehung zwischen Gruppenordnung und Elementpotenz 1

Sei \(G\) eine Gruppe und \(g\in G\) mit \(ord(g)=n\). Dann gilt: \(\forall l \in\mathbb{N}:g^{l}=1\Leftrightarrow n\mid l\).

Satz: Beziehung zwischen Gruppenordnung und Elementpotenz 2

Sei \(G\) eine Gruppe und \(g\in G\) mit \(ord(g)=n\). Dann gilt: \(\forall l,k\in\mathbb{N}:g^{l}=g^{k}\Leftrightarrow l\equiv k \mod n\).

Satz: Berechnung der Elementpotenz

Sei \(G=(G,\cdot)\) eine Gruppe und \(g\in G\) mit \(ord(g)=k\), d. h. \(g^{k}=1\). Sei \(n\in \mathbb{Z}\). Dann gilt: \(ord(g^{n})=\frac{k}{ggT(n,k)}\).

Beispiel: \((\mathbb{Z}_{13}^{*},\cdot)\) Es ist \(ord(2)=12\) und somit \(ord(2^{6})=\frac{12}{ggT(12,6)}= \frac{12}{6}=2\). Es genügt bereits die Ordnung eines Elements (Erzeugers) und man hat die ganze Gruppe.

Satz: Berechnung der Elementprodukts

Sei \(G=(G,+)\) eine Gruppe und \(g\in G\) mit \(ord(g)=k\), d. h. \(g\cdot k=0\). Sei \(n\in \mathbb{Z}\). Dann gilt: \(ord(k\cdot g)=\frac{k}{ggT(n,k)}\).

Beispiel: \((\mathbb{Z}_{15},+)\) Es ist \(ord(3)=5\), da \(\underbrace{3, 3+3=6, 6+3=9, 9+3=12, 12+3=15\equiv 0}_{5 \text{ Mal}}\) (wie oft können wir \(3\) addieren, um auf das neutrale Element \(0\) bezüglich \(+\) zu kommen?). Was ist nun die Ordnung von \(12\)? Auch hier gilt: \(ord(12)=ord(4\cdot 3)=\frac{5}{ggT(4,5)}=\frac{5}{1}=5\)

Algorithmus: Welche Zahlen in \((G,+)\) haben die Ordnung \(k\)?

Sei \((G,+)\) eine Gruppe. Gesucht sind alle \(x\in (G,+)\) mit der Ordnung \(ord(x)=k\): \(ord(x)=k\Leftrightarrow ggT(k,x)=1\).

Definition: Untergruppen

Sei \((G,\cdot)\) eine Gruppe. Eine Teilmenge \(U\) von \((G,\cdot)\) heißt Untergruppe, wenn \(U\) für sich eine Gruppe ist. Das ist genau dann der Fall, wenn:

  1. \(U\subset G\)
  2. \(1\in U\) (neutrales Element)
  3. \(a,b\in U\Rightarrow a\cdot b\in U\) (Abgeschlossenheit)
  4. \(a\in U\Rightarrow a^{-1}\in U\) (inverses Element)

Bemerkung: Untergruppe \(g^{k}\)

Sei \(G=(G,\cdot)\) eine Gruppe und \(g\in G\). Dann ist \(U=\{g^{k}\mid k \in\mathbb{Z}\}\) eine Untergruppe von \(G\).

Satz: Erzeugte Untergruppe

Sei \((G,\cdot)\) eine Gruppe und \(g\in G\). Hat \(g\) endliche Ordnung \(n\in\mathbb{N}\), so ist \(<g>=\{g^{k}\mid k\in\mathbb{Z}\}=\{g^{1},g^{2},...,g^{n}=1\}\) die von \(g\) erzeugte Untergruppe. \(<g>\) ist isomorph zu \((\mathbb{Z}_m,+)\), d. h. \(g^{k} \Leftrightarrow[g]\). Hat \(g\) endliche Ordnung sind alle \(k\) verschieden.

Definition: Zyklische Gruppe

Sei \(G=(G,\cdot)\) eine Gruppe. \(G\) heißt zyklisch, wenn sie von einem Element erzeugt wird: \(<g>=G\).

Beispiel: \((\mathbb{Z},+)\) ist zyklisch mit \(1\) als Erzeuger. \((\mathbb{Z}_{m},+)\) ist zyklisch mit \([1]\) als Erzeuger.

Satz: Kriterium für zyklische Gruppen

Eine zyklische Gruppe ist isomorph zu \((\mathbb{Z},+)\) oder zu \((\mathbb{Z}_{m},+)\).

Satz: Erzeuger von \((\mathbb{Z}_{m},+)\)

1 ist ein Erzeuger der zyklischen Gruppe \((\mathbb{Z}_{m},+)\) und es ist \(ord(1)=m\). Dann gilt mit Satz 1.20: \(ord(k)=\frac{m}{ggT(k,m)}\). \(k\) erzeugt \(\mathbb{Z}_{m}\), wenn \(ord(k)=m\). Es folgt also: \(k \text{ erzeugt }\mathbb{Z}_{m}\Leftrightarrow ggT(k,m)=1\).

Satz: Anzahl der Erzeuger einer zyklischen Gruppe

Sei \((G,\cdot)\) eine zyklische Gruppe mit \(G=<g>\) und \(|G|=n\) der Form \(G=\{g^{1},g^{2},...,g^{n}=1\}\). Dann hat \(G\) genau \(\varphi(n)\) Erzeuger.

Beispiel: Es ist \((\mathbb{Z}_{13}^{*},\cdot)\) eine zyklische Gruppe. Gesucht sind alle Erzeuger. Wir probieren \(g=2\) aus. Es ist \(|G|=12=2\cdot 2\cdot 3\) und \(2^{12}=1\mod 13\). Weiterhin gilt: \(2^{\frac{12}{2}}=2^{6}\equiv 12 \mod 13\neq 1\) und \(2^{\frac{12}{2}}=2^{4}\equiv 3 \mod 13\neq 1\) Damit ist \(2\) ein Erzeuger von \((\mathbb{Z}_{13}^{*},\cdot)\). Weitere Erzeuger sind \(2^{k}\) mit \(ggT(k,12)=1\), also \(2^{5}\equiv 6\mod 13, 2^{7}\equiv 11\mod 13\) und \(2^{7}\equiv 7\mod 13\).

Satz: Zusammenhang Erzeuger und Einheiten

Seien \((\mathbb{Z}_{m},\cdot)\) und \((\mathbb{Z}_{m},+)\) Gruppen. Die Einheiten von \((\mathbb{Z}_{m},\cdot)\) sind die Erzeuger von \((\mathbb{Z}_{m},+)\).

Satz: Satz von Lagrange

Sei \(G\) eine Gruppe mit endlicher Ordnung. Ist \(U\) eine Untergruppe von \(G\), so gilt: \(|U| \mid |G|\).

Beispiel: \(G\) sei eine Gruppe mit \(12\) Elementen. Als Ordnung für die Untergruppen kommen nur die Teiler von \(12\), also \(1, 2, 3, 4, 6\) und \(12\) infrage.

Satz: Elementpotenz und Gruppenmächtigkeit

Sei \(G\) eine Gruppe mit \(|G|=n\). Dann gilt für alle Gruppenelemente \(g\in G\): \(g^{n}=e\).

Satz: Kleiner Satz von Fermat

Seien \(a,m\in \mathbb{N}\). Dann gilt: \(ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1 \mod m\).

Bemerkung: Multiplikative Inverse mit dem kleinen Fermat

Man kann mit dem kleinen Satz von Fermat \((a^{\varphi(m)}\equiv 1\mod m\) mit \(ggT(a,m)=1)\) multiplikative Inverse in \((\mathbb{Z}_{m}^{*},\cdot)\) ausrechnen. Gesucht ist das Inverse \(7^{-1}\) von \(7\) in \((\mathbb{Z}_{15}^{*},\cdot)\). Es ist \(ggT(7,15)=1\), also ist \(7\in\mathbb{Z}^{*}_{15}\) und hat ein multiplikatives Inverses. Es ist \(7^{\varphi(15)}\equiv 1\mod 15\) und \(\varphi(15)=8\). Es folgt: \(7^{8}=\underbrace{7^{7}}_{\text{Inverses zu }7}\cdot 7\equiv 1\mod 15\). Es ist also \(7^{7}\equiv 13\mod 15\) das Inverse zu \(7\) in \((\mathbb{Z}_{15}^{*},\cdot)\).

Bemerkung: Schnelles Potenzieren

In \((\mathbb{Z}_{m},+\cdot)\) soll \(g^{e}\) mit \(g\in(\mathbb{Z}_{m},+\cdot)\) und \(e\in\mathbb{N}\) berechnet werden. Dabei kann man folgendermaßen vorgehen:

  1. Stelle \(e\) als Binärzahl dar. Sei dabei \(e_{(2)} = k_{0}k_{1}...k_{n}\) mit \(k_{i}\in\{0,1\}\).
  2. Berechne \(g^{2^{k_{0}}}, g^{2^{k_{1}}}, ..., g^{2^{k_{n}}}\).
  3. Multipliziere alle Ergebnisse, in denen \(k_{i}=1\).

Satz: Berechnung der Elementordnung

Sei \(G\) mit \(|G|=n\) eine endliche Gruppe und \(g\in G\). Gesucht ist die Ordnung \(ord(g)\) von \(g\). Sei weiterhin die Primfaktorzerlegung bekannt und gegeben durch: \(n=\prod_{p\mid n}{p^{e(p)}}\). Man muss aus \(n\) die unnötigen Primzahlen entfernen, d.h. wenn \(g^{\frac{n}{p_{i}}}=1\), dann ist der Wert unnötig. Allgemein gilt: Sei \(f(p)\) die größte ganze Zahl mit \(g^{\frac{n}{f(p)}}=1\). Dann gilt: \(ord(g)=\prod_{p\mid n}{p^{e(p)-f(p)}}\)

Beispiel: \((\mathbb{Z}_{13}^{*},\cdot)\). Es gilt: \(ord(\mathbb{Z}_{13}^{*})=12=2\cdot 2\cdot 3\). Gesucht ist die Ordnung von \(3\). \(3^{\frac{12}{2}}=3^{6}\equiv 1\), d.h. die \(2\) fliegt raus. \(3^{\frac{12}{2\cdot 2}}=3^{3}\equiv 1\), d.h. die zweite \(2\) fliegt auch raus. \(3^{\frac{12}{3}}=3^{4}\equiv 4\neq 1\), d.h. die \(3\) fliegt nicht raus. \(\Longrightarrow ord(3)=2^{0}\cdot 3^{1}=3\).

Satz: Wie teste ich, ob ein Element ein Erzeuger ist?

Sei \(G\) eine Gruppe mit \(|G|=n\). Dann ist \(g^{n}=1\). Ist \(g^{\frac{n}{p}}\neq1\) für jeden Primteiler von \(n\), dann ist \(g\) ein Erzeuger von \(G\).

Algorithmus: Diophantische Gleichung

Gegeben ist \(aX\equiv b \mod m\) mit \(a,b,m,X\in\mathbb{Z}\). Sei weiterhin \(ggT(a,m)=d\) und es gelte \(d\mid b\). Dann existieren genau \(d\) Lösungen von \(aX\equiv b\mod m\), die man wie folgt findet:

  1. Mit dem erweiterten Euklidischen Algorithmus bestimmen wir \(s,t\) in \(1=\frac{a}{d}\cdot s+\frac{m}{d}\cdot t\)
  2. Wir setzen: \(x_0=\frac{b}{d}\cdot s \mod \frac{m}{d}\)
  3. Für alle \(1\leq 1\leq d-1\) setzen wir: \(x_0+i\cdot \frac{m}{d}\)

Algorithmus: Chinesischer Restsatz

Gegeben ist ein System linearer Kongruenzen (eine simultane Kongruenz) der Form:

\(x\equiv a_{1}\mod m_{1}\) \(x\equiv a_{1}\mod m_{2}\) \(\vdots\) \(x\equiv a_{r}\mod m_{r}\)

Dann kann \(x\) wie folgt berechnet werden:

  1. Bilden von \(M=m_{1}\cdot m_{2}\cdot ...\cdot m_{r}\).
  2. Bilden von \(M_i=\frac{M}{m_i}\) für alle \(1\leq i\leq r\).
  3. Berechnung der Lösung \(x_{i}\) aller linearen Kongruenzen \(M_{i}X\equiv 1 \mod m_{i}\) (Berechnung der multiplikativen Inversen).
  4. Berechnung von \(x_{0}=\sum_{k=1}^{r}{a_{k}\cdot M_{k}\cdot x_{k} \mod m_{k}}\).

Die Lösung ist eindeutig bezüglich \(\mod M\).

Definition: Das direkte Produkt

Seien \(R_1, R_2, ..., R_n\) Ringe. Dann ist das direkte Produkt \(R\) definiert durch: \(R=R_1\times R_2\times ... \times R_n\).

Satz: Rechenregeln für das direkte Produkt

Seien \(R,S\) Ringe. Dann gilt für das direkte Produkt:

  1. \((r_1, r_2, ..., r_n)+(s_1, s_2, ..., s_n)=(r_1 + s_1, r_2+s_2, ..., r_n+s_n)\).
  2. \((r_1, r_2, ..., r_n)\cdot(s_1, s_2, ..., s_n)=(r_1 \cdot s_1, r_2\cdot s_2, ..., r_n\cdot s_n)\).
  3. Durch die Addition und Multiplikation entsteht wieder ein Ring.
  4. Alle \(R_i\) sind kommutativ \(\Rightarrow\) Ring aus direktem Produkt ist kommutativ.
  5. Alle \(R_i\) haben ein neutrales Element \(1 \Rightarrow\) Ring aus direktem Produkt hat ein neutrales Element, nämlich \((\underbrace{1, 1, ..., 1}_{n \text{ Mal}})\).

Definition: Ringhomomorphismus

Seien \(R,S\) Ringe. Die Abbildung \(\varphi:R\rightarrow S\) heißt Ring-Homomorphismus, wenn folgende Eigenschaften gelten:

  1. \(\varphi(a+b)=\varphi(a)+\varphi(b)\) (additiv).
  2. \(\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b)\) (multiplikativ).

Ist \(\varphi\) bijektiv, dann nennen wir \(\varphi\) Isomorphismus.

Beispiel: $$\varphi: \begin{cases} (\mathbb{Z},+,\cdot)\rightarrow (\mathbb{Z}_{m},+,\cdot)\\ a\rightarrow[a] \end{cases} $$ Beispiel: Es ist \((\mathbb{Z}_{p}^{*},\cdot)\) isomorph zu \((\mathbb{Z}_{p-1},+)\). Die Erzeuger sind die Zahlen \(x\leq p-1\) mit \(ggT(x,p-1)\), also insgesamt \(\varphi(p-1)\) Zahlen.

Satz: Der Ringhomomorphismus des direkten Produkts

Seien \(m_1, m_2, ..., m_n\) teilerfremd aus \(\mathbb{N}\) und \(m=m_1\cdot m_2\cdot ...\cdot m_n\). Dann ist folgende Abbildung ein Ringhomomorphismus:

\(\varphi:(\mathbb{Z}_{m},+,\cdot)\rightarrow \mathbb{Z}_{m_{1}} \times\mathbb{Z}_{m_{2}}\times...\times\mathbb{Z}_{m_{n}}\) \(\underbrace{[a]}_{\mod m}\rightarrow (\underbrace{[a]}_{\mod m_1}, \underbrace{[a]}_{\mod m_2}, ..., \underbrace{[a]}_{\mod m_n})\)

Bemerkung: Der Umweg über das direkte Produkt

Den Ringhomomorphismus des direkten Produkts kann man folgendermaßen zur Berechnung eines Produkts in \((\mathbb{Z}_m,+\cdot)\) verwenden:

  1. Zerlege \(m\) in teilerfremde \(m_1\cdot m_2\cdot ...\cdot m_n\).
  2. Verwende \(\varphi\) (Ringhomomorphismus).
  3. Rechne in \(\mathbb{Z}_{m_{1}}\times \mathbb{Z}_{m_{2}}\times ...\times \mathbb{Z}_{m_{n}}\).
  4. Rechne das Ergebnis mit dem Chinesischen Restsatz nach \(\mathbb{Z}_{m}\) zurück.

Beispiel: Bestimme in \(\mathbb{Z}_{60}\) alle \(x\) mit \(X^2=9\). Es ist \(60=\underbrace{3}_{m_1}\cdot \underbrace{4}_{m_2}\cdot \underbrace{5}_{m_3}\). \(\varphi(9)=(\underbrace{9}_{\mod3},\underbrace{9}_{\mod4}, \underbrace{9}_{\mod5})=(0,1,4)\) Mögliche Lösungen sind z.B. \((0,1,2), (0,3,2), (0,1,3), (0,3,3)\), denn es gilt z.B. \((0,3,2)\cdot(0,3,2)=(0,9,2)\equiv(0,1,4)\). Die Ergebnisse werden dann mit dem Chinesischen Restsatz in \(\mathbb{Z}_{60}\) zurückgerechnet.

Satz: Multiplikativität der eulerschen \(\varphi\)-Funktion

Seien \(m_1, m_2, ..., m_n\) teilerfremd aus \(\mathbb{N}\) und \(m=m_1\cdot m_2\cdot ...\cdot m_n\). Dann gilt:

\(\varphi(m)=\varphi(m_1)\cdot\varphi(m_2)\cdot ... \cdot \varphi(m_n)\)

Was ist \(\varphi(p^n)\)? \(\varphi(p^n)=|\{x:1\leq x\leq p^n\mid ggT(x,p^n)=1\}|\). Es gilt:

\(\varphi(p^n) =p^{n-1}\cdot (p-1)\) für \(n\in\mathbb{N}\).

Satz: Anzahl der Elemente in \(K^*\)

Sei \(K\) ein Körper mit \(q\) Elementen. Dann gibt es für jeden Teiler \(d\) von \((q-1)\) genau \(\varphi(d)\) Elemente der Ordnung \(d\) in \((K^*,\cdot)\), d.h. \(K^*\) hat \(q-1\) Elemente.

Satz: Körper und zyklische Gruppen

Ist \((K,+\cdot)\) ein endlicher Körper, so ist \((K^*,\cdot)\) zyklisch.

Satz: Wurzeln von \(1\) in einem Körper mit \(1+1\neq 0\)

Sei \(K\) ein Körper mit \(1+1\neq 0\). Dann hat \(1\) genau zwei Wurzeln, nämlich \(1\) und \(-1\).

Satz: Wurzeln von \(a\) in einem Körper mit \(1+1\neq 0\)

Sei \(K\) ein Körper mit \(1+1\neq 0\). Dann hat \(a\neq0\) keine oder genau zwei Wurzeln.

Satz: Wurzeln von \(a\) in einem Körper mit \(1+1\neq 0\)

Gegeben sei \((\mathbb{Z}_p,+,\cdot)\). \(p\) ist prim, \(\neq2\) und \(4\mid (p+1)\). Die Zahl \(a\in\mathbb{Z}_p\) mit \(a\neq0\) habe eine Wurzel. Dann ist \(a^{\frac{p+1}{4}}\) eine Wurzel von \(a\).

Bemerkung: Aufwand zum Aufspüren der Wurzel in \((\mathbb{Z}_n,+\cdot)\)

Gegeben sei \((\mathbb{Z}_n,+\cdot)\) und \(a\) eine Quadratzahl mit \(a=b\cdot b\). Wenn man die Primzahlzerlegung von \(n\) nicht kennt, dann ist es sehr schwer eine Wurzel von \(a\) zu finden.

Bemerkung: Verschlüsselung

Klartext \(\longrightarrow\) Verschlüsselungsfunktion \(E_k\) mit Schlüssel \(k\) \(\longrightarrow\) Schlüsseltext. Schlüsseltext \(\longrightarrow\) Entschlüsselungsfunktion \(D_d\) mit Schlüssel \(d\) \(\longrightarrow\) Klartext.

Algorithmus: Cäsar-Verschlüsselung

Gegeben sei die Abbildung \(c:\{0,1,...25\}\rightarrow\{A,B,...,Z\}\) mit \(c(0)=A, c(1)=B, ..., c(25)=Z\). Dann gilt:

  1. Verschlüsselung \(E_k: x\rightarrow x+k\)
  2. Entschlüsselung \(D_k: x\rightarrow x-k\)

Die Berechnung erfolgt \(\mod 26\).

Bemerkung: Arten von Verschlüsselungsverfahren

  1. Symmetrisches Verfahren: Die Schlüssel zum Ver- und Entschlüsseln sind gleich (oder können leicht auseinander berechnet werden).
  2. Asymmetrisches Verfahren: Die Schlüssel sind verschieden und könnten nicht (oder nur sehr schwer) auseinander berechnet werden.

Bemerkung: Blockverschlüsselung

Bei einer Blockverschlüsselung werden Blöcke konstanter Länge verschlüsselt.

Definition: Permutation

Eine Permutation \(\pi:X\rightarrow X\) ist eine bijektive Abbildung einer endlichen Menge \(X\) auf sich selbst. Die Umkehrabbildung bezeichnen wir mit \(\pi^{-1}\). Es gilt:

  1. \(\pi^{-1}(\pi(x))=x\).
  2. \(\pi(\pi^{-1}(x))=x\).
  3. \(\pi\circ\pi^{-1}=\pi^{-1}\circ\pi=id\) (identische Abbildung).

Algorithmus: Blockverschlüsselung durch Permutationen

Gegeben ist einen Block der Länge \(n\) mit \(b=(x_0, x_1, x_2, ...,x_n)\) und eine Permutation \(\pi\). Es gilt: \(b(1)=x_0, b(2)=x_1, ..., b(n)=x_n\).

  1. Verschlüsselung: Schlüsselblock \(c\): \(c(i) := b(\pi(i))\).
  2. Entschlüsselung: Block \(d\): \(d(i) := c(\pi^{-1}(i))\).

Beispiel: \(b=(R,A,B,X,U,T,S,B)\), \(\pi=(\begin{matrix}3& 7& 1& 8& 5& 2& 4& 6 \end{matrix})\), \(\pi=(\begin{matrix}3& 6& 1& 7& 5& 8& 2& 4\end{matrix})\). Es gilt: \(c(1)=b(\pi(1))=b(3)=B\) \(c(2)=b(\pi(2))=b(7)=S\) usw.. Am Ende erhält man: \(c=(B,S,R,B,U,A,X,T)\) und \(d=(R,A,B,X,U,T,S,B)\).

Definition: Die affine Chiffre

Gegeben sei das Alphabet \((\mathbb{Z}_p,+,\cdot)\) mit \(p\) als Primzahl. Dann nennen wir die folgenden Verschlüsselungs- und Entschlüsselungsabbildung affine Chiffre: Verschlüsselung:

\(x\rightarrow a\cdot x +b\text{ mit } a\neq0, \text{ Schlüssel: } (a,b)\)

Entschlüsselung:

\(y\rightarrow a^{-1}\cdot (y-b)\)

Bemerkung: Verschlüsselungsmodi

  1. ECB-Mode: Jeder Block wird einzeln, unabhängig von den anderen verschlüsselt.
  2. CBC-Mode (Ciperblock-Chaining-Mode):

    • Alphabet: \((\mathbb{Z}_r,+\cdot)\)
    • Blocklänge: \(n\)
    • Initialisierungsvektor IV: Block der Länge \(n\) (öffentlich)
    • Klartextblöcke: IV, \(m_1\), \(m_2\), ...
    • Schlüsselblöcke: \(c_o, c_1, ...\)
    • Verschlüsseln: \(c_0 := IV\) und \(c_j := E(c_{j-1}\oplus m_j)\)
    • Entschlüssen: \(m_j := D(c_j)-c_{j-1}\) mit \(E\) Blockverschlüsselung und \(D\) Blockentschlüsselung
  3. CFB-Mode (Cipher-Feedback-Mode):

    • Alphabet \((\mathbb{Z}_s,+,\cdot)\)
    • Blockchiffre der Länge \(n\). Der Klartext wird in Blöcke der Länge \(r<n\) eingeteilt
    • Initialisierungsvektor IV der Länge \(n\)
    • Verschlüsseln: \(I_1=IV\)

      1. \(O_j := E(I_j)\).
      2. \(t_j :=\) Die ersten \(r\) Zeichen von \(O_j\).
      3. \(c_j := m_j\oplus t_j\).
      4. \(I_{j+1} :=\) Die ersten \(r\) Zeichen von \(I_j\) löschen und \(c_j\) hinten anhängen.
    • Entschlüsseln: \(I_1=IV\)

      1. \(O_j := E(I_j)\).
      2. \(t_j :=\) Die ersten \(r\) Zeichen von \(O_j\).
      3. \(m_j := c_j\ominus t_j\).
      4. \(I_{j+1} :=\) Die ersten \(r\) Zeichen von \(I_j\) löschen und \(c_j\) hinten anhängen.

Vorteil: Der Klartextblock wird je nach Position verschieden verschlüsselt.

Beispiel (CBC): Alphabet \((\mathbb{Z}_{10},+,\cdot)\), Blocklänge \(n=5\) und Blockverschlüsselung mit der Permutation \(E := \pi=(\begin{matrix}3&1&5&4&2\end{matrix})\). Es ist \(\pi^{-1}=(\begin{matrix}2&5&1&4&3\end{matrix})\). Weiterhin ist \(IV=(7,1,0,3,1), m_1=(3,9,1,2,5), m_2=(1,1,8,0,4)\) Verschlüsselung: \(c_0=(7,1,0,3,1)\) \(c_1=E=E(0,0,1,5,6)=(1,0,6,5,0)\) \(c_2=E=E=(4,2,4,5,1)\) Entschlüsseln: \(m_1=D(c_1)-c_0=D(1,0,6,5,0)-(7,1,0,3,1)=(0,0,1,5,6)-(7,1,0,3,1)= (3,9,1,2,5)\) (stimmt) \(m_2=D(c_2)-c_1=D(4,2,4,5,1)-(1,0,6,5,0)=(2,1,4,5,4)-(1,0,6,5,0)= (1,1,8,0,4)\) (stimmt ebenfalls).

Beispiel (CFB): Alphabet \((\mathbb{Z}_{10},+,\cdot)\), Blockchiffre der Länge \(n=7\) mit Addition von \((1,5,9,8,1,0,2)\) (Verschlüsseln). Gegeben sei weiterhin ein Klartextblock der Länge \(r=4\). Ferner: \(IV=(3,1,3,5,9,1,5), m_1=(2,0,9,1), m_2=(1,1,3,6)\) (Länge \(4\), da Klartextblock Länge \(r=4\) hat. Verschlüsseln: \(I_1=(3,1,3,5,9,1,5)\)

  1. \(O_1=(3,1,3,5,9,1,5)\oplus(1,5,9,8,1,0,2)=(4,6,2,3,0,1,7)\)
  2. \(t_1=(4,6,2,3)\)
  3. \(c_1=m_1\oplus t_1=(2,0,9,1)\oplus(4,6,2,3)=(6,6,1,4)\)
  4. \(I_2=(9,1,5,6,6,1,4)\)

Das war der ertse Durchgang. Nun folgt der zweite:

  1. \(O_2=\underbrace{(9,1,5,6,6,1,4)}_{I_2}\oplus(1,5,9,8,1,0,2)= (0,6,4,4,7,1,6)\)
  2. \(t_2=(0,6,4,4,7,1,6)\)
  3. \(c_2=(1,1,3,6)\oplus(0,6,4,4)=(1,7,7,0)\)
  4. \(I_3=(6,1,4,1,7,7,0)\)

Entschlüsseln: \(I_1=(3,1,3,5,9,1,5)\)

  1. \(O_1=(3,1,3,5,9,1,5)\oplus(1,5,9,8,1,0,2)=(4,6,2,3,0,1,7)\)
  2. \(t_1=(4,6,2,3)\)
  3. \(m_1=(6,6,1,4)\ominus(4,6,2,3)=(2,0,9,1)\) (stimmt)
  4. \(I_2=(9,1,5,6,6,1,4)\)

Jetzt für \(m_2\)

  1. \(O_2=(9,1,5,6,6,1,4)\oplus(1,5,9,8,1,0,2)=(0,6,4,4,7,1,6)\)
  2. \(t_2=(0,6,4,4)\)
  3. \(m_2=(1,7,7,0)\ominus(0,6,4,4)=(1,1,3,6)\) (stimmt auch)
  4. \(6,1,4,1,7,7,0\)

Algorithmus: Die affine Blockverschlüsselung

  • Alphabet \((\mathbb{Z}_p,+\cdot)\) mit Primzahl \(p\)
  • Blocklänge \(n\)
  • \(M:\) invertierbare \(n\times n\) Matrix aus \(\mathbb{Z}_p\)
  • \(b:\) Vektor mit \(n\) Komponenten und Schlüssel \((M,b)\)
  • Verschlüsselung: \(\left(\begin{matrix}x_1\\x_2\\\vdots\\x_n \end{matrix}\right)\rightarrow\left(\begin{matrix}y_1\\y_2\\ \vdots\\y_n\end{matrix}\right)=M\cdot \left(\begin{matrix}x_1\\ x_2\\\vdots\\x_n \end{matrix}\right) + \left(\begin{matrix}b_1\\b_2 \\\vdots\\b_n \end{matrix}\right)\)
  • Entschlüsseln: \(M^{-1}\cdot (y-b)=x\)

Beispiel: \(\mathbb{Z}_7, n=2, M=\left(\begin{matrix}3&5\\1&3 \end{matrix}\right), b=\left(\begin{matrix}5\\6\end{matrix}\right)\) Es ist \(M^{-1}=\left(\begin{matrix}6&4\\5&6\end{matrix}\right)\), denn \(\left(\begin{matrix}3 & 5\\1 & 3\end{matrix}\right)\cdot \left( \begin{matrix}6&4\\5 & 6\end{matrix}\right)=\left(\begin{matrix}43&42 \\21&22\end{matrix}\right)\equiv \left(\begin{matrix}1 &0\\0&1 \end{matrix}\right)\mod7\). Gegeben sei nun der Nachrichtenvektor \(x= \left(\begin{matrix}2\\4\end{matrix}\right)\):

  1. Verschlüsseln: \(\left(\begin{matrix}3&5\\1&3\end{matrix}\right) \cdot \left(\begin{matrix}2\\4\end{matrix}\right)+\left(\begin{matrix} 5\\6\end{matrix}\right)=\left(\begin{matrix}6+20+5\\2+12+6\end{matrix} \right)=\left(\begin{matrix}31\\20\end{matrix}\right)\equiv \left( \begin{matrix}3\\6\end{matrix}\right)\mod7\).
  2. Entschlüsseln: \(\left(\begin{matrix}6&4\\5&6\end{matrix}\right) \cdot\left[\left(\begin{matrix}3\\6\end{matrix}\right)-\left( \begin{matrix}5\\6\end{matrix}\right)\right]=\left(\begin{matrix}6&4 \\5&6\end{matrix}\right)\cdot \underbrace{\left(\begin{matrix}5\\0 \end{matrix}\right)}_{\mod7}=\left(\begin{matrix}30\\25\end{matrix} \right)\equiv \left(\begin{matrix}2\\4\end{matrix}\right)\mod 7\)

Algorithmus: Die Feistel-Chiffre

Die Feistel-Chiffre ist eine spezielle Blockverschlüsselung. Gegeben sei das Alphabet \((\mathbb{Z}_2,+,\cdot)\), wobei \(m=2\) beliebig sein kann. Es handelt sich um eine Blockverschlüsselung der Länge \(t\) mit Schlüssel \(k\). Mit einer bestimmten Methode werden aus dem Schlüssel \(k\) Runden Schlüssel \(k_1,k_2, ...,k_n\) erzeugt. Die Feistel-Chiffre ist nun eine Blockverschlüsselung der Länge \(n=2t\):

  • Alphabet \((\mathbb{Z}_2,+,\cdot)\), wobei \(m=2\) beliebig sein kann.
  • Blocklänge \(t\rightarrow2t\)
  • Schlüssel \(k\rightarrow\) Rundenschlüssel \(k_1,k_2,...,k_r\)
  • Vorbereitung: \((\underbrace{L_0}_{t},\underbrace{R_0}_{t})\)
  • Verschlüsselung:

    \((L_i,R_i) :=(R_{i-1},\underbrace{L_{i-1}\oplus f_k(R_{i-1})}_{R_i})\) mit \(i=1,2,...,r\) \(\vdots\) \((L_r, R_r)\) ist der letzte Block (nur \(k\) ist geheim)

  • Entschlüsseln:

    \(R_{i-1}=L_i\)
    \(L_{i-1}=R_i\ominus f_{k_{i}}(R_{i-1})\) bzw. \(L_{i-1}=R_i \ominus f_{k_{i}}(L_i)\)

Beispiel: Länge \(t=4, r=2\) (2 Runden), Rundenschlüssel sind \(k_1=(1,0,0,0)\) und \(k_2=(0,1,0,0)\), Klartext \(x=10101110\). Verschlüsseln

  1. Klartext aufteilen: \((L_0,R_0)=(1010\mid1110)\)
  2. \((L_1,R_1)=(1110\mid1010\oplus \underbrace{f_{k_1}(1110)}_{\text{Schlüssel } k_1=(1,0,0,0) \text{ addieren}})=(1110\mid1010\oplus0110)\\=(1110\mid1100)\). Das war die erste Runde. Jetzt kommt Runde 2.
  3. \((L_1,R_1)=(1100\mid1110\oplus \underbrace{f_{k_2}(1100)}_{\text{Schlüssel }k_2=(0100) \text{ addieren}})=(1100\mid1110\oplus1000)\\=(1100\mid0110)\).

Entschlüsseln

  1. Der verschlüsselte Block ist \((1100\mid0110)=(L_2,R_2)\)
  2. \(R_1=L_2=1100\)
  3. \(L_1=R_2\oplus f_{k_2}(L_2)=0110\oplus \underbrace{f_{k_2}(1100)}_{\text{Schlüssel wieder addieren}}= 0110\oplus1000=1110=L_1\\\Rightarrow(L_1,R_1)=(1110\mid1100)\) (stimmt)
  4. \(R_0=L_1=1110\) und \(L_0=R_1\oplus f_{k_1}(1110)=1100 \oplus0110=1010\\\Rightarrow\) Der Klartextblock ist also \((L_0,R_0)=(1010\mid1110)\) (stimmt also)

Algorithmus: RSA-Verfahren

Das RSA-Verfahren ist ein asymmetrisches Verschlüsselungsverfahren.

  1. Wähle zwei verschiedene (große) Primzahlen \(p\) und \(q\).
  2. Bilde \(n=p\cdot q\).
  3. Berechne \(\varphi(n)\) durch \(\varphi(n)=(p-1)\cdot(q-1)\).
  4. Wähle eine Zahl \(e\) mit \(1<e<\varphi(n)\) und \(ggT(e,\varphi(n))=1\). \(e\in(\mathbb{Z}_{\varphi(n)}^{*},\cdot)\)
  5. Berechne \(d\) mit \(1<d<\varphi(n)\) und \(e\cdot d\equiv1\mod\varphi(n)\) mit dem erweiterten euklidischen Algorithmus.
  6. Der öffentliche Schlüssel ist das Paar \((n,e)\). Der private Schlüssel ist \((n,d)\).
  7. Der Klartext ist eine Zahl \(m\) mit \(0<m<n\).
  8. Verschlüsselung: \(c=m^{e}\mod n\).
  9. Entschlüsselung: \(c^d\mod n=m\).

Bemerkung: Sicherheit des RSA

  1. Kennt man \(p\) und \(q\), so kann man \(d\) berechnen.
  2. Kennt man \(d\), so kann man \(p\) und \(q\) mit wenig Aufwand berechnen. \(\Rightarrow\) \(d\) zu finden ist genauso schwierig (zeitaufwendig) wie \(n\) in \(p\cdot q\) zu zerlegen.

Bemerkung: Verringerung des Rechenaufwands mit dem Chinesischen Restsatz

Gegeben sei der Isomorphismus \(f:\mathbb{Z}_n\rightarrow \mathbb{Z}_p\times\mathbb{Z}_q,\) \(x\rightarrow(\underbrace{x}_{\mod p},\underbrace{x}_{\mod q})\). \((a,b)\rightarrow x\) mit \(x\equiv a\mod p\) und \(x\equiv b\mod q\). Verschlüsselung: \(c=m^e\mod n\) Entschlüsselung: \(m=c^d\mod n\) \(f:c\rightarrow(c,c)\) berechnet \((c,c)^d=(\underbrace{c^d}_{m_p=c^d\mod p}, \underbrace{c^d}_{c^d=m_q\mod q}\). Danach rechnet man das Ergebnis mit dem chinesischen Restsatz nach \(\mathbb{Z}_n\) zurück.

\(m\equiv m_p\mod p\) \(m\equiv m_q\mod q\)

Algorithmus: Das Rabin-Verschlüsselungsverfahren

  1. Seien \(p,q\) Primzahlen und \((p+1), (q+1)\) durch \(4\) teilbar.
  2. Berechne \(n=p\cdot q\).
  3. Öffentlicher Schlüssel: \(n\).
    Geheimer Schlüssel: \(p,q\).
  4. Verschlüsselung: Der Klartext \(m\in\{2,3,...,n-1\}\) wird durch \(c=m^2\mod n\) verschlüsselt.
  5. Entschlüsselung:

    1. In \((\mathbb{Z}_n,+\cdot)\) müssen alle Wurzeln von \(c\) gefunden werden.
    2. Eine der Wurzeln ist \(m\).
    3. Wir betrachten den Isomorphismus
      \(f:\mathbb{Z}_{p\cdot q}\rightarrow\mathbb{Z}_p \times\mathbb{Z}_q\) \(x\rightarrow(x,x)\) \(c\rightarrow(c,c)\)
    4. \(c\) hat in \(\mathbb{Z}_p\) zwei Wurzeln \(u_1,u_2\). \(c\) hat in \(\mathbb{Z}_q\) die Wurzeln \(v_1,v_2\). Alle Wurzeln sind gegeben durch \((u_1,v_1),(u_1,v_2),(u_2,v_1),(u_2,v_2)\).
    5. Die Ergebnisse werden mit dem Chinesischen Restsatz in \(\mathbb{Z}_n\) zurückgerechnet. Man erhält: \(w_1,w_2,w_3,w_4\). Eine davon ist \(m\).

Beispiel: Verschlüsselung:

  1. Seien \(p=11\), \(q=23\). Es gilt: \((11+1)\cdot (23+1)=288\) und \(4\mid 288\).
  2. Es ist \(n=11\cdot23=253\).
  3. Öffentlicher Schlüssel: \(253\). Geheimer Schlüssel: \(11,23\).
  4. Verschlüsselt wird der Text \(m=34\).
  5. \(c=34^2\equiv144\mod253\). \(c\rightarrow(c,c)\Rightarrow (c,c)= (\underbrace{1}_{\mod 11},\underbrace{1}_{\mod 23})\)

Entschlüsselung:

    • Wurzeln von \(c=144\) in \(\mathbb{Z}_{11}\): \(c^{\frac{11+1}{4}}= 144^3\equiv 1\mod 11\).
    • Wurzeln in \(\mathbb{Z}_{11}\): \(1\wedge -1\equiv 10\mod 11\).
    • Wurzeln von \(c=144\) in \(\mathbb{Z}_{23}\): \(c^{\frac{23+1}{4}}= 144^6\equiv 12\mod 23\).
    • Wurzeln in \(\mathbb{Z}_{23}\): \(12\wedge -12\equiv 11\mod 23\).
  1. Die Wurzeln in \(\mathbb{Z}_{11}\times \mathbb{Z}_{23}\) lauten also: \((1,12),(1,11),(10,12),(10,11)\).
  2. Rückrechnung mit dem Chinesischen Restsatz: Eine von den angegeben Wurzeln ist die richtige. Es muss \(34=m\) herauskommen. \((1,11)\) liefert das richtige Ergebnis \((34,34)\).

Algorithmus: Diffie-Hellman Schlüsselaustausch

  1. Alphabet: \((\mathbb{Z}_p^{*},\cdot)\).
  2. Erzeuger: \(g\in(\mathbb{Z}_p^{*},\cdot)\).
  3. Schlüssel: \(a\) (Alice), \(b\) (Bob).
  4. Schlüsselaustausch:

    1. Alice wählt \(a\in\{1,2,...,p-2\}\) und berechnet \(A=g^a\mod p\).
    2. Alice sendet \(A\) an Bob (\(a\) ist der geheime Schlüssel von Alice).
    3. Bob wählt \(b\in\{1,2,...,p-2\}\) und berechnet \(B=g^b\mod p\).
    4. Bob sendet \(B\) an Alice (\(b\) ist der geheime Schlüssel von Bob).
    5. Alice rechnet: \(B^a\mod p=g^{b\cdot a}\) (geheimer Schlüssel für Alice und Bob).
    6. Bob rechnet: \(A^b\mod p=g^{b\cdot a}\) (geheimer Schlüssel für Alice und Bob).
    7. Der gemeinsame (geheime) Schlüssel ist \(B^a=A^b=g^{a\cdot b} \mod p\).

Beispiel: Gegeben sei das Alphabet \((\mathbb{Z}_{107}^{*},\cdot)\) und ein dazugehöriger Erzeuger \(5\). Gesucht ist der gemeinsame geheime Schlüssel von Alice und Bob. \(p=107\) und \(g=5\) sind öffentlich.

  1. Alice wählt \(a=32\) und berechnet \(A=5^{32}\equiv 83\mod 107\).
  2. Alice sendet \(83\) an Bob (\(83\) ist der geheime Schlüssel von Alice).
  3. Bob wählt \(b=6\) und berechnet \(B=5^6\equiv 3\mod 107\).
  4. Bob sendet \(3\) an Alice (\(3\) ist der geheime Schlüssel von Bob).
  5. Alice rechnet: \(3^{32}\equiv 13\mod 107\) (geheimer Schlüssel für Alice und Bob).
  6. Alice rechnet: \(83^{6}\equiv 13\mod 107\) (geheimer Schlüssel für Alice und Bob).

Der gemeinsame geheime Schlüssel von Alice und Bob ist \(13\).

Algorithmus: Das ElGamal Verschlüsselungsverfahren

  1. Alphabet: \((\mathbb{Z}_p^{*},\cdot)\).
  2. Klartext: \(m\in\{2,3,...,p-1\}\).
  3. Schlüsselerzeugung:

    1. Wähle eine große Primzahl \(p\) und ein Gruppenelement \(g\in(\mathbb{Z}_p^{*})\) der Ordnung \(p\) (Erzeuger).
    2. Wähle ein zufälliges \(a\in\{0,1,...,p-2\}\).
    3. Berechne \(A := g^a\mod p\).
    4. Öffentlicher Schlüssel: \((p,g,A)\). Geheimer Schlüssel: \((p,g,a,A)\).
  4. Verschlüsselung:

    1. Alice wählt \(b\in\{0,1,...,p-2\}\) und berechnet \(B := g^b\mod p\).
    2. Der Diffie-Hellman-Schlüssel ist \(A^b=B^a=g^{a\cdot b}\mod p\).
    3. Alice verschlüsselt \(m\) zu \(c := m\cdot A^b\mod p\).
    4. Alice schickt Bob \((c,B)\).
  5. Entschlüsselung:

    1. Bob berechnet das Inverse des Diffie-Hellman-Schlüssels in \((\mathbb{Z}_p^{*},\cdot)\), also \((B^a)^{-1}\mod p\). Dabei gilt: \((B^a)^{-1}=B^{p-1-a}\mod p\).
    2. Bob berechnet \(m\) durch: \(m=B^{p-1-a}\cdot c\mod p\).

Beispiel: Gegeben sei das Alphabet \((\mathbb{Z}_{17}^{*}\cdot)\). Seien weiterhin \(a=10\) und \(b=9\).

  1. Schlüsselerzeugung:

    1. \(p=17\). Es ist \(g=3\) ein Erzeuger der Gruppe \((\mathbb{Z}_{17}^{*}\cdot)\), denn \(|G|=16=2^4\) und \(3^{\frac{16}{2}}=3^8\neq 1\mod 17\).
    2. \(a=10\).
    3. \(A=3^10=59049\equiv 8\mod 17\).
    4. Öffentlicher Schlüssel: \((17,3,8)\).
      Geheimer Schlüssel: \((17,3,10,8)\).
  2. Verschlüsselung:

    1. \(b=9\) und \(B=3^{9}=19683\equiv 14\mod 17\).
    2. Der Diffie-Hellman-Schlüssel ist \(A^b=8^9=134217728 \equiv 8\mod 17\).
    3. \(m=12\) wird verschlüsselt zu \(c=12\cdot 8=96\equiv 11\mod 17\).
  3. Entschlüsselung:

    1. Wir berechnen \((B^a)^{-1}\) durch\((B^a)^{-1}=B^{p-1-a}\): \(14^{17-1-10}=14^{6}\equiv 15\mod 17\).
    2. \(m=15\cdot 11\equiv 12\mod 17\) (stimmt).

Bemerkung: Schlüsselwahl bei ElGamal

Alice hat Bob bereits eine Nachricht mit ElGamal geschickt. Wenn Alice Bob eine zweite Nachricht mit ElGamal schicken möchte, dann sollte sie für jede Nachricht ein neues (zufälliges) \(b\) wählen. Nehmen wir an, Alice wählt dasselbe \(b\). Seien weiterhin \(m,m'\) zwei verschiedene Nachrichten. Dann gilt: \(c=A^b\cdot m\mod p\) \(c'=A^b\cdot m'\mod p\) \(\Rightarrow c'\cdot c^{-1}=A^b\cdot m'\cdot (A^b)^{-1}\cdot m^{-1}= m' \cdot m^{-1} \underbrace{\cdot A^b\cdot(A^b)^{-1}}_{=1}\) \(\Rightarrow c'\cdot c^{-1}=m'\cdot m^{-1}\mid \cdot m\) \(\Rightarrow c'\cdot c^{-1}\cdot m=m'\). Kennt man also ein Paar \((c,m)\), so kann man zu \(c'\) bei gleichem \(b\) den Klartext \(m'\) berechnen.

Definition: Hash-Funktion

Gegeben ist eine Kompressionsfunktion \(g\) mit \(m>n\). Die zu verschlüsselnden Texte werden in Blöcke der Länge \(r=m-n\) zerlegt. Es gilt: $$H_i=g(H_{i-1},x_i)$$

Algorithmus: Hash-Funktion

Gegeben seien:

  1. Alphabet: \(\{0,1\}\)
  2. Blocklänge: \(n=4\)
  3. Schlüssel \(k\): Wort der Länge \(5\)
  4. Verschlüsselung: \(f_k:\) zirkulärer Linksshift um so viele Stellen, wie der Schlüssel Einsen hat, anschließend Addition von \(0001\).

Mit Hilfe der Blockchiffre bekommt man eine Kompressionsfunktion \(g\) mit $$g:B^9\rightarrow B^4, (\underbrace{m}_{n\text{ Stellen}}, \underbrace{k}_{r \text{ Stellen}})\rightarrow f_k(m)$$ Aus \(g\) bekommt man eine Hashfunktion \(h\). Mit \(h\) berechne man den Hashwert von \(101110001101010\), wenn \(H_0=(0,0,0,0)\).

  1. Wir bestimmen \(r=m-n=9-4=5\).
  2. Die Nachricht wird in Blöcke der Länge \(r=5\) unterteilt: \(\underbrace{10011}_{x_1}\mid\underbrace{00011}_{x_2}\mid \underbrace{01010}_{x_3}\)
  3. \(H_1=g(0000\mid10011)=f_{10011}(0000)=0000\oplus0001=0001\).
  4. \(H_2=g(0000\mid00011)=f_{00011}(0001)=0010\oplus 0001=0101\).
  5. \(H_3=g(0101\mid01010)=f_{01010}(0101)=0101\oplus0001=0100\).
  6. Hashwert \(H_3=0100\).
  Schreib uns deine Hinweise