Abo
  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. Zum Login

Stellenmarkt
  1. Universität Konstanz, Konstanz
  2. ESG Elektroniksystem- und Logistik-GmbH, Fürstenfeldbruck
  3. ViGEM GmbH, Karlsruhe
  4. WBS GRUPPE, deutschlandweit (Home-Office)

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Top-Angebote
  1. 31,99€
  2. 139,00€ (Bestpreis!)
  3. (aktuell u. a. Speedlink Velator Gaming-Tastatur für 9,99€, Deepcool New Ark Gehäuse für 249...
  4. 104,90€


Haben wir etwas übersehen?

E-Mail an news@golem.de


Surface Hub 2S angesehen: Das Surface Hub, das auch in kleine Meeting-Räume passt
Surface Hub 2S angesehen
Das Surface Hub, das auch in kleine Meeting-Räume passt

Ifa 2019 Präsentationen teilen, Tabellen bearbeiten oder gemeinsam auf dem Whiteboard skizzieren: Das Surface Hub 2S ist eine sichtbare Weiterentwicklung des doch recht klobigen Vorgängers. Und Microsofts Pläne sind noch ambitionierter.
Ein Hands on von Oliver Nickel

  1. Microsoft Nutzer berichten von defektem WLAN nach Surface-Update
  2. Surface Microsofts Dual-Screen-Gerät hat zwei 9-Zoll-Bildschirme
  3. Centaurus Microsoft zeigt intern ein Surface-Gerät mit zwei Displays

Apple TV+: Apples Videostreamingdienst ist nicht konkurrenzfähig
Apple TV+
Apples Videostreamingdienst ist nicht konkurrenzfähig

Bei so einem mickrigen Angebot hilft auch ein mickriger Preis nicht: Apples Streamingdienst hat der Konkurrenz von Netflix, Amazon und bald Disney nichts entgegenzusetzen - und das wird sich auf Jahre nicht ändern.
Eine Analyse von Ingo Pakalski

  1. Apple TV+ Disney-Chef tritt aus Apple-Verwaltungsrat zurück
  2. Apple TV+ Apples Streamingangebot kostet 4,99 Euro im Monat
  3. Videostreaming Apple TV+ startet mit fünf Serien für 10 US-Dollar monatlich

Garmin Fenix 6 im Test: Laufzeitmonster mit Sonne im Herzen
Garmin Fenix 6 im Test
Laufzeitmonster mit Sonne im Herzen

Bis zu 24 Tage Akkulaufzeit, im Spezialmodus sogar bis zu 120 Tage: Garmin setzt bei seiner Sport- und Smartwatchserie Fenix 6 konsequent auf Akku-Ausdauer. Beim Ausprobieren haben uns neben einem System zur Stromgewinnung auch neue Energiesparoptionen interessiert.
Ein Test von Peter Steinlechner

  1. Fenix 6 Garmins Premium-Wearable hat ein Pairing-Problem
  2. Wearable Garmin Fenix 6 bekommt Solarstrom

  1. Google: Stadia kommt offenbar 2020 auf Android TV
    Google
    Stadia kommt offenbar 2020 auf Android TV

    Der Cloud-Gamingdienst Stadia von Google soll laut inoffiziellen Informationen im kommenden Jahr auch auf Android TV landen. Das Smart-TV-System ist in einigen Mediaplayern und Fernsehern vorinstalliert.

  2. GNU-Gründer: Richard Stallman tritt von MIT- und FSF-Position zurück
    GNU-Gründer
    Richard Stallman tritt von MIT- und FSF-Position zurück

    Nach verstörenden Äußerungen zu einem der Opfer Jeffrey Epsteins tritt der Gründer des GNU-Projekts, Richard Stallman, von seiner Position beim MIT und dem FSF-Vorstand zurück.

  3. Fossil: Google soll hybride Smartwatch-Technologie gekauft haben
    Fossil
    Google soll hybride Smartwatch-Technologie gekauft haben

    Beim 40-Millionen-Dollar-Deal mit Fossil Anfang 2019 hat Google offenbar Technologie und Entwickler rund um eine hybride Smartwatch gekauft. Fraglich ist, ob Google die Technik tatsächlich für eine eigene Uhr verwenden wird - bislang macht es weniger den Anschein.


  1. 10:31

  2. 10:16

  3. 10:06

  4. 09:30

  5. 09:06

  6. 09:03

  7. 08:37

  8. 07:43