Aufgabe 1 Generator

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Aufgabe 1 Generator

Beitrag von sab » 17. Dez 2012 08:06

Hallo,

ich glaube, ich stehe etwas auf dem Schlauch, was die Wahl des Generators angeht:

Bestimmen Sie einen Generator g von \((\mathbb{Z}_{p})\), indem Sie wiederholt ein (gleichverteilt) zufälliges g \(\in\) {2, . . . , p − 1} wählen,
bis \(g^{2} \ne 1~mod~p\) und \(g^{p'} \ne 1~mod~p\) gilt.

Wenn ich mir jetzt den Buchmann und auch die Gruppenübung zu ElGamal anschaue, kann ich doch nur \(g^{Primfaktoren~von~p}\) mit den gewünschten Eigenschaften aussuchen, oder? Sprich, ich muss erst bestimmen, welche Generatoren es gibt und kann mir dann einen gülten raussuchen. Oder denke ich zu kompliziert?

Viele Grüße,
sab

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Aufgabe 1 Generator

Beitrag von JannikV » 17. Dez 2012 08:47

Hi,

wenn du eine Gruppe \(\mathbb{Z}_p^*\) hast, s.d. \(p = 2p' + 1\) mit \(p\) und \(p'\) sind Primzahlen, scheint es ne ganze Menge Generatoren zu geben. Es geht also schnell einen zu raten und zu gucken ob es wirklich einer ist (bei mir braucht er ungefähr 2 bis 15 Versuche um einen zu finden). Welche Eigenschaften du dafür nachprüfen musst hast du ja schon geschrieben. Warum das so ist ist ne gute Frage. Da scheint man sich durch ein paar Beweise durchkämpfen zu müssen. Den hier habe ich bei meiner Suche gefunden: http://de.scribd.com/doc/53719998/39/Fi ... tive-roots
Vll hat ja noch jemand ne andere Schrift gefunden?!

VG

L4_
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 104
Registriert: 24. Apr 2012 15:44

Re: Aufgabe 1 Generator

Beitrag von L4_ » 24. Dez 2012 14:06

Bestimmen Sie einen Generator g von \((\mathbb{Z}_{p})\), indem Sie wiederholt ein (gleichverteilt) zufälliges g \(\in\) {2, . . . , p − 1} wählen,
bis \(g^{2} \ne 1~mod~p\) und \(g^{p'} \ne 1~mod~p\) gilt.
Ich bin bei meiner eigenen Implementierung etwas skeptisch...
Ich habe ebenfalls genau das implementiert - jedoch wird meine Wahl des g's bereits beim ersten Versuch erfolgreich und nicht wie bei JannikV nach mehreren Versuchen. Das Ver- und Entschlüsseln klappt auch bei mir, aber irgendwie es ist seltsam, dass mein zufällig gewähltes g bereits im ersten versuch auch der Generator wird.
Auf der anderen Seite Frage ich mich aber, ob die Wahrscheinlichkeit sowieso nicht verschwindend gering ist, dass die oberen Konditionen mal False auswerten.

Hat jemand eine idee hierzu?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Aufgabe 1 Generator

Beitrag von JannikV » 24. Dez 2012 14:13

Hast du das mehrfach getestet? Also ich hab auch oft beim ersten Versuch einen Generator gefunden. Die Wahrscheinlichkeit dafür ist bei Sophie-Germain-Primzahlen wohl ziemlich hoch. Aber eben nicht immer direkt beim ersten mal. Kann auch den ein anderen anderen Versuch mehr dauern.

Aber wenn du skeptisch bist kannst du ja einfach mal die Bitlänge auf nen einstelligen Wert ändern und per Hand nachrechnen ob was sinnvolles rauskommt.

VG

L4_
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 104
Registriert: 24. Apr 2012 15:44

Re: Aufgabe 1 Generator

Beitrag von L4_ » 24. Dez 2012 14:23

Hmm ja, aber sogar nur bei 8 Bit länge schafft er es beim 1. Versuch.... müsst mal per Hand nachrechnen.

Ferner müsste doch noch auch die Formel aus aus Ü4 gelten, oder?

Für alle x gilt:
g^x mod p == 1 => x teilt |G| (wobei |G| hier p-1 ist)

Ich habe genau das mal in endlosschleife überprüft, fange mit x = 1 an und inkrementiere dann immer um eins.
Aber die Auswertung (p-1) % x == 0 wird unter der genannten Voraussetzung bei mir nie true.

EDIT:
Ich muss wohl meine Effiziente Exponentierung nochmal untersuchen, 2^2 z.B. ergab gerade nicht 4..

EDIT2:
Gut, lag also an der Implementierung - jetz brauch der Generator auch mal länger - aber nun wird diese Folgerung oben unter der Voraussetzung nur einmal am Anfang wahr, danach aber scheinbar auch nie wieder...

sab
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 28. Okt 2011 08:42

Re: Aufgabe 1 Generator

Beitrag von sab » 2. Jan 2013 20:56

JannikV hat geschrieben:Es geht also schnell einen zu raten und zu gucken ob es wirklich einer ist (bei mir braucht er ungefähr 2 bis 15 Versuche um einen zu finden).
Ich rate jetzt tatsächlich auch einen und komme so auch in wenigen Versuchen auf eine (hoffentlich richtige) Lösung :)

Benutzeravatar
m_plaul
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 27. Mai 2009 12:43

Re: Aufgabe 1 Generator

Beitrag von m_plaul » 9. Jan 2013 16:14

Ich stehe hier etwas auf dem Schlauch, weil mir die Wahl von g noch nicht ganz klar ist.

Ist bei g^2 und g^p' != 1 mod p die rechte Seite nicht sowieso immer 1? 1 mod (irgendeine Zahl größer 1) ergibt doch immer 1. Da g nun im Intervall 2 bis p-1 liegt, ist das beim kleinsten Element 2 mit 2^2=4 != 1 mod p=1 sowieso erfüllt. Gleiches gilt für g^p'.

Das kann ich doch deshalb so einfach sagen, weil p' mindestens eine 96 Bit große Primzahl ist. D.h. irgendeine (Prim)zahl mit 96 Bits ist doch definitiv größer als 1, wodurch 1 mod (die besagte Zahl) doch immer 1 ergibt. Fazit wäre doch, dass 2 immer ein Generator ist?

errt
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 18. Okt 2012 19:12

Re: Aufgabe 1 Generator

Beitrag von errt » 9. Jan 2013 17:09

Nur dass da wohl eigentlich nicht \(g^2 \not= 1 \bmod{p}\) stehen sollte, sondern \(g^2 \not\equiv 1 \pmod{p}\), also \((g^2 \bmod{p}) \not= (1 \bmod{p})\). Und dass muss ja nicht zwangsläufig gelten.

Benutzeravatar
m_plaul
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 27. Mai 2009 12:43

Re: Aufgabe 1 Generator

Beitrag von m_plaul » 9. Jan 2013 18:33

Gut zu wissen, danke dir!
Aber woher weiß ich das, wenn ich nicht gerade das Forum als "Hilfestellung" habe und dann bei so einer Aufgabe in der Klausur sitze?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Aufgabe 1 Generator

Beitrag von JannikV » 9. Jan 2013 19:00

Blöde Antwort aber das ist bei modularer Arithmetik halt so. Wenn da irgendwas gleich oder kongruent irgendwas modulo irgendwas steht bedeutet das, dass sie beim Teilen durch den Modul den gleichen Rest lassen. Man rechnet also beiden Seiten modulo.


VG

Antworten

Zurück zu „Archiv“