Kryptologie/Erweiterter euklidischer Algorithmus


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.