Matroids Matheplanet Forum Index
Moderiert von Florian
Informatik » Kryptologie » ElGamal finden der Primitivwurzeln
Druckversion
Druckversion
Autor
Universität/Hochschule J ElGamal finden der Primitivwurzeln
steamroy
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-01-14


Schönen guten Tag,

zur Zeit arbeite ich an meiner Diplomarbeit zu dem Thema Kryptographie im allgemeinen. Ich stelle dabei AES, RSA, OTP sowie ElGamal (aufgrund der hohen Ähnlichkeit auch Diffie Hellmann) und die allgemeine Funktionsweise hybrider Verfahren vor, zusammen mit Beispielen und einer "oberflächlichen" Kryptanalyse.

Es handelt sich zwar um einen dualen IT-Studiengang, jedoch wurden die Grundlagen der Mathematik nur stiefmütterlich und Kryptographie bisher gar nicht behandelt. Ich entschuldige mich deshalb im vorhinein, wenn einige Bezeichnungen schlichtweg falsch sein sollten. Das letzte mal habe ich das ernsthaft vor 6 Jahren betrieben und die letzten 4 Wochen waren, neben meiner Arbeit, auffrischen, aufarbeiten, Fehler begehen, verzweifeln und wiederholen.

Eigentliche Fragestellung : Habe mich zwar durchs Forum geklickt, aber keinen Thread gesehen, der meine Frage zu genüge beantwortet (was bekanntlich nicht heißt, dass es einen solchen Thread nicht doch gibt).
Für ElGamal und DH werden die Parameter fed-Code einblenden
Dass dies bei DH aus öffentlichen Parametern und bei ElGamal aus privaten stammt, sei an dieser Stelle uninteressant.
p ist eine ungerade Primzahl von Genügender Größe.
Mein Problem ist fed-Code einblenden
fed-Code einblenden soll zufällig und gleichverteilt aus fed-Code einblenden gewählt werden.
Wie ich ElGamal verstanden haben, stellt fed-Code einblenden aber eine Primitivwurzel des Restklassenrings fed-Code einblenden . Deshalb erscheint mir die Aussage fed-Code einblenden ein wenig "flappsig" und unpräzise, da es den Anschein erweckt, dass ein fed-Code einblenden jede Zahl fed-Code einblenden annehmen kann solange fed-Code einblenden wahr ist.

Dabei ist doch fed-Code einblenden als Primitivwurzel (Teil der Gruppe mod p). Und ie Bestimmung eines fed-Code einblenden folgt aus:

fed-Code einblenden
fed-Code einblenden fed-Code einblenden
fed-Code einblenden

Unklar ist mir nun, wie die Eingrenzung des Restklassenrings/der zyklischen Gruppe vorgenommen wird.
Ist alleine die Erkenntniss, dass die Gruppe durch fed-Code einblenden gebildet wird ausreichend um mit Gewissheit sagen zu können, dass M eine zyklische Gruppe und damit jedes fed-Code einblenden eine Primitivwurzel von p ist? In diesem Fall wäre die Aussage fed-Code einblenden genügend und aussagekräftiger als die in der Literatur gebräuchliche fed-Code einblenden sein.

Falls nicht, müsste man die scheinbar zyklische Gruppe zuerst untersuchen und mit fed-Code einblenden fed-Code einblenden und n ein Element der Kardinalität ist, prüfen ob fed-Code einblenden mod p fed-Code einblenden

Über den letzten Teil bin ich selbst nich ganz sicher. Ich hoffe aber, dass die Idee kenntlich geworden ist und mir nicht mit einer Steinigung gedroht wird.

Ich hoffe auf Ihre Hilfe und möchte mich schon jetzt viele Male bedanken.


-----------------
Einstein, Newton, Pascal spielen Verstecken. Einstein sucht. Newton malt Quadrat mit a=1m auf Boden und stellt sich rein. Einstein findet Newton, sagt: Gefunden Newton. Newton sagt: nein ich bin Pascal N/m²



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
steamroy
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2021-01-14


Just nach dem absenden dieses Threads ist mir klar geworden, dass fed-Code einblenden gar nicht die Primitivwurzel ist, sondern die Ordnung der Gruppe. Nicht wahr?

Dann ist in fed-Code einblenden ,n der Generator und die Primitivwurzel.
Demnach hat sich meine ungelehrte Aussage über die Darstellung, der Auswahl von fed-Code einblenden ebenfalls erledigt.

Dann ist n Element der Menge M, die sich aus fed-Code einblenden ergibt. Meine Frage bezüglich der Primitivwurzeln und der zyklischen Gruppe bleiben jedoch unberührt. Kann man die Aussage "n ist ist in jedem Fall ein Element von M" ungeprüft stehen lassen? Oder muss man jedes n nocheinmal auf Zugehörigkeit der Gruppe prüfen?


-----------------
Einstein, Newton, Pascal spielen Verstecken. Einstein sucht. Newton malt Quadrat mit a=1m auf Boden und stellt sich rein. Einstein findet Newton, sagt: Gefunden Newton. Newton sagt: nein ich bin Pascal N/m²



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6662
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-01-14


Hallo steamroy,

zunächst:

Du musst zwischen Zahlen und Mengen, die aus Zahlen bestehen, streng unterscheiden!

So etwas ergibt keinen Sinn: \(\alpha=\{2,...,p-2\}\), \(\alpha\in\varphi(\varphi(p))\) etc.

Tatsächlich ist beim Elgamal-Verfahren p eine Primzahl, nämlich die Ordnung einer zyklischen Gruppe \((G,\cdot)\) mit erzeugendem Element g. Es gilt also \(G=\{g,g^2,...,g^p\}\).

Der geheime Schlüssel \(\alpha\) ist eine Zahl, die kleiner als p ist. Der öffentliche Schlüssel ist dann ein Element aus G, nämlich \(g^\alpha\in G\).

Das Elgamal-Verfahren beruht auf der (unbewiesenen) Tatsache, dass aus \(g^\alpha\) nicht \(\alpha\) bestimmt werden kann.

Ich empfehle dir, mal ein konkretes Zahlenbeispiel (mit moderaten Zahlen) durchzurechnen, um dir den Algorithmus klar zu machen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
steamroy
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2021-01-14


Guten Tag StrgAltEntf,

Danke für die schnelle Antwort. Das hat einige Unklarheiten beseitigt.

Bzgl. der falschen Notation... ich kann mich nicht genug entschuldigen. Ich versuche mir ein Thema anzueignen, von dem ich bis vor 4 Wochen nichts wusste, außer was fed-Code einblenden etc. sind. Das alleine ist schon arrogant zu nennen. Dann tue ich es noch, um damit eine wissenschaftliche Arbeit in die Welt zu setzen. Bin schon froh, dass sich da überhaupt jemand herblässt und mir ant

Die Algorithmen verstehe ich denke ich soweit, zumindest den groben Ablauf, die zugrunde liegende Idee, die das effiziente Rückrechnen verhindern soll und wie ich es programmieren könnte. Die Mathematik dahinter stellt für mich die größte Hürde dar. Außer Schulmathematik und Polynomdivision aus dem Mathegrundkurs der Studieneinführung, habe ich nur meine Bücher. Die tun zwar ihr bestes, können mich aber leider nicht korrigieren, wenn ich die Dinge falsch angehe. Deswegen vielen Dank an dich.

Hab ein, zwei Zahlenbeispiel durchgerechnet. Dabei hat sich auch die Frage nach der zyklischen Gruppe abschließend geklärt. Und falls noch jemand einmal eine solche Frage hat:
Diffie-Hellmann ( DH ) ElGamal zyklische Gruppe Restringklasse Primitivwurzel
Alle fed-Code einblenden sind Teil einer zyklische Gruppe und sind alle primitiven Wurzeln von p. fed-Code einblenden gibt an, wie viele fed-Code einblenden es gibt. Wenn fed-Code einblenden mod p

Nochmal, vielen Dank.


-----------------
Einstein, Newton, Pascal spielen Verstecken. Einstein sucht. Newton malt Quadrat mit a=1m auf Boden und stellt sich rein. Einstein findet Newton, sagt: Gefunden Newton. Newton sagt: nein ich bin Pascal N/m²



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6662
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-01-14


Zumindest über \(\IR\) brauchst du für dein Thema nicht so viel zu wissen 😃

Beachte, dass sich bei DH und Elgamal die Gruppen, in denen du rechnest i. d. R. unterscheiden.

Bei DH rechnet man in der Gruppe \((\IZ_p,\cdot)\) für eine Primzahl p. Hier benötigt man eine Primitivwurzel mod p.

Bei Elgamal rechnet man in der Gruppe \((\IZ_q,\cdot)\) für eine Primzahl q bzw. in einer Untergruppe davon. p ist ein Teiler von q-1 und ebenfalls eine Primzahl. \((\IZ_q,\cdot)\) hat dann eine Untergruppe der Ordnung p. Und dann wählt man ein Element g der Ordnung p, und man rechnet in der von g erzeugten Untergruppe. Für die Wahl von \(\alpha\) gibt es (wenn wir beide dasselbe mit \(\alpha\) meinen) p-1 (und nicht \(\varphi(\varphi(p))\)) Möglichkeiten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
steamroy
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-01-15


hm... Ok. das hatte ich nicht auf dem Schirm.

Wenn q eine genügend hohe Primzahl ist,dann gibt es ein fed-Code einblenden und ein fed-Code einblenden .Es gilt dann ebenfallsg fed-Code einblenden . φ(φ(q)) müsste demnach die Kardinalität
der ersten Untergruppe wiedergeben?
Sei q=17,dann fed-Code einblenden (17)=q-1=16.Da q eine Primzahl ist.Die Kardinalität der Untergruppe U findet sich dann durch φ(16)=24-1+(2-1)=8
Sei U={3,5,6,7,11,12,14}. Dann gibt es ein g und U mit einer Ordnung p. Hier steige ich jetzt bei deiner Erläuterung aus.
Wie ich es interpretieren würde, wäre bei dieser Konstellation eine Lösung nicht möglich, da kein p in U existiert, dass für (q-1/p)=a die Bedingung a fed-Code einblenden |\ a=(q-1)/p erfüllt. Allgemein sollte das hier ja nicht existieren können, da wir ja alle Teilerfremden in den Gruppen haben, die durch fed-Code einblenden (q) entstehen.
Oder wähle ich jetzt z.b. 6^5 mod 17 = 7 für meinen Public Key?

Also dagegen sind ja OTP und RSA ein Kinderspiel... AES ist nochmal en ähnlicher Prügel. AES wird aber durch die Runden aufgebläht und die Schlüssellänge, DH und ElGamal sind ne andere Liga.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6662
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2021-01-15


Du hast zwar schon abgehakt, ich antworte aber trotzdem mal.

Unklar ist mir, was du mit \(\IZ_{q'}\) und "erster Untergruppe" meinst.

q = 17 zu wählen, ist keine so gute Idee, da q-1 keinen großen Primteiler besitzt. Wähle für dein Beispiel besser q = 23 und p = 11.

Jetzt suchst du eine Element g in \((\IZ_{q},\cdot)\) der Ordnung 11. Z. B. g = 4.

Als Secret Key kannst du dann ein \(\alpha<p\) wählen, etwa \(\alpha=7\). Der Public Key ist dann \(4^7\mod 23=8\).

Überlege dir nun, wie z. B. die Nachricht "10" mithilfe des Public Keys  verschlüsselt wird.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
steamroy hat die Antworten auf ihre/seine Frage gesehen.
steamroy hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]