<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="de">
	<id>https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=RSA-Verfahren</id>
	<title>RSA-Verfahren - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=RSA-Verfahren"/>
	<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=RSA-Verfahren&amp;action=history"/>
	<updated>2026-11-16T00:45:39Z</updated>
	<subtitle>Versionsgeschichte dieser Seite in FLBK-Wiki</subtitle>
	<generator>MediaWiki 1.46.2</generator>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=RSA-Verfahren&amp;diff=3212&amp;oldid=prev</id>
		<title>Flbkwikiadmin: Die Seite wurde neu angelegt: „Das RSA-Verfahren war das erste praxistaugliche asymmetrische Verschlüsselungsverfahren. Es steckt bis heute in vielen Abläufen für sichere Verbindungen, digitale Signaturen und Zertifikate.  ==Definition== Das &#039;&#039;&#039;RSA-Verfahren&#039;&#039;&#039; ist ein asymmetrisches Verschlüsselungsverfahren. Ronald Rivest, Adi Shamir und Leonard Adleman haben es 1977 vorgestellt, die Anfangsbuchstaben ihrer Namen ergeben den Namen…“</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=RSA-Verfahren&amp;diff=3212&amp;oldid=prev"/>
		<updated>2026-11-15T06:51:20Z</updated>

		<summary type="html">&lt;p&gt;Die Seite wurde neu angelegt: „Das RSA-Verfahren war das erste praxistaugliche asymmetrische Verschlüsselungsverfahren. Es steckt bis heute in vielen Abläufen für sichere Verbindungen, digitale Signaturen und Zertifikate.  ==Definition== Das &amp;#039;&amp;#039;&amp;#039;RSA-Verfahren&amp;#039;&amp;#039;&amp;#039; ist ein &lt;a href=&quot;/Kryptographie#Asymmetrische_Verschlüsselung&quot; title=&quot;Kryptographie&quot;&gt;asymmetrisches Verschlüsselungsverfahren&lt;/a&gt;. Ronald Rivest, Adi Shamir und Leonard Adleman haben es 1977 vorgestellt, die Anfangsbuchstaben ihrer Namen ergeben den Namen…“&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Das RSA-Verfahren war das erste praxistaugliche asymmetrische Verschlüsselungsverfahren. Es steckt bis heute in vielen Abläufen für sichere Verbindungen, digitale Signaturen und Zertifikate.&lt;br /&gt;
&lt;br /&gt;
==Definition==&lt;br /&gt;
Das &amp;#039;&amp;#039;&amp;#039;RSA-Verfahren&amp;#039;&amp;#039;&amp;#039; ist ein [[Kryptographie#Asymmetrische Verschlüsselung|asymmetrisches Verschlüsselungsverfahren]]. Ronald Rivest, Adi Shamir und Leonard Adleman haben es 1977 vorgestellt, die Anfangsbuchstaben ihrer Namen ergeben den Namen des Verfahrens.&lt;br /&gt;
&lt;br /&gt;
Jeder Teilnehmer besitzt ein Schlüsselpaar:&lt;br /&gt;
* den &amp;#039;&amp;#039;&amp;#039;öffentlichen Schlüssel&amp;#039;&amp;#039;&amp;#039; &amp;lt;math&amp;gt;(e; N)&amp;lt;/math&amp;gt;, den jeder kennen darf,&lt;br /&gt;
* den &amp;#039;&amp;#039;&amp;#039;privaten Schlüssel&amp;#039;&amp;#039;&amp;#039; &amp;lt;math&amp;gt;(d; N)&amp;lt;/math&amp;gt;, den nur der Besitzer kennt.&lt;br /&gt;
&lt;br /&gt;
Die Zahl &amp;lt;math&amp;gt;N&amp;lt;/math&amp;gt; heißt &amp;#039;&amp;#039;&amp;#039;RSA-Modul&amp;#039;&amp;#039;&amp;#039;. In anderen Texten heißen oft auch die Zahlen &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt; allein öffentlicher und privater Schlüssel. Nachrichten sind Zahlen &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;0 \le m &amp;lt; N&amp;lt;/math&amp;gt;. Texte werden vorher in Zahlen umgewandelt.&lt;br /&gt;
&lt;br /&gt;
==Schlüsselerzeugung==&lt;br /&gt;
# Zwei verschiedene große Primzahlen &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt; wählen.&lt;br /&gt;
# Den RSA-Modul berechnen: &amp;lt;math&amp;gt;N = p \cdot q&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Den Wert der [[Satz von Euler#Eulersche φ-Funktion|eulerschen φ-Funktion]] berechnen: &amp;lt;math&amp;gt;\varphi(N) = (p - 1) \cdot (q - 1)&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Eine Zahl &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;1 &amp;lt; e &amp;lt; \varphi(N)&amp;lt;/math&amp;gt; wählen, die zu &amp;lt;math&amp;gt;\varphi(N)&amp;lt;/math&amp;gt; [[Euklidischer Algorithmus#Teilerfremdheit|teilerfremd]] ist: &amp;lt;math&amp;gt;\operatorname{ggT}(e; \varphi(N)) = 1&amp;lt;/math&amp;gt;.&lt;br /&gt;
# Die Zahl &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt; berechnen, für die &amp;lt;math&amp;gt;e \cdot d \equiv 1 \pmod{\varphi(N)}&amp;lt;/math&amp;gt; gilt. Sie ist das [[Erweiterter euklidischer Algorithmus#Modulares Inverses|modulare Inverse]] von &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; zum Modul &amp;lt;math&amp;gt;\varphi(N)&amp;lt;/math&amp;gt; und wird mit dem [[Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] berechnet.&lt;br /&gt;
&lt;br /&gt;
Veröffentlicht wird &amp;lt;math&amp;gt;(e; N)&amp;lt;/math&amp;gt;. Geheim bleiben &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt;, die beiden Primzahlen und &amp;lt;math&amp;gt;\varphi(N)&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
==Verschlüsseln und Entschlüsseln==&lt;br /&gt;
Der Sender verschlüsselt die Nachricht &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; mit dem öffentlichen Schlüssel des Empfängers:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;c = m^e \bmod N&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Der Empfänger entschlüsselt den Geheimtext &amp;lt;math&amp;gt;c&amp;lt;/math&amp;gt; mit seinem privaten Schlüssel:&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;m = c^d \bmod N&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Die Potenzen werden mit dem wiederholten Quadrieren und Multiplizieren berechnet (siehe [[Square-and-Multiply]]).&lt;br /&gt;
&lt;br /&gt;
==Korrektheit==&lt;br /&gt;
Wegen &amp;lt;math&amp;gt;e \cdot d \equiv 1 \pmod{\varphi(N)}&amp;lt;/math&amp;gt; gibt es eine ganze Zahl &amp;lt;math&amp;gt;k&amp;lt;/math&amp;gt; mit &amp;lt;math&amp;gt;e \cdot d = 1 + k \cdot \varphi(N)&amp;lt;/math&amp;gt;. Beim Entschlüsseln entsteht&lt;br /&gt;
&lt;br /&gt;
:&amp;lt;math&amp;gt;c^d \equiv \left(m^e\right)^d = m^{e \cdot d} = m^{1 + k \cdot \varphi(N)} \equiv m \pmod{N}&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Der letzte Schritt folgt aus dem [[Satz von Euler#Bedeutung für RSA|Satz von Euler]], wenn &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;N&amp;lt;/math&amp;gt; teilerfremd sind. Für einen RSA-Modul lässt sich zeigen, dass die Gleichung auch für alle übrigen Nachrichten gilt. Weil &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt; kleiner als &amp;lt;math&amp;gt;N&amp;lt;/math&amp;gt; ist, liefert die Rechnung genau die Nachricht &amp;lt;math&amp;gt;m&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
==Sicherheit==&lt;br /&gt;
Ein Angreifer kennt den öffentlichen Schlüssel &amp;lt;math&amp;gt;(e; N)&amp;lt;/math&amp;gt; und den Geheimtext &amp;lt;math&amp;gt;c&amp;lt;/math&amp;gt;. Um &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt; zu berechnen, braucht er &amp;lt;math&amp;gt;\varphi(N)&amp;lt;/math&amp;gt;, und dafür die Primzahlen &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt;. Er müsste also &amp;lt;math&amp;gt;N&amp;lt;/math&amp;gt; in seine Primfaktoren zerlegen.&lt;br /&gt;
&lt;br /&gt;
* &amp;#039;&amp;#039;&amp;#039;Einwegfunktion mit Falltür:&amp;#039;&amp;#039;&amp;#039; Zwei Primzahlen zu multiplizieren ist leicht. Für die Umkehrung, die [[Primfaktorzerlegung]] einer großen Zahl, ist kein schnelles Verfahren bekannt. Die Falltür ist die Kenntnis von &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt;.&lt;br /&gt;
* &amp;#039;&amp;#039;&amp;#039;Schlüssellänge:&amp;#039;&amp;#039;&amp;#039; Im Jahr 2020 wurde ein RSA-Modul mit 829 Bit (250 Dezimalstellen) faktorisiert. Das Bundesamt für Sicherheit in der Informationstechnik (BSI) empfiehlt einen Modul von mindestens 3000 Bit (Technische Richtlinie TR-02102-1, Version 2026-01).&lt;br /&gt;
* &amp;#039;&amp;#039;&amp;#039;Kleine Zahlen:&amp;#039;&amp;#039;&amp;#039; Rechenbeispiele mit zwei- bis vierstelligen Zahlen zeigen nur den Ablauf. Ihr Modul lässt sich sofort faktorisieren.&lt;br /&gt;
* &amp;#039;&amp;#039;&amp;#039;Auffüllen der Nachricht:&amp;#039;&amp;#039;&amp;#039; In der beschriebenen Grundform ergibt dieselbe Nachricht immer denselben Geheimtext, und kurze Nachrichten lassen sich durch Probieren erraten. In der Praxis wird die Nachricht deshalb vor dem Verschlüsseln mit Zufallswerten aufgefüllt.&lt;br /&gt;
* &amp;#039;&amp;#039;&amp;#039;Echtheit des Schlüssels:&amp;#039;&amp;#039;&amp;#039; Der Sender muss sicher sein, dass der öffentliche Schlüssel wirklich dem Empfänger gehört (siehe [[Zertifikat]] und [[Man-in-the-Middle-Angriff]]).&lt;br /&gt;
&lt;br /&gt;
RSA rechnet viel langsamer als symmetrische Verfahren. Große Datenmengen werden deshalb mit einem [[Kryptographie#Hybride Verfahren|hybriden Verfahren]] verschlüsselt. Mit vertauschten Rollen der beiden Schlüssel dient RSA auch zum Signieren (siehe [[Digitale Signatur]]).&lt;br /&gt;
&lt;br /&gt;
==Beispiele==&lt;br /&gt;
===Schlüsselpaar erzeugen===&lt;br /&gt;
Bob erzeugt ein Schlüsselpaar.&lt;br /&gt;
&lt;br /&gt;
# Primzahlen wählen: &amp;lt;math&amp;gt;p = 7&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;q = 19&amp;lt;/math&amp;gt;&lt;br /&gt;
# RSA-Modul berechnen: &amp;lt;math&amp;gt;N = 7 \cdot 19 = 133&amp;lt;/math&amp;gt;&lt;br /&gt;
# &amp;lt;math&amp;gt;\varphi(N) = (7 - 1) \cdot (19 - 1) = 6 \cdot 18 = 108&amp;lt;/math&amp;gt;&lt;br /&gt;
# &amp;lt;math&amp;gt;e&amp;lt;/math&amp;gt; wählen, teilerfremd zu 108: &amp;lt;math&amp;gt;e = 5&amp;lt;/math&amp;gt;, denn &amp;lt;math&amp;gt;\operatorname{ggT}(5; 108) = 1&amp;lt;/math&amp;gt;&lt;br /&gt;
# &amp;lt;math&amp;gt;d&amp;lt;/math&amp;gt; berechnen mit &amp;lt;math&amp;gt;5 \cdot d \equiv 1 \pmod{108}&amp;lt;/math&amp;gt;: Der [[Erweiterter euklidischer Algorithmus#Modulares Inverses berechnen|erweiterte euklidische Algorithmus]] liefert &amp;lt;math&amp;gt;d = 65&amp;lt;/math&amp;gt;. Probe: &amp;lt;math&amp;gt;5 \cdot 65 = 325 = 3 \cdot 108 + 1&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Öffentlicher Schlüssel: &amp;lt;math&amp;gt;(e; N) = (5; 133)&amp;lt;/math&amp;gt;. Privater Schlüssel: &amp;lt;math&amp;gt;(d; N) = (65; 133)&amp;lt;/math&amp;gt;. Die Werte &amp;lt;math&amp;gt;p&amp;lt;/math&amp;gt;, &amp;lt;math&amp;gt;q&amp;lt;/math&amp;gt; und &amp;lt;math&amp;gt;\varphi(N)&amp;lt;/math&amp;gt; werden nicht mehr gebraucht und bleiben geheim oder werden gelöscht.&lt;br /&gt;
&lt;br /&gt;
===Nachricht verschlüsseln===&lt;br /&gt;
Alice verschlüsselt die Nachricht &amp;lt;math&amp;gt;m = 4&amp;lt;/math&amp;gt; mit Bobs öffentlichem Schlüssel &amp;lt;math&amp;gt;(5; 133)&amp;lt;/math&amp;gt;:&lt;br /&gt;
:&amp;lt;math&amp;gt;c = m^e \bmod N = 4^{5} \bmod 133&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;4^{1} = 4&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;4^{2} \equiv 4 \cdot 4 = 16&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;4^{3} \equiv 16 \cdot 4 = 64&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;4^{4} \equiv 64 \cdot 4 = 256 \equiv 123&amp;lt;/math&amp;gt;&lt;br /&gt;
:&amp;lt;math&amp;gt;4^{5} \equiv 123 \cdot 4 = 492 \equiv 93&amp;lt;/math&amp;gt;&lt;br /&gt;
Der Geheimtext ist &amp;lt;math&amp;gt;c = 93&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
===Geheimtext entschlüsseln===&lt;br /&gt;
Bob entschlüsselt mit seinem privaten Schlüssel &amp;lt;math&amp;gt;(65; 133)&amp;lt;/math&amp;gt;:&lt;br /&gt;
:&amp;lt;math&amp;gt;m = c^d \bmod N = 93^{65} \bmod 133&amp;lt;/math&amp;gt;&lt;br /&gt;
Der Exponent ist &amp;lt;math&amp;gt;65 = 1000001_2&amp;lt;/math&amp;gt;. Mit [[Square-and-Multiply]] sind nur 6 Quadrierungen und 1 Multiplikation nötig:&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot; style=&amp;quot;text-align:center&amp;quot;&lt;br /&gt;
! Bit !! Potenz !! Quadrat mod 133 !! Zwischenergebnis mod 133&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;93^{1}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;93^{2}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93^{2} = 8649 \equiv 4&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;93^{4}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;4^{2} = 16&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;93^{8}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;16^{2} = 256 \equiv 123&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;93^{16}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;123^{2} = 15129 \equiv 100&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;93^{32}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;100^{2} = 10000 \equiv 25&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;93^{64}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;25^{2} = 625 \equiv 93&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93 \cdot 93 = 8649 \equiv 4&amp;lt;/math&amp;gt;&lt;br /&gt;
|}&lt;br /&gt;
Das letzte Zwischenergebnis ist der Klartext &amp;lt;math&amp;gt;m = 4&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
===Kleinen Modul faktorisieren===&lt;br /&gt;
Eve kennt nur den öffentlichen Schlüssel &amp;lt;math&amp;gt;(5; 133)&amp;lt;/math&amp;gt;. Weil 133 klein ist, findet sie die Primfaktoren durch Probieren: 133 ist nicht durch 2, 3, 5 teilbar, aber &amp;lt;math&amp;gt;133 = 7 \cdot 19&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Damit berechnet Eve &amp;lt;math&amp;gt;\varphi(N) = 6 \cdot 18 = 108&amp;lt;/math&amp;gt; und daraus wie Bob die Zahl &amp;lt;math&amp;gt;d = 65&amp;lt;/math&amp;gt; des privaten Schlüssels. Der Schutz ist gebrochen. Bei einem Modul der empfohlenen Länge von 3000 Bit, das sind rund 900 Dezimalstellen, gelingt die [[Primfaktorzerlegung]] mit den bekannten Verfahren nicht.&lt;br /&gt;
&lt;br /&gt;
[[Kategorie:Kryptologie]]&lt;br /&gt;
[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
</feed>