Hallo zusammen!
Ich habe mal eine Frage zum Diffie-Hellman-Problem. Warum nimmt man an, dass das Diffie-Hellman-Problem praktisch nicht lösbar ist? Ich hoffe, dass mir jemand professionell sowohl für Laie als auch für Professoren erklären kann. Ich danke im Voraus.
Viele Grüße
Falco
Hallo,
um nicht aneinander vorbei zu reden, hier nochmal das DHP aus dem Wikipedia Artikel:
Given an element g and the values of g^x and g^y, what is the value of g^(xy)?
Soweit ich weiß, ist bisher nicht bewiesen, dass das Problem schwer (NP-vollständig) ist. Der Ansatz, das Problem zu lösen wäre ja, entweder x oder y zu berechnen. Dazu müsstest du den diskreten Logarithmus auswerten. Dieser ist aber selbst ein schwer lösbares Problem. Entgegen dem „normalen“ Logarithmus ist der diskrete Logarithmus nicht stetig, wodurch auch Näherungsverfahren scheitern. Man könnte dann alle Varianten ausprobieren, oder einen optimierten Algorithmus verwenden. Aber bisher ist kein Algorithmus bekannt, der das Problem in polynomieller Zeit schafft.
Also im Prinzip gilt das DHP als schwer lösbar, weil bisher nicht das Gegenteil gezeigt worden ist.
Nico
Entgegen dem „normalen“ Logarithmus
ist der diskrete Logarithmus nicht stetig, wodurch auch
Näherungsverfahren scheitern.
Ich meinte die fehlende Monotonität, an der die Näherungsverfahren scheitern. Unstetig ist ja sowieso alles 
Hey Nico,
Bedeutet das, wenn ich keine Lösung zur diskreten Logarithmus habe, dann kann ich nicht das Diffie-Hellman-Problem lösen?
Viele Grüße
Falco
Hm… das ist eine gute Frage. Fakt ist, wenn du den diskreten Logarithmus lösen kannst, kannst du auch das DHP lösen. Theoretisch würden noch andere Lösungsmethoden bleiben. Ich bin mir aber nicht sicher, ob es diese praktisch gibt.
Hallo Nico!
Verstehe^^ ich hätte da noch paar Frage. Weißt du wo man solche Diffi- hellman Schlüsselaustausch finden kann, also in welchen programmen oder Sachen? Und meine andere Frage ist, ist dieses Fazit richtig: Also solange es keine schnelleren und simplen Lösungsmethoden für das DHP gibt werden die Großkonzerne wie Dell GmbH den Diffie Hellman Schlüsselaustausch nicht benutzen und in ihren Software installieren für ihre Kunden.
Viele Grüße
Falco
Hallo,
das DHP soll ja schwer lösbar sein. Darauf baut die Sicherheit des gesamten Systems auf. Die Lösung des DHP wäre ja prinzipiell das Knacken einer Verschlüsselung. Solange das nicht klappt, ist alles super.
Soweit ich weiß, wird das DHP bei El-Gamal Verschlüsselungen und Signaturen genutzt, die in abgewandelter Form auch Anwendung in SSL finden (Angaben ohne Gewähr
Nico
Danke Nico!
Hätte da noch eine Frage, welche Themen gehörten eigentlich alles zu Diffie-Hellman-Problem? Ich mach jetzt meine Facharbeit über dieses Thema und ich habe jetzt meine Facharbeit so aufgeführt.
1.Einleitung 2.Kryptologie Kryptographie Kryptoanalyse
Glaubst du, ich sollte noch den diskreten logarithmus Problem ausführen mit dem diesen Themen?
2 Restklassenringe und prime Restklassengruppen
2.1 Halbgruppen und Gruppen
2.1.1 Definitionen
2.1.2 Untergruppen
2.2 Ringe und Körper
2.2.1 Definitionen
2.2.2 Restklassen
2.2.3 Restklassengruppen
P-NP-Problem
NP-Vollständigkeit
2.2.4 Restklassenringe
2.2.5 Restklassenkörper
2.2.6 Der kleine Satz von Fermat
2.3 Beispiel
3 Diskrete Logarithmen
3.1 Allgemeine Definition
3.2 Der diskrete Logarithmus in Z/pZ*
3.4 Anwendungsbeispiel: Diffie-Hellman-Schlüsselaustausch
3.5 Algorithmen für das diskrete Logarithmus-Problem
3.5.1 Kategorisierung der Algorithmen
3.5.2 Enumerationsverfahren
3.5.3 Pollard-Algorithmus
3.5.4 Pohlig-Hellman-Algorithmus
3.5.5 Index-Calculus-Algorithmus
Die Sache ist, dass ich es verständlich für Laie und Fachlehrer machen muss.
Viele Grüße
Falco
Da wäre es erst mal interessant, für welchen Bildungsstand die Facharbeit sein soll. Ich hatte eine Facharbeit in der 10. Klasse. Dafür ist deine Gliederung zwar sehr gut, aber doch wahrscheinlich zu umfangreich. Der diskrete Logarithmus gehört aber auf jeden Fall mit in das Themengebiet. Bevor du zum Schlüsselaustausch kommst, kannst du ja noch kurz ein simples Verschlüsselungsverfahren erklären. Also etwas gaaaanz einfaches. Cäsar-Chiffre zum Beispiel.
Ansonsten rede einfach mal mit dem betreuenden Lehrer darüber. Der weiß am besten, was er lesen will. Er muss es ja auch letztendlich bewerten. Und gerade in diskreter Mathematik sind die meisten Lehrer weniger ausgebildet. Vorausgesetzt natürlich, das ganze soll für die Schule sein.
Nico
Ich hatte eine Facharbeit in der 10.
Klasse. Dafür ist deine Gliederung zwar sehr gut, aber doch
wahrscheinlich zu umfangreich.
Hallo Falco, hallo Nico,
Uff, jetzt haut’s mich aus den Socken. Ich verfolge Eure Diskussion mit, aber hätte nicht gedacht, dass solche Themen schon in der Schule behandelt werden könnten.
Selbst bei Senior-IT-ler mit Hochschulabschluss dürfte bei den Gliederungspunkten (außer der Einführung) nur „Bahnhof“ ankommen.
Auch wenn einige (wenige) noch asymmetrische Kryptosysteme verstehen, sind die mathematischen Grundlagen schon sehr anspruchsvoll und akademisch.
Wäre vielleicht interessant, wenn Falco was zum Thema und der Zielgruppe sagen würde.
Zum Verständnis von Kryptologie halte ich Diffie-Hellman auch mehr der Anwendungsmöglichkeiten wegen für interessant als wegen der mathematischen Herleitung.
Ciao, Allesquatsch
Hai!
Weißt du wo man
solche Diffi- hellman Schlüsselaustausch finden kann, also in
welchen programmen oder Sachen?
In jedem TV oder jeder SetTopBox (DVB Receiver) mit CI+ Kartenslot.
Das Fernsehgerät erzeugt mit Hilfe von Diffi-Hellman einen sicheren
Kanal (secure Channel) zur CI+ Providerkarte. Der Kanal wird dann zu Steuer- und Kontrollzwecken genutzt, zum Beispiel Autentifizierung
des Gerätes gegenüber der Karte und vice versa.
Der Plem
Hallo Allesquatsch!
Ich verfolge Eure Diskussion mit, aber hätte nicht gedacht, dass solche Themen schon in der Schule behandelt werden könnten.
Selbst bei Senior-IT-ler mit Hochschulabschluss dürfte bei den
Gliederungspunkten (außer der Einführung) nur „Bahnhof“
ankommen.
Mathematik ist leider nicht für jeden! Das ist schade 
Auch wenn einige (wenige) noch asymmetrische Kryptosysteme
verstehen, sind die mathematischen Grundlagen schon sehr
anspruchsvoll und akademisch.
Der Lehrer sagte zu mir, dass er nicht so viel Text haben möchte, er will viel Mathematisches, also viele zahlen ;D
Wäre vielleicht interessant, wenn Falco was zum Thema und der
Zielgruppe sagen würde.
Die Zielgruppe ist eigentlich ja nur für mein Mathelehrer ;D
Zum Verständnis von Kryptologie halte ich Diffie-Hellman auch
mehr der Anwendungsmöglichkeiten wegen für interessant als
wegen der mathematischen Herleitung.
Ich muss 2 Sachen beachten: Es muss mind. 15 Seiten sein nicht mehr/ nicht weniger. Des Weiteren muss die Darstellung verständlich sein und hier ist ja das Problem ein Laie würde das nie so einfach verstehen. Ich bräuchte ja mind. 50 Seiten um alle Mathematischen Begriffe zu erklären, daher sollte ja eine Art Allgemeinwissen schon vorhanden sein. Ich denke, der Lehrer wird schon verstehen, was ich geschrieben habe, denn für ihn ist diese Facharbeit, eine Facharbeit in Mathematik, daher muss die Mathematik im Kernpunkt sein und sehr wenig Text wie Geschichte, Funktionsweise enthalten sein.
Viele Grüße
Falco
Der Lehrer sagte zu mir, dass er nicht so viel Text haben
möchte, er will viel Mathematisches, also viele zahlen ;D
Mathematik in dem Bereich hat eigentlich nicht so viel mit Zahlen zu tun. Die Zahlen kommen dann erst ganz am Ende dazu, wenn wirklich etwas berechnet werden soll. Alles davor ist das Herleiten von Prinzipien
15 Seiten sind für ein so komplexes Thema natürlich schon recht wenig. Überlegen wir mal, was für das Thema unerlässlich ist. Eine Basis, mit der man rechnen kann, ist natürlich vonnöten. Dabei sind solche speziellen Sachen wie Ringe und Halbgruppen wohl doch etwas zu viel des Guten. Es reicht bestimmt, wenn du mit den Gruppen anfängst, dabei auf die Restklassengruppen eingehst und das alles dann auf Körper erweiterst. Dabei Rechenregeln in den Restklassen mit erwähnen. Bei den Körpern reichen ja die Restklassen modulo einer Primzahl. Körper modulo Primzahlpotenzen sind dann schon wieder sehr weit…
Über die Komplexität von Algorithmen (P-NP, NP-Vollständigkeit) würde ich mich an deiner Stelle ausschweigen, da das einerseits zu tief in die theoretische Informatik reingeht und andererseits sowieso nicht endgültig geklärt ist.
Den kleinen Fermat kannst du mit reinnehmen, wenn du glaubst, dass er dich weiter bringt. Ist vielleicht mal ganz interessant, dass man sieht, dass es in dem neuen Körper weitere Rechenregeln geben kann. Aber ansonsten hat er für DH ja eher eine untergeordnete Rolle.
Den diskreten Algorithmus würde ich, wie gesagt, drin behalten, da er essentiell für DH ist. Dazu aber vielleicht nicht so viel erzählen, sondern kurz umreißen, warum er als schwer gilt. Beweisen kann man das bisher sowieso nicht. Die Berechnungsalgorithmen sind vielleicht auch etwas viel.
DH ist ja eigentlich der Hauptteil. Hier würde ich, wie auch schon erwähnt, kurz ein Motivationsbeispiel geben. Also z.B. eine Cäsar-Chiffre zwischen zwei Parteien, die sich über einen gemeinsamen Schlüssel einig werden müssen. Dazu kannst du dich dann ja auslassen.
Insgesamt wird das Themenmaterial sicher mehr als ausreichen. Versuche am besten, Teile, die für DH nicht wesentlich sind, wegzulassen.
Nico
Mathematik ist leider nicht für jeden! Das ist schade
Ich befürchte, dass auch unter den Mathelehrern der gymnasialen Oberstufe kaum einer ist, der das Diffie-Hellman-Problem kennt. Die mathematischen Fähigkeiten von Lehrern sind meist auf das Niveau ausgerichtet, was es ihren Schülern zu vermitteln gilt.
Der Lehrer sagte zu mir, dass er nicht so viel Text haben
möchte, er will viel Mathematisches, also viele zahlen ;D
Das klingt irgendwie wie die kaiserliche Musikkritik an Mozart: „Zu viele Noten, mein lieber Mozart, zu viele Noten“
Die Forderung nach „Zahlen“ erscheint mir eher an dem ausgerichtet, was der Lehrer für verstehbar hält.
Die Zielgruppe ist eigentlich ja nur für mein Mathelehrer ;D
Dann solltest Du ihm liefern, was er erwartet.
Ich muss 2 Sachen beachten: Es muss mind. 15 Seiten sein nicht
mehr/ nicht weniger. Des Weiteren muss die Darstellung
verständlich sein und hier ist ja das Problem ein Laie würde
das nie so einfach verstehen.
„Diffie-Hellman-Problem für Laien“ ist so etwa auf dem Niveau von „Mofa-Führerschein für Kindergartenkinder“
Liefer ihm lieber was mit Zahlen. Vorsichtshalber Beispiele mit kleinen Zahlenwerten, da er ja offenkundig über 15 irgendwelche Probleme sieht.
Ich denke, der Lehrer wird schon verstehen,
was ich geschrieben habe,
Zumindest wird er versuchen, diesen Eindruck zu vermitteln.
Ich würde lieber einen Ausschnitt erläutern, denn das wichtigste Kriterium scheint ja „15“ und „Zahlen“ zu sein. Und dann kurz sagen, dass es was mit Diffie-Hellman zu tun hat und wo Diffie-Hellman vorkommt.
Mit „Primitivwurzel“ und einem gerechneten Beispiel für Diffie-Hellman-Schlüsselaustausch hast Du schon genügend Content.
Auf jeden Fall lernt man was für Leben.
Ciao, Allesquatsch