Faktorisierungsproblem: Unterschied zwischen den Versionen
(Die Seite wurde neu angelegt: Nachfolgend recherchieren Alice und Bob gemeinsam, ob RSA auch wirklich ausreichende Sicherheit für ihre Gespräche bietet. Sie finden dabei Folgendes:<br> <br> Die Si...) |
|||
| Zeile 10: | Zeile 10: | ||
[[Benutzer:Deininger_Matthias/Facharbeit/Einwegfunktion| Einwegfunktionen]] („one-way-functions“) sind Funktionen die sich relativ einfach berechnen lassen, deren Umkehrung aber erheblich schwieriger ist.„Schwierig“ bedeutet in diesem Zusammenhang, dass es selbst mit der Rechenstärke aller Computer der Welt erst in Millionen von Jahren eine Lösung der Funktion geben würde.<ref>vgl. [11, S.34]</ref><br> | [[Benutzer:Deininger_Matthias/Facharbeit/Einwegfunktion| Einwegfunktionen]] („one-way-functions“) sind Funktionen die sich relativ einfach berechnen lassen, deren Umkehrung aber erheblich schwieriger ist.„Schwierig“ bedeutet in diesem Zusammenhang, dass es selbst mit der Rechenstärke aller Computer der Welt erst in Millionen von Jahren eine Lösung der Funktion geben würde.<ref>vgl. [11, S.34]</ref><br> | ||
„Streng mathematisch gibt es keinen Beweis dafür, daß Einwegfunktionen überhaupt existieren, noch einen Hinweis darauf, daß sie konstruierbar sind. Trotzdem erfüllen viele Funktionen exakt diesen Zweck [...]“<ref>[11, S.34]</ref></div><br> | „Streng mathematisch gibt es keinen Beweis dafür, daß Einwegfunktionen überhaupt existieren, noch einen Hinweis darauf, daß sie konstruierbar sind. Trotzdem erfüllen viele Funktionen exakt diesen Zweck [...]“<ref>[11, S.34]</ref></div><br> | ||
| − | + | <br> | |
| − | Beispiel: Es ist einfach für Bob einen Porzellanteller von Alice zu zerbrechen, doch die Scherben anschließend wieder zum Teller zusammen zu fügen, so dass Alice nicht herausfindet, dass Bob den Teller zerbrochen hat, ist nicht einfach oder nahezu unmöglich. | + | Beispiel: Es ist einfach für Bob einen Porzellanteller von Alice zu zerbrechen, doch die Scherben anschließend wieder zum Teller zusammen zu fügen, so dass Alice nicht herausfindet, dass Bob den Teller zerbrochen hat, ist nicht einfach oder nahezu unmöglich.<br> |
| − | + | <br> | |
| + | Es existiert zwar bereits seit 1994 ein Programm von Peter Shor aus New Jersey, mit dessen Hilfe es möglich wäre, das Faktorisierungsproblem zu lösen, doch der nötige [[Benutzer:Deininger_Matthias/Facharbeit/Quantencomputer| Quantencomputer]], mit dem sich das Programm ausführen ließe, wurde bisher, so weit bekannt, noch nicht gebaut. <br> | ||
<br> | <br> | ||
<br> | <br> | ||
Version vom 12. September 2010, 10:08 Uhr
Nachfolgend recherchieren Alice und Bob gemeinsam, ob RSA auch wirklich ausreichende Sicherheit für ihre Gespräche bietet. Sie finden dabei Folgendes:
Die Sicherheit von RSA beruht auf der Schwierigkeit große Zahlen zu faktorisieren, also diese in ihre Primfaktoren zu zerlegen.
Als hartes Problem wird die Faktorisierung deshalb bezeichnet, weil sie die Umkehrung einer Einwegfunktion darstellt. Da die Faktorisierung heutzutage nicht effizient lösbar ist, spricht man in diesem Zusammenhang auch vom Faktorisierungsproblem.
Einwegfunktionen („one-way-functions“) sind Funktionen die sich relativ einfach berechnen lassen, deren Umkehrung aber erheblich schwieriger ist.„Schwierig“ bedeutet in diesem Zusammenhang, dass es selbst mit der Rechenstärke aller Computer der Welt erst in Millionen von Jahren eine Lösung der Funktion geben würde.[2]
Beispiel: Es ist einfach für Bob einen Porzellanteller von Alice zu zerbrechen, doch die Scherben anschließend wieder zum Teller zusammen zu fügen, so dass Alice nicht herausfindet, dass Bob den Teller zerbrochen hat, ist nicht einfach oder nahezu unmöglich.
Es existiert zwar bereits seit 1994 ein Programm von Peter Shor aus New Jersey, mit dessen Hilfe es möglich wäre, das Faktorisierungsproblem zu lösen, doch der nötige Quantencomputer, mit dem sich das Programm ausführen ließe, wurde bisher, so weit bekannt, noch nicht gebaut.
