Asymmetrisches Kryptosystem - Verständnisproblem

Die Grundidee ist, dass es zwei Zahlen gibt, die sich in einer Rechnung gegenseitig aufheben.

Mal ein einfaches Beispiel das nicht für eine Verschlüsselung geeignet ist, aber die Grundidee klar machen sollte.
Im folgenden gilt immer:
N ist die Nachricht
x ist der öffentliche Schlüssel
y ist der private Schlüssel

Nehmen wir mal die ganz einfache Rechnung N + x + y. Für x suchen wir uns mal 3 aus. Damit N + x + y = N gilt (damit wir nachdem wir beides gemacht haben wieder unsere Nachricht bekommen) muss y = -3 sein.
Du "verschlüsselst" also indem du 3 zu der Nachricht addierst, ich entschlüssel indem ich -3 addiere. Als echt Verschlüsselung eignet sich das aber nicht. Denn jeder, der weiß das mit 3 verschlüsselt wurde sieht sofort das mit -3 entschlüsselt wurde.

RSA verwendet also eine andere Rechnung.
Kleine Erklärung vorweg: "mod k" - dabei ist k eine Zahl - bedeutet "der Rest der Division durch k"
Beispiel: 13 mod 5 = 3 (13 = 2*5 + 3)

Bei RSA wird ist die Zahl k allen bekannt und es wird folgendes gerechnet: N^x mod k
y ist so, dass (N^x mod k)^y mod k = N ist. Das funktioniert natürlich nur wenn N < k ist (man muss also eine Nachricht eventuell in kleinere Teile aufteilen)
Wie man auf die Werte x,y und k kommt so dass das alles passt geht dann mehr in die details, da kannst du dir dann die links der anderen anschaun. Das wesentliche ist, dass nur weil du x und k kennst, du trotzdem große Probleme haben wirst y rauszufinden - im Gegensatz zum Beispiel am Anfang.

Nico T. schrieb:

wie kann nun eine Nachricht wieder entschlüsselt werden, wenn sie zuvor mit einem ganz anderen Schlüssel verschlüsselt wurde?

ganz einfach, wenn:

öffentlicher Schlüssel = eine Funktion f
geheimer Schlüssel = Umkehrfunktion von f

wenn f öffentlich ist, kann jeder verschlüsseln. Wenn die Umkehrfunktion geheim ist, kann aber (je nach Methode) nicht jeder entschlüsseln.

sorgt man dafür, daß f leicht zu berechnen ist, die Umkehrung aber schwierig zu finden ist, selbst wenn f öffentlich bekannt ist, hat man ein Schema, das leicht (und für jedermann) zu verschlüsseln, aber die Entschlüsselung schwer ist, es sei denn für denjenigen, der im Besitz des geheimen Schlüssels ist.

Analogie: f ~ "Haustür zufallen lassen", Umkehrung ~ "Haustür öffnen". Das erste kann jeder, das zweite nur derjenige, der im Besitz des Schlüssels ist.

volkard

großbuchstaben schrieb:

Nico T. schrieb:

wie kann nun eine Nachricht wieder entschlüsselt werden, wenn sie zuvor mit einem ganz anderen Schlüssel verschlüsselt wurde?

ganz einfach, wenn:

öffentlicher Schlüssel = eine Funktion f
geheimer Schlüssel = Umkehrfunktion von f

wenn f öffentlich ist, kann jeder verschlüsseln. Wenn die Umkehrfunktion geheim ist, kann aber (je nach Methode) nicht jeder entschlüsseln.

sorgt man dafür, daß f leicht zu berechnen ist, die Umkehrung aber schwierig zu finden ist, selbst wenn f öffentlich bekannt ist, hat man ein Schema, das leicht (und für jedermann) zu verschlüsseln, aber die Entschlüsselung schwer ist, es sei denn für denjenigen, der im Besitz des geheimen Schlüssels ist.

War alles schon gesagt, nur ist Dein Kram mit "f" abstrakter und sagt einem weniger.

großbuchstaben schrieb:

Analogie: f ~ "Haustür zufallen lassen", Umkehrung ~ "Haustür öffnen". Das erste kann jeder, das zweite nur derjenige, der im Besitz des Schlüssels ist.

Und die ist zu konkret und mißweisend.

volkard schrieb:

War alles schon gesagt, nur ist Dein Kram mit "f" abstrakter und sagt einem weniger.

weniger ist hier mehr - die richtige Abstraktion macht eine unüberschaubare Vielfalt von Einzelphänomenen auf einmal kristallklar.

volkard schrieb:

großbuchstaben schrieb:

Analogie: f ~ "Haustür zufallen lassen", Umkehrung ~ "Haustür öffnen". Das erste kann jeder, das zweite nur derjenige, der im Besitz des Schlüssels ist.

Und die ist zu konkret und mißweisend.

ich finde die Analogie im Gegenteil sogar sehr gelungen

volkard

großbuchstaben schrieb:

volkard schrieb:

großbuchstaben schrieb:

Analogie: f ~ "Haustür zufallen lassen", Umkehrung ~ "Haustür öffnen". Das erste kann jeder, das zweite nur derjenige, der im Besitz des Schlüssels ist.

Und die ist zu konkret und mißweisend.

ich finde die Analogie im Gegenteil sogar sehr gelungen

Mir fehlt der Zusammenhang der beiden Funktionen. Daß der private und der öffentliche Schlüssel genau zueinander passen.

Analogie: Hungriger werden ist ganz leicht, aber satter werden kann man nur, wenn man Essen hat. Helau.

volkard schrieb:

Mir fehlt der Zusammenhang der beiden Funktionen. Daß der private und der öffentliche Schlüssel genau zueinander passen.

also:

öffentlicher Schlüssel ~ Türknauf außen
Verschlüsselungsfunktion f ~ Tür mit Hilfe des Türknauf zufallen lassen

nicht-öffentlicher Schlüssel ~ Bartschlüssel
Entschlüsselungsfunktion f^{-1} ~ Tür mit Hilfe des Bartschlüssels öffnen

Tür öffnen o Tür schließen = id (identische Funktion)
Tür schließen o Tür öffnen = id

=> die beiden Funktionen sind zueinander invers.

Außerdem gehören sie paarweise zusammen, denn wenn ich Haustür A mit dem Schlüssel A öffne, und dann Haustür B zumache, erhalte ich nicht id. Ebensowenig, wie wenn ich Haustür A ins Schloß fallen lasse, und Haustür B öffne.

Ich finde die Analogie gut, davon ab bin ich wahrscheinlich nicht der erste, dem diese Analogie eingefallen ist.

rapso

Nico T. schrieb:

...wie kann nun eine Nachricht wieder entschlüsselt werden, wenn sie zuvor mit einem ganz anderen Schlüssel verschlüsselt wurde? ...

stell dir vor das verschluesselungsverfahren heisst "Multiplikation", der public key ist 2, der private key ist 0.5

klartest ist nun z.b. 37
verschluesselt mit dem public key ist es 37*PublicKey=37*2=74
entschluesselt mit dem private key ist es 74*PrivateKey=74*0.5=37

bei den richtigen verfahren ist nur die multiplikationen sind etwas komplexer.

das ist aber insofern irreführend, als hier der geheime Schlüssel sehr leicht aus dem öffentlichen berechnet werden kann. Der "öffentliche" Schlüssel dürfte hier also nicht veröffentlicht werden, wäre also gar nicht öffentlich.

Wichtig wäre aber die "Falltürfunktion", daß bei Kenntnis des öffentlichen Schlüssels *nur* die Verschlüsselung leicht sein darf.

ich warte lieber noch auf die Auto-Analogie von SeppJ

rapso

großbuchstaben schrieb:

das ist aber insofern irreführend,

dieses beispiel sollte verdeutlichen wie zwei verschiedene zahlen zum ver- bzw entschluesseln benutzt werden koennen (das war seine frage). IMO nicht irrefuehrend, sondern ein beispiel.

als hier der geheime Schlüssel sehr leicht aus dem öffentlichen berechnet werden kann.

und wenn kinder condome ueber bananen streifen schuetzen sie nichts.
aber das aendert nichts am verfahren.
es geht um die theorie die er verstehen moechte.

Der "öffentliche" Schlüssel dürfte hier also nicht veröffentlicht werden, wäre also gar nicht öffentlich.

natuerlich darf er veroeffentlich werden. jeder oeffentliche schluessel traegt das geheimniss seines gegenstuecks. dass du oder ich bei manchen davon keinen algorithmus kennen der das gegenstueck errechnet (wenn wir 'ausprobieren' mal nicht als algorithmus ansehen), heisst nicht, dass es garantiert sicher ist. die RSA challenge wurde abgebrochen, weil ersichtlich war, dass mit der verdoppelung der rechenleistung weitere schluessel fallen werden.

Wichtig wäre aber die "Falltürfunktion", daß bei Kenntnis des öffentlichen Schlüssels *nur* die Verschlüsselung leicht sein darf.

da hast du recht, das waere gut, aber bisher gibt es keinen verschluesselungsalgorithmus bei dem das bewiesen ist. die welt hofft einfach glueck zu haben, dass es weiterhin niemand entdeckt. vor einiger zeit konnte niemand die hypotenuse oder eine matrix inverse berechnen, wenn man damit verschluesselt haette...

volkard

rapso schrieb:

großbuchstaben schrieb:

das ist aber insofern irreführend,

dieses beispiel sollte verdeutlichen wie zwei verschiedene zahlen zum ver- bzw entschluesseln benutzt werden koennen (das war seine frage). IMO nicht irrefuehrend, sondern ein beispiel.

Ich fand das Beispiel gut.

Um vom öffentlichen Schlüssel *2 auf den privaten Schlüssel *0.5 zu kommen, muss man schon gehörig nachdenken. Zum öffentlichen *8 würde der private gar *0.125 heißen. Und zum öffentlichen *43 kann man den geheimen schon gar nicht ohne Computerunterstützung herausfinden. Es wäre *0.p02439 (weshalb auch die 41 viel interessanter ist als die 42).

Allerdings schützt dieses Beispiel-Verfahren nicht gegen moderne Mathematiker, die die Kunst des Dividierens beherrschen.