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

Ist mir etwas zu viel Mathematik

  1. Thema

Neues Thema Ansicht wechseln


  1. Ist mir etwas zu viel Mathematik

    Autor: wurstfett 30.04.19 - 10:45

    Ich verstehe nicht so ganz wie sie 1999 die Lösung kennen konnten. Oder woher sie die Primfaktoren kannten. Hatten die damals einen Supercomputer drangesetzt und wollten eigentlich nur sehen wie jemand das mit normeler Hardware löst? Könnte er dann nicht mal eben in der Cloud die primfaktoren geholt haben und dann so zur Lösung gekommen sein?

  2. Re: Ist mir etwas zu viel Mathematik

    Autor: justanotherhusky 30.04.19 - 10:49

    Die Ersteller des Rätsels haben sich die Primfaktoren selber ausgesucht.

  3. Re: Ist mir etwas zu viel Mathematik

    Autor: n27671 30.04.19 - 10:51

    Rivest hat zwei grosse Primzahlen gewählt und nur das Produkt dieser zwei Zahlen bekannt gegeben. Er kann das Rätsel schneller lösen, da er die Faktoren kennt. Diese aber aus dem Produkt herauszufinden ist (nach aktuellem Wissen und ohne Quantencomputer) noch schwieriger als das eigentliche Rätsel.
    Auch ein Cloud-Dienst bringt hier nicht viel, da die Berechnung wirklich sehr aufwändig ist.

  4. Re: Ist mir etwas zu viel Mathematik

    Autor: kendon 30.04.19 - 10:59

    Es ist 1999, ich denke mir das Rätsel aus: 29x37=1073.

    Ich gebe publik: "Die Lösung lautet 1073, aber wie bin ich drauf gekommen?"

    Jetzt schmeisst Du deinen Computer an und versuchst rauszufinden welche Rechnung ich genommen habe, in dem Du solange alle möglichen Produkte von Primzahlen ausrechnest, und guckst wo die Lösung stimmt. Gaaaaanz stark vereinfacht offensichtlich, und eine Lösung auf die man unter den gegebenen Bedingungen nur mit einem einzigen Rechenweg kommen kann.

    Im Endeffekt funktioniert asymmetrische Verschlüsselung (z.B. RSA) genau so, die Lösung ist der Public Key, die Rechnung der Private Key. Berechnen kann man den, nur der Aufwand ist so hoch dass es praktisch nicht machbar ist.

  5. Re: Ist mir etwas zu viel Mathematik

    Autor: wurstfett 30.04.19 - 11:29

    Mit der Erklärung verstehe ich wirklich eher worum es ging. Aus dem Artikel blieb bei mir irgendwie hängen dass eine zahl immer wieder quadriert und modulo genommen werden soll und mit dem Ergebnis weitergerechnet wird um irgendwann auf die Lösung zu kommen. Nach der Erklärung hier verstehe ich dass es quasi um das einsetzen der richtigen werte in eine Formel ging. danke für die Erklärung!

  6. So viel Mathematik ist das nicht

    Autor: Mingfu 30.04.19 - 11:54

    Wie schon genannt wurde: Wenn man die Primfaktoren des Modulus n kennt, ist das Rätsel sehr einfach zu lösen.

    Sei n = p * q mit p, q prim. Dann gilt nach kleinem fermatschen Satz:

    2^(p - 1) = 1 mod p
    2^(q - 1) = 1 mod q

    Das Rätsel 2^(2^t) mod n zu berechnen wird dadurch dann entsprechend einfach, wenn man zunächst in den Gruppen mod p und mod q rechnet.

    Dann lautet die Rechnung nämlich lediglich:

    2^((2^t) mod (p-1)) mod p
    2^((2^t) mod (q-1)) mod q

    Da p und q in der Größenordung von 1024 bit liegen, ist das also eine Rechnung, die dann einfach zu erledigen ist (das sind Rechnungen, wie sie auch bei normalen RSA-Verschlüsselungen auftreten).

    Das Ergebnis mod p und mod q setzt man dann mit dem Chinesischen Restsatz zusammen.

    Wir nehmen mal zur Veranschaulichung das Beispiel, welches auch dem Rätsel beiliegt:

    n = 253 = 11 * 23
    t = 10

    Es geht also um die Berechnung von 2^(2^10) mod 253.

    Wir berechnen also:
    2^(2^10 mod 10) mod 11 = 2^(1024 mod 10) mod 11 = 2^4 mod 11 = 16 mod 11 = 5
    2^(2^10 mod 22) mod 23 = 2^(1024 mod 22) mod 23 = 2^12 mod 23 = 2

    Ergibt nach Anwendung des Chinesischen Restsatzes = 71 mod 253.

  7. Re: Ist mir etwas zu viel Mathematik

    Autor: ChristophAugenAuf 30.04.19 - 12:23

    Grundlage von RSA ist ein Körper der auf Basis einer Restklasse gebildet wird. In einem Körper gibt es bzgl der Multiplikationsverknüpfung zu jeder Zahl ein inverses Element (außer zum neutralen Element der Addition)

    Beispiel: Restklasse 7

    Zur Zahl 4 ist hier das multiplikativ inverse Element 2
    Beweis: 4*2 / 7 = 1 Rest 1

    Der Knackpunkt ist jetzt, dass außer dem Schlüsselersteller niemand die Restklasse der beiden multiplikativ Inversen kennt. Denn verschlüsselt / entschlüsselt wird nicht über die Multiplikation sondern über Exponentieren. Die Restklasse die beim Exponentieren verwendet wird und bekannt ist, ist die Multiplikation der beiden geheimen Primfaktoren. Die geheime Restklasse ist die Eulersche FUnktion der beiden geheimen Primfaktoren.

    Beim Verschlüsseln mit RSA multiplizierst Du in der bekannten Restklasse den Geheimtext nun mit sich selbst, die Wiederholungen ist der öffentliche Schlüssel. Beim Entschlüssen wird der Geheimtext mit sich selbst multipliziert mit Wiederholungen in der Anzahl des privaten Schlüssels, auch wieder in der bekannten Restklasse. So gelangt man wieder zum Ausgangspunkt, den Klartext. Du siehst, dass unter Vernachlässigen von sonstigen Optimierungen die beiden Exponenten sowohl als öffentlich als auch private Komponente des Schlüssels dienen können.


    Falls Dir das nicht reicht: Der RSA Artikel bei Wikipedia ist gut verständlich und benötigt zum nachvollziehen kein großes Mathematiktalent.

  8. Re: Ist mir etwas zu viel Mathematik

    Autor: kendon 30.04.19 - 12:24

    Wie gesagt, da ist ganz viel Vereinfachung drin, komplett verstehe ich es auch nicht, aber für mich reicht das Verständnis was ich oben erklärt habe. Ich verstehe auch nicht den Destillationsprozess von Benzin auf chemischer Ebene, und halte mich trotzdem für einen passablen Fahrer und kann grundlegende Reparaturen und Wartungen an meinem Auto selbst durchführen ;)

  9. "Destillationsprozess von Benzin auf chemischer Ebene"

    Autor: Herricht 30.04.19 - 13:41

    Ist Destillation nicht reine Physik?

  10. Re: "Destillationsprozess von Benzin auf chemischer Ebene"

    Autor: kendon 30.04.19 - 15:27

    "Destillation" war hier verallgemeinernd verwendet, der gesamte Prozess wird auch als "Cracken" bezeichnet, in dem (Zitat Wikipedia) "mittel- und langkettige Kohlenwasserstoffe in kurzkettige Kohlenwasserstoffe gespalten werden". Nach meinem betont laienhaften Verständnis geht das über rein physikalische Vorgänge hinaus.
    Um genau zu sein sind Destillationsvorgänge nur ein Teil der gesamten Kette der Benzinherstellung.

    Allgemein wage ich zu bezweifeln dass jemand in diesem Forum in der Lage ist den Prozess in seiner Gänze zu überblicken, geschweige denn erklären zu können, aber wie wir sehen reicht es immerhin für Offtopic-Trollerei...

  11. Re: Ist mir etwas zu viel Mathematik

    Autor: derdiedas 30.04.19 - 15:34

    Faktorisierung ist einfach um Potenzen schwerer als eine einfache Multiplikation zweier Primzahlen :-)

    Wenn ich 59*17*13 rechne bekomme ich leicht 13039 heraus. Wenn ich Dir aber als Aufgabe gebe 13093 in drei Primzahlen zu zerlegen ist das um einiges komplizierter, und Du wirst einige Zeit beschäftigt sein.

  1. Thema

Neues Thema Ansicht wechseln


Um zu kommentieren, loggen Sie sich bitte ein oder registrieren Sie sich. Sie müssen ausserdem in Ihrem Account-Profil unter Forum einen Nutzernamen vergeben haben. Zum Login

Stellenmarkt
  1. BHS Corrugated Maschinen- und Anlagenbau GmbH, Weiherhammer
  2. operational services GmbH & Co. KG, Frankfurt am Main, Berlin, Dresden, München
  3. LAUDA Dr. R. Wobser GmbH & Co. KG, Burgwedel, Lauda-Königshofen
  4. Hornbach-Baumarkt-AG, Bornheim bei Landau Pfalz

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Top-Angebote
  1. 399€
  2. (u. a. We Are The Dwarves für 0,75€, Dark Souls: Remastered für 13,99€, Anno 2205 Ultimate...
  3. (u. a. Black+Decker Akku-Schlagbohrschrauber BDCHD18KBST, 18Volt für 99,90€, Hazet...


Haben wir etwas übersehen?

E-Mail an news@golem.de


  1. SIA: US-Chipbranche will 37 Milliarden Dollar für America First
    SIA
    US-Chipbranche will 37 Milliarden Dollar für America First

    Um ihre Führung bei Chiptechnologie zu sichern, müssen die USA viel Geld ausgeben. 5G wird dort auch als entscheidend für Kriegsführung angesehen.

  2. Sony: The Last of Us 2 wird PS5-kompatibel
    Sony
    The Last of Us 2 wird PS5-kompatibel

    Ab Juli 2020 dürfen Entwickler bei Sony nur noch Spiele zur Freigabe einreichen, die auf der PS4 und auf der Playstation 5 funktionieren.

  3. Android: Oppo bringt Smartphones mit Vierfachkamera ab 200 Euro
    Android
    Oppo bringt Smartphones mit Vierfachkamera ab 200 Euro

    Das Oppo A52 und Oppo A72 kommen in Deutschland auf den Markt: Käufer erhalten Mittelklassegeräte mit Qualcomm-Chips und Vierfachkameras.


  1. 18:38

  2. 17:09

  3. 16:30

  4. 15:57

  5. 14:57

  6. 14:15

  7. 14:00

  8. 13:14