Abo
  1. Foren
  2. Kommentare
  3. Security
  4. Alle Kommentare zum Artikel
  5. › MIT: Kryptopuzzle 15 Jahre zu früh…

und wie hat man Richtigkeit der Lösung

  1. Thema

Neues Thema Ansicht wechseln


  1. und wie hat man Richtigkeit der Lösung

    Autor: hle.ogr 30.04.19 - 16:05

    Verifiziert? Irgendwie geht das nicht aus dem Text füt mich hervor.

  2. Re: und wie hat man Richtigkeit der Lösung

    Autor: Compufreak345 30.04.19 - 16:31

    > Doch Rivest gab demjenigen, der das Rätsel löst, eine Möglichkeit, die Primfaktoren zu erfahren. Er verschlüsselte eine kurze Nachricht mit dem Ergebnis des Rätsels und teilte diese ebenfalls mit.

    Ich würde mal annehmen durch die Entschlüsselung der hier beschriebenen Nachricht.

  3. Re: und wie hat man Richtigkeit der Lösung

    Autor: hle.ogr 30.04.19 - 16:46

    Genau die Formulierung verstehe ich nciht. Ist nun die Lösung der Schlüssel, um die Nachricht zu entschlüsseln? Im text steht, dass in der verschlüsselten Nachricht die Primenfaktoren stehen, mit der man das Ganze schneller berechnen kann. Irgendwie habve ich es nicht verstanden, oder es ist einfach nur schlecht im Artikel formuliert.

  4. Re: und wie hat man Richtigkeit der Lösung

    Autor: Compufreak345 30.04.19 - 16:59

    Die Formulierung ist nicht optimal, aber ich bin mir recht sicher dass es so ist:

    Mit der Lösung ist eine kurze Nachricht verschlüsselt. Der Schlüssel um diese Nachricht zu entschlüsseln ist die Lösung.

    In dieser kurzen Nachricht sind (wahrscheinlich neben einem kurzen Text) die Primfaktoren enthalten, mit der man das Rätsel schneller lösen kann. Die können somit auch als Nachweis dienen das Rätsel gelöst zu haben da man die sonst wohl eher nicht herausbekommt.

    Ist irgendwie leicht verwirrend aber ich hoffe ich habe es etwas besser verständlich hingekriegt ^^

  5. Re: und wie hat man Richtigkeit der Lösung

    Autor: Apfelbaum 30.04.19 - 17:05

    Ich hab den Artikel gar nicht gelesen, deshalb danke ich dir sehr für diese kompakte und leicht verständliche Erläuterung des Ablaufs! Super :-).

  6. Re: und wie hat man Richtigkeit der Lösung

    Autor: hle.ogr 30.04.19 - 17:36

    Aber das würde bedeuten, dass er vielleicht gar nicht das Rätsel wirklich gelöst hat. Vielleicht hat er ja auch nur einfach die Verschlüsselung geknackt :-o Obwohl das dann einem Disaster gleichkommt.

    Aber danke für die Antwort.

  7. Re: und wie hat man Richtigkeit der Lösung

    Autor: _Keks_ 30.04.19 - 23:07

    Du solltest wirklich den Artikel lesen. Deine Frage wird da geklärt und auch dein letzter Comment wird da erklärt. Die Verschlüsselung zu knacken hätte länger gedauert als das Rätsel zu lösen.

  8. Re: und wie hat man Richtigkeit der Lösung

    Autor: shoggothe 30.04.19 - 23:12

    Ja, lies den Artikel. Da steht auch, dass der Lösungsweg bei der Präsentation offenbart wird und bisher der Öffentlichkeit noch nicht bekannt ist.

  9. Re: und wie hat man Richtigkeit der Lösung

    Autor: ML82 01.05.19 - 03:50

    nicht wenn man besser raten kann ... menschen spielen auch lotto ^^



    1 mal bearbeitet, zuletzt am 01.05.19 03:51 durch ML82.

  10. Re: und wie hat man Richtigkeit der Lösung

    Autor: Quantium40 01.05.19 - 07:08

    Das geht aber aus dem Rätsel hervor:
    > pw.println("The result is the secret message (8 bits per character),");
    > pw.println("including information that will allow you to factor n.");
    > pw.println("(The extra information is a seed value b, such that ");
    > pw.println("5^b (mod 2^1024) is just below a prime factor of n.)");

  11. Re: und wie hat man Richtigkeit der Lösung

    Autor: x.adama 01.05.19 - 08:48

    Mein erster Gedanke war auch, wie kann man eine Lösung für ein Problem anbieten, wenn die Lösung des Problems auch für den Ersteller des Rätsel nicht möglich ist. Ich habe das Rätsel so verstanden, dass auf dem Weg zur Lösung mehrere Zwischenschritte erforderlich sind, die die "Summe" reduzieren. Dies geschieht durch die Primzahlen, die für jeden Zwischenschritt zur Verfügung gestellt werden. Würde man diese Primzahlen gleich zu Beginn zur Verfügung stellen, könnte man auch diesen Vorgang automatisieren und in das Programm einbauen. Die Lösung würde dann innerhalb kurzer Zeit errechnet werden können, bzw. könnte man die Reduzierung der Summe schon vorab, für den letzten Schritt errechnen, sich das abarbeiten der Quadrierungen ersparen. Aber was solls. Die Aufgabe alle Sandkörner am Strand von Ibiza zu zählen, ist noch anspruchsvoller, aber mindestens genauso sinnvoll.

  12. Re: und wie hat man Richtigkeit der Lösung

    Autor: Mingfu 01.05.19 - 09:25

    x.adama schrieb:
    --------------------------------------------------------------------------------
    > Mein erster Gedanke war auch, wie kann man eine Lösung für ein Problem
    > anbieten, wenn die Lösung des Problems auch für den Ersteller des Rätsel
    > nicht möglich ist.

    Für den Ersteller ist die Lösung des Rätsels trivial. Da er nämlich den Modulus n = p * q aus zwei selbst gewählten großen Primzahlen p und q zusammengesetzt hat, die er jedoch nicht verrät (sondern nur deren Produkt n gibt er bekannt), kann er dieses Rätsel viel einfacher berechnen. Er muss nämlich nicht sämtliche Quadrierungsschritte ausführen.

    Nach dem kleinen Satz von Fermat gilt nämlich für Primzahlen p, dass (2^(p-1)) mod p = 1 ist bzw. (2^p) mod p = 2. Die Potenzen ergeben also einen Zyklus der Periodenlänge p-1, fangen also dann wieder von vorn an. Somit muss man also gar nicht die ganzen Quadrierungsschritte durchführen, sondern muss nur wissen, wie groß der Rest ist, wenn man den Exponenten durch (p-1) teilt. Und nur diese dann vergleichsweise kleine Potenzierung rechnet man auch wirklich aus.

    Nun ist n natürlich keine Primzahl (sondern das Produkt aus zwei Primzahlen), so dass man den kleinen fermatschen Satz darauf nicht direkt anwenden kann, aber man kann das entweder mod p und mod q (die beides Primzahlen sind) separat berechnen und dann mittels chinesischem Restwertsatz mod n zusammensetzen oder aber die entsprechende Beziehung für n nutzen, die lautet: 2^((p-1) * (q-1)) mod n = 1. Außenstehende können das dagegen nicht nutzen, weil ohne die Kenntnis von p und q eben auch das Produkt (p-1) * (q-1) nicht zu ermitteln ist. Damit ist es also für sie nicht möglich, die Periodenlänge der Potenzen mod n zu bestimmen.



    1 mal bearbeitet, zuletzt am 01.05.19 09:26 durch Mingfu.

  13. Re: und wie hat man Richtigkeit der Lösung

    Autor: hle.ogr 01.05.19 - 09:34

    Danke, so hatte ich es auch verstanden, wenngleich nicht mit dem vertiefenden Kenntnissen. Mir war nur nicht ganz klar, wie geprüft wird, ob man die richtige Lösung errechnet hat. Aber die Lösung ist wohl tatsächlich der Schlüssel zum entschlüsseln der Nachricht. Das war mir nicht so ganz klar, zumindest hatte ich naiv gedacht, dass man ja auch überlegen könnte, direkt die Verschlüsselung "errechnen". Zeit genug hätte man ja.

  14. Re: und wie hat man Richtigkeit der Lösung

    Autor: Mingfu 01.05.19 - 10:02

    Die Faktorisierung von n in die Primfaktoren p und q durchzuführen, sollte normalerweise auch in dieser Zeit keinesfalls funktionieren. Da n eine Zahl in der Größenordnung von 2048 bit ist, müsste man ansonsten RSA selbst mit dieser Schlüssellänge (die heutzutage als auf absehbare Zeit sicher angenommen wird) als gebrochen ansehen.

    Die Verschlüsselung der verwendeten Nachricht selbst, ist praktisch ein One-Time-Pad, damit also nicht angreifbar. Denn das Ergebnis der Potenzierung und damit der Schlüssel zum Entschlüsseln der Nachricht wird als pseudozufällige Bitfolge angesehen. Auch darüber kommt man also nicht weiter.

    Die Quadrierungsschritte auszuführen dürfte wahrscheinlich der einzig gangbare Weg sein.

  15. Re: und wie hat man Richtigkeit der Lösung

    Autor: gbomacfly 01.05.19 - 18:30

    Apfelbaum schrieb:
    --------------------------------------------------------------------------------
    > Ich hab den Artikel gar nicht gelesen, ...


    Das ist so oft das große Problem bei Diskussionen hier...



    1 mal bearbeitet, zuletzt am 01.05.19 18:32 durch gbomacfly.

  16. Re: und wie hat man Richtigkeit der Lösung

    Autor: Apfelbaum 01.05.19 - 21:39

    Das Problem liegt aber bei denen, die, obwohl sie den Artikel nicht gelesen haben, trotzdem ihre Meinung kundtun müssen.
    Du hast sicher gleich festgestellt, dass ich unter allen Threads zu diesem Artikel nur ein stiller Mitleser bin.

    Ein ebenso großes Problem hier sind aber auch provokative Trollposts.

  17. Re: und wie hat man Richtigkeit der Lösung

    Autor: 0110101111010001 03.05.19 - 09:41

    wieso bist du dann noch hier?

Neues Thema Ansicht wechseln


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Zum Login

Stellenmarkt
  1. SEW-EURODRIVE GmbH & Co KG, Bruchsal
  2. Dataport, Rostock
  3. Animus GmbH & Co. KG, Ratingen
  4. J. Schmalz GmbH, Glatten bei Freudenstadt

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Top-Angebote
  1. (heute u. a. Saugroboter)
  2. 149€
  3. (u. a. Metal Gear Solid V: The Definitive Experience für 8,99€ und Train Simulator 2019 für 12...
  4. (u. a. Seasonic Focus Gold 450 W für 46,99€ statt über 60€ im Vergleich)


Haben wir etwas übersehen?

E-Mail an news@golem.de


Physik: Den Quanten beim Sprung zusehen
Physik
Den Quanten beim Sprung zusehen

Quantensprünge sind niemals groß und nicht vorhersehbar. Forschern ist es dennoch gelungen, den Vorgang zuverlässig zu beobachten, wenn er einmal angefangen hatte - und sie konnten ihn sogar umkehren. Die Fehlerkorrektur in Quantencomputern soll in Zukunft genau so funktionieren.
Von Frank Wunderlich-Pfeiffer


    Digitaler Knoten 4.0: Auto und Ampel im Austausch
    Digitaler Knoten 4.0
    Auto und Ampel im Austausch

    Auf der Autobahn klappt das autonome Fahren schon recht gut. In der Stadt brauchen die Autos jedoch Unterstützung. In Braunschweig testet das DLR die Vernetzung von Autos und Infrastruktur, damit die autonom fahrenden Autos im fließenden Verkehr links abbiegen können.
    Ein Bericht von Werner Pluta

    1. LTE-V2X vs. WLAN 802.11p Wer hat Recht im Streit ums Auto-WLAN?
    2. Vernetztes Fahren Lobbyschlacht um WLAN und 5G in Europa
    3. Gefahrenwarnungen EU setzt bei vernetztem Fahren weiter auf WLAN

    Wolfenstein Youngblood angespielt: Warum wurden diese dämlichen Mädchen nicht aufgehalten!?
    Wolfenstein Youngblood angespielt
    "Warum wurden diese dämlichen Mädchen nicht aufgehalten!?"

    E3 2019 Der erste Kill ist der schwerste: In Wolfenstein Youngblood kämpfen die beiden Töchter von B.J. Blazkowicz gegen Nazis. Golem.de hat sich mit Jess und Soph durch einen Zeppelin über dem belagerten Paris gekämpft.
    Von Peter Steinlechner


      1. Load Balancer: HAProxy 2.0 bringt Neuerungen für HTTP und die Cloud
        Load Balancer
        HAProxy 2.0 bringt Neuerungen für HTTP und die Cloud

        In der neuen LTS-Version 2.0 liefern die Entwickler des Open-Source-Load-Balancers HAProxy unter anderem mit einem Kubernetes Ingress Controller und einer Data-Plane-API aus. Auch den Linux-Support hat das Team vereinheitlicht.

      2. Huawei: USA können uns "nicht totprügeln"
        Huawei
        USA können uns "nicht totprügeln"

        Huawei ist viel stärker von dem US-Boykott betroffen als erwartet, räumt der Gründer ein. Doch trotz hoher Umsatzeinbußen werde der Konzern in ein paar Jahren gestärkt aus den Angriffen hervorgehen.

      3. Freier Videocodec: Realtek stellt ersten SoC mit AV1-Decoder vor
        Freier Videocodec
        Realtek stellt ersten SoC mit AV1-Decoder vor

        Der Chiphersteller Realtek hat ein SoC für Set-Top-Boxen vorgestellt, das einen AV1-Decoder enthält. Es ist der erste Chip mit Hardware-Unterstützung für den freien Videocodec. Geräte damit sollten 2020 verfügbar sein.


      1. 15:35

      2. 14:23

      3. 12:30

      4. 12:04

      5. 11:34

      6. 11:22

      7. 11:10

      8. 11:01