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?

  1. Thema

Neues Thema Ansicht wechseln


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

Stellenmarkt
  1. Lidl Dienstleistung GmbH & Co. KG, Neckarsulm
  2. LIDL Stiftung & Co. KG, Neckarsulm
  3. Klosterfrau Berlin GmbH, Berlin
  4. Bayerische Versorgungskammer, München

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Hardware-Angebote
  1. 274,00€
  2. 349,00€
  3. 107€ (Bestpreis!)
  4. täglich neue Deals bei Alternate.de


Haben wir etwas übersehen?

E-Mail an news@golem.de


CO2-Emissionen und Lithium: Ist das Elektroauto wirklich ein Irrweg?
CO2-Emissionen und Lithium
Ist das Elektroauto wirklich ein Irrweg?

In den vergangenen Monaten ist die Kritik an batteriebetriebenen Elektroautos stärker geworden. Golem.de hat sich die Argumente der vielen Kritiker zur CO2-Bilanz und zum Rohstoff-Abbau einmal genauer angeschaut.
Eine Analyse von Friedhelm Greis

  1. Reichweitenangst Mit dem E-Auto von China nach Deutschland
  2. Ari 458 Elektro-Lieferwagen aus Leipzig kostet knapp 14.000 Euro
  3. Nobe 100 Dreirädriges Retro-Elektroauto parkt senkrecht an der Wand

Mobilfunktarife fürs IoT: Die Dinge ins Internet bringen
Mobilfunktarife fürs IoT
Die Dinge ins Internet bringen

Kabellos per Mobilfunk bringt man smarte Geräte am leichtesten ins Internet der Dinge. Dafür haben deutsche Netzanbieter Angebote für Unternehmen wie auch für Privatkunden.
Von Jan Raehm

  1. Smart Lock Forscher hacken Türschlösser mit einfachen Mitteln
  2. Brickerbot 2.0 Neue Schadsoftware möchte IoT-Geräte zerstören
  3. Abus-Alarmanlage RFID-Schlüssel lassen sich klonen

In eigener Sache: Neue Workshops zu agilem Arbeiten und Selbstmanagement
In eigener Sache
Neue Workshops zu agilem Arbeiten und Selbstmanagement

Wir haben in unserer Leserumfrage nach Wünschen für Weiterbildungsangebote gefragt. Hier ist das Ergebnis: Zwei neue Workshops widmen sich der Selbstorganisation und gängigen Fehlern beim agilen Arbeiten - natürlich extra für IT-Profis.

  1. Golem Akademie Golem.de startet Angebote zur beruflichen Weiterbildung
  2. In eigener Sache Zweiter Termin für Kubernetes-Seminar
  3. Leserumfrage Wie können wir dich unterstützen?

  1. Wettbewerb: US-Regierung ermittelt gegen Amazon, Facebook und Google
    Wettbewerb
    US-Regierung ermittelt gegen Amazon, Facebook und Google

    In den USA könnte es ungemütlich für die großen Tech-Unternehmen werden. Das US-Justizministerium will mögliche Behinderungen des Wettbewerbs durch Amazon, Facebook und Google prüfen. Die Gründe dafür könnten auch politischer Natur sein.

  2. Auto-Entertainment: Carplay im BMW wird teils günstiger
    Auto-Entertainment
    Carplay im BMW wird teils günstiger

    Für BMWs Carplay-Unterstützung müssen Kunden ein Navigationssystem kaufen und ein kostenpflichtiges Abonnement abschließen. Das ist nun günstiger geworden.

  3. Cabrio: Renault R4 Plein Air als Elektro-Retroauto
    Cabrio
    Renault R4 Plein Air als Elektro-Retroauto

    Renault hat sein Kultmodell aus den späten 60er Jahren neu aufgelegt. Der Renault 4 Plein Air ist zeitgemäß mit einem Elektroantrieb ausgerüstet.


  1. 08:22

  2. 07:30

  3. 07:18

  4. 19:25

  5. 17:38

  6. 17:16

  7. 16:30

  8. 16:12