Kryptologie/Kongruenzen

Einleitung

Das Caesar- und das RSA-Kryptosystem basieren auf der Kongruenz zwischen ganzen Zahlen. Dies ist eine mathematische Beziehung, die die Differenz zweier ganzen Zahlen misst und dieser Differenz eine natürliche Zahl zuordnet, deren Vielfaches der Differenz entspricht. Kongruenzen werden uns auf fast jeder Seite zum RSA-Kryptosystem begegnen.

Kongruenz

Definition Kongruenz

Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt:

• Zwei Zahlen $a$ und $b$ heißen kongruent modulo $m$, wenn $m$ die Differenz $a-b$ teilt.

• Zwei Zahlen $a$ und $b$ heißen inkongruent modulo $m$, wenn $m$ die Differenz $a-b$ nicht teilt.

Unter Verwendung der mathematischen Notation lassen sich diese beiden Aussagen wie folgt schreiben:

• $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$

• $a\not \equiv b{\bmod {m}}\Leftrightarrow m\nmid (a-b)$

Bemerkung: Um Kongruenzen in späteren Beweisen nutzen zu können, müssen wir noch einige Eigenschaften der Kongruenz modulo $m$ zeigen (siehe Aufgabe).

Beispiel Kongruenz

Beispiel (kongruent)

Seien $a=3$, $b=5$ und $m=2$.

$a=3$ und $b=5$ heißen kongruent modulo $m=2$, wenn $2\mid (3-5)$ gilt.

Nach Definition der Teilbarkeit gilt $m\cdot k=(a-b)=2\cdot k=(3-5)$ mit $k\in \mathbb {Z}$.

Wegen $3-5=-2$ folgt:

$2\cdot k=-2$ für $k=-1$.

Somit sind $3$ und $5$ kongruent modulo $2$ bzw. formal:

$2\mid (3-5)\Leftrightarrow$ $3\equiv 5{\bmod {2}}$.

Beispiel (inkongruent)

Seien $a=3$, $b=5$ und $m=3$.

$a=3$ und $b=5$ heißen kongruent modulo $m=3$, falls $3\mid (3-5)$ gilt.

Nach Definition der Teilbarkeit müsste dann $3\cdot k=(3-5)$ mit $k\in \mathbb {Z}$ geeignet sein.

Wegen $3-5=-2$ folgt:

$3\cdot k=-2$ für $k=-{\frac {2}{3}}$, aber $-{\frac {2}{3}}=k\not \in \mathbb {Z}$.

Somit sind $3$ und $5$ inkongruent modulo $2$ bzw. formal:

$2\not \mid (3-5)\Leftrightarrow$ $3\not \equiv 5{\bmod {3}}$.

Satz zu wichtige Eigenschaften der Kongruenz

Seien $a,b,c,d\in \mathbb {Z}$ und $m\in \mathbb {N}$. Es gelten folgende Folgerungen zum modulo $m$:

$(1)$: $a\equiv b{\bmod {m}}\Rightarrow$ $-a\equiv -b{\bmod {m}}$,

$(2)$: $a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}\Rightarrow$ $a+c\equiv b+d{\bmod {m}}$,

$(3)$: $a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}\Rightarrow$ $ac\equiv bd{\bmod {m}}$.

Beweis Satz zu wichtige Eigenschaften der Kongruenz

Zu $(1)$:

Kongruenz und Lemma der Teilbarkeit
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Lemma der Teilbarkeit: $(2)$
Seien $a,b,c,d,m\in \mathbb {Z}$, dann gilt: $a\mid 1\Leftrightarrow a=\pm 1$.

Voraussetzung

Sei $a\equiv b{\bmod {m}}$ mit $a,b,\in \mathbb {Z}$ und $m\in \mathbb {N}$.

Zu zeigen

Aus $a\equiv b{\bmod {m}}$ folgt $-a\equiv -b{\bmod {m}}$

Beweis

$a\equiv b{\bmod {m}}$

$\Leftrightarrow m\mid (a-b)$, nach Definition Kongruenz

$\Rightarrow m\mid (-a+b)$, nach $(2)$ aus Satz 1 der Teilbarkeit

$\Leftrightarrow -a\equiv -b{\bmod {m}}$, nach Definition Kongruenz ■

Zu $(2)$:

Kongruenz und Lemma der Teilbarkeit
Kongruenz
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow m\mid (a-b)$.
Lemma der Teilbarkeit: $(1)$
Seien $a,b,c,d,m\in \mathbb {Z}$, dann gilt: $a\mid b\Leftrightarrow a\mid (-b)$.

Voraussetzung

Seien $a\equiv b{\bmod {m}}$, $c\equiv d{\bmod {m}}$ mit $a,b,c,d\in \mathbb {Z}$ und $m\in \mathbb {N}$.

Zu zeigen

$a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}\Rightarrow$ $a+c\equiv b+d{\bmod {m}}$

Beweis

$a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}$

$\Leftrightarrow m\mid (a-b)$ und $m\mid (c-d)$, nach Definition Kongruenz

$\Rightarrow m\mid (a-b+c-d)$, nach $(3)$ aus Satz 1 der Teilbarkeit

$\Leftrightarrow m\mid (a+c-b-d)$

$\Leftrightarrow m\mid (a+c)-(b+d)$

$\Leftrightarrow a+c\equiv b+d{\bmod {m}}$, nach Definition Kongruenz ■

Zu $(3)$:

Den Beweis können Sie in der Lernaufgabe eigenständig führen.

Lernaufgabe

Aufgabe 1

Reflexivität, Symmetrie, Transitivität und Kongruenz
Reflexivität
Seien $m\in \mathbb {N}$. Für alle $a\in \mathbb {Z}$ gilt $a\equiv a{\bmod {m}}$.
Symmetrie
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$. Wenn $a\equiv b{\bmod {m}}$, dann gilt $b\equiv a{\bmod {m}}$.
Transitivität
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$. Wenn $a\equiv b{\bmod {m}}$ und $b\equiv c{\bmod {m}}$, dann gilt $a\equiv c{\bmod {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)$.

Beweisen Sie, dass die Kongruenz modulo $m$ auf der Menge $\mathbb {Z}$ reflexiv, symmetrisch und transitiv ist. Beweisen Sie hierfür zunächst die Reflexivität und erklären Sie dann den Beweis zur Symmetrie anhand von Kommentaren. Beweisen Sie anschließend die Transitivität selbstständig.

Reflexivität
Zur Reflexivität Voraussetzung Seien $m\in \mathbb {N}$ und $a\in \mathbb {Z}$ Zu zeigen Für alle $a\in \mathbb {Z}$ gilt $a\equiv a{\bmod {m}}$ Beweis $a\equiv a{\bmod {m}}$ $\Leftrightarrow m\mid (a-a)$, nach Definition der Kongruenz Dies gilt offensichtlich für alle $a\in \mathbb {Z}$.■

Symmetrie

Voraussetzung

Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$.

Zu zeigen

Wenn $a\equiv b{\bmod {m}}$, dann gilt $b\equiv a{\bmod {m}}$

Beweis

$a\equiv b{\bmod {m}}$

$\Leftrightarrow m\mid (a-b)$

$\Leftrightarrow m\mid -(a-b)$

$\Leftrightarrow m\mid -a+b$

$\Leftrightarrow m\mid b-a$

$\Leftrightarrow b\equiv a{\bmod {m}}$, nach Definition der Kongruenz■

Lösung
Zur Reflexivität Voraussetzung Seien $m\in \mathbb {N}$ und $a\in \mathbb {Z}$ Zu zeigen Für alle $a\in \mathbb {Z}$ gilt $a\equiv a{\bmod {m}}$ Beweis $a\equiv a{\bmod {m}}$ $\Leftrightarrow m\mid (a-a)$, nach Definition der Kongruenz $\equiv m\mid 0$, was offensichtlich gilt.■

Transitivität

Zur Transitivität Voraussetzung Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$. Zu zeigen Wenn $a\equiv b{\bmod {m}}$ und $b\equiv c{\bmod {m}}$, dann gilt $a\equiv c{\bmod {m}}$ Beweis $a\equiv b{\bmod {m}}$ $\Leftrightarrow m\mid (a-b)$, nach Definition der Kongruenz und $b\equiv c{\bmod {m}}$ $\Leftrightarrow m\mid (b-c)$ Nun folgt $\Leftrightarrow m\mid (a-b)+(b-c)$ $\Leftrightarrow m\mid (a-c)$ $\Leftrightarrow a\equiv c{\bmod {m}}$■

Aufgabe 2

Kongruenz und Teilbarkeit
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$.

Beweisen Sie, dass für $a,b,c,d\in \mathbb {Z}$ und $m\in \mathbb {N}$ gilt:

$a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}\Rightarrow$ $ac\equiv bd{\bmod {m}}$.

Nutzen Sie hierfür die Definitionen aus dem rechten Kasten und formen Sie mehrmals um.

Lösung

Voraussetzung Seien $a\equiv b{\bmod {m}}$, $c\equiv d{\bmod {m}}$ mit $a,b,c,d\in \mathbb {Z}$ und $m\in \mathbb {N}$. Zu zeigen $a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}\Rightarrow$ $ac\equiv bd{\bmod {m}}$ Nach Voraussetzung gilt $a\equiv b{\bmod {m}}$ und $c\equiv d{\bmod {m}}$ $\Leftrightarrow m\mid (a-b)$ und $m\mid (c-d)$, nach Definition Kongruenz $\Leftrightarrow ml=a-b$ und $mk=c-d$, nach Definition Teilbarkeit mit geeignete $k,l\in \mathbb {Z}$ $\Leftrightarrow ml+b=a$ und $mk+d=c$ $\Rightarrow (ml+b)\cdot (mk+d)=ac$ $\Leftrightarrow m^{2}lk+mld+bmk+bd=ac$ $\Leftrightarrow bd+m(ld+bk+lkm)=ac$ $\Leftrightarrow m(ld+bk+lkm)=ac-bd$ $\Leftrightarrow m\mid (ac-bd)$, nach Definition Teilbarkeit, da $(ld+bk+lkm)\in \mathbb {Z}$ $\Leftrightarrow ac\equiv bd{\bmod {m}}$, nach Definition Kongruenz ■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4.2: Größte gemeinsame Teiler	4.3: Kongruenzen	4.4: Division mit Rest