Zusammenhang zwischen Erzeuger und Primitivwurzel?

Wissenschaft Physik
#1

Hallo!

Ich versuche mich gerade an dem Public-Key-Kryptosystem ElGamal.
In unterschiedlichen Büchern werden unterschiedliche Begriffe verwendet.

Zunächst soll man sich bei ElGamal eine Primzahl überlegen, diese ist dann die Ordnung einer Gruppe G.
Dazu braucht man noch einen Erzeuger dieser Gruppe G. In anderen Publikationen wird von der Primitivwurzel zu G gesprochen.

Wie hängen diese Begriffe zusammen?

Beispiel: Primzahl p =17, Erzeuger/Primitivwurzel g = 3

#2

Public-Key-Kryptosystem ElGamal

Kann man das essen?
Hört sich jedenfalls exotisch an.

Gruß
peak

PS: sry^^

#3

Leider nicht essbar.

Public-Key-Kryptosystem ElGamal

Kann man das essen?
Hört sich jedenfalls exotisch an.

Nein, ist leider nicht essbar. :wink:
Es handelt sich um ein Verschlüsselungsverfahren, dass auf dem diskreten-Logarithmus-Problem basiert.
Siehe: http://de.wikipedia.org/wiki/Elgamal-Kryptosystem

#4

Public-Key-Kryptosystem ElGamal

Kann man das essen?

Die Frage gehört wohl eher ins Religionsbrett, denn im Alten Testament steht geschrieben, dass man Kamele nicht essen soll.

SCNR
Torsten

#5

Hallo Dude,

Ich versuche mich gerade an dem Public-Key-Kryptosystem
ElGamal.
In unterschiedlichen Büchern werden unterschiedliche Begriffe
verwendet.

Welche Buecher verwendest du denn? Schonmal in ‚Buchmann - Einfuehrung in die Kryptographie‘ reingeschaut? Das hat mir bei meiner Pruefung sehr geholfen.

Zunächst soll man sich bei ElGamal eine Primzahl überlegen,
diese ist dann die Ordnung einer Gruppe G.
Dazu braucht man noch einen Erzeuger dieser Gruppe G. In
anderen Publikationen wird von der Primitivwurzel zu G
gesprochen.

Ich glaube, dass das das Selbe ist. In Buchmann wird von einer Primitivwurzel g mod p gesprochen, was aber auch g ist, wenn g kleiner als p ist. g ist aber auch gleichzeitig dein Erzeuger, sofern mich meine Algebrakenntnisse nicht im Stich lassen.

Wie hängen diese Begriffe zusammen?

Beispiel: Primzahl p =17, Erzeuger/Primitivwurzel g = 3

Was willst du eigentlich konkret wissen?

Gruss x303

#6

Was willst du eigentlich konkret wissen?

Ich will wissen warum manchmal vom Erzeuger und manchmal von der Primitivwurzel gesprochen wird.

Ich glaube mittlerweile, dass diese Begriffe nicht das selbe bedeuten.
Es handelt sich lediglich um einen Erzeuger, wenn es sich bei der Gruppe G um eine normale Gruppe handelt. Wenn es sich bei der Gruppe G um einen Primkörper handelt (der ja benötigt wird um mit ElGamal zu signieren) dann braucht man eine Primitivwurzel.

Stimmt das?

#7

Was willst du eigentlich konkret wissen?

Ich will wissen warum manchmal vom Erzeuger und manchmal von
der Primitivwurzel gesprochen wird.

Ich weiß jetzt auch nicht, welche Literatur du liest.
Ich hab hier, wie schonmal erwähnt, das Buch von
„Buchmann - Einführung in die Kryptographie“.
Wenn ich im ElGamal Verfahren nachschaue, taucht nur die Primitivwurzel auf.

Die Definition dazu:

Eine ganze Zahl a, für die die Restklasse a+pZ die prime Restklassengruppe (Z/pZ)* erzeugt, heißt Primitivwurzel mod p.

p ist die Primzahl
Z sind die ganzen Zahlen

Ich glaube mittlerweile, dass diese Begriffe nicht das selbe
bedeuten.
Es handelt sich lediglich um einen Erzeuger, wenn es sich bei
der Gruppe G um eine normale Gruppe handelt. Wenn es sich bei
der Gruppe G um einen Primkörper handelt (der ja benötigt wird

Aber ein Körper ist doch auch immer eine Gruppe!? Ob Prim oder nicht.

um mit ElGamal zu signieren) dann braucht man eine
Primitivwurzel.

Stimmt das?

Ganz genau kann ich dir das jetzt nicht sagen. Aber schau mal hier:

Korollar 3.21.3. Ist K ein endlicher Körper mit q Elementen, so ist die Einheitengruppe K* zyklisch von der Ordnung q-1. Sie hat genau phi(q-1) Erzeuger.

und im Bsp 3.22.2. Für p=13 ist p-1=12. Aus Theorem 3.17.2 folgt, daß phi(12)=4. Also gibt es vier Primitivwurzeln mod 13, nämlich 2,6,7 und 11.

hilft dir das weiter?

Gruss x303

#8

Was willst du eigentlich konkret wissen?

Ich will wissen warum manchmal vom Erzeuger und manchmal von
der Primitivwurzel gesprochen wird.

Ich weiß jetzt auch nicht, welche Literatur du liest.
Ich hab hier, wie schonmal erwähnt, das Buch von
„Buchmann - Einführung in die Kryptographie“.
Wenn ich im ElGamal Verfahren nachschaue, taucht nur die
Primitivwurzel auf.

Z.B.
Moderne Verfahren der Kryptographie von Beutelsbacher.

Die Definition dazu:

Eine ganze Zahl a, für die die Restklasse a+pZ die prime
Restklassengruppe (Z/pZ)* erzeugt, heißt Primitivwurzel mod p.

p ist die Primzahl
Z sind die ganzen Zahlen

Ich glaube mittlerweile, dass diese Begriffe nicht das selbe
bedeuten.
Es handelt sich lediglich um einen Erzeuger, wenn es sich bei
der Gruppe G um eine normale Gruppe handelt. Wenn es sich bei
der Gruppe G um einen Primkörper handelt (der ja benötigt wird

Aber ein Körper ist doch auch immer eine Gruppe!? Ob Prim oder
nicht.

Ja aber nicht jede Gruppe ist ein Körper!

um mit ElGamal zu signieren) dann braucht man eine
Primitivwurzel.

Stimmt das?

Ganz genau kann ich dir das jetzt nicht sagen. Aber schau mal
hier:

Korollar 3.21.3. Ist K ein endlicher Körper mit q Elementen,
so ist die Einheitengruppe K* zyklisch von der Ordnung q-1.
Sie hat genau phi(q-1) Erzeuger.

und im Bsp 3.22.2. Für p=13 ist p-1=12. Aus Theorem 3.17.2
folgt, daß phi(12)=4. Also gibt es vier Primitivwurzeln mod
13, nämlich 2,6,7 und 11.

hilft dir das weiter?

Ich akzeptiere einfach dass es hier wohl zwei Begriffe gibt je nachdem in welcher mathematischen Struktur man sich befindet…

_ElGamal Chiffrierverfahren:
Es sei g ein Erzeuger der Gruppe G. Die Gruppe G und der Erzeuger g seien öffentlich bekannt…

ElGamal Signaturverfahren:
Das Signaturverfahren läßt sich nur über einen Primkörper realisieren. Es gilt hier also g Element F*p ist Primitivwurzel._

#9

Was willst du eigentlich konkret wissen?

Ich will wissen warum manchmal vom Erzeuger und manchmal von
der Primitivwurzel gesprochen wird.

Ich weiß jetzt auch nicht, welche Literatur du liest.
Ich hab hier, wie schonmal erwähnt, das Buch von
„Buchmann - Einführung in die Kryptographie“.
Wenn ich im ElGamal Verfahren nachschaue, taucht nur die
Primitivwurzel auf.

Z.B.
Moderne Verfahren der Kryptographie von Beutelsbacher.

Die Definition dazu:

Eine ganze Zahl a, für die die Restklasse a+pZ die prime
Restklassengruppe (Z/pZ)* erzeugt, heißt Primitivwurzel mod p.

p ist die Primzahl
Z sind die ganzen Zahlen

Ich glaube mittlerweile, dass diese Begriffe nicht das selbe
bedeuten.
Es handelt sich lediglich um einen Erzeuger, wenn es sich bei
der Gruppe G um eine normale Gruppe handelt. Wenn es sich bei
der Gruppe G um einen Primkörper handelt (der ja benötigt wird

Aber ein Körper ist doch auch immer eine Gruppe!? Ob Prim oder
nicht.

Ja aber nicht jede Gruppe ist ein Körper!

das hab ich auch nicht behauptet :wink:

um mit ElGamal zu signieren) dann braucht man eine
Primitivwurzel.

Stimmt das?

Ganz genau kann ich dir das jetzt nicht sagen. Aber schau mal
hier:

Korollar 3.21.3. Ist K ein endlicher Körper mit q Elementen,
so ist die Einheitengruppe K* zyklisch von der Ordnung q-1.
Sie hat genau phi(q-1) Erzeuger.

und im Bsp 3.22.2. Für p=13 ist p-1=12. Aus Theorem 3.17.2
folgt, daß phi(12)=4. Also gibt es vier Primitivwurzeln mod
13, nämlich 2,6,7 und 11.

hilft dir das weiter?

Ich akzeptiere einfach dass es hier wohl zwei Begriffe gibt je
nachdem in welcher mathematischen Struktur man sich
befindet…

_ElGamal Chiffrierverfahren:
Es sei g ein Erzeuger der Gruppe G. Die Gruppe G und der
Erzeuger g seien öffentlich bekannt…

ElGamal Signaturverfahren:
Das Signaturverfahren läßt sich nur über einen Primkörper
realisieren. Es gilt hier also g Element F*p ist
Primitivwurzel._

Puhh. Für mich klingt das dann doch irgendwie gleich. Zumindest scheinen ein Erzeuger und eine Primitivwurzel die selbe Aufgabe zu erfüllen. Beutelsbacher ist Algebraiker, oder? Vielleicht benutzt er deswegen den Begriff Erzeuger anstatt Primitivwurzel!? (Buchmann ist Informatiker.) Hab grad bei mir in meinem Kryptographie-Skript nachgeschaut. Dort heißt es „primitives Element“ :wink:

Gruss x303