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: Anonymer Nutzer 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?

  1. Thema

Neues Thema Ansicht wechseln


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

Stellenmarkt
  1. RSG Group GmbH, Berlin
  2. Sky Deutschland GmbH, Unterföhring bei München
  3. über experteer GmbH, Sindelfingen
  4. über experteer GmbH, Nürnberg

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Spiele-Angebote
  1. 3,99€
  2. 44,99€
  3. (-79%) 12,50€
  4. 137,70€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Geothermie: Wer auf dem Vulkan wohnt, muss nicht so tief bohren
Geothermie
Wer auf dem Vulkan wohnt, muss nicht so tief bohren

Die hohen Erwartungen haben Geothermie-Kraftwerke bisher nicht erfüllt. Weltweit setzen trotzdem immer mehr Länder auf die Wärme aus der Tiefe - nicht alle haben es dabei leicht.
Ein Bericht von Jan Oliver Löfken

  1. Nachhaltigkeit Jute im Plastik
  2. Nachhaltigkeit Bauen fürs Klima
  3. Autos Elektro, Brennstoffzelle oder Diesel?

IAA 2019: PS-Wahn statt Visionen
IAA 2019
PS-Wahn statt Visionen

IAA 2019 Alle Autobosse bekennen sich auf der IAA zur Nachhaltigkeit, doch auf den Ständen findet man weiterhin viele große, spritfressende Modelle. Dabei stellt sich die grundsätzliche Frage: Ist das Konzept der Automesse noch zeitgemäß?
Eine Analyse von Dirk Kunde


    HP Pavilion Gaming 15 im Test: Günstig gut gamen
    HP Pavilion Gaming 15 im Test
    Günstig gut gamen

    Mit dem Pavilion Gaming 15 bietet HP für 1.000 Euro ein Spiele-Notebook an, das für aktuelle Titel genügend 1080p-Leistung hat. Auch Bildschirm und Ports taugen, dafür nervt uns die voreingestellte 30-fps-Akku-Drossel.
    Ein Test von Marc Sauter

    1. Gaming-Notebooks Asus ROG mit Core i9 und fixen oder farbstarken Displays

    1. Beatbox: Das Pappmischpult zum Selberbauen
      Beatbox
      Das Pappmischpult zum Selberbauen

      Kickstarter ist auch eine Plattform für sonderbare Produkte. Die Beatbox ist beispielsweise ein programmierbares MIDI-Mischpult, das von Nutzern zusammengebaut wird. Das Chassis ist aus Pappe konstruiert. Die Buttons stammen von Arcade-Automaten.

    2. iPhone 11 Pro Max: Das neue iPhone hat 4 GByte RAM und wesentlich mehr Akku
      iPhone 11 Pro Max
      Das neue iPhone hat 4 GByte RAM und wesentlich mehr Akku

      Auch beim iPhone 11 Pro Max lässt sich iFixit eine komplette Demontage nicht entgehen: Das Gerät nutzt wohl tatsächlich 4 GByte RAM. Außerdem waren die Bastler vom wesentlich größeren Akku und gleich zwei Ladekabeln überrascht.

    3. Fairtube: Google lädt die Youtuber-Gewerkschaft zu Gesprächen ein
      Fairtube
      Google lädt die Youtuber-Gewerkschaft zu Gesprächen ein

      Mehr Transparenz, mehr Entscheidungsrecht und eine Anlaufstelle: Fairtube fordert von Googles Videoplattform Youtube bessere Arbeitsbedingungen für Inhalteersteller. Die Parteien werden im Oktober miteinander sprechen. Beide Seiten sind in ihren Ansichten recht weit voneinander entfernt.


    1. 13:29

    2. 13:01

    3. 12:08

    4. 11:06

    5. 08:01

    6. 12:30

    7. 11:51

    8. 11:21