Kryptologie/Erweiterter euklidischer Algorithmus

Aus Wikiversity


Einleitung

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

ganze Zahl gibt, für die ist.

Wir schreiben [2][3].

Teilerfremdheit
Zwei ganze Zahlen und , wobei mindestens einer der beiden Zahlen ungleich Null ist,

heißen teilerfremd, wenn [4]. Betrachten wir mehr als zwei Zahlen, dann

nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen

zueinander teilerfremd sind[5][4].

Bei der Schlüsselerzeugung des RSA-Kryptosystems muss das multiplikative Inverse von mit bestimmt werden. Wir können hierzu den erweiterten euklidischen Algorithmus nutzen, denn dieser berechnet das multiplikative Inverse in ganzzahligen Restklassenringen[6][7].

In einem ersten Schritt bestimmt der Algorithmus hierfür den größten gemeinsamen Teiler zweier natürlicher Zahlen und . Anschließend werden in einem zweiten Schritt zwei ganze Zahlen und , welche die folgende Gleichung erfüllen[6]:

[6].

Angewandt auf das RSA-Verschlüsselungsverfahren können wir so das multiplikative Inverse von bestimmen, da wir in umformen können[8].

Die Umformung erfolgt mittels Definition von Kongruenz und Teilbarkeit:

, nach Definition der Kongruenz

, nach Definition der Teilbarkeit

, wobei nach Voraussetzung des RSA-Kryptosystem teilerfremd zu

Erweiterter Euklidischer Algorithmus

Der erweiterte euklidische Algorithmus wird auf zwei Zahlen angewandt und besteht aus zwei Teilen:

  1. Berechnung des (auch als euklidischer Algorithmus bekannt[9])
  2. Berechnung zweier ganzer Zahlen und , welche die Gleichung erfüllen[10]

Zu Teil 1: Berechnung des

Größte gemeinsame Teiler, Lemma 1 des ,

Division mit Rest und Lemma 2 des

Größte gemeinsame Teiler
Seien , wobei mindestens eine der beiden Zahlen ungleich Null.

Wir bezeichnen mit als den größten gemeinsamen

Teiler der Zahlen und , falls gilt:

: und

und

: Für alle mit und [11].

Lemma 1 des
Seien , wobei nicht . Es gilt [12].
Division mit Rest
Seien mit eindeutig bestimmte Zahlen und gibt,

für die gilt: [13][14].

Lemma 2 des
Seien und , dann folgt: [15].

Betrachten wir zunächst die Berechnung des .

Wir haben bei der formalen Einführung des bereits gezeigt, dass nach Lemma 1 des und setzen daher voraus, dass gilt.

Wir können die Division mit Rest auf und anwenden und erhalten

, mit .

Nun unterscheiden wir zwei Fälle:

  • , dies ist die Abbruchbedingung und wir sind mit Teil 1 fertig
  • und wir müssen fortfahren.

Im ersten Fall teilt die Zahl die Zahl mit , es gilt und wir sind mit dem ersten Teil des erweiterten euklidischen Algorithmus fertig.

Im zweiten Fall wenden wir die Division mit Rest auf und an und erhalten mit . Es ergeben sich erneut zwei Fälle: und .

Tritt der erste Fall "Rest der Gleichung ist Null" ein, so verfahren wir analog zum und erhalten den gesuchten mit , da nach Lemma 2 des gilt: .

Andernfalls verfahren wir analog zu dem obigen Fall .

Wir folgen diesem Schema -mal, bis wir ein mit berechnen und das Verfahren abgebrochen wird.

Somit erhalten wir [16].

Dies lässt sich besonders gut anhand eines Beispiels nachvollziehen.

Beispiel Berechnung des

Seien und .

Nach der Division mit Rest gilt:

Gleichung 1: , Fall

Gleichung 2: , Fall

Gleichung 3: , Fall

Es gilt .

Zu Teil 2: Berechnung der ganzzahligen Koeffizienten und

Größte gemeinsame Teiler, Lemma von Bézout
Größte gemeinsame Teiler
Seien , wobei mindestens eine der beiden Zahlen ungleich Null.

Wir bezeichnen mit als den größten gemeinsamen

Teiler der Zahlen und , falls gilt:

: und

und

: Für alle mit und [11].

Lemma von Bézout
Für alle existieren , sodass gilt: [17][18].

Aus der Berechnung des wissen wir, dass

für Durchführungen und

oder

für Durchführungen

des Schemas aus Teil 1 ist.

Es gilt nach dem Lemma von Bézout .

Wurde zur Berechnung des nur die Gleichung benötigt, so ist und wir können die ganzzahligen Koeffizienten und aus der Gleichung ablesen.

Andernfalls müssen wir durch das Einsetzen der Informationen aus den Gleichungen, die man bei der Berechnung des berechnet hat, die Gleichung erzeugen.

Allgemein ergeben sich drei Fälle:

  • die Gleichung enthält und in der Form bzw. wird in diese Form umgestellt
  • die Gleichung beinhaltet genau einen der beiden vorausgesetzten Zahlen und
  • die Gleichung enthält weder noch .

Im ersten Fall sind die ganzzahligen Koeffizienten der Zahlen bzw. genau bzw. und können, nach geeigneter Umstellung, in die Form abgelesen werden. Das Verfahren wird daraufhin abgebrochen.

Im zweiten Fall kann der ganzzahlige Koeffizient der vorhanden Zahl bzw. genau bzw. noch nicht abgelesen werden, da die Informationen zur fehlenden Zahl bzw. sich auf die den Koeffizienten der vorhanden Zahl bzw. auswirken können. Die vorhandene Zahl wird stattdessen "nur" beibehalten und nicht durch andere Informationen ersetzt. Der fehlende gesuchte Koeffizient muss durch erneutes Einsetzten von Informationen aus vorherigen Gleichungen aus Teil 1 bestimmt werden, wobei die bereits vorhandene Zahl bzw. nicht weiter durch Informationen ersetzt werden muss.

Im letzten Fall müssen wir die in der Gleichung enthalten Reste aus den vorherigen Gleichungen aus Teil 1 erneut einsetzen[15].

Wir veranschaulichen das Vorgehen anhand eines Beispiels.

Beispiel Berechnung der ganzzahligen Koeffizienten und

Berechnung der Faktoren und mit .

Wir wissen aus dem obigen Beispiel zu Teil 1, dass gilt:

und wir wissen nach Gleichung 2 aus Teil 1, dass gilt:

Da wir die Gleichung nach umformen wollen, muss der zunächst alleine auf einer Seite stehen

, Fall

, Fall

, Fall mit Umformung

Nun können wir die Koeffizienten und ablesen.

Zur Veranschaulichung führen wir noch die Probe durch:

.

Lernaufgabe

Aufgabe

Wenden Sie den erweiterten euklidischen Algorithmus auf und an.

Bemerkung: Wir nutzen diese Rechnung im Beispiels der Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens.

Lösung
Wir wenden den erweiterten euklidischen Algorithmus auf das Beispiel zur Schlüsselgenerierung des RSA-Verschlüsselungsverfahrens an.

Berechnung

Nach der Division mit Rest gilt:

Gleichung 1: , Fall

Gleichung 2: , Fall

Gleichung 3: , Fall

Gleichung 4: , Fall

Gleichung 5: , Fall

Es gilt .

Berechnung der Faktoren und mit

Da wir die Gleichung nach umformen wollen, muss der zunächst alleine auf einer Seite stehen

, Fall

, Fall , da nach Gleichung 3 aus Teil 1

, Fall

, Fall , da nach Gleichung 2 aus Teil 1 mit

, da , Fall

, Fall da nach Gleichung 1 aus Teil 1

, durch Umformung

, Fall

und

Probe

Lernempfehlung

Kursübersicht
Übergeordnete Lerneinheit
7.1: Schlüsselerzeugung des RSA-Verschlüsselungsverfahrens
Vorherige Lerneinheit Aktuelle Lerneinheit Empfohlene Lerneinheit
7.1.4: Miller-Rabin-Test (Primzahltest 3) 7.1.5: Erweiterter euklidischer Algorithmus 7.1.6: Eulersche φ-Funktion

Literatur

  1. Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
  2. 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)
  3. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. 22f.
  4. 4,0 4,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 26.
  5. Seite „Teilerfremdheit“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 26. September 2019, 13:33 UTC. URL: https://de.wikipedia.org/w/index.php?title=Teilerfremdheit&oldid=192615323 (Abgerufen: 10. Januar 2020, 13:56 UTC; Formulierung verändert)
  6. 6,0 6,1 6,2 Seite „Erweiterter euklidischer Algorithmus“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 20. Dezember 2018, 08:34 UTC. URL: https://de.wikipedia.org/w/index.php?title=Erweiterter_euklidischer_Algorithmus&oldid=183868594 (Abgerufen: 30. Dezember 2019, 14:06 UTC; Formulierung verändert)
  7. Forster, O. (2015). Algorithmische Zahlentheorie (2., überarbeitete und erweiterte Auflage). Springer Spektrum. S. 45.
  8. 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. 124.
  9. Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
  10. Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
  11. 11,0 11,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Lemgo: Heldermann Verlag. S. 24.
  12. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 30.
  13. Seite „Division mit Rest“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 24. Januar 2020, 18:50 UTC. URL: https://de.wikipedia.org/w/index.php?title=Division_mit_Rest&oldid=196144598 (Abgerufen: 2. Februar 2020, 14:22 UTC; Formulierung verändert)
  14. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 19.
  15. 15,0 15,1 Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 32.
  16. Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag, S. 31f.
  17. Seite „Lemma von Bézout“. In: Wikipedia, Die freie Enzyklopädie. Bearbeitungsstand: 11. Oktober 2019, 09:53 UTC. URL: https://de.wikipedia.org/w/index.php?title=Lemma_von_B%C3%A9zout&oldid=193035164 (Abgerufen: 6. Januar 2020, 13:39 UTC; Formulierung verändert)
  18. Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 47.