serious-cool

Zyklische Gruppen bilden die mathematische Grundlage für asymmetrische Kryptosysteme. Dieser Beitrag vermittelt die mathematischen Grundlagen von zyklischen Gruppen

Etwas Algebra

Eigenschaften von Gruppen:

• Abgeschlossenheit. Bei jeder Operation zwischen Elementen einer Gruppe liegt das Ergebnis wieder in der Gruppe.
• Assoziativ Gesetz: a * b * c = a * ( b * c )
• Es existiert ein neutrales Element a * e = a
• Es existieren Inverse Elemente a * a^-1 = e ( e = neutrales Element.)

Diese Eigenschaften gelten für alle Gruppen existiert folgende Eigenschaft zusätzlich:

• Kommutativ Gesetz: a * b = b * a

spricht man von Abelschen Gruppen

Beispiel

Frage: ist Z₉ eine multiplikative Gruppe?

Z₉ = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } Operation: Multiplikation x mod 9

4 * 4^-1 = 1 mod 9; 4^-1 = 7 denn 4 * 7 = 28 = 1 mod 9

Allerdings existieren für a nur Inverse wenn ggT ( a, 9 ) = 1 gilt. Also existiert für 0, 3, 6 kein Inverses Element. Wir definieren uns Z₉^* = { 1, 2, 4, 5, 7, 8,} neu indem wir alles Elemente für die keine Inverse existiert raus werfen.Ohne Beweis erhalten wir nun eine multiplikative Gruppe.

Definition: eine Gruppe ist endlich wenn sie endlich viele Elemente hat.

Bemerkung: Die Anzahl an Elementen einer Gruppe G wird als Kardinalität oder Ordnung der Gruppe bezeichnet. Schreibweise: #G oder |G| Bsp.: |Z₉^*| = 6

Experimente mit Zahlen

Z₁₁^* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Definition: Die Ordnung eines Elements a ist die kleinste positive Ganzzahl k , so dass gilt: a^k = a * a * ... * a = 1 wobei 1 das neutrale Element der Gruppe G ist.

Bsp.: a = 3: a¹ = 3; a² = 9; a³ = 27 = 5 mod 11; a⁴ = a³ * a = 15 = 4 mod 11; a⁵ = 4 * 3 = 1 mod 11;  => ord( 3 ) = 5

Definition: Elemente a mit der Ordnung ord( a ) = |G| heißen primitive Elemente. Weiter sind folgende Bezeichnungen gängig: Generatoren oder erzeugende Elemente

Bsp.: a = 2: a¹ = 2; a² = 4; a³ = 8; a⁴ = 5 mod 11; a⁵ = 10 mod 11;  a⁶ = 9 mod 11; a⁷ = 7 mod 11;a⁸ = 3 mod 11; a⁹ = 6 mod 11; a¹⁰ = 1 mod 11 => ord( 2 ) = 10

Definition: Gruppen die mindestens ein primitves Element enthalten heißen zyklische Gruppen

In der Kryptographie sind vor allem folgenden Mengen besonders wichtig: Jede Menge Z_p^* = { 1, 2, ... , p-1 } mit p = Primzahl, bildet eine zyklische Gruppe.

Wichtige Eigenschaften zyklischer Gruppen:

1. Für jedes a der Gruppe G gilt: a^|G| = 1
2. Für jedes a gilt ord( a ) teilt |G|
3. Falls |G| eine Primzahl ist sind alle Elemente a in G primitive Elemente.