Faktorisierungsproblem: Unterschied zwischen den Versionen
| (20 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
| + | <div style="text-align:right;">[[Bild:Buch.PNG]][[Benutzer:Deininger_Matthias/Facharbeit/Fachwortverzeichnis| Fachwortverzeichnis]]</div> | ||
| + | ===Sicherheit von RSA=== | ||
| + | |||
| + | <div style="text-align:center;">[[Bild:Server-Sicherheitssystem-Hund.PNG|700px]]<br> | ||
| + | © Klaus Schmeh aus "Kryptografie. Verfahren–Protokolle–Infrastrukturen" </div> | ||
| + | <br> | ||
| + | ====Faktorisierungsproblem==== | ||
| + | <br> | ||
Nachfolgend recherchieren Alice und Bob gemeinsam, ob RSA auch wirklich ausreichende Sicherheit für ihre Gespräche bietet. Sie finden dabei Folgendes:<br> | Nachfolgend recherchieren Alice und Bob gemeinsam, ob RSA auch wirklich ausreichende Sicherheit für ihre Gespräche bietet. Sie finden dabei Folgendes:<br> | ||
<br> | <br> | ||
| Zeile 4: | Zeile 12: | ||
<br> | <br> | ||
<div style = "text-align: center;margin:auto; border: 2px solid #E5CC00;border-color: green;"> | <div style = "text-align: center;margin:auto; border: 2px solid #E5CC00;border-color: green;"> | ||
| − | „Es wird fast ausnahmslos angenommen, dass die Faktorisierung zu den harten Problemen gehört, es konnte bisher jedoch nicht mathematisch bewiesen werden.“<ref>[ | + | „Es wird fast ausnahmslos angenommen, dass die Faktorisierung zu den harten Problemen gehört, es konnte bisher jedoch nicht mathematisch bewiesen werden.“<ref>[9, S.186]</ref></div> |
<br> | <br> | ||
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.<br> | 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.<br> | ||
<div style = "text-align: left;margin:auto; border: 2px solid #E5CC00;border-color: green;"> | <div style = "text-align: left;margin:auto; border: 2px solid #E5CC00;border-color: green;"> | ||
| − | [[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 | + | [[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 möglich sein würde, das Inverse zu einem Wert bezüglich der Funktion zu finden.<ref>vgl. [9, 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>[ | + | „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>[9, 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 zusammenzufügen, so dass Alice nicht herausfindet, dass Bob den Teller zerbrochen hat, ist nicht einfach oder nahezu unmöglich.<br> |
| − | Beispiel: Es ist einfach für Bob einen Porzellanteller von Alice zu zerbrechen | + | |
<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> | 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> | ||
| − | Eine Möglichkeit die Faktorisierung zu erschweren und damit RSA angriffssicherer zu machen besteht darin, bei der Schlüsselerzeugung darauf zu achten, dass es sich bei den generierten Primzahlen | + | Eine Möglichkeit, die Faktorisierung zu erschweren und damit RSA angriffssicherer zu machen, besteht darin, bei der Schlüsselerzeugung darauf zu achten, dass es sich bei den generierten Primzahlen um große Zahlen von ungefähr gleicher Länge handelt. Dies kann dazu beitragen, dass sich die vollständige Primzahlsuche noch schwieriger gestaltet. |
| − | <div style = "text-align: center;margin:auto; | + | <div style = "text-align: center;width:600px;margin:auto;border: 2px solid #E5CC00;border-color: green;"> |
Faktorisierungsangriff: Verfahren zur Ermittlung der Primfaktorzerlegung einer Zahl</div><br> | Faktorisierungsangriff: Verfahren zur Ermittlung der Primfaktorzerlegung einer Zahl</div><br> | ||
| − | + | Ein Beispiel für einen Faktorisierungsangriff ist die [[Benutzer:Deininger_Matthias/Facharbeit/Fermat_Faktorisierung| Fermat’sche Faktorisierung]].<br><br> | |
| − | Ein Beispiel für einen Faktorisierungsangriff ist die [[Benutzer:Deininger_Matthias/Facharbeit/Fermat_Faktorisierung| Fermat’sche Faktorisierung]]<br> | + | Als Alice und Bob bei ihrer Suche auf Angriffe stoßen, erschrecken sie und befürchten, dass die ganze Mühe vergebens war und sie doch ein anderes Verfahren wählen müssen.<br> |
| − | Als Alice und Bob bei ihrer Suche auf Angriffe stoßen, erschrecken sie und befürchten, dass die ganze Mühe | + | |
Warum die beiden das Verfahren nicht wechseln müssen, kannst du auf der nächsten Seite herausfinden.<br> | Warum die beiden das Verfahren nicht wechseln müssen, kannst du auf der nächsten Seite herausfinden.<br> | ||
| + | <br> | ||
| + | [[Bild:Weiter.png|weiter]] [[Benutzer:Deininger_Matthias/Facharbeit/Angriffe_auf_RSA| ''' weiter zu den Angriffen auf RSA''']] | ||
<br> | <br> | ||
<br> | <br> | ||
| + | [[Benutzer:Deininger_Matthias/Facharbeit| zurück zur Übersicht]] | ||
---- | ---- | ||
<references /> | <references /> | ||
Aktuelle Version vom 23. Dezember 2010, 03:13 Uhr
Sicherheit von RSA
© Klaus Schmeh aus "Kryptografie. Verfahren–Protokolle–Infrastrukturen"
Faktorisierungsproblem
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 möglich sein würde, das Inverse zu einem Wert bezüglich der Funktion zu finden.[2]
Beispiel: Es ist einfach für Bob, einen Porzellanteller von Alice zu zerbrechen. Doch die Scherben anschließend wieder zum Teller zusammenzufü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.
Eine Möglichkeit, die Faktorisierung zu erschweren und damit RSA angriffssicherer zu machen, besteht darin, bei der Schlüsselerzeugung darauf zu achten, dass es sich bei den generierten Primzahlen um große Zahlen von ungefähr gleicher Länge handelt. Dies kann dazu beitragen, dass sich die vollständige Primzahlsuche noch schwieriger gestaltet.
Ein Beispiel für einen Faktorisierungsangriff ist die Fermat’sche Faktorisierung.
Als Alice und Bob bei ihrer Suche auf Angriffe stoßen, erschrecken sie und befürchten, dass die ganze Mühe vergebens war und sie doch ein anderes Verfahren wählen müssen.
Warum die beiden das Verfahren nicht wechseln müssen, kannst du auf der nächsten Seite herausfinden.
weiter zu den Angriffen auf RSA
zurück zur Übersicht
