Kryptologie/Kongruenzen

Einleitung

Das Caesar- und das RSA-Kryptosystem basieren auf der Kongruenz zwischen ganzen Zahlen^[1]^[2]. 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^[3]. Kongruenzen werden uns auf fast jeder Seite zum RSA-Kryptosystem begegnen.

Kongruenz

Definition Kongruenz

Seien $a, b \in ℤ$ und $m \in ℕ$ , 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 mod m \Leftrightarrow m ∣ (a - b)$

$a \equiv̸ b mod m \Leftrightarrow m ∤ (a - b)$ ^[4]^[5]

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

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 ∣ (3 - 5)$ gilt.

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

Wegen $3 - 5 = - 2$ folgt:

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

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

$2 ∣ (3 - 5) \Leftrightarrow$ $3 \equiv 5 mod 2$ .

Beispiel (inkongruent)

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

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

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

Wegen $3 - 5 = - 2$ folgt:

$3 \cdot k = - 2$ für $k = - \frac{2}{3}$ , aber $- \frac{2}{3} = k \in̸ ℤ$ .

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

$2 ∤ (3 - 5) \Leftrightarrow$ $3 \equiv̸ 5 mod 3$ .

Satz zu wichtige Eigenschaften der Kongruenz

Seien $a, b, c, d \in ℤ$ und $m \in ℕ$ . Es gelten folgende Folgerungen zum modulo $m$ :

$(1)$ : $a \equiv b mod m \Rightarrow$ $- a \equiv - b mod m$ ,

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

$(3)$ : $a \equiv b mod m$ und $c \equiv d mod m \Rightarrow$ $a c \equiv b d mod m$ ^[7].

Beweis Satz zu wichtige Eigenschaften der Kongruenz

Zu $(1)$ :

Kongruenz und Lemma der Teilbarkeit
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].
Lemma der Teilbarkeit: $(2)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ 1 \Leftrightarrow a = \pm 1$ ^[8].

Voraussetzung

Sei $a \equiv b mod m$ mit $a, b, \in ℤ$ und $m \in ℕ$ .

Zu zeigen

Aus $a \equiv b mod m$ folgt $- a \equiv - b mod m$

Beweis

$a \equiv b mod m$

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

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

$\Leftrightarrow - a \equiv - b mod m$ , nach Definition Kongruenz ■^[7]

Zu $(2)$ :

Kongruenz und Lemma der Teilbarkeit
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].
Lemma der Teilbarkeit: $(1)$
Seien $a, b, c, d, m \in ℤ$ , dann gilt: $a ∣ b \Leftrightarrow a ∣ (- b)$ ^[7].

Voraussetzung

Seien $a \equiv b mod m$ , $c \equiv d mod m$ mit $a, b, c, d \in ℤ$ und $m \in ℕ$ .

Zu zeigen

$a \equiv b mod m$ und $c \equiv d mod m \Rightarrow$ $a + c \equiv b + d mod m$

Beweis

$a \equiv b mod m$ und $c \equiv d mod m$

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

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

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

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

$\Leftrightarrow a + c \equiv b + d mod m$ , nach Definition Kongruenz ■^[7]

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 ℕ$ . Für alle $a \in ℤ$ gilt $a \equiv a mod m$ ^[9].
Symmetrie
Seien $a, b \in ℤ$ und $m \in ℕ$ . Wenn $a \equiv b mod m$ , dann gilt $b \equiv a mod m$ ^[9].
Transitivität
Seien $a, b \in ℤ$ und $m \in ℕ$ . Wenn $a \equiv b mod m$ und $b \equiv c mod m$ , dann gilt $a \equiv c mod m$ ^[9].
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].

Beweisen Sie, dass die Kongruenz modulo $m$ auf der Menge $ℤ$ reflexiv, symmetrisch und transitiv ist^[10]. 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 ℕ$ und $a \in ℤ$

Zu zeigen

Für alle $a \in ℤ$ gilt $a \equiv a mod m$

Beweis

$a \equiv a mod m$

$\Leftrightarrow m ∣ (a - a)$ , nach Definition der Kongruenz

Dies gilt offensichtlich für alle $a \in ℤ$ .■^[9]

Symmetrie

Voraussetzung

Seien $a, b \in ℤ$ und $m \in ℕ$ .

Zu zeigen

Wenn $a \equiv b mod m$ , dann gilt $b \equiv a mod m$

Beweis

$a \equiv b mod m$

$\Leftrightarrow m ∣ (a - b)$

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

$\Leftrightarrow m ∣ - a + b$

$\Leftrightarrow m ∣ b - a$

$\Leftrightarrow b \equiv a mod m$ , nach Definition der Kongruenz■^[9]

Lösung

Zur Reflexivität

Voraussetzung

Seien $m \in ℕ$ und $a \in ℤ$

Zu zeigen

Für alle $a \in ℤ$ gilt $a \equiv a mod m$

Beweis

$a \equiv a mod m$

$\Leftrightarrow m ∣ (a - a)$ , nach Definition der Kongruenz

$\equiv m ∣ 0$ , was offensichtlich gilt.■^[9]

Transitivität

Zur Transitivität

Voraussetzung

Seien $a, b \in ℤ$ und $m \in ℕ$ .

Zu zeigen

Wenn $a \equiv b mod m$ und $b \equiv c mod m$ , dann gilt $a \equiv c mod m$

Beweis

$a \equiv b mod m$

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

und

$b \equiv c mod m$

$\Leftrightarrow m ∣ (b - c)$

Nun folgt

$\Leftrightarrow m ∣ (a - b) + (b - c)$

$\Leftrightarrow m ∣ (a - c)$

$\Leftrightarrow a \equiv c mod m$ ■^[9]

Aufgabe 2

Kongruenz und Teilbarkeit
Kongruenz
Seien $a, b \in ℤ$ und $m \in ℕ$ , dann gilt $a \equiv b mod m \Leftrightarrow m ∣ (a - b)$ ^[5].
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 ∣ b$ ^[11]^[12].

Beweisen Sie, dass für $a, b, c, d \in ℤ$ und $m \in ℕ$ gilt:

$a \equiv b mod m$ und $c \equiv d mod m \Rightarrow$ $a c \equiv b d mod m$ ^[7].

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

Lösung
Voraussetzung Seien $a \equiv b mod m$ , $c \equiv d mod m$ mit $a, b, c, d \in ℤ$ und $m \in ℕ$ . Zu zeigen $a \equiv b mod m$ und $c \equiv d mod m \Rightarrow$ $a c \equiv b d mod m$ Nach Voraussetzung gilt $a \equiv b mod m$ und $c \equiv d mod m$ $\Leftrightarrow m ∣ (a - b)$ und $m ∣ (c - d)$ , nach Definition Kongruenz $\Leftrightarrow m l = a - b$ und $m k = c - d$ , nach Definition Teilbarkeit mit geeignete $k, l \in ℤ$ $\Leftrightarrow m l + b = a$ und $m k + d = c$ $\Rightarrow (m l + b) \cdot (m k + d) = a c$ $\Leftrightarrow m^{2} l k + m l d + b m k + b d = a c$ $\Leftrightarrow b d + m (l d + b k + l k m) = a c$ $\Leftrightarrow m (l d + b k + l k m) = a c - b d$ $\Leftrightarrow m ∣ (a c - b d)$ , nach Definition Teilbarkeit, da $(l d + b k + l k m) \in ℤ$ $\Leftrightarrow a c \equiv b d mod m$ , nach Definition Kongruenz ■^[7]

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

Literatur

↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 75.
↑ Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 122.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 75.
↑ „Kongruenz (Zahlentheorie)“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 6. Dezember 2019, 12:31 UTC. URL: https://de.wikipedia.org/w/index.php?title=Kongruenz_(Zahlentheorie)&oldid=194679801 (Abgerufen: 6. Dezember 2019, 12:36 UTC; Formulierung verändert)
↑ ^5,0 ^5,1 ^5,2 ^5,3 ^5,4 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
↑ Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.
↑ ^7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 39.
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.
↑ ^9,0 ^9,1 ^9,2 ^9,3 ^9,4 ^9,5 ^9,6 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 157.
↑ Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 156.
↑ Seite „Teilbarkeit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 15:44 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilbarkeit&oldid=194364839 (Abgerufen: 12. Dezember 2019, 14:43 UTC; Formulierung verändert)
↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.

[1] Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Springer. S. 75.

[2] Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) (S. 120–126). S. 122.

[3] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 75.

[4] „Kongruenz (Zahlentheorie)“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 6. Dezember 2019, 12:31 UTC. URL: https://de.wikipedia.org/w/index.php?title=Kongruenz_(Zahlentheorie)&oldid=194679801 (Abgerufen: 6. Dezember 2019, 12:36 UTC; Formulierung verändert)

[:33-5] 5,0 ^5,1 ^5,2 ^5,3 ^5,4 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.

[6] Shoup, V. (2008). A Computational Introduction to Number Theory and Algebra (2. Aufl.). S. 23.

[:1-7] 7,0 ^7,1 ^7,2 ^7,3 ^7,4 ^7,5 Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 39.

[:08-8] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.

[:0-9] 9,0 ^9,1 ^9,2 ^9,3 ^9,4 ^9,5 ^9,6 Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 157.

[10] Reiss, K., & Schmieder, G. (2014). Basiswissen Zahlentheorie: Eine Einführung in Zahlen und Zahlbereiche (3. Aufl.). Springer Spektrum. S. 156.

[:12-11] Seite „Teilbarkeit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 25. November 2019, 15:44 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilbarkeit&oldid=194364839 (Abgerufen: 12. Dezember 2019, 14:43 UTC; Formulierung verändert)

[:22-12] Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Kryptologie/Kongruenzen

Inhaltsverzeichnis

Einleitung

Kongruenz

Definition Kongruenz

Beispiel Kongruenz

Satz zu wichtige Eigenschaften der Kongruenz

Beweis Satz zu wichtige Eigenschaften der Kongruenz

Lernaufgabe

Aufgabe 1

Aufgabe 2

Lernempfehlung

Literatur

Navigationsmenü

Kryptologie/Kongruenzen

Einleitung

Kongruenz

Definition Kongruenz

Beispiel Kongruenz

Satz zu wichtige Eigenschaften der Kongruenz

Beweis Satz zu wichtige Eigenschaften der Kongruenz

Lernaufgabe

Aufgabe 1

Aufgabe 2

Lernempfehlung

Literatur

Navigationsmenü

Suche