Kryptografie (5) : RSA

in #deutsch5 years ago (edited)

RSA ist ein asymmetrisches Verschlüsselungsverfahren. Das heißt, dass ein Benutzer ein Schlüsselpaar hat. Einmal einen Public-Key zum verschlüsseln und einen Private-Key zum entschlüsseln. Die beiden Schlüssel passen zueinander. Wird allerdings ein Schlüssel verloren, so muss ein neues Schlüsselpaar generiert werden, und die alten Nachrichten lassen sich nicht mehr ver- oder entschlüsseln, je nachdem welchen Key man verloren hat.

RSA (Rivest Shamir Adleman)

Das Verfahren trägt die ersten Buchstaben seiner Erfinder. Die Sicherheit von RSA basiert darauf, dass es schwer ist eine große Zahl zu faktorisieren, also in ihre Primfaktoren zu zerlegen. Weiterhin soll verhindert werden, dass man aus dem Public-Key (e,N) nicht so ohne weiteres auf den Private-Key (d,N) schließen kann. Es wird eine Schlüssellänge von mindestens 2048-bit, besser noch 4096-bit empfohlen. Es können also Zahlen dargestellt werden zwischen 0 und (2^4096)-1.

Mit der asymmetrischen Verschlüsselung sollen außerdem die "Man-In-The-Middle-Attacks" verhindert werden. Das heißt, es soll einer dritten Person nicht möglich sein die Kommunikation zwischen dem Sender und dem Empfänger zu belauschen. Was passiert aber wenn ein Angreifer die Public-Keys vom Sender und dem Empfänger abgreift? Nichts! Denn mit dem Public-Key kann man Nachrichten nur verschlüsseln und nicht entschlüsseln. Die dazugehörigen Private-Keys bleiben ja für immer auf der Sender- bzw. Empfängerseite. Zumindest sollte es das.
Ein Angreifer kann aber versuchen den Private-Key zu Brute-Forcen. Sowas kann extrem lange dauern. Lohnt sich also nicht. Das Generieren eines Schlüsselpaars kann zwischen Sekunden und Minuten dauern, je nachdem wie die Schlüsselstärke gewählt wird.

Formeln

Hier ein Überblick über die Verwendeten Formeln
rsa.png

Ein Rechenbeispiel

Gehen wir das Verfahren mal anhand eines praktischen Beispiels durch. Wir benötigen zuerst zwei (große) Primzahlen p und q. Nehmen wir mal p=7, q=11 also lautet unser N N=pq=77 (1). Nun brauchen wir eine natürliche Zahl e, die teilerfremd zu (p-1)(q-1), also 60 ist. Nehmen wir mal e=47 (2,3). Jetzt haben wir schon mal unseren Public-Key "berechnet".
Er lautet (e,N)=(47,77) (4). Jetzt beginnt der Spaß unseren Private-Key zu berechnen. Wir müssen aus 1=ed mod phi(N) (5) den Parameter d bestimmen. Also, setzen wir alle bekannten Werte ein, so ergibt dies: 1=47*d mod 60. Um d zu bestimmen wird der Erweiterte Euklidische Algorithmus angewendet. (Ich verzichte hier auf die genaue Berechnung, da dies den Beitrag sprengen würde). Das Ergbnis lautet d=23, und somit haben wir unseren Private-Key (d,N)=(23,77) (6). Da wir jetzt ein Schlüsselpaar haben, können wir unsere Nachrichten gemäß der asymmetrsichen Verschlüsselung ver- und entschlüsseln.

Für die Ver- und Entschlüsselung einer Nachricht m gibt es die beiden Formeln (7) und (8):
Zum Verschlüsseln gilt also im unseren Fall m^47 mod 77.
Zum Entschlüsseln gilt m^47*23 mod 77.

Sort:  

Resteem. Wie auch die letzten Teile sehr gut zusammengefasst.

This post is supported by $0.22 @tipU upvote funded by @lauch3d :)
@tipU voting service: instant, profitable upvotes + profit sharing tokens | For investors.

Sehr geil! Danke für die Zusammenfassung! :)

Je höher die Primzahlen p und q, desto sicherer ist die Verschlüsselung? Außerdem sollte man jede Zahl, welche man frei wählen kann, wohl zufällig wählen, oder?

Hoffe ich hab keinen Denkfehler..^^

Genau. Die Primzahlen werden zufällig von der Anwendung ermittelt (bsp. Miller-Rabin-Test) die man für die Verschlüsselung benutzt. Mann muss nur noch die Schlüssellänge selber festlegen. Je nachdem wie hoch dieser Wert ist können entsprechend große Primzahlen bestimmt werden.

Ich vertrau keinem Prozessor bei der Zufallsgenerierung

Da würfel ich lieber :)

Posted using Partiko Android



This post has been voted on by the SteemSTEM curation team and voting trail. It is elligible for support from @curie.

If you appreciate the work we are doing, then consider supporting our witness stem.witness. Additional witness support to the curie witness would be appreciated as well.

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Interessant. Danke und resteemed!

Conocer el mundo

Alles richtig gemacht, weiter viel Erfolg...

Du hast ein kleines Upvote von einem Kurator des GSB erhalten. Zusätzlich erhältst du bis zu 30 weitere Votes von Mitgliedern die uns in einen Trail folgen.
Schließe dich uns an!!! klicke auf diesen Link. Wir helfen und unterstützen neue Mitglieder und Chatten in einem freundschaftlichen Miteinander.

Aktueller Kurator ist @don-thomas

N E U - jeden Donnerstag findet bei uns ab 19 Uhr die Quasselstunde statt wo du nicht nur mit uns reden kannst - es werden auch tolle Preise verlost

Eine neue Aktion von GSB um ein wenig leben in die Bude zu bringen. Zeigt etwas Gemeinschaftssinn und macht dort mit.
Sei auch du dabei beim täglichen Story Feed.
Ein Schnappschuss von Dir den du uns zeigen möchtest? Ein Kaffebildchen am frühen Morgen in dem du alle Gruppenmitglieder begrüßt? Ein kleiner Joke und auch mal ein etwas derber Witz den du uns mitteilen möchtest? Dann bist du dort genau richtig

https://steemit.com/deutsch/@steem-bootcamp/story-feed-deutsch-20-07-2019-fuer-alles-moegliche-and-unmoegliche

Sehr schön, @maini was meinst du?

An der Stelle würde ich dir empfehlen noch den STEM Hashtag zu verwenden.

Und vielleicht mal bei @de-stem und @steemstem vorbei zu schauen, dort würdest du mit solchen Themen gut reinpassen.

Hallo satren,

das hört sich ja interessant an. Ich wusste nicht das es sowas in der Richtung gibt. Danke für den Hinweis!

Congratulations @ozelot47! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

You made more than 50 comments. Your next target is to reach 100 comments.

You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word STOP

To support your work, I also upvoted your post!

Vote for @Steemitboard as a witness to get one more award and increased upvotes!