Mathematische Grundlagen: Unterschied zwischen den Versionen

Version vom 2. September 2010, 23:35 Uhr

Aber nun zu den mathematischen Grundlagen, die für RSA relevant sind.

Aufgabe:

Alice möchte Bob die Punktzahl ihrer letzten Matheklausur übersenden. Da sie nun weiß, dass ein Unbekannter ihre Nachrichten liest, versucht sie die Information so zu übersenden, dass Mallory die Punktzahl nicht herausfindet. Weil sie noch kein Verschlüsselungsverfahren einsetzt, versucht sie es wie folgt:
„Meine Punktzahl ist der größte gemeinsame Teiler der Zahlen 90 und 105.“
Und es funktioniert tatsächlich, Mallory, der Mathe immer gehasst hat, erkennt nicht, welche Punktzahl Alice erreicht hat.

Kannst du die Punktzahl von Alice ermitteln?

Den größten gemeinsamen Teiler (ggT) von natürlichen Zahlen hast du bereits in der 5.Klasse berechnet. Dazu hast du, wie in obigem Beispiel, Zahlen in ihre Primfaktoren zerlegt und daraus anschließend den ggT ermittelt. Das es zu jeder natürlichen Zahl n eine eindeutige Primfaktorzerlegung gibt, zeigt folgender Satz:

Satz 1.0 (Fundamentalsatz der elementaren Zahlentheorie oder Satz über die eindeutige Primfaktorzerlegung)
Jede natürliche Zahl n > 1 lässt sich auf eindeutige Weise in ein Produkt von Primfaktoren zerlegen.

Der größte gemeinsame Teiler ist allgemein wie folgt definiert:

Definition 1.1 Es seien . Die größte natürliche Zahl, die sowohl a als auch b teilt, heißt größter gemeinsamer Teiler und wird mit ggT(a,b) bezeichnet.

Es gibt eine effizientere Methode, als die Primfaktorzerlegung, um den ggT zweier natürlicher Zahlen zu bestimmen und damit die Punktzahl von Alice zu ermitteln. Diese Methode wird als Euklidischer Algorithmus bezeichnet, weil er ca. 300 v. Chr. von Euklid in seinem Buch „Elemente“ beschrieben wurde. Historiker vermuten jedoch, dass Euklid den Algorithmus nicht selbst entdeckt hat und schätzen die Entstehungszeit auf ca. 500 v. Chr.
Der Algorithmus beruht auf Division mit Rest.

Algorithmus 1.2 (Euklidischer Algorithmus) Es seien . Man bestimmt , so dass gilt:

Dann gilt ggT(a,b) =ggT(b,r).
Anschließend wendet man das Verfahren auf b und r an. Dies führt man so lange fort, bis man den ggT direkt bestimmen kann.

Für die Zahlen von Alice würde dies bedeuten:




In allgemeiner ausgeschriebener Form lautet der Euklidische Algorithmus:

Algorithmus 1.3 Es seien , ohne Beschränkung der Allgemeinheit* (oBdA.) sei (*da Analoges auch für gilt). Dann existieren eindeutig bestimmte Zahlen und mit




                                     
                                     
                                     



Folglich bricht das Verfahren nach endlich vielen Schritten ab, es gilt ggT(a,b)= . Denn aus der ersten Gleichung folgt ggT(a,b)=ggT(b, ), aus der zweiten ggT(b, )=ggT(, ), usw. aus der letzten Gleichung folgt ggT(, ) = ggT (, ) = □

Aufgabe:

Da Alice gefallen an der getarnten Übermittlung von Zahlen gefunden hat und weil sie hofft den Unbekannten damit zu verwirren, sendet sie auch das genaue Datum ihres jährlichen Treffens im August mit der „ggT-Methode“ an Bob. Beim diesjährigen Treffen möchten die beiden unter anderem die richtige Verwendung des Verschlüsselungsalgorithmus besprechen, den sie anschließend für ihre Kommunikation nutzen möchten. Alice verheimlicht diesmal sogar, dass sie die ggT-Methode verwendet, doch Bob erkennt, den zusammenhangslosen Satz als „Chiffre“.
„Bob, bevor ich es wieder vergesse, das Geburtsjahr meiner Oma ist 1911 und mein großer Bruder ist 1980 geboren.“

Folglich ist der größte gemeinsame Teiler von 1911 und 1980 gesucht.








Also ist 3 der größte gemeinsame Teiler von 1911 und 1980, woraus folgt, dass sich Alice und Bob am 03.08 treffen möchten.
Zur Überprüfung hier die Primfaktorenzerlegung von




Lemma 1.4 (Lemma von Bézout) Zu existieren ganze Zahlen x und y mit

Diese Darstellung des größten gemeinsamen Teilers zweier Zahlen heißt auch Vielfachsummendarstellung. Das Lemma ist eine unmittelbare Folgerung aus dem Euklidischen Algorithmus. Beides zusammen - Euklidischer Algorithmus und Vielfachsummendarstellung – heißt erweiterter Euklidischer Algorithmus.

Aufgabe:

Bob übermittelt mit gleichem Verfahren, wie lange er bei Alice bleiben kann.
„Ich werde dich, wie schon vor 350 Tagen, auch diesmal gerne besuchen und die 585 km Anfahrt in Kauf nehmen.“

Wie lange wird Bob bleiben? Berechne den ggT von 350 und 585 mithilfe des Euklidischen Algorithmus.

Nun soll noch die Vielfachsummendarstellung von 235 und 350 bestimmt werden:


    
    


Der Euklidische Algorithmus lässt sich mithilfe von Computerprogrammen effizient umsetzten. Um das effizienteste Verfahren zur Umsetzung des Euklidischen Algorithmus kennen zu lernen, benötigst du noch Grundlagen der Modulo-Rechnung, die du auf der nächsten Seite kenne lernen wirst.

weiter zur Modulo-Rechnung