Diffie-Hellman
-
Hallo!
Kann mir jemand das mit der diskreten Diskreten Exponentialfunktion erklären?
ich versteh das nicht ganz wozu ist sie gut?
zum Diffie-Hellman Verfahren
ist es zu "brechen" oder nicht? im Sinne von "Brechen"/Ermittlung/Errechnung des Schlüssels? (mal unabhängig wie lang es dauert)bzw ist das ganze überhaupt lösbar?
wie lange würde es dauern? (bei Schlüssellängen von 100 Stellen etc)
Ist der Wert eindeutig zu berechnen bzw ist dieses Problem eindeutig lösbar?
mfg
-
-
hast du dir den Link angesehen?
ich schon, BEVOR ich gepostet habe.
sie beantwortet keine meiner Fragen schon gar nicht die letzteren (nach der ersten)
mfg
-
Dann frage doch bitte gezielt nach dem, was du nicht verstehst.
-
naja zum Bsp ob sie immer bzw unter welchen Bedingungen sie eindeutig ist. Ist sie das überhaupt? es wird ja nur ein Rest angegeben.
edit: bzw ob das Ergebnis eindeutig ist also ob es mehr als eine Eingabe gibt die die selbe Ausgabe ergibt.
mfg
-
Nein, sie ist nicht injektiv, d.h. zwei verschiedene x können dasselbe Bild haben. Deshalb ist der diskrete Logarithmus, nach dem du ja auch schon gefragt hattest, als Minimum aller dieser x definiert.
-
danke, wo ist die Begründung zu dem Aufbau dieser Funktion? (also, dass man die Funktion so aufbaut)
was ist ein primitives Element*? (sry habs gelesen verstehs aber ned, da kein Mathematiker)
wieso diese Zahlen(typen?)
*bzw eine primitive Wurzel oder eine Primzahlenrestgruppe?
mfg
-
Seien F,K Körper, K in F enthalten. Dann heist F Körpererweiterung von K.
Sei nun x Element von F, dann bezeichnet K(x) den kleinsten Körper, welcher K und x enthält.
Allgemeiner kann man für eine Teilmenge von F genannt S schreiben K(S) als der kleinste Körper, welcher K und S enthält.
Sei $ die leere Menge.
Wir haben zwei triviale Beziehungen:
K($)=K und K(F)=F
Falls für ein Element y aus F gilt F=K(y), dann nennt man y ein primitives Element der Körpererweiterung F von K.
Es gibt auch noch einen sehr wichtigen Satz zu dieser Thematik:
http://planetmath.org/encyclopedia/ProofOfPrimitiveElementTheorem2.html
-
Primitive Elemente haben nichts, aber auch gar nichts mit Primitivwurzeln zu tun
-
gut ich fasse meine Fragen neu zusammen:
Ich weiss jetzt was eine Restklasse ist und was eine prime Restklasse ist.
diese Fragen hätt ich noch/wären noch offen:
Wieso werden gerade diese Zahlentypen ausgewählt? (Primitivwurzeln etc) bzw warum gerade prime Restklassen? (bei Diffie-Hellman)
plus: was ist eine Primitivwurzel?
mfg
-
muhi schrieb:
Wieso werden gerade diese Zahlentypen ausgewählt? (Primitivwurzeln etc) bzw warum gerade prime Restklassen? (bei Diffie-Hellman)
Weil es damit halt funktioniert. Restklassen sind überaus beliebt, weil man darüber ziemlich viel weiß. Mit denen kann man relativ gut rechnen, trotzdem ist für manche Operationen eben nicht bekannt wie man sie schnell rückgängig machen kann. (Und immer wenn etwas hat von dem man nicht weiß wie man's schnell lösen kann, dann baut man ein krypto-system draus ;)).
Prime Restklassen haben den Vorteil, dass sie auch noch invertierbar sind. Das gibt noch mehr Struktur.plus: was ist eine Primitivwurzel?
x ist d-te wurzel von a, wenn x^d = a. x ist primitive d-te wurzel, wenn zusätzlich x^i != a für 1<=i<d. Wenn man also wirklich hoch d nehmen muß und nicht schon vorher das gewünschte element rauskommt.
Betrachte zum Beispiel die 4. Wurzeln aus 1 (achtung wurzel im algebraischen sinne, d.h. nullstellen von x^4-1). Da gibt's genau 4 Stück: 1,-1,i,-i.
Für jede davon ist die 4. Potenz 1. Aber es gilt sogar schon 1^1 =1 und (-1)^2 = 1, die sind also nicht primitiv. Du kannst ja mal nachprüfen, dass i und (-i) primitiv sind. Wenn man mal eine primitive Wurzel d-te Wurzel von 1 hat, nennen wir sie x, dann kriegt man alle anderen Wurzeln von 1 als x1,x2,x3,...,xd.
Und mit denen wiederum kriegt man, wenn man eine Wurzel aus a hat dann auch alle Wurzeln von a. Deshalb sind primitive Wurzeln recht praktisch.