Erklärung natürliche Zahle schlüssel Algorithmus pgp Privacy Verständnisfrage

Verständnisfrage zu einem Algorithmus

Von: , Frage gestellt am Fr, 7. Jul 2000

Hallo Matheexperten,

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???

Besten Dank im Voraus

MfG

Markus

4 Antworten zu dieser Frage

1. Antwort von nach 28 Minuten hilfreich

   Re: Verständnisfrage zu einem Algorithmus

   Hallo, 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.
   
   Ciao Lutz
   

   • Antwort von nach 3 Stunden hilfreich

     Re^2: Verständnisfrage zu einem Algorithmus

     Hi Lutz, 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".
     
     Mit freundlichem Gruß
     Martin
     

2. Antwort von nach 8 Stunden hilfreich

   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
   
   1. Dann gibt es den Satz von Euler:
   Für jede natürliche Zahl s und jede nat. Zahl m<=n gilt:
   m^{s(p-1)*(q-1)+1} mod n = m
   (Der Satz folgt aus dem kleinen Fermatschen Satz)
   
   2. 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
   
   3. 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 < n codiert weden können.
   A verschlüsselt nun eine Nachricht m mit dem öffentlichen Schlüssel von B in eine Nachricht m₁ = m^e mod n.
   B wendet seinen privaten Schlüssel (d,n) auf die erhaltene Nachricht m₁ wie folgt an: Er berechnet
   m₂ = m₁^d mod n.
   
   Und nun kommts:
   m₂ = m₁^d mod n = (m^e)^d mod n = m^e*d mod n = m^{s(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.
   

   • Antwort von nach 8 Stunden hilfreich

     Re: RSA-Algorithmus

     Vielen Dank,
     
     genau nach einer solchen Erklärung habe ich gesucht.
     
     MfG
     
     Markus
     

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!