ich interessiere mich für Verschlüsselungsalgorithmen. Ich habe hierbei allerdings ein generelles Verständnisproblem, wie ein asynchroner Verschlüsselungs - Algorithmus funktioniert. Wie kann ich etwas mit einem öffentlichen Schlüssel chiffrieren und mit einem anderen privaten schlüssel wieder entschlüsseln? Ein Beispiel für dieses Verfahren ist etwa PGP (Pretty Good Privacy), dort verschlüsselt man mit einem Public - Key, mit einem Private - Key dechiffriet man wieder.
Dabei ist es auch nicht möglich, vom Public key auf den Private Key zu schließen.
Wie könnte ein solcher Algorithmus aussehen, kann mir jemand dazu ein simples Beispiel geben???
Dabei ist es auch nicht möglich, vom Public key auf den
Private Key zu schließen.
Das stimmt nicht ganz, prinzipiell ist das immer m"oglich, z.B. beim RSA, der auch bei PGP verwendet wird, l"auft das dann darauf hinaus, dass im "offentlichen Schl"ussel das Produkt zweier Primzahlen steckt, man zur R"ucktransformation aber diese Primzahlen direkt braucht. Das Faktorisieren von allgemeinen Zahlen ist ein sehr hartes Problem, so dass man nur die Bitl"ange hoch genug setzen muss, dass kein Computer dieser Erde den Code knacken kann (oder in vern"unftiger Zeit knacken kann, sonst dauert das Verschl"usseln zu lange).
Anbei: Primzahlrekorde werden mit sehr speziellen Testkandidaten durchgef"uhrt, die man einfacher auf Faktoren testen kann.
Anbei: Primzahlrekorde werden mit sehr speziellen
Testkandidaten durchgef"uhrt, die man einfacher auf Faktoren
testen kann.
das stimmt, aber bei den Primzahl-Rekord-Zahlen handelt es sich um Zahlen, die wirklich EXTREM groß sind (ich glaube, die Stellenzahl liegt inzwischen in der Größenordnung Milliarden). Eine allgemeine Zahl von dieser Größe kann nicht mit vertretbarem Aufwand auf „Primheit“ getestet werden; lediglich mit den „speziellen Kandidaten“ wie den Mersenneschen Zahlen („2^N-1“) ist das möglich.
Die Primzahlen, die bei den Verschlüsselungsalgorithmen zum Einsatz kommen, sind dagegen „allgemeine“ Zahlen, die zwar auch groß sind, aber mit Stellenzahlen in der Größenordnung 100 immer noch VIEL kleiner als die Rekordzahlen sind. Und Zahlen von dieser Größe können sehr wohl „schnell“ auf Primheit getestet werden, obwohl sie NICHT schnell in ihre Primfaktoren zerlegt werden können! Bei den Verfahren, die es erlauben, eine große (aber nicht EXTREM große) Zahl schnell auf Primheit zu checken, handelt es sich um die sogenannten „probabilistischen Primzahltests“.
RSA-Algorithmus
Also: wie unten schon gesagt wurde, ist es für Menschen und Computer gleichermaßen deutlich einfacher, Primzahlen miteinander zu multiplizieren, als eine große Zahl in ihre Primfaktoren zu zerlegen.
Darauf beruht das Prinzip des RSA-Algorithmus:
Seien p,q Primzahlen und n=p*q
Dann gibt es den Satz von Euler:
Für jede natürliche Zahl s und jede nat. Zahl ms(p-1)*(q-1)+1 mod n = m
(Der Satz folgt aus dem kleinen Fermatschen Satz)
Ist e irgendeine natürliche Zahl, die zu (p-1)*(q-1) teilerfremd ist, dann lassen sich mit dem Euklidischen Algorithmus Zahlen d und s finden, sodass
e*d=s(p-1)(q-1)+1
Jetzt sind wir fast fertig
Nimm das Paar (e,n) als öffentlichen und das Paar (d,n) als privaten Schlüssel.
Wenn nun A an B eine Nachricht sendet, wird die zunächst in kleine Stücke zerhackt, die in natürliche Zahlen m 1 = me mod n.
B wendet seinen privaten Schlüssel (d,n) auf die erhaltene Nachricht m1 wie folgt an: Er berechnet
m2 = m1d mod n.
Und nun kommts:
m2 = m1d mod n = (me)d mod n = med mod n = ms(p-1)(q-1)+1 mod n = m
Es kommt also am Ende tatsächlich wieder die Ursprungsnachricht raus.
Es müssen nur die Primzahlen p und q so groß gewählt werden, dass niemand so schnell n=p*q in sie zerlegen kann.