Kryptologie/Restklassen

Einleitung

Wie in einer vorherigen Lernaufgabe gezeigt werden konnte, handelt es sich bei der Kongruenz modulo $m$ um eine Äquivalenzrelation. Äquivalenzrelationen teilen Mengen in elementfremde Untermengen ein. Diese Untermengen nennt man Äquivalenzklasse. Die Äquivalenzklasse einer ganzen Zahl $a$ bei Kongruenz modulo $m$ heißt Restklasse einer Zahl $a$ modulo einer Zahl $m$. Beide im Kurs behandelten Kryptosysteme nutzen Restklassen zur Ver- und Entschlüsselung. Wir betrachten diese daher hier näher.

Restklassen

Definition Restklassen

Wir bezeichnen $[a]_{m}$ als Restklasse einer Zahl $a\in \mathbb {Z}$ modulo einer Zahl $m\in \mathbb {N}$, die Menge aller ganzen Zahlen, die den gleichen Rest bei Division durch $m$ aufweisen wie $a$.

Formal schreibt man:

$[a]_{m}:=\{b\in \mathbb {Z} \mid {\text{ es existiert ein }}k\in \mathbb {Z} :b=k\cdot m+a\}=\{b\mid b\equiv a{\bmod {m}}\}$.

Beispiel Restklassen

Restklassen modulo 4:

$[0]_{4}=\{...,-12,-8,-4,0,4,8,12,...\}$

$[1]_{4}=\{...,-11,-7,-3,1,5,9,13,...\}$

$[2]_{4}=\{...,-10,-6,-2,2,6,10,14,...\}$

$[3]_{4}=\{...,-9,-5,-1,3,7,11,15,...\}$

Bemerkung

• Ein Element einer Restklasse nennen wir Repräsentant der Restklasse und wir nennen die Elemente $0,\dots ,m-1$ Standardrepräsentanten für die Restklassen modulo $m$.
• Die Menge aller Restklassen modulo $m$ bezeichnen wir als den Modul $\mathbb {Z} /m\mathbb {Z}$.

Bemerkung: Wir zeigen in einer anderen Lerneinheit, dass es sich beim Modul $\mathbb {Z} /m\mathbb {Z}$ um einen Ring mit $m$ Elementen handelt. Wir nennen diesen daher Restklassenring.

Addition und Multiplikation von Restklassen

Definition Addition und Multiplikation in $\mathbb {Z} /m\mathbb {Z}$

Restklasse, Innere Verknüpfung, Repräsentant, Kongruenz und Teilbarkeit
Restklasse
Sei $a\in \mathbb {Z}$ modulo einer Zahl $m\in \mathbb {Z}$ die Menge aller ganzen Zahlen, die den gleichen Rest bei Division durch $m$ aufweisen wie $a$. Dann ist $[a]_{m}=\{b\in \mathbb {Z} \mid b\equiv a{\bmod {m}}\}$ die Restklasse zu $a$.
Innere Verknüpfung
Sei $M$ eine Menge und $\circ :M\times M\rightarrow M$ eine Abbildung, die jedem Paar $(x,y)$ mit $x,y\in M$ ein Element $\in M$ $x\circ y$ zuordnet, so heißt diese Abbildung innere Verknüpfung.
Repräsentant (einer Restklasse)
Ein Element einer Restklasse nennen wir Repräsentant der Restklasse. Die Elemente $0,\dots ,m-1$ Standardrepräsentanten für die Restklassen modulo $m$.
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $k$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.

Sei $\mathbb {Z} /m\mathbb {Z}$ die Menge aller Restklassen modulo $m$. Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann definieren wir die folgende innere Verknüpfungen $\oplus$ und $\odot$ wie folgt:

$(1)$: $[a]_{m}\oplus [b]_{m}=[a+b]_{m}$

$(2)$: $[a]_{m}\odot [b]_{m}=[a\cdot b]_{m}$

Bemerkung: Die Definition von Addition und Multiplikation beinhaltet Repräsentanten der Restklassen. Wir zeigen daher nach dem Beispiel, dass es irrelevant ist, welche Repräsentanten man aus der Restklasse wählt. Addition und Multiplikation sind also unabhängig von den hier gewählten Repräsentanten.

Beispiel

Wähle $a=4,b=6$ und $m=10$.

Zu $(1)$:

$[a]_{m}\oplus [b]_{m}=[4]_{10}\oplus [6]_{10}=[4+6]_{10}=[10]_{10}=[0]_{10}$,

bzw. wenn man die Definition der Restklasse umschreibt:

$[a]_{m}\oplus [b]_{m}=[4]_{10}\oplus [6]_{10}=[4+6]_{10}=4+6{\bmod {1}}0\equiv 10{\bmod {1}}0\equiv 0{\bmod {1}}0$.

Zu $(2)$:

$[a]_{m}\odot [b]_{m}=[4]_{10}\odot [6]_{10}=[4\cdot 6]_{10}=[24]_{10}=[4]_{10}$,

bzw. wenn man die Definition der Restklasse umschreibt:

$[a]_{m}\odot [b]_{m}=[4]_{10}\odot [6]_{10}=[4\cdot 6]_{10}=4\cdot 6{\bmod {1}}0=24{\bmod {1}}0=4{\bmod {1}}0$.

Wir können jedoch zeigen, dass die Addition bzw. Multiplikation unabhängig von der Wahl der Repräsentanten ist:

Beweis Unabhängigkeit von Addition und Multiplikation von den Repräsentanten der Restklassen

Voraussetzung

Zu zeigen

Beweis

Seien $v_{1},v_{2}\in [v]_{m}$ und $w_{1},w_{2}\in [w]_{m}$.

Dann sind nach der Definition der Restklasse $v_{1}\equiv v_{2}{\bmod {m}}$ und $w_{1}\equiv w_{2}{\bmod {m}}$.

Nach der Kongruenz gilt daher: $v_{1}=v_{2}+k_{1}m$ und $w_{1}=w_{2}+k_{2}m$ mit $k_{1},k_{2}\in \mathbb {Z}$ geeignet.

Nun gilt für die Addition:

$[v_{1}]_{m}\oplus [w_{1}]_{m}$

$=[v_{1}+w_{1}]_{m}$

$=[(v_{2}+k_{1}m)+(w_{2}+k_{2}m)]_{m}$

$=[(v_{2}+w_{2})+m(k_{1}+k_{2})]_{m}$

$=[(v_{2}+w_{2})+m(k_{1}+k_{2})]_{m}$

$=[v_{2}+w_{2}]_{m}$, da jedes Vielfache $nm\equiv 0{\bmod {m}}$ mit $n\in \mathbb {Z}$

$=[v_{2}]_{m}\oplus [w_{2}]_{m}$

Analog gilt für die Multiplikation:

$[v_{1}]_{m}\odot [w_{1}]_{m}$

$=[v_{1}\cdot w_{1}]_{m}$

$=[(v_{2}+k_{1}m)\cdot (w_{2}+k_{2}m)]_{m}$

$=[v_{2}w_{2}+v_{2}k_{2}m+k_{1}mw_{2}+k_{1}k_{2}m^{2}]_{m}$

$=[v_{2}w_{2}+m(v_{2}k_{2}+k_{1}w_{2}+k_{1}k_{2}m)]_{m}$

$=[v_{2}\odot w_{2}]_{m}$, da jedes Vielfache $nm\equiv 0{\bmod {m}}$ mit $n\in \mathbb {Z}$

$=[v_{2}]_{m}\odot [w_{2}]_{m}$■

Bemerkung: Auch die Teilbarkeit in $\mathbb {Z} /m\mathbb {Z}$ wird analog zur Teilbarkeit (in $\mathbb {Z}$) definiert.

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4.4: Division mit Rest	4.5: Restklassen	4.6: (Halb-)Gruppen und Ringe