Diskussion:Diffie-Hellman-Schlüsselaustausch

Zum Archiv

Wie wird ein Archiv angelegt?

Automatische Archivierung

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Automatische Archivierung

Auf dieser Seite werden Abschnitte halbmonatlich automatisch archiviert, deren jüngster Beitrag mehr als 365 Tage zurückliegt und die mindestens einen signierten Beitrag enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Der Gedanke ist eigentlich banal

$g^{ab}\mod n=(g^{a})^{b}\mod n=(g^{b})^{a}\mod n$

Nein - n muss keine Primzahl sein! --Franz Scheerer aus Wiesbaden (Diskussion) 09:24, 29. Jan. 2023 (CET)

Das Diffie-Hellman-Verfahren ist so definiert, dass n eine Primzahl ist, siehe Paper. Gibt man die Eigenschaft auf, ist es kein Diffie-Hellman mehr, sondern eine davon abgeleitete Variante. Die prime Eigenschaft ist notwendig für die Sicherheit des Verfahrens, siehe Abschnitt Diffie-Hellman-Schlüsselaustausch#Prime_Restklassengruppe_und_Primitivwurzel. Eine prime Restklassengruppe mit Primitivwurzel als Generator ergibt die Werte 0 bis n-1 als mögliches Geheimnis. Wenn n nicht prim ist, ist das nicht sichergestellt: die nicht-prime Restklassengruppe kann weniger Elemente haben, demnach gibt es eine geringere Anzahl an Geheimnissen, die ein Angreifer durchprobieren muss. --Matthäus Wander 12:13, 30. Jan. 2023 (CET)

Die Anzahl der Geheimnisse ist die Eulersche Phi-Funktion. Sie ist in der Tat maximal für eine Primzahl. Der Unterschied ist bei größeren Zahlen jedoch relativ gering und kann durch die Wahl eines größeren Wertes für n leicht ausgeglichen werden. Das Verfahren funktioniert jedenfalls auch für ein nicht-primes n. Alice und Bob können sich trotzdem auf ein gemeinsames Passwort verständigen. Claus Peter Schnorr schlägt vor eine Primzahl p zu wählen, so dass (p-1), die Phi-Funktion, einen hinreichend großen Primfaktor q besitzt. Dann kann g als Generator einer Untergruppe mit q Elementen gewählt werden. Dann nimmt $g^{x}\mod p$ insgesamt q verschiedene Werte an. Wenn q > $2^{256}$ ist, ist das sehr sicher. Aber n muss gar keine Primzahl sein, sofern die Eulersche Phi-Funktion einen solch großen Primfaktor q besitzt. Wir könnten n = $q^{2}$ wählen. --Franz Scheerer aus Wiesbaden (Diskussion) 16:10, 30. Jan. 2023 (CET)

$phi(n)$ gibt erstmal nur die Anzahl der Gruppenelemente in der primen Restklassengruppe wieder. Das entspricht nur dann der Anzahl Geheimnisse, wenn eine Primitivwurzel für die prime Restklassengruppe existiert, also ein Generator, aus dem sich jedes Element der Gruppe erzeugen lässt. Eine Primitivwurzel existiert nicht für jedes beliebige $n$. --Matthäus Wander 20:05, 30. Jan. 2023 (CET)

Die Eulersche Phi-Funktion hat zunächst einmal, von der Definition, noch gar nichts mit Gruppentheorie zu tun. Es ist einfach die Anzahl zu n teilerfremder Zahlen größer oder gleich 1 und kleiner n. Wir können jetzt genau diese teilerfremden Zahlen und die Verknüpfung, Mulitiplikation modulo n, verwenden, um eine Gruppe (im Sinne der Mathematik) zu definieren. Die teilerfremden Zahlen sind dann die Gruppenelemente. Es gibt noch viel mehr Gruppen, die wir betrachten könnten. Die Gruppenelemente sind im Allgemeinen keine Zahlen. Es können zum Beispiel Punkte auf einer Kurve sein. Bei endlichen Gruppen gibt es immer eine definierte Anzahl an Gruppenelementen, die Gruppenordnung. Aber für die Kryptographie brauchen wir so tief indie Gruppentheorie nicht einsteigen. Die Gruppe mit den teilerfremden Zahlen und die Multiplikation modulo n genügt uns eigentlich völlig. --Franz Scheerer aus Wiesbaden (Diskussion) 09:26, 31. Jan. 2023 (CET)

Die Antwort ist für das Diskussionsthema (muss n prim sein? Gibt phi(n) die Anzahl Geheimnisse wieder?) irrelevant. --Matthäus Wander 14:06, 31. Jan. 2023 (CET)

Um ein gemeinsames Passwort zu vereinbaren wird eine Primzahl definitiv nicht benötigt. Die oben genannte Gleichung gilt nämlich für alle großen natürlichen Zahlen. Damit es sicher ist, müssen die Zahlen hinreichend groß sein. --178.202.60.40 18:59, 31. Jan. 2023 (CET)

Nein nicht n sollte eine Primzahl sein, sondern die Ordnung der Gruppe. Die Eulersche Phi-Funktion ist jedoch für größere Zahlen keine Primzahl. Das Problem lösen wir, indem wir als Gruppe eine Untergruppe benutzen. Dazu muss die Eulersche-Phi-Funktion einen hinreichend großen Primfaktor enthalten. --178.202.60.40 19:06, 31. Jan. 2023 (CET)

Es stimmt, der Diffie-Hellman-Schlüsselaustausch wurde mit einer Primzahl als Modulus vorgeschlagen. Wenn wir eine zusammengesetzte Zahl verwenden, ist es ein modifiziertes Verfahren. Wir können auch durchaus eine Primzahl verwenden mit einer Untergruppe deren Ordnung eine kleinere Primzahl q ist, wie es Claus Peter Schnorr vorgeschlagen hat. Für q genügt eine Primzahl mit 256 Binärschnittstellen. --Franz Scheerer aus Wiesbaden (Diskussion) 10:45, 1. Feb. 2023 (CET)

Das ist aus meiner Sicht die beste Lösung. Wir wählen zwei Primzahlen p und q wie es Professor Schnorr vorgeschlagen hat. Das ist dann konform mit dem Diffie-Hellman-Schlüsselaustausch und nicht zu knacken, wenn die Gruppenordnung q größer $2^{256}$ gewählt wird. --Franz Scheerer aus Wiesbaden (Diskussion) 10:48, 2. Feb. 2023 (CET)

Auf der anderen Seite, warum sollten wir ein Verfahren verwenden, dass exakt so im Lehrbuch steht. Wir können jedenfalls die Primzahl p durch eine etwa gleich große zusammengesetzte Zahl n ersetzen. Der Schlüsselaustausch funktioniert weiterhin. Falls die Gruppenordnung der Untergruppe eine hinreichend große Primzahl q ist und wir g als einen Generator der Untergruppe wählen, ist das sicher. Es ist auch vollkommen egal, was das Lehrbuch sagt. Der ausgetauschte Schlüssel soll schließlich geheim sein. Idealer Weise ist auch das Schlüsselaustausch-Protokoll geheim, aber auch dann noch sicher, wenn es der Angreifer kennt. --Franz Scheerer aus Wiesbaden (Diskussion) 10:27, 4. Feb. 2023 (CET)