| |
| Autor |
  ElGamal finden der Primitivwurzeln |
|
steamroy
Junior 
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
 |
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
  
\alpha und p bestimmt.
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
\alpha .
\alpha
\alpha={2,..., p-2} bzw. \alpha={2,..., \phi(p)-1}
Wie ich ElGamal verstanden haben, stellt
\alpha
\IZ_\phi(p)
\alpha={2,..., \phi(p)-1}
\alpha
\IZ
1<\alpha<p-2
Dabei ist doch
\alpha
\alpha
Sei p\el\IP , wobei \IP die Menge aller Primzahlen sei.
Dann ist die M Menge aller Primitivewurzeln \alpha von p gleich
der Menge aller Teilerfremden von \phi(p), also \alpha\el\IZ_(p-2) \| \alpha\el\phi(\phi(p)).
Daraus folgt die Begrenzung der Menge M, wie oben beschrieben durch p-2, da \phi(p) / \phi(p)=1 offensichtlich ist.
Unklar ist mir nun, wie die Eingrenzung des Restklassenrings/der zyklischen Gruppe vorgenommen wird.
Ist alleine die Erkenntniss, dass die Gruppe durch
\phi(\phi(p))
\alpha
\alpha={\alpha\el\phi(\(phi(p))}
\alpha={2,..., p-2}
Falls nicht, müsste man die scheinbar zyklische Gruppe zuerst untersuchen und mit
\alpha^n wobei
\alpha\el\phi(\(phi(p))}
\alpha^n
\el\phi(\phi(p)) ist.
Ü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²
|
 Notiz  Profil
 Quote
 Link |
steamroy
Junior 
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
|      Beitrag No.1, vom Themenstarter, eingetragen 2021-01-14
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6673
Herkunft: Milchstraße
 | 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.
|
Notiz Profil
Quote
Link |
steamroy
Junior
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
| 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
\IN \IZ \IR
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
\alpha
\phi(\phi(p))
\alpha
\alpha^n
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²
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6673
Herkunft: Milchstraße
| 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.
|
Notiz Profil
Quote
Link |
steamroy
Junior
Dabei seit: 24.10.2013
Mitteilungen: 19
Herkunft: Hessen , Deutschland
| 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
g \el\IZ_q´
p \el\IZ_q´
p\el\IZ_p
der ersten Untergruppe wiedergeben?
Sei q=17,dann
\phi(q)=\phi
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
\el\IN
\phi
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.
|
Notiz Profil
Quote
Link |
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6673
Herkunft: Milchstraße
| 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.
|
Notiz Profil
Quote
Link |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Themenstart: 2021-01-14