Kryptologie/(Halb-)Gruppen und Ringe

Einleitung

Um zu zeigen, dass die Menge aller Restklassen $\mathbb{Z}/m\mathbb{Z}$ einen (Restklassen-)Ring bilden, was viele nützliche Eigenschaften garantiert, müssen wir noch einige Definitionen einführen. Zusätzlich betrachten wir den mathematischen Begriff der Ordnung, der uns bei der Kryptoanalyse des RSA-Kryptosystems von Nutzen ist.

Innere Verknüpfung

Definition Innere Verknüpfung

Sei $M$ eine Menge und $\circ :M\times M\to M$ eine Abbildung, die jedem Paar $(x,y)$ mit $x,y\in M$ ein $x\circ y$ zuordnet, so heißt diese Abbildung innere Verknüpfung.

Beispiel Innere Verknüpfung

Bei der Addition in $\mathbb{Z}$ gilt: $+:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$ mit dem Paar $(x,y)$ mit $x,y\in \mathbb{Z}$.

Seien $x=3$ und $y=5$, dann gilt nach Definition der inneren Verknüpfung: $x+y=3+5=8$.

Neutrales Element

Definition Neutrales Element

Sei $H=(H,\circ )$ eine Halbgruppe und $e\in H$. Wir nennen $e$ neutrales Element der Halbgruppe $H$, falls $e\circ a=a\circ e=a$ für alle $a\in H$.

Beispiel Neutrales Element

In $\mathbb{Z}$ ist $0$ das neutrale Element der Addition und $1$ das neutrale Element der Multiplikation.

Es gilt: $0+x=x+0=x$ und $1\cdot x=x\cdot 1=x$ für jedes $x\in \mathbb{Z}$.

Inverses Element

Definition Inverses Element

Sei $H=(H,\circ )$ eine Halbgruppe, $a,e\in H$ und $e$ das neutrale Element der Halbgruppe $H$. Wir nennen $b\in H$ das inverse Element bzw. die Inverse von $a$, falls gilt

$a\circ b=b\circ a=e$.

Beispiel Inverses Element

In $\mathbb{Z}$ ist das (additiv) Inverse einer Zahl $a\in \mathbb{Z}$ die Zahl, die zu $a$ addiert $0$ ergibt. Es gilt $a+(-a)=a-a=0$. Also ist $-a$ das additive Inverse zu $a$ in $\mathbb{Z}$.

Halbgruppe

Definition Halbgruppe

Innere Verknüpfung
Innere Verknüpfung
Sei $M$ eine Menge und $\circ :M\times M\to M$ eine Abbildung, die jedem Paar $(x,y)$ mit $x,y\in M$ ein $x\circ y$ $\in M$ zuordnet, so heißt diese Abbildung innere Verknüpfung.

Eine Halbgruppe $H=(H,\circ )$ besteht aus einer Menge $H$ und einer inneren Verknüpfung

$\circ :H\times H\to H,(a,b)\mapsto a\circ b,$

die assoziativ ist, d. h. für alle $a,b,c\in H$ gilt

$a\circ (b\circ c)=(a\circ b)\circ c$.

Gruppe

Definition Gruppe

Eine Halbgruppe $H$, die ein neutrales Element besitzt in der und jedes Element der Halbgruppe invertierbar ist, heißt Gruppe.

Definition Kommutative Gruppe

Eine Gruppe $G$ heißt kommutative Gruppe, wenn die zugehörige Halbgruppe $H$ kommutativ ist, d.h.

für alle $a,b\in H$ gilt: $a\circ b=b\circ a$.

Bemerkung: Im folgenden müssen wir noch die Ordnung von Elementen in Gruppen definieren und einen zugehörigen Satz formulieren. Dies benötigen wir, um in einer späteren Lerneinheiten Aussagen über die Sicherheit des asymmetrischen RSA-Kryptosystems treffen zu können.

Definition Ordnung von Elementen in Gruppen

Sei $G$ eine Gruppe und $1\in G$ das neutrale Element der Gruppe.

Wenn es ein $e\in \mathbb{N}$ gibt, sodass $a^e=1\in G$ gilt für alle $a\in G$, dann heißt die kleinste derartige Zahl Ordnung von $a$ in $G$ und wird als $or{d}_G(a)$ geschrieben.

Gibt es kein solches $e$, dann ist die Ordnung von $a$ in $G$ unendlich.

Satz zur Ordnung von Elementen in Gruppen

Seien $a\in G$ und $e\in \mathbb{N}$.

Es gilt $a^e=1$ genau dann, wenn $or{d}_G(a)\mid e$.

Beweis

Voraussetzung

$a\in G$ und $e\in \mathbb{Z}$.

Zu zeigen

Es gilt $a^e=1$ genau dann, wenn $or{d}_G(a)\mid e$.

Beweis

Hinrichtung

Wir zeigen zunächst aus $or{d}_G(a)\mid e$ folgt $a^e=1$.

Seien $f=or{d}_g(a)$ und $or{d}_G(a)\mid e$ bzw. $e=kf$ mit $k\in \mathbb{N}$.

Es gilt

$a^e$

$=a^{kf}$, nach $or{d}_G(a)\mid e$ bzw. $e=kf$

$=(a^f{)}^k$

$=(1{)}^k$, nach Definition Ordnung von Elementen in Gruppen

$=1$.

Also $a^e=1$.

Rückrichtung

Division mit Rest
Division mit Rest
Seien $a,b\in \mathbb{Z}$ mit $b\ne 0$ eindeutig bestimmte Zahlen $k\in \mathbb{Z}$und $r\in \mathbb{N}$ gibt, für die gilt: $a=k\cdot b+r,0\le r<|b|$.

Nun zeigen wir die Rückrichtung, nämlich aus

$a^e=1$

folgt

$or{d}_G(a)\mid e$

.

Hierfür müssen wir zeigen, dass $or{d}_G(a)\mid e$.

Sei $a^e=1$ und nach der Division mit Rest $e=qf+r$ mit $0\le r<f$.

$a^r$

$=a^{e-qf}$, nach Umformung von $e=qf+r$

$=a^e{a}^{-qf}$

$=a^e(a^f{)}^{-q}$

$=(a^f{)}^{-q}$, nach Voraussetzung $a^e=1$

$=(1{)}^{-q}$, da $f\in \mathbb{N}$ die kleinste Zahl mit $a^f=1$

$=1$.

Da $0\le r<n$, muss $r=0$ gelten und somit $e=kf$. Also gilt $or{d}_G(a)\mid e$.

Ring

Definition Ring

Innere Verknüpfung, Halbgruppe, Gruppe und kommutative Gruppe
Innere Verknüpfung
Sei $M$ eine Menge und $\circ :M\times M\to M$ eine Abbildung, die jedem Paar $(x,y)$ mit $x,y\in M$ ein $x\circ y$ zuordnet, so heißt diese Abbildung innere Verknüpfung.
Halbgruppe
Eine Halbgruppe $H=(H,\circ )$ besteht aus einer Menge $H$ und einer inneren Verknüpfung $\circ :H\times H\to H,(a,b)\mapsto a\circ b,$ die assoziativ ist, d. h. für alle $a,b,c\in H$ gilt $a\circ (b\circ c)=(a\circ b)\circ c$.
Gruppe
Eine Halbgruppe $H$, die ein neutrales Element besitzt und jedes Element der Halbgruppe invertierbar ist, heißt Gruppe.
Kommutative Gruppe
Eine Gruppe $G$ heißt kommutative Gruppe, wenn die zugehörige Halbgruppe $H$ kommutativ ist, d.h. $a,b\in H$ gilt: $a\circ b=b\circ a$.

$(R,+,\cdot )$ heißt Ring, wenn für die Menge $R$ mit den zwei inneren Verknüpfungen $+$ und $\cdot$ gilt

• $(R,+)$ eine kommutative Gruppe ist,
• $(R,\cdot )$ eine Halbgruppe ist,
• die Distributivgesetze gelten für alle $a,b,c\in R$, d.h.
  • $a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und $(a+b)\cdot c=(a\cdot c)+(b\cdot c)$

Lernaufgabe

Aufgabe

Beweisen Sie die Assoziativität von $(\mathbb{Z}/m\mathbb{Z},\odot )$.

Bemerkung: Sie zeigen somit, dass $(\mathbb{Z}/m\mathbb{Z},\odot )$ eine Halbgruppe ist.

Lösung

Nach Definition muss für die Assoziativität gelten: Für alle $a,b,c\in G:a\circ (b\circ c)=(a\circ b)\circ c$. Übertragen auf die Menge $(\mathbb{Z}/m\mathbb{Z},\odot )$ bedeutet dies: Für alle $[a{]}_m,[b{]}_m,[c{]}_m\in \mathbb{Z}/m\mathbb{Z}:[a{]}_m\odot ([b{]}_m\odot [c{]}_m)=([a{]}_m\odot [b{]}_m)\odot [c{]}_m$. Wir beginnen mit der linken Seite der Gleichung: $[a{]}_m\odot ([b{]}_m\odot [c{]}_m)$ $=[a{]}_m\odot [b\cdot c{]}_m$, nach Definition Multiplikation in $\mathbb{Z}/m\mathbb{Z}$ $=[a\cdot (b\cdot c){]}_m$, nach Definition Multiplikation in $\mathbb{Z}/m\mathbb{Z}$ $=[(a\cdot b)\cdot c{]}_m$, Assoziativgesetz in $\mathbb{Z}$ $=[(a\cdot b){]}_m\odot [c{]}_m$, nach Definition Multiplikation in $\mathbb{Z}/m\mathbb{Z}$ $=([a{]}_m\odot [b{]}_m)\odot [c{]}_m$, nach Definition Multiplikation in $\mathbb{Z}/m\mathbb{Z}$ Insgesamt haben wir somit die Assoziativität von $(\mathbb{Z}/m\mathbb{Z},\odot )$ gezeigt und somit auch, dass $(\mathbb{Z}/m\mathbb{Z},\odot )$ eine Halbgruppe ist■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4.5: Restklassen	4.6: (Halb-)Gruppen und Ringe	4.7: Restklassenring