Kryptologie/Kongruenzen

Aus Wikiversity


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 und , dann gilt:

  • Zwei Zahlen und heißen kongruent modulo , wenn die Differenz teilt.
  • Zwei Zahlen und heißen inkongruent modulo , wenn die Differenz nicht teilt.

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

  • [4][5]

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

Beispiel Kongruenz

Beispiel (kongruent)

Seien , und .

und heißen kongruent modulo , wenn gilt.

Nach Definition der Teilbarkeit gilt mit .

Wegen folgt:

für .

Somit sind und kongruent modulo bzw. formal:

.


Beispiel (inkongruent)

Seien , und .

und heißen kongruent modulo , falls gilt.

Nach Definition der Teilbarkeit müsste dann mit geeignet sein.

Wegen folgt:

für , aber .

Somit sind und inkongruent modulo bzw. formal:

.

Satz zu wichtige Eigenschaften der Kongruenz

Seien und . Es gelten folgende Folgerungen zum modulo :

: ,

: und ,

: und [7].

Beweis Satz zu wichtige Eigenschaften der Kongruenz

Zu :

Kongruenz und Lemma der Teilbarkeit
Kongruenz
Seien und , dann gilt [5].
Lemma der Teilbarkeit:
Seien , dann gilt: [8].

Voraussetzung

Sei mit und .

Zu zeigen

Aus folgt

Beweis

, nach Definition Kongruenz

, nach aus Satz 1 der Teilbarkeit

, nach Definition Kongruenz[7]

Zu :

Kongruenz und Lemma der Teilbarkeit
Kongruenz
Seien und , dann gilt [5].
Lemma der Teilbarkeit:
Seien , dann gilt: [7].

Voraussetzung

Seien , mit und .

Zu zeigen

und

Beweis

und

und , nach Definition Kongruenz

, nach aus Satz 1 der Teilbarkeit

, nach Definition Kongruenz[7]

Zu :

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 . Für alle gilt [9].
Symmetrie
Seien und . Wenn , dann gilt

[9].

Transitivität
Seien und . Wenn und ,

dann gilt [9].

Kongruenz
Seien und , dann gilt [5].

Beweisen Sie, dass die Kongruenz modulo 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 und

Zu zeigen

Für alle gilt

Beweis

, nach Definition der Kongruenz

Dies gilt offensichtlich für alle .■[9]

Symmetrie

Voraussetzung

Seien und .

Zu zeigen

Wenn , dann gilt

Beweis

, nach Definition der Kongruenz[9]

Lösung
Zur Reflexivität

Voraussetzung

Seien und

Zu zeigen

Für alle gilt

Beweis

, nach Definition der Kongruenz

, was offensichtlich gilt.■[9]

Transitivität
Zur Transitivität

Voraussetzung

Seien und .

Zu zeigen

Wenn und , dann gilt

Beweis

, nach Definition der Kongruenz

und

Nun folgt

[9]

Aufgabe 2

Kongruenz und Teilbarkeit
Kongruenz
Seien und , dann gilt [5].
Teilbarkeit
Eine ganze Zahl teilt eine ganze Zahl genau dann, wenn es eine

ganze Zahl gibt, für die ist.

Wir schreiben [11][12].

Beweisen Sie, dass für und gilt:

und [7].

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

Lösung
Voraussetzung

Seien , mit und .

Zu zeigen

und

Nach Voraussetzung gilt

und

und , nach Definition Kongruenz

und , nach Definition Teilbarkeit mit geeignete

und

, nach Definition Teilbarkeit, da

, 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

  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)
  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.
  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.
  8. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 23.
  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.
  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)
  12. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.