Einführung

Hast du die Lektion über moderne Kryptographie gesehen?  Beim letzten Checkpoint  war dies die beliebteste Frage der Benutzer:

In der Lektion haben wir gesehen, wie die Primzahlzerlegung eine Grundlegende Rolle beim Bau von mathematischen Sperren spielt. Eine mathematische Sperre (oder Einwegfunktion) erfordert ein Verfahren das  einfach durchzuführen und schwer rückgängig zu machen ist.

Z.B.  wenn ich zwei große Primzahlen nach dem Zufallsprinzip wähle, wie z. B.: P1 = 709  und P2 = 733

Wenn ich sie multipliziere, bekommen ich :  N = P1 * P2

N = 709 * 733 = 519697       (das ist einfach zu berechnen)

Es kommt folgendes heraus: eine große Zahl (519697) und die Primfaktorzerlegung für diese große Zahl (709 * 733)

Jetzt stell dir vor, ich verstecke die Primfaktorzerlegung und biete dir nur Folgendes an:

519697 =?%nbsp;*?%nbsp;%nbsp;%nbsp;%nbsp;%nbsp;(Dies ist schwer zu berechnen)

Wenn ich Sie bitte, die Primfaktorzerlegung zu finden bitten%nbsp;, wo würden Sie%nbsp; anfangen? Keine Sorge, jeder würde mit diesem Problem kämpfen!%nbsp; Um die Lösung zu finden, müsste man eine Reihe von Versuchen mit Irrtümern machen. Multiplikation ist schnell (und leicht) zu berechnen, während die Primfaktorzerlegung (hart und) langsam ist. Diese einfache Tatsache bildet die Grundlage für das RSA-Verschlüsselungsschema.

👁️ Um den Unterschied zu sehen, schau dir dieses animierte Diagramm an.

Aber bevor wir weiter machen, müssen wir uns auf den ersten Schritt konzentrieren und uns eine  wichtige Frage stellen . Wenn wir sagen: "wähle zwei große Primzahlen nach dem Zufallsprinzip aus", wie tun wir dies möglichst schnell? Ist das ein einfaches Problem?

Wenn man darüber eine Weile nachdenkt, bist du vielleicht damit einverstanden, dass dieser Schritt die Möglichkeit erfordert, zu überprüfen, ob eine zufällig generierte Zahl, (z. B.  99194853094755497), eine Primzahl ist oder zusammengesetzt ist. Hast du eine Schaltfläche auf deinem Taschenrechner, die dir das sagt?

Ich nicht…. Warum ist das so?

Um dies herauszufinden, lass uns mit einer Herausforderung beginnen...