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. MVV Trading GmbH, Mannheim
  2. DRÄXLMAIER Group, Vilsbiburg bei Landshut
  3. ARI Fleet Germany GmbH, Eschborn, Stuttgart
  4. Hong Kong Economic and Trade Office, Berlin

Golem pur
  • Golem.de ohne Werbung nutzen

Anzeige
Top-Angebote
  1. (u. a. MSI MPG Z390 Gaming Edge AC für 149,90€, MSI MPG Z390 Gaming Pro Carbon AC für 180,90€)
  2. (u. a. Sandisk Ultra 400 GB microSDXC für 56,90€, Verbatim Pinstripe 128-GB-USB-Stick für 10...
  3. 89,90€ (Bestpreis!)
  4. 449,90€ (Release am 26. August)


Haben wir etwas übersehen?

E-Mail an news@golem.de


IT-Arbeit: Was fürs Auge
IT-Arbeit
Was fürs Auge

Notebook, Display und Smartphone sind für alle, die in der IT arbeiten, wichtige Werkzeuge. Damit man etwas mit ihnen anfangen kann, ist ein anderes Werkzeug mindestens genauso wichtig: die Augen. Wir geben Tipps, wie man auch als Freiberufler augenschonend arbeiten kann.
Von Björn König

  1. Sysadmin "Man kommt erst ins Spiel, wenn es brennt"
  2. Verdeckte Leiharbeit Wenn die Firma IT-Spezialisten als Fremdpersonal einsetzt
  3. IT-Standorte Wie kann Leipzig Hypezig bleiben?

Google Maps: Karten brauchen Menschen statt Maschinen
Google Maps
Karten brauchen Menschen statt Maschinen

Wenn Karten nicht mehr von Menschen, sondern allein von Maschinen erstellt werden, erfinden diese U-Bahn-Linien, Hochhäuser im Nationalpark und unmögliche Routen. Ein kurze Liste zu den Grenzen der Automatisierung.
Von Sebastian Grüner

  1. Kartendienst Google bringt AR-Navigation und Reiseinformationen in Maps
  2. Maps Duckduckgo mit Kartendienst von Apple
  3. Google Maps zeigt Bikesharing in Berlin, Hamburg, Wien und Zürich

OKR statt Mitarbeitergespräch: Wir müssen reden
OKR statt Mitarbeitergespräch
Wir müssen reden

Das jährliche Mitarbeitergespräch ist eines der wichtigsten Instrumente für Führungskräfte, doch es ist gerade in der IT-Branche nicht mehr unbedingt zeitgemäß. Aus dem Silicon Valley kommt eine andere Methode: OKR. Sie erfüllt die veränderten Anforderungen an Agilität und Veränderungsbereitschaft.
Von Markus Kammermeier

  1. Arbeit Hilfe für frustrierte ITler
  2. IT-Arbeitsmarkt Jobgarantie gibt es nie
  3. IT-Fachkräftemangel Freie sind gefragt

  1. UMTS: 3G-Abschaltung kein Thema für die Bundesregierung
    UMTS
    3G-Abschaltung kein Thema für die Bundesregierung

    Nutzer, die kein LTE in ihren Verträgen festgeschrieben haben, sollten wechseln, da 3G zunehmend abgeschaltet werde. Das erklärte das Bundesverkehrsministerium und sieht keinen Grund zum Eingreifen.

  2. P3 Group: Wo die Mobilfunkqualität in Deutschland am niedrigsten ist
    P3 Group
    Wo die Mobilfunkqualität in Deutschland am niedrigsten ist

    Die Qualität des Mobilfunks in Deutschland ist in den einzelnen Bundesländern sehr unterschiedlich. Dort, wo Funklöcher gerade ein wichtiges Thema sind, ist die Versorgung gar nicht so schlecht.

  3. Mecklenburg-Vorpommern: Funkmastenprogramm verzögert sich
    Mecklenburg-Vorpommern
    Funkmastenprogramm verzögert sich

    Wegen fehlender Zustimmung der EU ist das Geld für ein Mobilfunkprogramm in Mecklenburg-Vorpommern noch nicht verfügbar. Dabei hat das Bundesland laut einer P3-Messung große Probleme.


  1. 18:00

  2. 18:00

  3. 17:41

  4. 16:34

  5. 15:44

  6. 14:42

  7. 14:10

  8. 12:59