Matroids Matheplanet Forum Index
Moderiert von Bilbo matph
Matroids Matheplanet Forum Index » Informatik » Komplexität diskreter Logarithmen
Autor
Kein bestimmter Bereich Komplexität diskreter Logarithmen
steamroy
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.10.2013
Mitteilungen: 19
Wohnort: Hessen , Deutschland
  Themenstart: 2021-02-14

Schönen guten Tag, eine Frage bezüglich der schwierigkeit diskreter Logarithmen lässt mir keine Ruhe. Wenn ich das anhand von Diffie-Hellmann / ElGamal kurz erläutern dürfte. DH öffentliche Parameter die jedem (auch einem Angreifer) bekannt sind: Die Primzahl p Die natürliche zahl g

a=log_A g mod p bzw. \ B=g^b mod p -> b=log_A g mod p Wobei a den privaten Schlüssel von Alice und b den privaten Schlüssel von Bob darstellt. Jetzt kommt mir aber die Berechnung des a oder des b sehr trivial vor, gerade wenn ich aus sicht der Komplexitätstheorie auf ein log_x (a) schaue. Gleiches gilt für ElGamal. Öffentliche Parameter sind: p als Primzahl g als natürliche Zahl

hier Viele Grüße


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2969
  Beitrag No.1, eingetragen 2021-02-14

Du scheinst da die Funktionen zu plotten und nicht die Komplexität ihrer Berechnung. Die zwei Dinge haben kaum etwas miteinander zu tun. Simples Beispiel: $x^2$ wächst schneller als $\sqrt{x}$. Jetzt berechne mal ohne Taschenrechner auf 10 Nachkommastellen $5^2$ und $\sqrt{5}$. Wofür benötigst du länger?


   Profil
steamroy
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.10.2013
Mitteilungen: 19
Wohnort: Hessen , Deutschland
  Beitrag No.2, vom Themenstarter, eingetragen 2021-02-14

Ah, natürlich! Vielen Dank für die Richtigstellung. Ich wäre diesem weißen Kaninchen noch ewig nachgejagt. Kannst du eventuell dazu eine Graphik oder ein Buch empfehlen, dass das verdeutlicht? Eine Google-Suche führt mich immer wieder zu dem von mir verlinkten Graphen(o.ä.).


   Profil
steamroy
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.10.2013
Mitteilungen: 19
Wohnort: Hessen , Deutschland
  Beitrag No.3, vom Themenstarter, eingetragen 2021-02-14

Hmm... Das Problem bei diesem Logarithmus ist, dass ein x nicht eindeutig bestimmbar ist, alleine durch das lösen der gleichung. Da wir in einem Ring sind entsteht bei dem addieren von k*(p-1) zu x eine weitere Lösung, sodass zwar eine Lösungsmenge M bestimmbar ist, diese aber N groß sein kann. Die Schwierigkiet ist es dann aus der Menge M die richtige Lösung zu filtern. Ansonsten ist dem Angreifer nur bekannt, dass er ein \ a\el\ M hat, aber nicht welches es ist. Sehe ich das richtig?


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2969
  Beitrag No.4, eingetragen 2021-02-14

Literaturtipps wird jemand anderes geben müssen. Für diese Art der Kryptographie ist es wichtig zu wissen, dass man mit relativ wenig Aufwand modular potenzieren kann (Stichwort: Repeated Squaring), es nach jetzigem Stand jedoch keinen effizienten Algorithmus für die Umkehr, nämlich den modularen/diskreten Logarithmus gibt. PS.: Der diskrete Logarithmus ist im Allgemeinen weder eindeutig noch immer lösbar. Bspw. $5^n \equiv 16 \mod 19$ hat die zwei Basislösungen $7$ und $16$. $5^n \equiv 2 \mod 19$ ist hingegen unlösbar. [Die Antwort wurde nach Beitrag No.2 begonnen.]


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7081
Wohnort: Milchstraße
  Beitrag No.5, eingetragen 2021-02-14

\quoteon(2021-02-14 15:48 - steamroy im Themenstart) Der entsprechende Graph befindet sich hier \quoteoff Hallo steamroy, dieser Funktionsgraph hat nichts mit dem Diskreten-Logarithmus-Problem zu tun. Das Zauberwort lautet "diskret". D. h. du musst jeweils noch modulo p rechnen. Dann springt der Funktionsgraph wild, scheinbar wahllos zwischen 1 und p-1 hin und her. \quoteon(2021-02-14 16:29 - steamroy in Beitrag No. 3) Das Problem bei diesem Logarithmus ist, dass ein x nicht eindeutig bestimmbar ist, alleine durch das lösen der gleichung. \quoteoff Nein, das ist nicht das Problem. [Die Antwort wurde nach Beitrag No.2 begonnen.]


   Profil
steamroy hat die Antworten auf ihre/seine Frage gesehen.

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]