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. |
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 |
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:
- Berechnung des (auch als euklidischer Algorithmus bekannt[9])
- 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, |
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
Ü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
- ↑ Buchmann, J. (2016). Einführung in die Kryptographie (6. Aufl.). Berlin, Heidelberg: Springer. S. 37.
- ↑ 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.
- ↑ 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.
- ↑ 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,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)
- ↑ Forster, O. (2015). Algorithmische Zahlentheorie (2., überarbeitete und erweiterte Auflage). Springer Spektrum. S. 45.
- ↑ 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.
- ↑ Lehman, E., Leighton, T., & Meyer, A. R. (2010). Mathematics for computer science. Technical report, 2006. Lecture notes. S. 249.
- ↑ Kurzweil, H. (2008). Endliche Körper: Verstehen, rechnen, anwenden (2., überarb. Aufl). Springer. S. 57.
- ↑ 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.
- ↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 30.
- ↑ 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)
- ↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag. S. 19.
- ↑ 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.
- ↑ Burton, D. M., & Dalkowski, H. (2005). Handbuch der elementaren Zahlentheorie mit über 1000 Übungsaufgaben und ihren Lösungen. Heldermann Verlag, S. 31f.
- ↑ 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)
- ↑ Ziegenbalg, J. (2015). Elementare Zahlentheorie: Beispiele, Geschichte, Algorithmen (2., überarb. Aufl). Springer Spektrum. S. 47.